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

Игра завершается, когда количество камней в куче превышает 46. Победителем становится игрок, сделавший последний ход, и получивший в куче 46 или более камней. В начальный момент в куче было S камней, 1≤ S ≤ 45.

Последовательно решите следующие задания:

1. При каких S: а) Петя выигрывает первым ходом; б) Ваня выигрывает первым ходом при любой игре Пети.
2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом при любой игре Вани.
3. Назовите такое значение S, при котором Ваня может выиграть своим первым или вторым ходом при любой игре Пети.

Данная задача решается последовательно. Решив первый пункт, мы легко можем решить следующий. Начнем с пункта 1а.

1а. При каких S Петя выигрывает первым ходом.

Игрок выигрывает в том случае, когда количество камней в куче больше или  равно 46. Самый сильный ход, который может сделать Петя — увеличить количество камней в куче в два раза. Получается, что минимальная выигрышная S будет равна:

46:2=23

То есть при S={23..45} Петя выигрывает первым ходом, просто умножив эти числа на два. Будем считать, что позиции S={23..45} — выигрышные, то есть любой игрок, у которого в куче появилось 23 или более камней выиграет.

1б. При каких S Ваня выигрывает первым ходом при любой игре Пети.

Мы знаем, что позиции 23..45 — выигрышные, значит Ваня может выиграть в том случае, если у Пети не останется другой возможности, кроме как сделать своим первым ходом количество камней в куче равным 23..45.

Самый слабый ход, который может сделать Петя — увеличить количество камней на один. Получается, что при S=22 Петя сделает выигрышную позицию для Вани:

22 + 1 = 23 — Ваня выиграет следующим ходом

22 + 3 = 25 — Ваня выиграет следующим ходом

22 * 2 = 44 — Ваня выиграет следующим ходом

То есть при S=22 Ваня выиграет, а Петя — проиграет. Будем считать, что позиция S=22 — проигрышная для любого игрока, кому она попадётся.

2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом при любой игре Вани.

Мы знаем, что позиция S=22 проигрышная, Петя ходит первым и он должен выиграть. То есть он должен сделать для Вани проигрышную позицию, то есть количество камней в куче после его хода должно стать равным 22. При том, что у Пети есть три возможных хода (+1, +3, *2), Петя может получить 22 камня в куче из следующих позиций S:

21 + 1 = 22

19 + 3 = 22

11 * 2 = 22

То есть Петя выиграет при S = 21, 19, 11, сделав количество камней в куче равным 22. Будем считать, что позиции 21, 19, 11 выигрышные для любого игрока, у которого они появятся.

3. Назовите все значения S, при которых Ваня может выиграть своим первым или вторым ходом при любой игре Пети.

Из пункта 2 решения мы знаем, что позиции 21, 19, 11 обеспечивают победу игроку вторым ходом. То есть мы должны найти такое S, чтобы у Пети не было другой возможности, кроме как сделать количество камней в куче равным или 21, или 19, или 11, или чтобы их количество было в диапазоне {23..45}.

Очевидно, что это число 18. При любой игре Пети Ваня получит выигрышную позицию:

18 + 1 = 19 — выигрышная позиция

18 + 3 = 21 — выигрышная позиция

18 * 2 = 36 — выигрышная позиция

Ответы:

1а: 23..45

1б: 22

2: 21, 19, 11

3: 18