Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, II тур регионального этапа

На столе есть две кучки камней, в которых соответственно 100 и 101 камень. Двое играют в игру, делая ходы по очереди. За ход разрешается взять кучку, убрать из неё какое-то количество камней (хотя бы один) и разбить оставшиеся в этой кучке камни на две непустые кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре: тот, кто делает первый ход, или его соперник? ( М. Туревский )

Комментарий/решение

Ответ: Первый

Игрок А (тоесть игрок, который первый ходит) забирает один камень из 101 камней и разбивает его на кучки 99, 1

Оставшиеся кучки это 100, 99, 1. Заметим, что кучки над которыми можно делать операции только 99 и 100.

Рассмотрим случай, когда игрок В (игрок, который ходит второй) забирает камень из кучи 99. Тогда он заберет из кучки n камней и разделит оставшееся на кучки b и с. Игрок А заберет n+1 камней и так же разделит оставшееся на b и с. Таким образом, у игрока А всегда будет ход.

Рассмотрим случай, когда игрок В берет камень из кучи 100 хотябы два камня.

Тогда он поделит оставшиеся на b и с, а игрок А заберет n-1 камней и также поделит их на b и с.

Рассмотрим случай, коода игрок В берет 1 камень из кучки 100. Тогда он оставит кучки b+c=2k-1, и пусть у нас тут b - четное.

Тогда игрок А берет 1 камень и разбивает кучку на кучки b-1 и с. Получаем одинаковые кучки с;с и получаем такую же пару b-1;b которую мы только что разобрали, тоесть у игрока А всегда найдется ход.

Доказано