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

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

Задание 20 проверяет умение анализировать игру двух участников с полной информацией и конечным числом ходов. Нужно построить логику «от конца игры к началу» — определить, какие позиции выигрышные, какие проигрышные, и на основе этого найти конкретные числовые значения начального количества камней $S$, удовлетворяющие условиям задачи. Здесь проверяются не программирование и не перебор кода, а строгая логика и аккуратная работа с неравенствами и множествами чисел.

Задача моделирует игру: есть куча (или две кучи) камней, игроки по очереди делают ходы по фиксированным правилам, игра заканчивается, когда количество камней достигает порога $N$, победителем становится тот, кто сделал последний ход. Обычно рассматриваются три связанные подзадачи, и задание, о котором идёт речь, — вторая из них: нужно найти значения $S$, при которых первый игрок не может выиграть за один ход, но гарантированно выигрывает своим вторым ходом.

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

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

• он не может выиграть за один ход;
• он гарантированно выигрывает своим вторым ходом, независимо от игры второго игрока (Вани).

Это задание входит в блок из трёх пунктов (20.1, 20.2, 20.3), каждый оценивается в 1 балл, то есть всё задание может принести до 3 баллов. Ответ записывается как последовательность цифр — найденные значения $S$ в порядке возрастания без разделителей.

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

• Позиция — состояние игры, то есть количество камней в куче (для одной кучи) или пара чисел $(x,y)$ (для двух куч).
• Выигрышная позиция (В) — позиция, из которой игрок, делающий ход, может гарантированно довести игру до победы при любых ответах соперника.
• Проигрышная позиция (Л) — позиция, из которой любой ход ведёт в выигрышную позицию для соперника.
• Ход: если разрешены операции «добавить $a$», «добавить $b$», «умножить на $k$», то из позиции $x$ достижимы позиции $x+a,\; x+b,\; kx$.
• Условие завершения игры: игра заканчивается, когда позиция $x \ge N$; сделавший такой ход побеждает.
• Множество $F_1$ — позиции, из которых можно выиграть одним ходом: $$F_1=\{x<N:\; x+a\ge N \ \lor\ x+b\ge N \ \lor\ kx\ge N\}.$$
• Множество $F_2$ — позиции, из которых игрок гарантированно выигрывает своим вторым ходом. Это те $t\notin F_1$, для которых все возможные ходы соперника переводят игру в позицию из $F_1$, и при этом ни один ход соперника не завершает игру раньше времени: $$F_2=\{t\notin F_1:\; (t+a\in F_1)\land(t+b\in F_1)\land(kt\in F_1),\; \text{все результаты}<N\}.$$
• Общий принцип: $F_k$ строится через $F_{k-1}$ по той же логике — обратная индукция от конца игры.

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

1. Обратная индукция для одной кучи со сложением. Строим $F_1$ как множество чисел, близких к порогу $N$ — обычно это непрерывный отрезок $[N-c,\;N-1]$, где $c$ — наибольший шаг сложения. Пример: если ходы $+1$ и $+3$, $N=10$, то $F_1=\{7,8,9\}$, так как $7+3=10$.

2. Обратная индукция с умножением. Умножение обычно расширяет $F_1$ «вниз» сильнее, чем сложение, поэтому именно операция умножения часто определяет левую границу множества. Пример: ход $\times 2$, $N=20$ добавляет в $F_1$ все $x\ge10$, так как $2\cdot10=20$.

3. Анализ периодичности (для больших $N$). Если множество $F_1$ — сплошной интервал, часто оказывается, что и вся структура В/Л-позиций периодична с шагом, равным сумме или НОК шагов ходов. Это полезно для задач с большим диапазоном $S$, где перебор занял бы много времени.

4. Двумерный анализ для двух куч. Если есть две кучи $(x,y)$, а ход — это изменение одной из них (например, добавить камни в одну кучу или удвоить одну кучу), позицию нужно рассматривать как пару. Множества $F_1, F_2,\dots$ строятся аналогично, но состоят из пар чисел; часто удаётся свести задачу к одной переменной — сумме $x+y$ или максимуму $\max(x,y)$, если правила симметричны относительно куч.

5. Табличный перебор для контроля. Для небольших $N$ полезно построить таблицу «позиция — статус (В/Л) — куда ведут ходы» вручную от $N-1$ до $1$. Это медленный, но безошибочный способ проверки правильности построенных множеств $F_1, F_2$.

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

1. Выпишите порог $N$ и разрешённые операции (например, $+a$, $+b$, $\times k$).
2. Постройте множество $F_1$: решите неравенства $x+a\ge N$, $x+b\ge N$, $kx\ge N$ и объедините решения — это позиции, из которых можно выиграть одним ходом.
3. Найдите дополнение к $F_1$ на отрезке $[1,N-1]$ — назовём его «не-$F_1$». Это позиции, из которых первым ходом победить нельзя.
4. Постройте множество $F_2$: среди чисел не-$F_1$ найдите такие $t$, что все три результата ходов из $t$ ($t+a$, $t+b$, $kt$) одновременно строго меньше $N$ и принадлежат $F_1$. Обязательно проверяйте оба условия — если хотя бы один ход соперника заканчивает игру ($\ge N$), такое $t$ не подходит, потому что тогда выиграет соперник, а не наш игрок.
5. Найдите искомые $S$: среди чисел не-$F_1$ отберите те, из которых хотя бы одним ходом можно попасть в множество $F_2$ (решите уравнения $S+a=t$, $S+b=t$, $kS=t$ для каждого $t\in F_2$, проверяя целочисленность и попадание в допустимый диапазон).
6. Отсортируйте найденные значения по возрастанию и запишите ответ подряд без разделителей.

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

Пример 1. Порог $N=68$, ходы: $+1$, $+4$, $\times5$.

Шаг 1 — строим $F_1$: решаем $x+1\ge68$ ($x\ge67$), $x+4\ge68$ ($x\ge64$), $5x\ge68$ ($x\ge13{,}6$, то есть $x\ge14$). Самое слабое условие — $x\ge14$, оно покрывает и остальные. Значит $F_1=\{14,15,\dots,67\}$, а не-$F_1=\{1,\dots,13\}$.

Шаг 2 — строим $F_2$ среди $t\in\{1,\dots,13\}$. Нужно, чтобы $t+1,\;t+4,\;5t$ были одновременно $<68$ и $\ge14$. Условие $5t<68$ даёт $t\le13$. Условие $t+1\ge14$ даёт $t\ge13$. Значит единственное подходящее значение — $t=13$. Проверка: $13+1=14$, $13+4=17$, $5\cdot13=65$ — все три числа лежат в $[14,67]=F_1$ и меньше $68$. Значит $F_2=\{13\}$.

Шаг 3 — ищем $S\in\{1,\dots,13\}$, из которого один ход даёт $13$: $S+1=13\Rightarrow S=12$; $S+4=13\Rightarrow S=9$; $5S=13$ — не целое. Получаем $S=9$ и $S=12$.

Ответ: 912.

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

$F_1$: $x+1\ge42$ ($x\ge41$), $x+3\ge42$ ($x\ge39$), $2x\ge42$ ($x\ge21$). Слабейшее условие $x\ge21$ покрывает остальные, поэтому $F_1=\{21,\dots,41\}$, не-$F_1=\{1,\dots,20\}$.

$F_2$: нужно $t+1,\;t+3,\;2t$ одновременно $<42$ и $\ge21$. Из $2t<42$ следует $t\le20$. Из $t+1\ge21$ следует $t\ge20$. Значит $t=20$. Проверка: $20+1=21$, $20+3=23$, $2\cdot20=40$ — всё в $F_1$ и меньше $42$. $F_2=\{20\}$.

Ищем $S$: $S+1=20\Rightarrow S=19$; $S+3=20\Rightarrow S=17$; $2S=20\Rightarrow S=10$.

Ответ по возрастанию: 101719.

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

$F_1$: $x\ge47$, $x\ge44$, $x\ge24$ — самое слабое условие $x\ge24$. Значит $F_1=\{24,\dots,47\}$, не-$F_1=\{1,\dots,23\}$.

$F_2$: нужно $t+1,\;t+4,\;2t$ одновременно $<48$ и $\ge24$. $2t<48\Rightarrow t\le23$. $t+1\ge24\Rightarrow t\ge23$. Значит $t=23$. Проверка: $23+1=24$, $23+4=27$, $2\cdot23=46$ — всё подходит. $F_2=\{23\}$.

Ищем $S$: $S+1=23\Rightarrow S=22$; $S+4=23\Rightarrow S=19$; $2S=23$ — не целое.

Ответ по возрастанию: 1922.

Во всех трёх примерах видна одна и та же логика: сначала находится единственная (или несколько) «переходная» позиция $t$, из которой соперник обязан подарить победу, а затем ищутся ходы, ведущие именно в эту позицию.

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

• Забывают проверить, что ход соперника не завершает игру досрочно. Если хотя бы один из ходов из $t$ даёт результат $\ge N$, соперник сам выиграет этим ходом — такое $t$ нельзя включать в $F_2$, даже если оставшиеся ходы формально попадают в $F_1$.
• Путают «существует ход» и «все ходы». Для $F_1$ достаточно существования хотя бы одного выигрывающего хода. Для $F_2$ требуется, чтобы абсолютно все ходы соперника вели в $F_1$ — здесь нельзя ослаблять условие.
• Не проверяют целочисленность и границы. При решении уравнений вида $kS=t$ важно убирать нецелые и выходящие за диапазон $1\le S\le N-1$ решения.
• Путают порядок операций умножения и сложения при построении $F_1$. Умножение обычно расширяет множество сильнее сложения — стоит явно решить неравенство для каждой операции отдельно и объединить результаты.
• Для двух куч забывают рассмотреть ход по каждой из куч отдельно. Нужно перебрать все допустимые операции применительно к $x$ и к $y$ по отдельности, а не только к их сумме.
• Путают, кто первый ходит. Если по условию первым ходит не тот игрок, для которого ищется стратегия, знаки и порядок множеств $F_1, F_2$ нужно интерпретировать относительно чужого хода.

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

• Начните с ручного построения таблицы позиций для маленьких значений $N$ (10–20), чтобы прочувствовать логику В/Л-позиций без спешки.
• Освойте формальную запись множеств $F_1, F_2, F_3$ через неравенства — это ускоряет решение и снижает число ошибок по сравнению с полным перебором.
• Прорешайте задачи всех трёх типов подряд (обычная стратегия, победа вторым ходом, подсчёт количества стратегий), чтобы видеть общую структуру и различия между ними.
• Для самоконтроля напишите короткую программу (даже на псевдокоде), которая строит множества $F_k$ автоматически, и сравнивайте с ручным решением — так быстро находятся ошибки в границах.
• Регулярно решайте задачи с разными комбинациями операций: только сложение, сложение и умножение, сложение и деление — чтобы не привыкать к одному шаблону.
• Отдельно потренируйтесь на теме «две кучи»: там важно аккуратно перебирать ходы по каждой куче и следить, не сводится ли задача к анализу одной переменной (суммы или разности).