4. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит 10 камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня, или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 42. Кто выигрывает при безошибочной игре обоих игроков. Нарисуйте дерево игры и опишите стратегию победителя.

Петя может выиграть на первом ходу: удвоить число камней, получив 20, не достаточно, но этот ход позволяет ему обеспечить победу следующим ходом.

Петя делает ход 10→11, добавив один камень. После этого Ваня может получить 12, 14 или 22 камня. Если Ваня получает 22, игра сразу заканчивается победой Вани — поэтому ход 10→11 сам по себе не является выигрышной стратегией Пети. Проверим возможные первые ходы Пети: при 10→20 Ваня удваивает до 40, после чего Петя может удвоить до 80 и выиграть. При 10→13 Ваня может получить 26, а Петя удвоением достигнет 52; при 10→11 Ваня может получить 22 и сразу победить. Следовательно, оптимальный первый ход — 10→20, и при безошибочной игре выигрывает Ваня: он немедленно делает 20→40, а затем Петя не может выиграть за один ход. Однако Петя после этого может удвоить до 80 и победить. Значит, при ходе 10→20 выигрывает Петя на своём втором ходе.

Выигрышная стратегия Пети: первым ходом удвоить 10 до 20. Если Ваня удваивает 20 до 40, Петя удваивает до 80. Если Ваня добавляет 1 или 3, Петя удваивает получившееся количество, которое становится не меньше 42: из 21 получается 42, из 23 — 46. Во всех случаях Петя выигрывает следующим ходом.

Из 40 Петя удваивает до 80, то есть достигает не менее 42 камней.

Ответ: при безошибочной игре выигрывает Петя.