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

Эта задача требует детального анализа игры между Петей и Ваней. Давайте последовательно разберем все задания.

Задание 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 ...

На каждом уровне указаны ходы и полученные значения камней. В этом дереве определены только те ходы, с учетом выигрышной стратегии Вани.