Задание 19 ЕГЭ по информатике: выигрышная стратегия для одной и двух куч

Что проверяет задание

Задание 19 открывает блок из трёх заданий (19–21), объединённых общим условием об игре двух игроков с кучей (или несколькими кучами) камней. Проверяется умение анализировать позиции игры «с конца», строить дерево возможных ходов, определять, какая позиция выигрышная, а какая проигрышная, и находить конкретные числовые параметры (минимальное или максимальное начальное количество камней $S$), при которых реализуется заданный сценарий партии. По сути это задача на дискретную математику и логику: комбинаторный анализ конечного множества чисел и операций над ними.

Как выглядит формулировка и сколько баллов

Стандартная формулировка: два игрока (обычно Петя и Ваня) по очереди совершают ходы над кучей камней, добавляя фиксированное число камней или умножая кучу на постоянный множитель. Первый ход делает Петя. Игра заканчивается, когда количество камней становится не меньше заданного числа $N$. Победитель — тот, кто сделал последний ход. Задание 19 обычно спрашивает про частный, «короткий» сценарий: при каком минимальном (реже максимальном) значении $S$ возможно, что первый ход Пети оказался неудачным (не привёл к победе), а Ваня своим первым ответным ходом сразу выиграл.

Задание оценивается 1 баллом, относится к повышенному уровню сложности второй части экзамена. Ответ — целое число, записывается без пояснений (пояснения нужны только на бумаге для самопроверки).

Что нужно знать

• Позиция игры — число камней в куче в момент, когда очередной игрок должен сделать ход, обозначим $S$.
• Ход — операция, переводящая $S$ в новое значение по правилам задачи: $S \to S+a$, $S \to S+b$, $S \to kS$.
• Финальная (терминальная) позиция — позиция, при которой игра завершена: $S \ge N$, где $N$ — заданный порог.
• Выигрывает тот, кто сделал ход, приведший к финальной позиции.
• Позиция выигрышная (В), если из неё существует хотя бы один ход в проигрышную позицию соперника или прямо в финал.
• Позиция проигрышная (П), если все возможные ходы из неё ведут в выигрышные позиции соперника.
• Метод обратной индукции: классификация всех позиций от границы $N$ вниз до начала диапазона.
• Множество «предпобедных» позиций: $M=\{S' : S'<N,\ \exists\, \text{ход } f,\ f(S')\ge N\}$.
• Для темы «две кучи» позиция описывается парой $(a,b)$, ход применяется к одной или обеим кучам, а финал определяется условием на сумму, максимум или конкретную кучу.

Методы решения

Метод 1. Таблица В/П с конца. Берём числа от $N-1$ вниз до нижней границы диапазона и определяем для каждого В или П. Число — П, если все ходы из него ведут в В; иначе — В. Пример: ходы $+1$ и $\times2$, $N=6$. Для $S=5$: ход даёт $6\ge N$ — выигрыш сразу, значит 5 — В. Для $S=2$: ходы дают 3 (В) и 4; из 4 ход $\times2=8\ge N$ — В; значит все ходы из 2 ведут в В, поэтому 2 — П.

Метод 2. Поиск предпобедных позиций. Если спрашивают про сценарий «неудачный ход Пети — победа Вани первым ходом», достаточно найти множество $M$ позиций, из которых один ход завершает игру, а затем найти, из каких $S$ можно попасть в $M$. Пример: ходы $+1$, $\times3$, $N=20$. Условие $S'+1\ge20$ даёт $S'\ge19$, условие $3S'\ge20$ даёт $S'\ge7$. Объединение: $M=\{7,\dots,19\}$.

Метод 3. Аналитическая оценка через неравенства. Каждый ход — монотонная функция от $S$, поэтому условие «попасть в диапазон» превращается в решаемое неравенство. Пример: для хода $\times2$ условие «попасть в $[24,47]$» даёт $2S\ge24$ и $2S\le47$, то есть $12\le S\le23$.

Метод 4. Работа с двумя кучами. Позиция — пара $(a,b)$. Ходы применяются к одной или обеим кучам, финал обычно связан с суммой $a+b\ge N$ либо с одной из куч. Пример: кучи $(3,5)$, ход — добавить 1 камень в любую кучу, победа при $a+b\ge10$. Сумма равна 8; следующий ход даёт 9 (не финал), после него — 10 (финал). Значит из суммы 9 любой ход выигрывает, а из суммы 8 все ходы ведут в 9 — то есть 8 является проигрышной суммой для того, кто должен из неё ходить.

Метод 5. Программный перебор. Если границы велики, полезно смоделировать процесс в псевдокоде: рекурсивно определить функцию $win(S)$, перебирая все возможные ходы. Это надёжный способ проверить ответ, полученный аналитически.

Алгоритм решения по шагам

1. Выписать все операции хода и число $N$.
2. Определить множество финальных значений: $S\ge N$.
3. Построить множество предпобедных позиций $M$: все $S'<N$, из которых хотя бы один ход даёт результат $\ge N$. Решить неравенства для каждой операции, взять объединение диапазонов, отсекая значения $\ge N$.
4. Для каждой операции хода Пети найти диапазон $S$, при котором результат попадает в $M$.
5. Взять минимум (или максимум, если требуется) по всем операциям — это искомое значение.
6. Проверить контрольные соседние значения $S$, чтобы убедиться, что более выгодного варианта нет.
7. Если задание спрашивает максимум, действовать аналогично, учитывая верхнюю границу диапазона $S\le N-1$.

Разбор примеров

Пример 1. Ходы: $S+1$, $S+4$, $5S$; порог $N=68$. Нужно минимальное $S$, при котором Петя сходил неудачно, а Ваня выиграл первым ходом.

Шаг 1. Находим $M$: условия $S'+1\ge68\Rightarrow S'\ge67$; $S'+4\ge68\Rightarrow S'\ge64$; $5S'\ge68\Rightarrow S'\ge13{,}6\Rightarrow S'\ge14$. Самое слабое ограничение даёт умножение: $M=\{14,\dots,67\}$.

Шаг 2. Ищем минимальное $S$, из которого ход Пети попадает в $M$:

• $S+1\in M\Rightarrow S\ge13$;
• $S+4\in M\Rightarrow S\ge10$;
• $5S\in M\Rightarrow 5S\ge14\Rightarrow S\ge3$ (при $5S<68\Rightarrow S\le13$).

Минимум среди $\{13,10,3\}$ равен 3.

Шаг 3. Проверка: при $S=3$ ход Пети $5\cdot3=15\in M$; из 15 Ваня делает $5\cdot15=75\ge68$ — победа. Ход Пети сам не завершил игру ($15<68$).

Шаг 4. Для $S=1,2$: ходы дают числа меньше 14, значит меньших вариантов нет. Ответ: $S=3$.

Пример 2. Ходы: $S+1$, $S+3$, $2S$; $N=42$.

Шаг 1. Условия: $S'+1\ge42\Rightarrow S'\ge41$; $S'+3\ge42\Rightarrow S'\ge39$; $2S'\ge42\Rightarrow S'\ge21$. Слабейшее ограничение даёт умножение: $M=\{21,\dots,41\}$.

Шаг 2. Минимальное $S$:

• $S+1\in M\Rightarrow S\ge20$;
• $S+3\in M\Rightarrow S\ge18$;
• $2S\in M\Rightarrow S\ge11$ (и $S\le20$).

Минимум среди $\{20,18,11\}$ равен 11.

Шаг 3. Проверка: при $S=11$ ход $2\cdot11=22\in M$; из 22 ход $2\cdot22=44\ge42$ — победа. Ход Пети не финиширует ($22<42$).

Шаг 4. Для $S=10$: ходы дают 11, 13, 20 — все меньше 21, значит меньше 11 не получится. Ответ: $S=11$.

Пример 3. Ходы: $S+1$, $S+4$, $2S$; $N=48$.

Шаг 1. Условия: $S'+1\ge48\Rightarrow S'\ge47$; $S'+4\ge48\Rightarrow S'\ge44$; $2S'\ge48\Rightarrow S'\ge24$. Объединение: $M=\{24,\dots,47\}$.

Шаг 2. Минимальное $S$:

• $S+1\in M\Rightarrow S\ge23$;
• $S+4\in M\Rightarrow S\ge20$;
• $2S\in M\Rightarrow S\ge12$ (и $S\le23$).

Минимум среди $\{23,20,12\}$ равен 12.

Шаг 3. Проверка: при $S=12$ ход $2\cdot12=24\in M$; из 24 ход $2\cdot24=48\ge48$ — победа Вани. Ход Пети не завершил игру ($24<48$).

Шаг 4. Для $S=11$: ходы дают 12, 15, 22 — все меньше 24, значит 12 — минимальное значение. Ответ совпадает с искомым.

Во всех трёх примерах решающую роль играет операция умножения — она даёт самый широкий диапазон предпобедных позиций и, соответственно, наименьшее допустимое $S$.

Типичные ошибки и ловушки

• Забывают проверить, что ход Пети сам не выигрышный (результат должен быть строго меньше $N$), из-за чего множество $M$ строится неверно.
• Ищут только по одной операции (например, только по сложению), забывая, что множитель обычно даёт более широкий диапазон и меньшее значение $S$.
• Путают направление неравенства: для сложения $S+a\ge N$ даёт $S\ge N-a$, а для умножения $kS\ge N$ даёт $S\ge N/k$ с округлением вверх, так как $S$ целое.
• Не проверяют условие $S'<N$ при построении $M$, из-за чего в множество ошибочно попадают уже финальные позиции.
• Путают задачу на минимум с задачей на максимум при невнимательном чтении условия.
• В задачах с двумя кучами забывают, что ход может применяться выборочно к одной из куч, и упускают часть возможных ходов при построении таблицы.
• Не делают финальную проверку граничных значений, из-за чего пропускают более выгодный вариант ответа.

Как готовиться

Начинать стоит с построения полной таблицы В/П вручную на небольших числах (до 15–20), чтобы прочувствовать механику обратной индукции — от финала к началу. Затем перейти к разбору частных формулировок задания 19: «выигрыш первым ходом», «выигрыш вторым ходом», «количество значений $S$» — каждая формулировка требует немного разного алгоритма, но опирается на одно и то же понятие предпобедных и проигрышных позиций. Полезно решать несколько задач подряд, каждый раз выписывая ходы в виде формул и решая систему неравенств явно, не полагаясь на интуицию. Хорошим тренажёром служит короткая программа, которая перебором проверяет функцию $win(S)$ для всех $S$ в заданном диапазоне — это позволяет быстро находить ошибки в ручных вычислениях. Отдельно нужно потренироваться на задачах с двумя кучами: важно аккуратно перечислять все допустимые ходы (к одной куче, к другой, иногда к обеим одновременно) и не забывать про условие завершения игры, которое может зависеть от суммы, максимума или конкретной кучи. После каждой решённой задачи стоит подставлять найденное значение обратно в условие и проверять, что сценарий партии полностью соответствует описанному в тексте задания.