Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза.Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игроказначит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрышный ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.
Задание 2. Укажите два таких значения S, при которых у Коли есть выигрышная стратегия, причём
– Коля не может выиграть за один ход;
– Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша. Для каждого указанного значения S опишите выигрышную стратегию Коли.
Задание 3. Укажите значение S, при котором
– у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;
– у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Саши. Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.
Пусть S —исходное количество камней в куче.
Задание 1. a) Коля может выиграть первым ходом, если S ∈ {21, 22, . . . , 40}. Для S ∈ {21, 22, . . . , 38} ему нужно удвоить количество камней в куче. Для S = 39 он может либо добавить 2 камня, либо удвоить количество камней. Для S = 40 Коля может добавить 1 или 2 камня, или удвоить количество камней. Если количество камней в куче меньше 21, то за один ход нельзя получить кучу, в которой больше 40 камней.
б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно в куче будет S = 20 камней. Тогда после первого хода Коли в куче будет или 21 камень, или 22 камня, или 40 камней. В любом случае Саше достаточно удвоить количество камней и выиграть своим первым ходом.
Задание 2. Возможные значения S: 19 и 18. В этих случаях Коля, очевидно, не может выиграть первым ходом.Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 20 камней. Эта позиция разобрана в п. 1б). Если в куче 20 камней, то игрок, который будет ходить (теперь это Саша), выиграть не может, а его противник (то есть Коля) следующим ходом выиграет.
Задание 3. Возможное значение S: 17.После первого хода Коли камней в куче будет или 18, или 19, или 34. Если в куче станет 34 камня, Саша удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 18 или 19 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Саша), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Коли (разобраны все ходы) |
1-й ход Саши (только ход по стратегии) |
2-й ход Коли (разобраны все ходы) |
2-й ход Саши (только ход по стратегии) |
|
| 17 | 17 + 1 = 18 | 18 + 2 = 20 | 20 + 1 = 21 | 21 · 2 = 42 |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 + 2 = 19 | 19 + 1 = 20 | 20 + 1 = 21 | 21 · 2 = 42 | |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 · 2 = 34 | 34 · 2 = 68 | |||