Теория:
Для решения задания \(21\) необходимо рассмотреть игру двух игроков до четвёртого хода. Условие задания предполагает рассмотрение ходов Первого игрока, ответных ходов Второго игрока и затем Первого игрока и, наконец, победных ходов Второго игрока.
Чтобы избежать сложности в объяснении, первый игрок назван именем, начинающимся на букву П, обозначая тот факт, что он ходит всегда первым и его ходы в общем счёте игры нечётные. Соответственно, второй игрок назван именем на букву В, так как его ход ответный — второй — и далее все ходы в общем счёте игры чётные.
В задании \(21\) Первый игрок на своём первом ходу делает все возможные ходы, а Второй игрок — только те, которые через ход приведут его к победе. Это реализация выигрышной стратегии Второго игрока. Выигрышная стратегия подразумевает, что первый ход Вани (Второго игрока) должен быть таким, чтобы все ответные ходы Первого игрока (Пети) приводили Ваню к выигрышу.
Пример \(1\)
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними находится одна куча камней. Каждый из игроков в свой ход может добавить в неё один камень или увеличить количество камней в куче вдвое. Выигравшим считается тот игрок, после хода которого в куче станет не менее \(46\) камней.
В начальный момент в куче \(S\) камней, при этом известно, что \(1<=S<=46\).
Найди наименьшее значение \(S\), при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.
Найди наименьшее значение \(S\), при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.
Для решения можем воспользоваться электронными таблицами.
Сформируем таблицу и впишем в неё формулы.
Рис. \(1\). Формулы
Определим правила для условного форматирования ячеек. Учтём, что для контроля над игрой следует проверять на значение выигрыша значения после первого и второго хода Пети и первого хода Вани.
Рис. \(2\). Правила условного форматирования
Подберём, изменяя значение в ячейке \(B1\), количество камней в куче, при котором Ваня выигрывает на своём первом или втором ходу. Учтём, что на каждый ход Пети у Вани должен быть выигрышный ход, при этом ни на первом, ни на втором Петином ходу не должно достигаться выигрышное значение. Про ходы Вани следует помнить, что ход должен быть таким, чтобы выигрышное значение достигалось либо на первом Ванином ходу, либо на втором. При этом количество камней \(20\) удовлетворяет этому условию.
Рис. \(3\). Подбор значения
При количестве камней \(=\) \(20\) Петя делает ходы \(21\) и \(40\), при Петином ходе \(40\) Ваня выигрывает своим первым ходом, увеличив количество камней в два раза. При Петином ходе \(21\) Ваня делает ход \(21+1=22\) и при любом ходе Пети выигрывает своим вторым ходом.
А количество камней, равное \(22\),
Рис. \(4\). Проверка значения
не удовлетворяет условию, так как Ваня имеет гарантированный выигрыш на своём первом ходу.
Такое решение может оказаться громоздким, если задача будет решаться для двух куч или для большего числа шагов.
Для решения составим программу на языке Python.
Опишем функцию.
 | Определим функцию для двух переменных. \(a\) — количество камней в куче после очередного хода, \(h\) — количество ходов. Ходы Вани чётные, поэтому, если после хода Вани достигается выигрышное значение, функция должна выводить True, в противном случае — False |
 | Количество шагов игры мы считаем от начала, поэтому все нечётные ходы — \(1\), \(3\), \(5\) — это ходы Пети, а чётные ходы — \(2\), \(4\), \(6\) — ходы Вани. На чётном ходу Ваня должен выиграть одним из своих ходов, но если Петя может выиграть любым своим ходом, то у Вани не остаётся шансов на победу |
Включим функцию в программу.
 | Перебираем различное количество камней, считаем ходы, начиная с \(0\). Выводим количество камней, при котором функция равна True |
Программа и результат её работы.
Рис. \(5\). Программа
Здесь также присутствует результат \(22\), который не удовлетворяет условию задачи. И его надо отсеять.
Пример \(2\)
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых \(2\), а во второй — \(S\) камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет \(2\) камня в какую-то кучу. Игра завершается в тот момент, когда общее число камней в двух кучах становится не менее \(142\). Если в момент завершения игры количество камней в одной из куч не менее \(142\), то выиграл Ваня, в противном случае — Петя.
Найди такое значение \(S\), при котором выполняются одновременно два условия:
— Ваня может выиграть своим первым или вторым ходом;
— у Вани нет стратегии, при которой он гарантированно выиграет своим первым ходом.
— Ваня может выиграть своим первым или вторым ходом;
— у Вани нет стратегии, при которой он гарантированно выиграет своим первым ходом.
Рис. \(6\). Программа и результат её работы
Проверим результат в электронных таблицах.
При ходе Пети (\(4\), \(66\)) Ваня выигрывает на своём втором ходу:
— зелёные ячейки таблицы.
Рис. \(7\). Результат вычислений \(1\)
При ходе Пети (\(2\), \(68\)) Ваня выигрывает на своём втором ходу:
— зелёные ячейки таблицы.
Рис. \(8\). Результат вычислений \(2\)
При ходе Пети (\(2\), \(132\)) Ваня выигрывает на своём первом ходу:
— голубая ячейка таблицы.
Рис. \(9\). Результат вычислений \(3\)
Проверь, что \(69\) камней не дают правильного результата.
Источники:
Рис. 1. Формулы. © ЯКласс.
Рис. 2. Правила условного форматирования. © ЯКласс.
Рис. 3. Подбор значения. © ЯКласс.
Рис. 4. Проверка значения. © ЯКласс.
Рис. 5. Программа. © ЯКласс.
Рис. 6. Программа и результат её работы. © ЯКласс.
Рис. 7. Результат вычислений 1. © ЯКласс.
Рис. 8. Результат вычислений 2. © ЯКласс.
Рис. 9. Результат вычислений 3. © ЯКласс.