Ответ: Стратегии в игре с кучами
Задание 1: а) $S=29,30,\ldots,57$; б) $S=15$. Задание 2: $S=15$, первый ход Пети — удвоить вторую кучу. Задание 3: $S=21$; Ваня после первого хода Пети выбирает ход, обеспечивающий немедленный выигрыш следующим ходом.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч по своему выбору один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию обозначают (10, 5). За один ход можно получить позиции (11, 5), (20, 5), (10, 6), (10, 10). Для ходов у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 65. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 7 камней, во второй куче — $S$ камней; $1 \leq S \leq 57$.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными.
Задание 1. Укажите все значения $S$, при которых Петя может выиграть за один ход. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$, когда такая ситуация возможна.
Задание 2. Укажите значение $S$, при котором у Пети есть выигрышная стратегия, Петя не может выиграть за один ход, а своим вторым ходом может выиграть независимо от хода Вани. Для указанного значения $S$ опишите выигрышную стратегию Пети.
Задание 3. Укажите значение $S$, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, позволяющей гарантированно выиграть первым ходом. Для указанного значения $S$ опишите выигрышную стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Где здесь ошибаются
Забывают, что игра заканчивается сразу после получения суммы не менее 65.
Считают выигрышным ход, после которого сумма меньше 65, без анализа ответа соперника.
В дерево выигрышной стратегии включают все возможные ходы, хотя нужно включать только ходы, совместимые со стратегией выигрывающего игрока.
Путают удвоение количества камней в одной куче с удвоением общей суммы.