Теория
Игра с двумя кучами камней: игроки ходят по очереди, за ход можно увеличить одну из куч (например, добавить 1 камень или удвоить кучу), а выигрывает тот, после чьего хода сумма камней становится не меньше заданного порога \(S\). Такие задачи — это задания 19–21 ЕГЭ по информатике.
Ключевые понятия — выигрышная и проигрышная позиция. Позиция выигрышная, если из неё есть хотя бы один ход, который сразу приносит победу или оставляет сопернику проигрышную позицию. Позиция проигрышная, если все ходы из неё ведут в выигрышные позиции соперника. Эти определения рекурсивны: чтобы оценить позицию, нужно оценить все позиции, достижимые из неё, а игра конечна, потому что камни добавляются и сумма рано или поздно доходит до порога.
Из определений следует практическое правило: проигрышные позиции — это те, где любой ход «открывает» сопернику выигрыш. Зная их, легко играть: надо каждым ходом переводить игру в проигрышную для соперника позицию. Часто такие позиции образуют закономерность (например, при ходе «+1» с порогом 6 проигрышны все позиции с суммой 4).
Важно: выигрышность позиции не зависит от того, как играли раньше, — только от текущих куч, порога и правил ходов. Поэтому одну и ту же позицию можно оценивать один раз и запоминать результат.
Пример с решением
- Условие. Две кучи, за ход можно добавить 1 камень в любую кучу. Порог \(S = 4\). Кто выигрывает из позиции (1, 1)?
- Ходы из позиции. Возможны (2, 1) и (1, 2) — сумма 3, победы сразу нет.
- Оценка позиции (2, 1). Из неё есть ход (3, 1): сумма 4, победа. Значит, позиция (2, 1) выигрышная.
- Оценка позиции (1, 2). Аналогично выигрышная.
- Вывод. Оба хода из (1, 1) ведут в выигрышные для соперника позиции, поэтому (1, 1) — проигрышная: при правильной игре выигрывает второй.
- Проверка калькулятором. Режим «Кто выигрывает из позиции», правила «Две кучи: +1 в любую», \(a = 1\), \(b = 1\), порог 4 — ответ «проигрышная».
- Обратный пример. Если порог равен 3, то из (1, 1) ход (2, 1) сразу даёт сумму 3 — позиция выигрышная, и первый игрок побеждает за один ход.
Главное
- Выигрышная позиция: есть ход в проигрышную позицию или ход, сразу дающий сумму не меньше порога.
- Проигрышная позиция: все ходы ведут в выигрышные позиции соперника.
- Стратегия: каждым ходом переводить игру в проигрышную для соперника позицию.
- Задания 19–21: сначала находят проигрышные позиции, затем — выигрышные ходы в них.