Задание 20: Выигрышная стратегия. Задание 2

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