Задание №20. Короткий конспект
Первый выбор Пети, все ответы Вани и завершающий второй ход; короткая проверка стратегии и минимальности.
Петя начинает и должен гарантированно победить вторым собственным ходом, не имея победы первым. Порядок действий: Петя — Ваня — Петя. Поэтому второй ход Пети является третьим действием всей партии. После достижения порога игра немедленно заканчивается.
Три набора позиций
Позиция оценивается для игрока, который сейчас ходит. Все обозначения ниже относятся к ещё продолжающейся игре.
| Смысл | Метка и проверка |
|---|---|
| Победа за ход | W_1: есть завершающее действие |
| Вынужденная передача победы сопернику | L_1: все выходы — продолжающиеся позиции из W_1 |
| Победа вторым, но не первым | W_2: исходная позиция вне W_1, есть ход в L_1 |
Порядок решения
- Фиксируются состояние, все разрешённые ходы, начальные ограничения и условие окончания. Для двух куч сохраняется пара, а не только сумма.
- Находятся позиции с немедленной победой, затем позиции, все выходы которых передают такую победу сопернику.
- Выбирается один первый ход Пети во второй набор. Проверяются все ответы Вани и хотя бы один завершающий ход Пети после каждого.
- Исключаются начальные позиции с первым выигрышем. Из оставшихся выбираются значения в количестве и порядке, указанном в вопросе.
«Существует» обозначается \exists, «для каждого» — \forall. Здесь порядок: \exists\text{П}_1\ \forall\text{В}_1\ \exists\text{П}_2. Последний выбор Пети зависит от наблюдаемого ответа Вани.
Опорная проверка
В задаче о двух наименьших значениях ↗ действуют правила уменьшения кучи ↗: S\ge11, вычитание трёх или пяти, деление на четыре с округлением вниз, победа при десяти или меньше.
Победа за ход возможна из 11–43. Петя переводит 47 в 44 или 48 в 45. Любой ответ Вани попадает в 11–43, откуда Петя заканчивает игру. Меньшие 44–46 дают победу Ване, а 11–43 позволяют Пете выиграть сразу. Ответ: 47 48.
Возможные ловушки
Проверка одной партии не доказывает гарантию: у Вани нужны все ответы. Требование успеха после всех первых ходов Пети, наоборот, излишне: плохой ход 48\to43 не отменяет стратегию через 45. Остановка проверяется до продолжения, иначе Ване может быть приписан ответ после уже состоявшейся победы.