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

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

…

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