Теория:
Для решения задания \(20\) необходимо рассмотреть игру двух игроков до третьего хода. Условие задания предполагает рассмотрение ходов Первого игрока, ответных ходов Второго игрока и завершающих победных ходов Первого игрока.
Чтобы избежать сложности в объяснении, Первый игрок назван именем, начинающимся на букву П, обозначая тот факт, что он ходит всегда первым и его ходы в общем счёте игры нечётные. Соответственно, Второй игрок назван именем на букву В, так как его ход ответный — второй — и далее все ходы в общем счёте игры чётные.
В задании \(20\) Первый игрок может сделать не все возможные ходы, а только те, которые через ход приведут его к победе. Это реализация выигрышной стратегии Первого игрока. Выигрышная стратегия подразумевает, что первый ход Пети (Первого игрока) должен быть таким, чтобы все ответные ходы Второго игрока (Вани) приводили Петю к выигрышу.
Рассмотрим пример
Два игрока — Первый и Второй — играют в следующую игру. Перед ними находится одна куча камней. Каждый из игроков в свой ход может добавить в неё один камень или увеличить количество камней в куче вдвое. Выигравшим считается тот игрок, после хода которого в куче станет не менее \(46\) камней.
В начальный момент в куче \(S\) камней, при этом известно, что \(1<=S<46\).
Укажи такое значение \(S\), при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанного значения \(S\) опиши выигрышную стратегию Пети.
Выполним решение вручную.
Из анализа таблицы полной игры определим выигрышное для Пети количество камней, \(11\).
Зелёным цветом выделены выигрышные ходы Пети. При его первом ходе \(11*2\) на все ответные ходы Вани у Пети есть ходы, приводящие его к выигрышу.
В электронных таблицах также организуется вычисление по формулам для полного дерева игры, но значение \(S\) не вычисляется, а определяется перебором в интервале \(1<=S<46\), определённым условием задачи.
В электронных таблицах также организуется вычисление по формулам для полного дерева игры, но значение \(S\) не вычисляется, а определяется перебором в интервале \(1<=S<46\), определённым условием задачи.
Рассмотрим на примере задания из демоверсии \(2023\) года
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними находится одна куча камней. Каждый из игроков в свой ход может добавить в неё один камень или увеличить количество камней в куче вдвое. Для того чтобы делать ходы, у каждого игрока есть неограниченное число камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее \(129\). Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу из \(129\) или больше камней.
В начальный момент в куче \(S\) камней, при этом известно, что \(1<=S<=128\).
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найди два наименьших значения \(S\), при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запиши в порядке возрастания.
Рассмотрим решение в электронных таблицах.
Сформируем таблицу и впишем в неё формулы.
Рис. \(1\). Формулы
Определим правила для условного форматирования ячеек (в примере показано правило для столбца \(C\)). Для столбца \(D\) и \(E\) правило останется тем же, рекомендуем поменять цвет выделения. Форматирование проводится для трёх столбцов с вычислениями для того, чтобы, контролируя выигрышную сумму, получаемую Первым игроком, не пропустить ситуацию, когда Первый игрок на своём первом ходу получит такую сумму или Второй игрок сделает это и не даст возможности Первому игроку выполнить условие задачи.
Рис. \(2\). Условное форматирование
Подберём, изменяя значение в ячейке \(C1\), количество камней в куче, при котором Петя выигрывает на своём втором ходу. При этом обязательно выполнение условия выигрыша при любом ходе Вани.
Выигрышная стратегия Пети выделена в таблице.
Рис. \(3\). Результат \(1\)
Для достижения этого значения выигрышная стратегия Пети заключается в удвоении количества камней на первом ходу, а далее, при любом ходе Вани, он выигрывает, сделав ход в ячейку, выделенную зелёным цветом.
Рис. \(4\). Результат \(2\)
Для достижения этого значения выигрышная стратегия Пети заключается в увеличении количества камней на \(1\) первым ходом, а далее, при любом ходе Вани, он выигрывает, сделав ход в ячейку, выделенную зелёным цветом.
Ответ: \(32\), \(63\).
Источники:
Рис. 1. Формулы. © ЯКласс.
Рис. 2. Условное форматирование. © ЯКласс.
Рис. 3. Результат 1. © ЯКласс.
Рис. 4. Результат 2. © ЯКласс.