Петр и Виталий нарисовали на песке сорок палочек и решили сыграть в игру. Они стирают палочки по очереди. Разрешается за один ход стереть 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 после своих ходов. Это приводит к победе Петра на нулевой позиции после его хода.