1
1

В $%2016$% аквариумах плавают $%1,2,...,2016$% золотые рыбки. Две кошки по очереди выбирают два аквариума с разным количеством рыбок и переселяют нескольких рыбок с одного аквариума в другой так, чтобы количество рыбок в этих аквариумах стала одинаковой. Проигрывает кот, который не может сделать очередной ход. Имеет ли кто-то из котов выигрышную стратегию? Если имеет, то кто?

задан 28 Дек '15 0:22

10|600 символов нужно символов осталось
1

Тут идея симметрии вообще-то работает, только рассматривать надо числа вида $%n$% и $%2017-n$%. Они имеют разную чётность, поэтому не могут быть выбраны в процессе одного и того же хода.

Стратегия второго кота состоит в том, что надо выбирать в качестве ответного хода числа, симметричные тем, которые использовал первый. Если первый выбрал аквариумы с $%k$% и $%m$% рыбками, где числа имеют одинаковую чётность, и получил в итоге два аквариума с $%\frac{k+m}2$% рыбками в каждом, то второй в ответ должен выбрать числа $%2017-k$% и $%2017-m$%, получая два аквариума, в каждом из которых по $%2017-\frac{k+m}2$% рыбок. Последнее важно в связи с тем, что эти числа симметричны двум предыдущим, то есть после каждого из ходов второго кота симметрия будет поддерживаться. Существенно также то, что симметричные числа имеют противоположную чётность, поэтому они не затрагиваются при одном и том же ходе, и симметричный ответ всегда существует. По этой причине, у второго кота всегда есть ответ, то есть он не проигрывает.

Осталось заметить, что игра заканчивается в течение конечного числа ходов, поэтому указанная выше стратегия является выигрышной. Действительно, легко проверяется (проще всего это сделать на числовой прямой), что сумма модулей попарных разностей чисел при каждом из ходов строго уменьшается.

ссылка

отвечен 28 Дек '15 9:29

10|600 символов нужно символов осталось
1

Не уверен ... но видимо симметричные ответы второго приведут его к выигрышу... (имеется ввиду, что первый выбирает аквариумы с $%N$% и $%M$% рыбками... то второй берёт аквариумы c $%2006-N$% и $%2006-M$% рыбками) ...

ссылка

отвечен 28 Дек '15 2:17

изменен 28 Дек '15 2:20

@all_exist: тут симметрия сразу же нарушается. Скажем, при первом ходе может быть M или N равно 1003. Это количество далее изменится, и симметрично будет уже не ответить.

(28 Дек '15 3:15) falcao

@falcao, мдя... почему-то считал, что аквариумов 2006 (имелось ввиду 2016)... ((( ... про 2017 не додумал ...

(28 Дек '15 13:35) all_exist

@all_exist: а я далеко не сразу осознал, что симметрия в принципе работает. Пытался сначала искать какие-то другие инварианты, основываясь на признаке окончания игры. Потом стал смотреть стратегии для "малых" n, и тогда оказалось, что идея работает.

(28 Дек '15 19:52) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×33

задан
28 Дек '15 0:22

показан
551 раз

обновлен
28 Дек '15 19:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru