Каждое задание на теорию игр разбивается на три задачи (19, 20, 21). В 19 задаче – один ответ в пустую ячейку, в 20 и в 21 – один или два ответа в одну или две пустые ячейки соответственно Задание 19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два камня; в) добавить в кучу три камня; г) увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче превышает 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 33. Найдите значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.

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

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

Основной принцип:

1. Если игрок делает ход, который переводит игру в позицию, где противнику не удастся выиграть, то текущий игрок в выигрышной позиции.
2. Позиция считается проигрышной, если после текущего хода противник в ту же очередь получит возможность сделать ход и выиграть.

Рассмотрим все возможные случаи:

1. Если S = 34 (в выигрыше тот, кто играет, так как и при любом ходе он получает >= 34).
2. Если S = 33 - Петя ставит >34 и выигрывает.
3. Если S = 32, Петя может сделать 3 (снова получает 34) – выигрыш.
4. Если S = 31, Петя может сделать 3 до 34 или 2 до 33 – выигрыш.
5. Если S = 30, Петя делает 3 до 33 и не может выиграть.
6. Если S = 29, Петя может сделать 3 до 32 – проигрыш.
7. Если S = 28, игрок может увеличивать кучу до 29 (Петя тоже сможет 32) – выигрыш для Пети.
8. Если S = 27, Петя не может сделать (может 3 до 30) – позиция выигрыша Вани.
9. Если S = 26, проигрыш Петя (сделает 29 или 27 позиций) - выигрыш.
10. Если S = 25, Петя добавляет к 27– 30 - выигрыш Вани.
11. Если S = 24, Ваня снова в проигрышной позиции.
12. Если S = 23, выигрыш Вани.
13. Если S = 22, Петя в проигрышной позиции.
14. Если S = 21, проигрыш.
15. Если S = 20, выигрыш.
16. Если S = 19, проигрыш.
17. Если S = 18, выигрывает Петя.
18. Если S = 17, проигрыш.
19. Если S = 16, выигрывает.
20. Если S = 15, проигрыш.
21. Если S = 14, выигрывает.
22. Если S = 13, проигрыш.
23. Если S = 12, выигрывает.
24. Если S = 11, проигрыш.
25. Если S = 10, выигрывает.
26. Если S = 9, проигрыш.
27. Если S = 8, выигрывает.
28. Если S = 7, проигрыш.
29. Если S = 6, выигрывает.
30. Если S = 5, проигрыш.
31. Если S = 4, выигрывает.
32. Если S = 3, проигрыш.
33. Если S = 2, выигрывает.
34. Если S = 1, проигрыш.

Таким образом, Ваня выигрывает при следующих исходных значениях S:

Решение: S = 30. Ваня делает выигрышный ход.