Два игрока, Петя и Ваня, играют в игру. Перед ними куча камней. Игроки ходят по очереди, начиная с Пети. За один ход игрок может добавить в кучу один камень или удвоить количество камней в куче. Игра заканчивается, когда количество камней в куче становится не менее 129. Побеждает игрок, сделавший последний ход.
Задание 19
Укажите значение S (начальное количество камней), при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение задания 19
Для победы необходимо достичь 129 или более камней. 129 можно получить, добавив один камень к 128 или удвоив 64. Если в куче 64 камня, то удвоение даст 128, а добавление одного камня – 129. Любое количество камней от 65 до 128 гарантирует победу игроку, удваивающему количество камней.
Чтобы Ваня выиграл первым ходом, после хода Пети должно остаться 64 или 65 камней. Если у Пети 64 камня, он может добавить один камень (65) или удвоить количество камней (128). В обоих случаях Ваня выиграет своим ходом, удвоив количество камней (130 или 256).
Чтобы Петя не мог выиграть за один ход, а Ваня мог выиграть своим первым ходом, начальное количество камней должно быть 64.
Ответ: 64
Задание 20
Укажите все значения S, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом.
Решение задания 20
Ключевая позиция – 64 камня. Чтобы Петя выиграл вторым ходом, после его первого хода должно остаться 64 камня. 64 камня можно получить, добавив один камень к 63 или удвоив 32. Следовательно, начальное количество камней может быть 32 или 63.
Ответ: 32, 63
Задание 21
Найдите максимальное значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети.
Решение задания 21
Ваня выигрывает вторым ходом, если после хода Пети остаётся 64 камня. Петя может получить 64 из 32 (удвоение) или 63 (добавление одного камня). Если начальное количество камней 62, Петя может сделать +1 (63) или ×2 (124). Если Петя сделал +1, Ваня делает +1 и получает 64. Если Петя сделал ×2, Ваня делает ×2 и получает 248, выигрывая первым ходом. Таким образом, максимальное значение S, при котором Ваня всегда выигрывает первым или вторым ходом, равно 62.
Ответ: 62
Решение задач на теорию игр, таких как задания 19-21 ЕГЭ по информатике, требует внимательного анализа возможных ходов и построения выигрышной стратегии. Построение дерева игры позволяет наглядно увидеть все возможные варианты и избежать ошибок. Понимание решения одной задачи помогает в решении последующих, что подчеркивает важность системного подхода.