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

Классический разбор задачи: 1) Суть правила - В кучке из X спичек за ход можно убрать 1, 2 или 3 спички. - Побеждает тот, кто оставит в кучке ровно 1 спичку после своего хода. - Вы ходите первым. 2) Что нужно определить - За какие X первый игрок имеет выигрышную стратегию? - Какие X приводят к проигрышу для игрока, который делает первый ход? 3) Основной вывод - Непобедимыми (проигрывающими для того, кто ходит) оказываются такие X, для которых начать нельзя оставить сопернику число, конгруентное 1 по модулю 4. - В итоге получаем: первый игрок выигрывает для всех X, если X не равно 1 по модулю 4. А если X ≡ 1 (мод 4), то выигрывает второй игрок. 4) Подробности доказательства (в пошаговом виде) - База: - X = 1: игра уже завершилась до вашего хода; текущий игрок проигрывает. - X = 2, 3, 4: можно сразу оставить 1 спичку (2→1, 3→1, 4→1). Значит, X = 2,3,4 — выигрышные позиции. - Индуктивное предположение: для всех меньших X принцип выполнится. - Рассмотрим X ≥ 5. - Если X ≡ 1 (мод 4) (то X = 1,5,9,13,...): можно сделать только ходы к X-1, X-2, X-3, которые дают значения ≡ 0, ≡ 3, ≡ 2 (мод 4). Все эти позиции являются выигрышными для следующего игрока, поэтому X ≡ 1 (мод 4) — проигрышная позиция для того, кто ходит. - Если X ≡ 0, 2 или 3 (мод 4): можно сделать ход так, чтобы после своего хода осталось число ≡ 1 (мод 4). - X ≡ 0: убрать 3, оставить X-3 ≡ 1 (мод 4). - X ≡ 2: убрать 1, оставить X-1 ≡ 1 (мод 4). - X ≡ 3: убрать 2, оставить X-2 ≡ 1 (мод 4). Так что из любых X, не равного 1 по модулю 4, можно перейти в позицию ≡ 1 (мод 4). Оттуда противник не может выиграть: любой его ход приводит к 4k, 4k-1 или 4k-2, а затем вы возвращаете игру к тому же виду и в конце концов добиваетесь оставления 1. 5) Стратегия на практике - Основной прием: держать после своего хода число, которое равно 1 по модулю 4. - Если стартовое X не равно 1 по модулю 4, вы можете сделать первый ход так, чтобы осталось число ≡ 1 (мод 4): - Если X ≡ 0 (мод 4): убираете 3. - Если X ≡ 2 (мод 4): убираете 1. - Если X ≡ 3 (мод 4): убираете 2. - Затем, после любого хода соперника, удаляете нужное количество, чтобы сумма его хода и вашего равнялась 4. Таким образом после вашего хода снова остаётся число ≡ 1 (мод 4). - Когда на очередном ходе у оппонента останутся 2, 3 или 4 спички, вы легко добьёте до 1 спички (2→0? нет, мы оставляем 1: 2−1=1; 3−2=1; 4−3=1). 6) Примеры - X = 2, 3, 4: можно выиграть сразу, оставив 1. - X = 5: это число ≡ 1 (мод 4) — проигрышная позиция для игрока, ходящего первым. Любой ваш ход даст сопернику шанс уйти в состояние ≡1 (мод 4) и затем выиграть. - X = 6, 7, 8: выигрышные. Пример для 6: вы можете убрать 1, чтобы оставить 5 (≡1 модулю 4); далее по стратегии вы выиграете. - X = 9: снова проигрыш для первого игрока (9 ≡ 1 по модулю 4). Итоговый ответ - Первый игрок выигрывает, если X не равен 1 по модулю 4. - Первый игрок проигрывает, если X ≡ 1 (мод 4) (то есть X = 1, 5, 9, 13, ...). Если хочешь, могу проверить конкретное число X и подсказать конкретный первый ход и дальнейшую последовательность ходов. Просто скажи X.