Рассмотрим следующую игру: сначала в кучке лежат Х спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1, 2 или 3 спички; выигрывает тот, кто оставит в…

Кратко постановка: в начале в кучке X спичек, за ход можно убирать 1–3. Побеждает тот, кто после своего хода оставит в кучке 1 спичку. Вы ходите первым.

1. Как определить выигрышные и проигрышные позиции

• Если на вашем ходе в кучке 2, 3 или 4 спички, вы можете победить сразу, оставив 1 спичку (убрать 1, 2 или 3 соответственно).
• Отсюда можно ввести обобщение: проигрышные позиции для игрока, который ходит сейчас, — это числа, которые дают после любого хода позицию, из которой соперник может победить. По разбивке по модулю4 получается:
  • числа, кратные 4 плюс 1, т.е. s ≡ 1 (mod 4) — проигрыш для того, кто ходит.
  • остальные числа — выигрывают для игрока, который ходит: можно сделать ход так, чтобы после него в кучке получилось число ≡ 1 (mod 4).

2. Практическая стратегия

• Чтобы выиграть, нужно на своем первом ходу привести кучку к виду ≡ 1 (mod 4).
  • если N ≡ 2 (mod 4) — убрать 1
  • если N ≡ 3 (mod 4) — убрать 2
  • если N ≡ 0 (mod 4) — убрать 3
  • если N ≡ 1 (mod 4) — выиграть нельзя (первый игрок проигрывает при оптимной игре)

3. Применение к данным числам

• 15: 15 ≡ 3 (mod 4) → убрать 2, остаётся 13 (13 ≡ 1 mod 4). Дальше можно повторять принцип «потянуть на 4» и привести к победе. Пример продолжения: 15 → 13 (вы), противник уходит к 12/11/10, вы → 9, затем → 5, затем → 1 и побеждаете.
• 12: 12 ≡ 0 (mod 4) → убрать 3, остаётся 9 (9 ≡ 1 mod 4). Дальше та же схема: противник → 8/7/6, вы → 5, затем → 1. Победа.
• 17: 17 ≡ 1 (mod 4) — проигрыш для первого игрока при оптимальной игре. Любой первый ход (к 16, 15 или 14) позволит противнику вывести к 13 (1 mod 4) и снова вести игру по выигрышной схеме.
• 13: 13 ≡ 1 (mod 4) — проигрыш для первого игрока по той же причине.

Ответ

• Заранее выиграть можно при стартовых числах 12 и 15.
• Числа 17 и 13 — проигрышны для первого игрока при оптимальной игре.