Задание №21. Ответная стратегия Вани

Петя начинает игру, а Ваня должен обеспечить победу не позднее своего второго хода при любом выборе Пети. При этом гарантировать победу первым ходом Ваня не может. Эти требования совместимы: в одной ветви Ваня выигрывает сразу, в другой ему нужен ещё один ход. Решение должно охватить оба случая и отдельно показать, почему первого хода не всегда хватает.

Какие позиции нужны Ване

Позиция — состояние игры перед очередным ходом. Для одной кучи это число камней; рядом учитывается, кто ходит. Чтобы обеспечить победу, Ване нужен план ответа на каждый разрешённый выбор Пети. Такой план называется стратегией. Одна удачная последовательность ходов ещё не доказывает её существование.

После первого действия Пети Ваня должен получить одну из двух возможностей: закончить игру сейчас либо выбрать ход, после которого любой ответ Пети позволит Ване закончить следующим. Если Петя уже выиграл своим действием, ответной возможности нет. Поэтому условие окончания проверяется после каждого хода.

Полный пример: ветви разной длины

В задаче о победе Вани первым или вторым ходом ↗ используются правила уменьшения кучи ↗. Начальное количество S\ge11. Разрешено убрать три камня, убрать пять или разделить количество на четыре с округлением вниз. Побеждает тот, кто оставит не более десяти камней. Нужен минимум S, при котором Ваня гарантирует победу первым или вторым своим ходом, но не гарантирует её первым.

1. Позиции перед завершающими ходами

Из текущего числа s доступны s-3, s-5 и \lfloor s/4\rfloor. Последняя запись означает деление с округлением вниз. Деление оставляет не больше десяти, когда s<44; вычитания не расширяют эту границу. Поэтому победа за один ход возможна из всех целых чисел от 11 до 43. Этот набор обозначим W_1.

Из 44, 45 и 46 любой ход передаёт сопернику такой выигрыш. Эти позиции обозначим L_1: ходящий ещё не побеждает, но вынужден позволить сопернику закончить игру.

Значит, позиция с первым ходом в 44, 45 или 46 позволяет гарантировать победу вторым собственным ходом. Если немедленной победы из неё нет, она относится к набору W_2. Вблизи найденной границы это 47–51:

Это нужная для поиска минимума часть W_2, а не весь набор. В каждой строке соперник получает L_1 и любым ответом возвращает позицию с немедленной победой.

2. Все первые ходы Пети из 52

Следующее начальное число — 52. Петя может получить 49, 47 или 13. Ни один ход не заканчивает игру, а Ваня в каждой ветви имеет нужную возможность.

Ветка через 13 уже закончена: после хода Вани осталось десять камней. Её не нужно искусственно продлевать до второго хода. Две другие ветви требуют проверки всех следующих ответов Пети.

3. Продолжение двух длинных ветвей

После 52\to49\to46 Петя ходит из 46. Действия прежние: вычитание трёх, пяти или деление на четыре вниз. Ваня должен после каждого ответа оставить не более десяти.

После 52\to47\to44 Петя ходит из 44. Здесь получаются другие числа, но та же гарантия:

Все ответы Пети сохранены. На каждом ходе Вани показано одно подходящее действие — этого достаточно, поскольку он сам его выбирает. В короткой ветви выполнены два действия всей партии, в длинных — четыре; это соответственно первый и второй собственные ходы Вани.

4. Почему нет гарантии первого хода

Петя вправе выбрать 52\to49. Из 49 Ваня может получить только 46, 44 или 12. Все три результата больше десяти, поэтому ни один его ход пока не выигрывает. Уже эта ветвь опровергает гарантию победы первым ходом. Возможность сразу победить в другой ветви, через 13, этому не противоречит.

5. Почему 52 — минимум

Все меньшие допустимые начальные числа уже охвачены найденными наборами. Из 11–43 Петя может выиграть сразу. Из 44–46 Ваня гарантированно выигрывает первым, что запрещено вторым требованием задачи. Из 47–51 Петя сам обеспечивает победу вторым ходом по указанным переходам в 44–46, поэтому Ваня не имеет требуемой гарантии. Число 52 подходит по всем проверенным ветвям. Ответ: 52.

Ветви разной длины при росте кучи

В задаче с растущей кучей ↗ используются правила игры до 67 ↗: начало от 1 до 66; ходы — прибавить один, прибавить четыре, утроить; победа — при 67 или более. Немедленная победа возможна из 23–66. Позиция 22 любым ходом передаёт такой выигрыш: получаются 23, 26 или 66. Из любого допустимого числа не больше 21 можно прибавить один и оставить не больше 22, откуда немедленной победы ещё нет. Из 23–66 текущий игрок уже может выиграть сам. Поэтому 22 — единственная позиция, вынуждающая передать немедленную победу сопернику. Получить её можно из 18 прибавлением четырёх или из 21 прибавлением единицы; утроением получить 22 нельзя, поскольку 22 не делится на три.

При начале 17 все действия Пети дают 18, 21 или 51. Из 18 Ваня прибавляет четыре, из 21 — один, в обоих случаях оставляя 22. После ответов Пети 23, 26 или 66 Ваня завершает игру утроением, утроением или прибавлением единицы. Из 51 он сразу утраивает и побеждает первым ходом. Гарантии первого нет: например, из 18 ни одно действие Вани ещё не достигает 67.

Меньшие начальные значения не подходят: Петя может прибавить один и оставить не более 17. В этом диапазоне у Вани нет ни немедленной победы, ни хода в 22 для гарантии второго. Поэтому минимальное значение — 17.

Та же проверка для двух куч

В задаче об ответной стратегии с двумя кучами ↗ действуют правила игры до суммы 154 ↗: начало (11,S), 1\le S\le142; прибавление четырёх или утроение одной выбранной кучи; победа по общей сумме не меньше 154.

У каждого хода Пети четыре возможных результата. Ваня может выбрать собственный ответ для каждого из них. Если ответ не заканчивает игру, проверяются все четыре следующих действия Пети. Пара чисел сохраняется до конца расчёта: одинаковая сумма не означает одинаковые возможности утроения.

Возможные ловушки

• Требовать второй ход в каждой ветви. В основном примере ↗ ветвь 52\to13\to10 уже приносит победу. Её исключение заменит «первым или вторым» на «только вторым». Проверяется крайний разрешённый срок, а законченная ветвь не продолжается.
• Запретить любую победу первым. В том же примере отсутствие гарантии подтверждается ветвью через 49. Ранняя победа через 13 разрешена. Для опровержения гарантии достаточно одного первого хода Пети, после которого Ваня сразу выиграть не может.
• Доказывать отсутствие гарантии плохим ходом Вани. Из 13 он мог бы выбрать невыгодное действие, но у него есть 13\to10. Поэтому такой выбор не опровергает гарантию. Нужна позиция, где нет ни одного завершающего действия, как 49.
• Оставить Пете только удобный ответ. В игре до 67 ↗ после передачи 22 недостаточно показать только 22\to23\to69. Петя вправе получить также 26 и 66. Гарантия проверяется на всех трёх ветвях.
• Объявить найденное число минимумом без сравнения. В задаче о наименьшем начале ↗ стратегия для 52 доказывает только его пригодность. Минимальность требует отдельно исключить диапазоны 11–43, 44–46 и 47–51.