Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Игра завершается в тот момент, когда общее количество камней в двух кучах становится не менее 20. Если в момент завершения игры общее число камней в двух кучах не менее 35, то выиграл Ваня, в противном случае — Петя. Кто выигрывает при безошибочной игре обоих игроков? Укажите стратегию выигрывающего игрока — какой ход он должен сделать в каждой из позиций, которые могут ему встретиться при правильной игре. Докажите, что описанная стратегия — выигрышная.

Answer 1

Выигрывает Петя. Для того чтобы выиграть, он должен утроить количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.

Таблица содержит все возможные варианты ходов второго игрока. Из неё видно, что при любом ходе второго игрока у первого имеется ход, приводящий к победе. Причём у первого игрока есть два варианта выигрышного хода. Описание любого из них является правильным решением.
Ответ: Выигрывает Петя. Для того чтобы выиграть, он
должен утроить количество камней во второй куче