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

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

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

• строить множество позиций, из которых можно выиграть немедленно;
• строить множества позиций, из которых гарантирован выигрыш не позднее второго, третьего и так далее хода;
• переносить эту логику на игры с одной кучей камней и на игры с двумя кучами, где состояние описывается парой чисел $(a, b)$.

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

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

Типовая формулировка: два игрока по очереди изменяют кучу (или две кучи) камней по фиксированным правилам (добавить $k$ камней, умножить на $m$ и т.п.), первый ход делает Петя. Игра заканчивается, когда количество камней становится не менее $N$; выигрывает сделавший последний ход. Задан диапазон начального количества камней $S$, обычно $1 \le S \le N-1$.

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

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

• Позиция — количество камней перед очередным ходом (для одной кучи — число, для двух куч — пара $(a,b)$).
• Игра завершается, как только позиция становится $\ge N$; выигрывает игрок, сделавший последний ход.
• Проигрышная позиция (П): все ходы из неё ведут в выигрышные позиции соперника.
• Выигрышная позиция (В): существует ход в позицию $\ge N$ либо в проигрышную позицию соперника. $$x \in \text{В} \iff \exists\, x \to x' : x' \ge N \ \text{или}\ x' \in \text{П}$$ $$x \in \text{П} \iff \forall\, x \to x' : x' \in \text{В}$$
• Для задач «выиграть не позже второго хода» нужны более тонкие множества: $$A = \{x < N : \exists\, x \to y,\ y \ge N\}$$ — из $x$ можно выиграть немедленно; $$B = \{x < N,\ x \notin A : \forall\, x \to x',\ x' \in A\}$$ — из $x$ нельзя выиграть сразу, но любой ход соперника загоняет его в $A$ для следующего игрока; $$C = \{x < N : \exists\, x \to y,\ y \ge N \ \text{или}\ y \in B\}$$ — из $x$ можно выиграть не позднее второго хода.
• Условие «выиграть не позже второго хода, но не первым»: все ходы противника из $S$ попадают в $C$, и при этом не все ходы противника из $S$ попадают в $A$.

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

1. Обратный анализ для одной кучи. Строится таблица В/П для чисел от $N-1$ вниз до 1. Пример: $N=10$, ходы $+1$ и $+2$. Число 9 — В (можно дойти до 10). Число 8 — В (ход +2 даёт 10). Число 7: ходы дают 8 (В) и 9 (В) — оба В, значит 7 — П. Так последовательно заполняется вся таблица.

2. Построение множеств $A$, $B$, $C$ через неравенства. Вместо перебора всех чисел можно сразу выразить границы множеств. Например, если ходы $+1$ и умножение на 2, а $N=20$: $A$ — это $x$, для которых $x+1\ge20$ или $2x\ge20$, то есть $x\ge19$ или $x\ge10$, значит $A=[10,19]$. Далее аналогично ищется $B$ среди $x<10$: нужно, чтобы оба хода из $x$ попадали в $A$, то есть $x+1\ge10$ и $2x\ge10$, откуда $x\ge9$, значит $B=\{9\}$.

3. Табличный метод для двух куч. Состояние — пара $(a,b)$. Таблица строится по возрастанию суммы $a+b$ (или максимума), для каждой пары проверяются все допустимые ходы (изменение одной или обеих куч), позиция помечается В или П по тому же правилу. Пример: правило «увеличить любую кучу на 1» при финише при $a+b\ge4$. Тогда $(1,1)$: ходы в $(2,1)$ и $(1,2)$ — сумма 3, ещё не финиш, нужно смотреть их статус; в итоге классификация строится снизу вверх по сумме.

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

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

1. Выписать порог окончания игры $N$ и диапазон начальных значений $S$.
2. Найти множество $A$ — позиции немедленного выигрыша, выразив условия каждой операции через неравенства относительно $N$.
3. Если нужно «не позже второго хода» — найти $B$: позиции, не входящие в $A$, из которых все ходы ведут в $A$.
4. Построить $C = A \cup \{x : \exists\, x\to y,\ y\in B\}$.
5. Если по условию нужно «не позже третьего/четвёртого хода», аналогично строить следующие множества (по тому же принципу «все ходы соперника из позиции ведут в уже построенное множество»).
6. Перебрать $S$ от минимального (или максимального, если ищется наибольшее) значения и для каждого проверить: все ли ходы из $S$ попадают в нужное множество (например $C$), и выполняется ли дополнительное условие (например «не все ходы из $S$ попадают в $A$»).
7. Зафиксировать первое подходящее $S$ и убедиться, что меньшие (или бОльшие) значения не подходят — это защищает от ошибки в границах.

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

Пример 1. Ходы: $+1$, $+4$, $\times 5$; порог $N=68$; диапазон $1\le S\le 67$.

Шаг 1. Множество $A$: нужно $x+1\ge68$, или $x+4\ge68$, или $5x\ge68$. Последнее условие $x\ge13{,}6$, то есть $x\ge14$, покрывает и первые два. Значит $A=[14,67]$.

Шаг 2. Множество $B$ ищем среди $x\le13$: нужно, чтобы $x+1$, $x+4$, $5x$ все были в $A=[14,67]$. Условие $x+1\ge14$ даёт $x\ge13$. Проверка $x=13$: ходы дают 14, 17, 65 — все в $A$. Значит $B=\{13\}$.

Шаг 3. Множество $C = A \cup \{x:$ ход из $x$ ведёт в 13$\}$. Кто может дойти до 13: $x+1=13\Rightarrow x=12$; $x+4=13\Rightarrow x=9$. Значит $C = [14,67]\cup\{9,12\}$.

Шаг 4. Перебор $S$: нужно, чтобы все три хода из $S$ ($S+1$, $S+4$, $5S$) попали в $C$, и не все — в $A$.

Проверка $S=8$: ходы дают 9, 12, 40. Все три числа в $C$ (9 и 12 — отдельно добавленные элементы, 40 — в $[14,67]$). При этом 9 и 12 не входят в $A$, значит второе условие тоже выполнено.

Проверка меньших значений ($S=1\ldots7$) показывает, что хотя бы один из ходов не попадает в $C$ (например, при $S=7$ ходы дают 8, 11, 35, а 8 и 11 не входят в $C$). Значит минимальное подходящее $S=8$, что совпадает с ответом.

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

$A$: условие $2x\ge42 \Rightarrow x\ge21$ покрывает и остальные операции, значит $A=[21,41]$.

$B$ среди $x\le20$: нужно $x+1\ge21$, то есть $x\ge20$. Проверка $x=20$: ходы 21, 23, 40 — все в $A$. $B=\{20\}$.

$C$: кто ходом попадает в 20? $x+1=20\Rightarrow x=19$; $x+3=20\Rightarrow x=17$; $2x=20\Rightarrow x=10$. $C=[21,41]\cup\{10,17,19\}$.

Проверка $S=16$: ходы дают 17, 19, 32 — все три в $C$, и 17, 19 не в $A$. Условие выполняется. Меньшие значения $S=9\ldots15$ дают хотя бы один ход вне $C$ (проверяется прямой подстановкой). Минимальное $S=16$ совпадает с ответом.

Пример 3. Ходы: $+1$, $+4$, $\times2$; порог $N=48$.

$A$: $2x\ge48 \Rightarrow x\ge24$, это условие покрывает остальные. $A=[24,47]$.

$B$ среди $x\le23$: нужно $x+1\ge24$, то есть $x\ge23$. Проверка $x=23$: ходы 24, 27, 46 — все в $A$. $B=\{23\}$.

$C$: кто ходом попадает в 23? $x+1=23\Rightarrow x=22$; $x+4=23\Rightarrow x=19$ (умножение на 2 не даёт целого решения). $C=[24,47]\cup\{19,22\}$.

Проверка $S=18$: ходы дают 19, 22, 36 — все в $C$, при этом 19 и 22 не входят в $A$. Условие выполняется. Проверка $S=9\ldots17$ показывает отсутствие хотя бы одного попадания в $C$. Минимальное $S=18$ совпадает с ответом.

Во всех трёх примерах видна одна и та же схема: сначала аналитически находится $A$ через неравенство для самой «сильной» операции (обычно умножения), затем $B$ — единственная (или несколько) точка на границе, затем $C$ — объединение $A$ с прообразами точек из $B$, и наконец перебор небольшого диапазона $S$ для нахождения минимального значения.

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

• Путают «выиграть не позже второго хода» с обычной выигрышной стратегией — забывают, что нужно гарантировать успех именно к определённому ходу, а не когда-либо.
• Забывают проверить второе условие задачи (например, «нет стратегии выиграть первым ходом») и останавливаются после нахождения множества $C$.
• В множество $B$ включают позицию, для которой ходом соперника можно попасть в $A$, но не всеми ходами — для $B$ нужно, чтобы абсолютно все доступные ходы вели в $A$.
• Ошибаются на границе неравенств: «не менее $N$» означает $\ge N$, а не $>N$; пропуск этой детали сдвигает все множества на единицу.
• Для двух куч забывают, что ход может менять только одну кучу или обе сразу — нужно внимательно перечислить все варианты хода, иначе множество позиций строится неверно.
• При переборе $S$ проверяют только один из возможных ходов противника, хотя условие «при любой игре Пети» требует проверки всех вариантов хода.
• Считают, что раз камней «неограниченное количество», то некоторые ходы могут быть недоступны — на самом деле все операции всегда разрешены независимо от текущего числа камней.

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

• Прорешать 15–20 задач с одной кучей и отдельно 10–15 задач с двумя кучами из открытого банка заданий, начиная с более простых пунктов (найти любое выигрышное $S$, затем количество таких $S$, и только потом — тонкие условия про порядок хода).
• Тренировать построение множеств $A$, $B$, $C$ аналитически через неравенства, а не полным перебором — это сильно ускоряет решение на экзамене.
• Проверять оба условия задачи как отдельный чек-лист: «выигрывает не позже нужного хода» и «не может выиграть раньше» — потеря баллов чаще всего происходит из-за игнорирования второго условия.
• Для самопроверки допустимо один раз построить полную таблицу В/П вручную для небольшого $N$, чтобы прочувствовать логику обратного анализа, прежде чем переходить на аналитические неравенства.
• Разобрать отдельно несколько задач с двумя кучами, где ход затрагивает обе кучи одновременно — это самый частый источник ошибок из-за роста числа вариантов ходов.
• Перед экзаменом решить 3–5 задач на время, фиксируя, сколько минут занимает построение всех нужных множеств — это задание требует аккуратности, а не скорости, поэтому важно не торопиться на границах интервалов.