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

Кратко постановка: в начале в кучке 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 — проигрышны для первого игрока при оптимальной игре.