B2 Симуляция процесса по шагам

Идея метода: некоторые задачи описывают процесс, который разворачивается шаг за шагом — игру, алгоритм, последовательность операций. Метод состоит в том, чтобы явно проследить несколько первых шагов процесса, найти паттерн (закономерность, цикл, инвариант) и затем использовать его для ответа без полного перебора.

Почему не просто симулировать все шаги? Потому что на олимпиадах число шагов может быть очень большим (например, $2025$ шагов), а поиск паттерна — это ключевая олимпиадная компетенция. Метод учит переходить от «вычислить» к «понять, почему так устроено».

Интуиция: представь, что ты наблюдаешь за часовым механизмом. Можно ждать 12 часов, а можно заметить, что стрелка делает полный оборот каждые 12 часов — и использовать этот цикл. Симуляция по шагам — это «прокрутить механизм несколько раз», чтобы увидеть цикл.

Важно: часто нужно не просто найти паттерн, но и доказать, что он продолжается. Инвариант или явная формула для $n$-го шага — это доказательство.

• Принцип периодичности: если состояние системы конечно и процесс детерминирован (следующее состояние однозначно определяется текущим), то через конечное число шагов процесс войдёт в цикл. Когда использовать: процесс с конечным набором состояний.
• Инвариант шага: величина (сумма, остаток от деления, чётность), которая не меняется при каждом шаге. Когда использовать: нужно доказать достижимость или недостижимость некоторого состояния.
• Нахождение $n$-го состояния через остаток: если цикл имеет длину $T$, то состояние после $n$ шагов совпадает с состоянием после $(n \ \mathrm{mod}\ T)$ шагов. Когда использовать: большое число шагов, маленький цикл.
• Монотонная величина: если некоторая величина строго убывает (или возрастает) при каждом шаге и ограничена, то процесс завершится. Когда использовать: доказательство конечности процесса.

• Провести первые 5–10 шагов вручную и выписать состояния в таблицу.
• Искать повторение состояния — как только нашёл первое повторение, цикл найден.
• Выявить инвариант — найти величину, которая остаётся постоянной на каждом шаге (сумма, чётность, остаток по модулю $k$).
• При игровых задачах зафиксировать «позиции проигрыша» и «позиции выигрыша», двигаясь от базовых случаев.
• Использовать остатки от деления: если $n$ большое, а период равен $T$, ответ для $n$ — такой же, как для $n \mod T$.
• Проверить граничные случаи: шаг 0, последний шаг, чётный/нечётный шаг.

Поверхностные признаки (что буквально написано):
- «После каждого хода», «на каждом шаге», «операцию повторяют $n$ раз».
- Описание правила, по которому один объект превращается в другой или изменяется.
- «Что произойдёт через 100 (1000, 2023) шагов?»

Структурные признаки (форма выражения, объекты):
- Процесс задан рекурсивно или итеративно: следующее состояние зависит только от предыдущего.
- Конечное число «состояний» (цифр, клеток на доске, жетонов).
- Задача об игре с двумя игроками и правилами хода.

Цель задачи (что от тебя хотят):
- Найти состояние системы после $n$ шагов.
- Определить, кто выиграет при оптимальной игре.
- Доказать, что некоторое состояние достижимо или недостижимо.

Задача 1. На доске написано число 1. Каждый ход число умножают на 3. Какова последняя цифра числа после 100 ходов?

Источник: тренировочная (типичная задача на периодичность последних цифр, ВсОШ 6–7 класс).

Как думать (рассуждение ученика$):
1. $Что я вижу? Процесс умножения на 3, повторяемый 100 раз. Интересует только последняя цифра.$2. *$Триггер: «после $n$ шагов», последняя цифра → последняя цифра степеней тройки циклична.$3. *$Первый ход: выпишу несколько последних цифр степеней тройки: $3^0=1$, $3^1=3$, $3^2=9$, $3^3=27→7$, $3^4=81→1$. Цикл: $1,3,9,7,1,3,9,7,\ldots$ с периодом $4.
4. *$Применяю остаток:* $100 = 4 \cdot 25 + 0$. Остаток 0 → последняя цифра совпадает с $3^0 = 1$... стоп, после 100 ходов число равно $3^{100}$. $100 \mod 4 = 0$. В цикле позиция 0 соответствует последней цифре 1.

Решение:
Последние цифры степеней 3: $3^1 \to 3$, $3^2 \to 9$, $3^3 \to 7$, $3^4 \to 1$, $3^5 \to 3$, ... — период 4.$3^{100}$: $100 = 4 \cdot 25$, значит $100 \mod 4 = 0$ → последняя цифра такая же, как у $3^4$, то есть 1.

Ответ: последняя цифра равна $1$.

Что в этой задаче было главным: не умножать 100 раз, а найти период и использовать остаток от деления.

Задача 2. Игра: на столе лежат 15 камней. Два игрока ходят по очереди, каждый может взять 1, 2 или 3 камня. Проигрывает тот, кто не может сделать ход (камней не осталось). Кто выигрывает при правильной игре — первый или второй?

Источник: тренировочная (классика теории игр, ВсОШ 6–8 класс).

Как думать (рассуждение ученика$):
1. $Что я вижу? Игра с камнями и правилами. Нужно определить победителя.$2. *$Триггер: игровая задача с правилами хода → анализировать позиции выигрыша/проигрыша снизу вверх.$3. *$Первый ход: промаркирую позиции. Позиция 0 камней — проигрышная (П) для того, кто ходит: нет хода. 1, 2, 3 — выигрышные (В): берёшь все и оппонент на П. Позиция 4 камней: можно взять 1, 2 или 3, остаётся 3, 2 или 1 — все выигрышные → оппонент выиграет, значит 4 — П.$4. *$Паттерн:* П на 0, 4, 8, 12, ... — каждые 4 числа. 15 = 4·3 + 3 → позиция 15 выигрышная (В).

Решение:
Позиции: П = {0, 4, 8, 12, 16, ...}, В = остальные.$15 \mod 4 = 3 \neq 0$ → позиция 15 — выигрышная. Первый игрок берёт $15 - 12 = 3$ камня, оставляет 12 (П) → далее при любом ходе второго первый всегда оставляет кратное 4.

Ответ: побеждает первый игрок, взяв сначала 3 камня.

Что в этой задаче было главным: найти проигрышные позиции — они образуют арифметическую прогрессию с шагом, равным (максимальный ход + 1).

• Ошибка: остановиться на симуляции, не найдя паттерн → Симуляция 100 шагов вручную невозможна на олимпиаде за отведённое время. → Как избежать: после 5–10 шагов активно ищи цикл или инвариант.
• Ошибка: неверно определить длину цикла → Записал 4 значения и решил, что период равен 4, хотя на самом деле истинный период начинается позже. → Как избежать: проверяй, что повторение состояния действительно происходит: выпиши ещё несколько значений после предполагаемого конца цикла.
• Ошибка: неверно применить остаток от деления → При периоде 4 и $n = 100$: $100 \mod 4 = 0$, и это соответствует четвёртому элементу цикла (не нулевому). → Как избежать: явно соответствуй остатку элементу цикла; остаток 0 = последний элемент цикла.
• Ошибка: в игровых задачах — анализировать только первый ход, а не все последствия → Нашёл «хороший» первый ход, но не проверил, что у оппонента нет ответа. → Как избежать: строй таблицу В/П для всех позиций от 0 до $n$.
• Ошибка: считать, что проигрышная позиция — это «маленькое число камней» → Позиция 3 (можно взять все) — выигрышная, позиция 4 — проигрышная. → Как избежать: всегда анализируй снизу вверх, не угадывай.