Позиции от конца игры

Как найти все S, при которых у Пети или у Вани есть выигрышная стратегия?

Идут от конца игры: сначала находят позиции, из которых выигрывают одним ходом, затем — позиции, которые зависят только от уже найденных. У конца игры всё известно: кто дошёл до 21, тот выиграл. Отступая на ход назад, каждый раз опираемся только на то, что уже знаем. Так разберём ту же игру: +1 или ×2, победа при s ≥ 21.

Группы позиций называют для того, кто сейчас ходит, а не для Пети или Вани. Буква — чем кончится игра, если оба играют правильно: В — ходящий выигрывает, П — проигрывает. Цифра — каким по счёту ходом всё решится: для В — своим ходом, для П — ходом соперника. В1 — ходящий выигрывает первым же ходом, П1 — соперник выигрывает своим первым ходом.

Из каких позиций можно выиграть сразу?

В1 — есть ход, после которого игра кончается. Из 11 можно получить 22, значит 11 — В1. Что 11 → 12 игру не заканчивает, неважно: игрок выберет удвоение.

Удвоением выигрывают, когда 2S ≥ 21, то есть S ≥ 11. Прибавлением — только из 20, а оно уже в этом списке. Получаем В1 = 11, 12, …, 20.

Позиция, где порог уже достигнут, — не В1: игра кончилась, ходить больше некому.

А если выиграть сразу нельзя и любой ход отдаёт сопернику В1?

П1 — все ходы ведут в В1 соперника: что ни сделай, он выиграет следующим ходом. Из 10 получается 11 или 20 — обе позиции В1. Значит, 10 — П1.

Других П1 здесь нет. Позиция П1 не может быть В1, поэтому S ≤ 10. И даже слабый ход +1 должен дать В1: S + 1 ≥ 11, то есть S ≥ 10. Остаётся только П1 = 10.

«Проигрыш» здесь значит, что соперник может выиграть наверняка. Если он ошибётся, партия пойдёт иначе.

Как выиграть своим вторым ходом?

В2 — выиграть сразу нельзя, но есть ход в П1: отдаёшь сопернику ловушку и выигрываешь следующим ходом. Ловушка у нас одна — 10. Попасть в неё: S + 1 = 10 или 2S = 10, то есть из 9 и из 5. Сразу ни из 9, ни из 5 не выиграть, поэтому В2 = 5, 9.

Из 5 стратегия — удвоить, из 9 — добавить один. Стратегию из 5 мы уже видели на дереве.

Когда соперник выигрывает не позже своего второго хода, но сразу — не при любом нашем ходе?

П2 — все ходы ведут в В1 или В2 соперника, но не все — в В1. Отдали сопернику В1 — он выигрывает сразу, В2 — вторым ходом. Если бы все ходы вели в В1, это была бы П1.

Найдём П2 нашей игры. Позиции 10–20 уже заняты, ищем среди 1–9. Проверим оба хода по очереди:

1. Ход +1 должен привести в В1 или В2. Из позиций 1–9 он даёт числа от 2 до 10, а из них В2 — только 5 и 9. Значит, кандидаты — 4 и 8.
2. Ход ×2 тоже должен привести в В1 или В2. Из 4 получится 8 — это не В1 и не В2, и 4 отпадает. Из 8 получится 16 — это В1.

Остаётся П2 = 8: из 8 Петя попадёт в 9 (В2 Вани) или в 16 (В1 Вани).

Ходы в В1 и в В2 вместе не обязательны: если все ходы ведут в В2, это тоже П2.

Как разобрать всю игру сразу?

Группы находят строго по порядку — В1, П1, В2, П2, — и каждая следующая опирается только на уже найденные. Вот все четыре правила на примерах из нашей игры:

Пройди разбор нашей игры по шагам:

Позиции 1–4, 6 и 7 ни в одну группу не попали. Это не значит, что они проигрышные: до победы из них больше двух ходов, а такие задания 19–21 не спрашивают.

Как вопросы заданий связаны с группами?

Все вопросы — о начальной позиции, где ходит Петя: задание 20 ищет В2, задание 21 — П2, а задание 19 бывает двух видов.

Буква группы — про того, кто ходит, а вопрос 21 — про Ваню. В П2 ходит Петя, а выигрывает Ваня. Вот стратегия Вани при S = 8:

Здесь видно и отрицание из задания 21. «Нет стратегии выиграть первым ходом» не значит «первым ходом выиграть нельзя». После 8 → 16 Ваня выигрывает сразу, но Петя может сходить 8 → 9 — и тогда сразу Ване не выиграть. Чтобы опровергнуть «при любом ходе», хватит одного хода-исключения.

• Группыдля того, кто ходит; находят от конца игры
• В1есть ход, который кончает игру
• П1все ходы ведут в В1
• В2не В1, но есть ход в П1
• П2не П1, но все ходы ведут в В1 или В2
• Задание 19неудачный ход Пети — возможность; «при любом ходе» — П1
• Задание 20В2
• Задание 21П2: «нет гарантии первым» — не «невозможно»