Петр и Виталий нарисовали на песке сорок палочек и решили сыграть в игру. Они стирают палочки по очереди. Разрешается за один ход стереть 2, 3 или 4 палочки. Проигрывает тот, кто…

Коротко: Петр имеет беспроигрышную стратегию.

Пояснение пошагово

1. Различие позиций

• Возможные ходы: убрать 2, 3 или 4 палочки.
• Позиция, из которой ходящий не может сделать ход (мало палочек): 0 и 1 палочка. Эти позиции проигрышные (P-позиции).

2. Определяем остальные позиции

• Независимо от того, какие ходы есть, если из позиции можно перейти в P-позицию, то текущий игрок имеет выигрышный ход (N-позиция).
• Если же все ходы ведут в N-позиции, то текущий игрок проигрывает (P-позиция).

Раскладываем по малым значениям:

• n = 0, 1 → P
• n = 2 → можно пойти в 0 (P) → N
• n = 3 → можно пойти в 1 или 0 (P) → N
• n = 4 → можно пойти в 1 или 0 (P) → N
• n = 5 → можно пойти в 1 (P) → N
• n = 6 → все ходы ведут в N (4→2, 3→3, 2→4) → P
• n = 7 → все ходы ведут в N → P
• n = 8,9,10,11 → N
• n = 12 → P И так далее. Видимо, повторяется периодически: позиции 0,1,6,7,12,13,18,19,... являются P-позициями.

Замечаем закономерность: P-позиции зачерпываются числами, равными 0 или 1 по модулю 6. То есть:

• н ≡ 0 или 1 (mod 6) → P-позиции
• н ≡ 2,3,4,5 (mod 6) → N-позиции

3. Применяем к начальному состоянию Начальная куча = 40 палочек. 40 ≡ 4 (mod 6) → это N-позиция. Значит ходящий может гарантировать победу.

4. Конкретная беспроигрышная стратегия для Петра

• Первый ход Петра: убрать 4 палочки, оставить 36 (кратно 6).
• Затем поддерживать правило: после хода Виталия оставить число палочек, кратное 6. Делать это можно так: если Виталий возьмёт x палочек (x ∈ {2,3,4}), Петр забирает 6 − x палочек. Так в сумме за каждый полный раунд удаляется 6 палочек, и после каждого хода Петра остаётся кратное 6 число палочек.
• Пример рутины: 40 → Петр убирает 4 → 36. Виталий может взять 2, 3 или 4:
  • если 2: остаётся 34, Петр берёт 4 → 30;
  • если 3: остаётся 33, Петр берёт 3 → 30;
  • если 4: остаётся 32, Петр берёт 2 → 30. И далее по той же схеме: 30 → (после хода Виталия) оставляем 24 → 18 → 12 → 6 → 0. Когда остаётся 0 палочек после хода Петра, у Виталия ходов уже нет — он проигрывает.

Итог

• У Петра есть беспроигрышная стратегия. Он начинает с удаления 4 палочек, затем каждый раз отвечает так, чтобы общее количество палочек, удалённых за пару ходов (первый ход Петра плюс ответ Виталия) равнялось 6, т.е. поддерживает кратность 6 после своих ходов. Это приводит к победе Петра на нулевой позиции после его хода.