Выигрышная стратегия

В заданиях 19, 20 и 21 одна игра и три вопроса о ней. Два игрока по очереди меняют кучи камней, и нужно понять, при каком начальном числе камней кто-то из них может выиграть наверняка. Вот задача, которую мы решим в этой теме:

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах всего 100 камней или больше. В начальный момент в первой куче было 7 камней, во второй куче — S камней; 1 ≤ S ≤ 92. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

Задание 21. Найдите минимальное значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.»

Главное здесь — не числа, а логика: где хватает одного удачного хода, а где нужно выдержать любой ход соперника. Разберём условие:

Две кучи и порог 100 — это сотни позиций, руками их не разобрать. Поэтому учиться будем на маленькой игре с одной кучей, а потом то же рассуждение запишем программой. Тема состоит из пяти подтем и дополнительного урока — у каждой своя страница. Идём по ним по порядку:

1. Игра и вопросы 19–21 — ты сейчас здесь: ход, стратегия и вопрос о неудачном ходе.
2. Позиции от конца игры — группы В1, П1, В2, П2 и какой вопрос о какой группе.
3. Программа — то же рассуждение одной функцией на Python.
4. Две кучи — решим задачу темы: ответы 24, 23 42 и 39.
5. Уменьшение кучи и ходы с условием — деление с округлением, ходы «если чётное», наибольшее S.
6. Третий ход и позиция шире числа — дополнительный урок для редких задач.

Что происходит в игре за один ход?

Ход — одно действие одного игрока: из одного числа камней получается другое. Учебная игра, на которой разберём всю логику темы:

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

Из 7 камней можно получить 7 + 1 = 8 или 7 · 2 = 14 — что-то одно. Число камней перед ходом называют позицией: «в куче 10, ходит Ваня».

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

«Петя выигрывает вторым ходом» — это три хода игры: Петя, Ваня, Петя. Проверить только два — частая ошибка.

Когда игра заканчивается?

Порог проверяют после каждого хода: кто первым до него дошёл, тот выиграл, и дальше никто не ходит. Если Петя из 12 получил 24, он уже выиграл — Ваня после этого не ходит.

«Не менее 21» — это s ≥ 21: подходят и 21, и 22, и 40, ровно 21 получать не нужно. Одно слово в условии меняет сравнение, а с ним и все три ответа:

не менее 21

s >= 2121 подходит

более 21

s > 21нужно хотя бы 22

не более 21

s <= 21в играх, где кучу уменьшают

менее 21

s < 2121 уже не подходит

S = 6. Петя удвоил — 12, Ваня удвоил — 24 и выиграл. Значит, при S = 6 Ваня всегда выигрывает первым ходом?

Нет. Это одна партия — одна сыгранная игра. Она показывает, что Ваня может выиграть, но не что он выиграет всегда: для этого нужно проверить все ходы Пети. Петя мог сходить и 6 → 7, а из 7 Ваня получит 8 или 14 — игра не кончится:

Выигрышная стратегия — план игрока, который приводит к победе при любых ходах соперника. Возьмём S = 5. Петя удваивает кучу и отдаёт Ване 10. Ваня может получить 11 или 20 — и из обеих позиций Петя выигрывает следующим ходом:

Такой рисунок называют деревом игры. В дереве стратегии у Пети нарисован один выбранный ход, а у Вани — все. Последний ход Пети зависит от ответа Вани: «если 11 — удвоить, если 20 — добавить один». Это нормальная стратегия.

Как проверить, что стратегия выигрышная?

На своём ходе хватает одного удачного хода, а на ходе соперника удачными должны быть все его ходы. Свой ход игрок выбирает сам — ему нужен хотя бы один хороший. А ход соперника выбирает соперник, и он выберет самый неудобный для нас, поэтому проверять приходится каждый. Проверим стратегию Пети при S = 5:

1. Ход Пети: 5 → 6 или 5 → 10. Ход 5 → 6 неудачный, но это неважно: Петя выберет 5 → 10.
2. Ход Вани: 10 → 11 или 10 → 20. Оба ответа нужно проверить: если бы хоть один спасал Ваню, гарантии бы не было.
3. Ход Пети: из 11 есть 22, из 20 есть 21. На каждый ответ Вани нашёлся победный ход.

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

Порядок тоже важен: Петя выбирает первый ход заранее и не может поменять его, узнав ответ Вани.

Что значит «Ваня выиграл своим первым ходом после неудачного первого хода Пети»?

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

При S = 6 она есть: Петя удваивает — 12, и Ваня удваивает — 24. Это партия, выделенная на первом дереве. А при S = 5 — уже нет: даже два удвоения подряд дают 5 · 2 · 2 = 20, до 21 не хватает. Поэтому наименьшее S для этого вопроса — 6.

Здесь за два хода игры — Петин и Ванин — куча должна дойти от S до порога. Быстрее всего она растёт, если оба раза сделать самый сильный ход. Отсюда правило: наименьшее S — то, при котором два самых сильных хода подряд дотягивают до порога.

• Хододно действие одного игрока
• Конец игрыпосле каждого хода, сравнение — точно по условию
• Второй ход Петитретий ход игры; второй ход Вани — четвёртый
• Партияодин вариант игры — показывает возможность
• Стратегияпобеда при любых ходах соперника — гарантия
• Свой ходхватает одного удачного
• Ход соперникаудачными должны быть все
• Неудачный ход Петивозможность: наименьшее S — два сильнейших хода подряд