Задание №21. Короткий конспект
Все первые ходы Пети, ответы Вани и отдельная проверка отсутствия гарантированного выигрыша первым ходом.
Петя начинает. Ваня должен победить первым или вторым собственным ходом при любой игре Пети, но не иметь гарантии первого выигрыша. В отдельных ветвях ранняя победа разрешена. После окончания игры продолжений нет.
Опорные обозначения
Позиция оценивается для игрока, который сейчас ходит. Все три набора относятся к ещё не законченной игре.
- W_1: Есть завершающий победный ход
- L_1: Все ходы передают сопернику продолжающуюся позицию из W_1
- W_2: Победы сразу нет, но есть ход в L_1
Порядок решения
- Фиксируются начальные ограничения, разрешённые действия и условие окончания. Для двух куч сохраняется пара чисел.
- Находятся W_1, затем L_1 и W_2. Это позволяет распознать первый и второй выигрыш того, кому передаётся ход.
- Проверяются все первые ходы Пети: каждый должен оставить Ване позицию из W_1 или W_2. Победа самого Пети сразу исключает начальное значение.
- Отдельно находится хотя бы один выход Пети вне W_1. Он опровергает гарантию первого выигрыша Вани. Остальные выходы могут разрешать раннюю победу.
- Выбирается минимум; все меньшие допустимые значения исключаются с указанием причины.
«Для каждого» обозначается \forall, «существует» — \exists. Порядок: \forall\text{П}_1\ \exists\text{В}_1; если игра продолжается, \forall\text{П}_2\ \exists\text{В}_2. Все выборы Пети сохраняются, ответ Вани подбирается для каждой полученной позиции.
Опорная проверка
В задаче об ответной стратегии ↗ действуют правила уменьшения кучи ↗: S\ge11, убрать три или пять, разделить на четыре с округлением вниз; победа при десяти или меньше.
Из 52 Петя получает 49, 47 или 13. Ваня передаёт соответственно 46, 44 или сразу заканчивает ходом 13\to10. Из 46 и 44 любой ответ Пети даёт немедленную победу Ване. Из 49 у Вани нет завершающего хода, поэтому гарантия первого исключена. Минимум — 52.
Возможные ловушки
Продление ветви через 10 добавляет несуществующие ходы. Запрет ранней победы ошибочно исключает ветвь через 13. Плохой выбор самого Вани не опровергает гарантию: нужна позиция без единого завершающего действия, как 49. Для проверки стратегии сохраняются все ответы Пети, включая неудобные.