Всесиб 2023, 10 класс, задача 2
( баллов) Вася и Петя играют в «Бери или дели». В этой игре сначала есть одна большая куча камней. Каждым ходом очередной игрок либо делит одну из уже имеющихся к моменту его хода куч любым способом на две меньших, либо забирает одну из уже имеющихся куч. Выигрывает игрок, после хода которого камней на поле вообще не останется. Игроки делают ходы по очереди, первым ход делает Вася, но этим и только этим ходом он не имеет права забрать всю кучу сразу. Кто из них победит в этой игре? Замечание: куча может содержать всего один камень.
Ответ
Ответ. Всегда победит Вася.
Решение. Пусть к моменту, когда игра закончится, обоими игроками было сделано ходов типа взятия кучки и ходов типа деления кучки на две. Каждый ход первого типа уменьшает число имеющихся на поле кучек на один, а каждый ход второго типа увеличивает это число на один. В начале была одна кучка, а в конце - ноль, поэтому имеем соотношение , откуда . Общее количество сделанных при этом ходов равно - нечётно, следовательно, последний ход сделал первый игрок, то есть Вася, он и победил. Ответ не зависит от количества камней в начале.