В кучке ровно 2020 камней. Катя и Петя по очереди (начинает Катя) делят одну из кучек на две непустые части. Побеждает тот, после чьего хода в каждой кучке будет не более двух камней. Кто выигрывает при правильной игре обеих сторон?

задан 23 Май 2:34

изменен 23 Май 2:35

1

Разве это не самый лёгкий из случаев? Делим кучку пополам, а потом копируем ходы соперника. Наверное, интереснее случай нечётного, или произвольного числа камней.

(23 Май 2:43) falcao
1

В общем виде, судя по всему, ответ сложный. Тут функция Гранди вроде как не ограниченная. Но для чётного числа камней всё ясно.

(23 Май 2:55) falcao
1

Я нашёл в программе функцию Гранди и число камней, когда начинающий проигрывает. Оказалось, оно есть в oeis, и там ссылка на статью "классиков".

(23 Май 3:02) falcao

@falcao, Вы пишете: "Наверное, интереснее случай нечётного, или произвольного числа камней." /////////// При $%k=3$%, а также при всех чётных $%k$% побеждает Катя. В остальных случаях - Петя. Разве не так?

(23 Май 11:43) Казвертеночка
1

@Казвертеночка: при k=5 выигрывает второй, но при k=7 уже первый, делая 5+2. По-моему, общий случай до сих пор является открытой задачей.

(23 Май 15:34) falcao

@falcao, мне тоже казалось, что это открытая проблема. Оказалось, что лишь казалось: http://olympiads.mccme.ru/matboi/usl10_11.pdf

(23 Май 23:58) Казвертеночка
1

@Казвертеночка: я понял, в чём дело. Я рассматривал случай, когда кучки из двух камней делить уже нельзя. Тем самым я усложнил задачу -- именно она оказалась открытой. А без этого ограничения критерий простой (для любого числа куч), и он отмечен в начале статьи по ссылке.

Так или иначе, для чётного n работает простая симметрия независимо от варианта.

(24 Май 0:04) falcao

@falcao, большое спасибо!

(24 Май 10:07) Казвертеночка
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,333
×80
×34
×20
×3

задан
23 Май 2:34

показан
47 раз

обновлен
24 Май 10:07

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

по почте:

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

по RSS:

Ответы

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

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