Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 63. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 63 или больше камней. В начальный момент в куче было Sкамней; 1 < S< 62. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Выполните следующие задания. Во всех случаях обосновывайте Выполните следующие задания. Задание 1 a) Укажите все такие значения числа S, при которых Петя может выиграть за один ход. б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Задание 2 Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: - Петя не может выиграть за один ход; - Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения Sопишите выигрышную стратегию Пети. Задание 3 Укажите значение S, при котором одновременно выполняются два условия: - у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; - у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения Sопишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах - количество камней в куче. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание

Эта задача требует детального анализа игры между Петей и Ваней. Давайте последовательно разберем все задания. ### Задание 1 #### a) Укажите все такие значения числа S, при которых Петя может выиграть за один ход. Чтобы Петя мог выиграть за один ход, ему нужно сделать так, чтобы количество камней в куче стало 63 или больше. Для этого он может использовать три вида ходов: добавить 1 камень, добавить 4 камня или увеличить количество камней в 5 раз. - Если S + 1 ≥ 63, то S ≥ 62. Но нам сказано, что 1 < S < 62. - Если S + 4 ≥ 63, то S ≥ 59. То есть, для S = 59 он может добавить 4 камня и выиграть. - Если S * 5 ≥ 63, то S ≥ 12.6. Но S — целое число, соответственно, S = 13, 14, 15, …, 62 также подходят. Однако 63 камней или больше уже не может быть, сохраняем только те значения для S, которые меньше 63. Итак, значения, при которых Петя может выиграть за один ход, — это: - S = 59 (добавление 4 камней) - S = 60, 61, 62 (добавление 1 камня) Таким образом, **все значения S, при которых Петя может выиграть за один ход**: - **59, 60, 61, 62**. #### b) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Можно проверить значения S от 1 до 62. Если Петя не может выиграть, мы ищем значения, при которых все возможные ходы Вани приведут к его победе. - Например, начнем с S = 58. Петя может лишь добавить 1 (S = 59) или 4 (S = 62). Ваня, соответственно: - Если S = 59, Ваня прибавит 4 (S = 63) и победит. - Если S = 62, Ваня прибавит 1 (S = 63) и также победит. Таким образом, **значение S, при котором Петя не может выиграть за один ход, а Ваня всегда может выиграть** — это **58**. **Выигрышная стратегия Вани:** Если Петя начинает с 58 камнями: - Если Петя добавляет 1 → Vanya добавляет 4 (победитель). - Если Петя добавляет 4 → Vanya добавляет 1 (победитель). --- ### Задание 2 Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: - Петя не может выиграть за один ход; - Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Первое значение S, которое интересно рассмотреть, это **S = 57**: - Петя может прибавить 1 (S = 58) или 4 (S = 61). - Если Ваня прибавляет 1 (S = 58), Петя затем добавляет 4 (победитель). - Если Ваня прибавляет 4 (S = 61), Петя затем добавляет 2 (победитель). Следующее значение — **S = 56**. - Петя может также прибавить 1 или 4. - Если Ваня добавляет 1 → S = 57, следовательно, ход Пети (добавляя 4) приведет к 61. - Если Ваня добавляет 4 → S = 60, следовательно, ход Пети (добавляя 1) приведет к 61. Таким образом, **два значения S**, у которых у Пети есть выигрышная стратегия: - **56 и 57**. --- ### Задание 3 Укажите значение S, при котором одновременно выполняются два условия: - у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; - у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Рассмотрим **S = 54**. Если Петя играет первым, его ходы: - Если Петя добавляет 1 или 4, у Вани есть способы выиграть: - Если S = 55, Ваня добавляет 4 и получает 59; затем следовательно Петя направляется к 60 (то есть в следующий поворот все равно выиграет Ваня). - Если S = 58 (при добавлении 4), Ваня получает 62, а затем в следующем ходе всегда добавляет 1 и выигрывает. В этой позиции у Вани не будет стратегии гарантированной победы в первом ходе (например, добавление 1 ведет к невыгодному положению), поэтому Ваня должен дождаться второго хода. **Выигрышная стратегия Вани:** (если Петя начинает с 54) - Если добавляет 1 (S = 55) или 4 (S = 58), он всегда сможет выиграть в следующий ход. ### Дерево возможных партий для S = 54 ``` 54 / \ 55 58 / \ / \ 56 59 62 64 /\ /\ /\ /\ 67 63 65 66 ... ``` На каждом уровне указаны ходы и полученные значения камней. В этом дереве определены только те ходы, с учетом выигрышной стратегии Вани.