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

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

…

• Позиция — количество камней перед очередным ходом (для одной кучи — число, для двух куч — пара $(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$ и диапазон начальных значений $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$»). …