Та же игра, что в задании 19. Повышенный уровень: нужно найти значения, при которых Петя не может выиграть первым ходом, но гарантированно выигрывает вторым, как бы ни ходил Ваня; ответ — два числа по возрастанию, за оба верных 1 балл.
| Ответ | два числа в таблице ответа |
|---|---|
| Баллы | 1 балл |
| Проверяет | умение найти выигрышную стратегию игры: при каком начальном числе камней первый игрок выигрывает своим вторым ходом при любой игре соперника |
| Сколько времени закладывать | около 7 минут по спецификации ФИПИ |
Условие. В куче камней, . Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней вдвое. Игра заканчивается, когда в куче становится 30 камней или больше; победил тот, кто сделал последний ход. Найдите два значения , при которых Петя не может выиграть первым ходом, но может выиграть своим вторым ходом при любой игре Вани. Запишите их по возрастанию.
Ответ: 7 и 13
Условие.
Перед игрой в кучу кладут камней (). Игроки Катя и Олег ходят по очереди, первой ходит Катя. Каждым ходом можно добавить в кучу один камень, добавить в кучу три камня или увеличить количество камней в куче вдвое. Побеждает тот, после чьего хода в куче стало не меньше 127 камней. Найдите два значения , при которых Катя не может выиграть первым ходом, но может выиграть своим вторым ходом, как бы ни играл Олег. Ответы запишите в порядке возрастания.
Решение.
Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче стало не меньше 127 камней). Из 64 ход «×2» даёт 128 — партия окончена, а из 63 ни один ход до конца не доводит. Значит, это все кучи от 64 до 126.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.
Пример: из 60 Катя партию сразу не заканчивает, но ходит в опорную позицию 63, и на любой ответ Олега Катя заканчивает партию: 64 → 128, 66 → 132, 126 → 127.
Все подходящие значения: из каждого Катя ставит Олега в опорную позицию, а сама первым ходом не побеждает. В ответ идут 60 и 62.
Ответ: 60 62
Условие.
Петя и Ваня играют с двумя кучами: в первой 8 монет, во второй — монет, где . Ходят по очереди, первым ходит Петя. За ход игрок может положить в любую из куч ещё две монеты или утроить количество монет в любой из куч. Партия заканчивается, как только в двух кучах суммарно окажется не меньше 116 монет; победителем считается тот, кто сделал последний ход. Найдите два значения , при которых у Пети есть выигрышная стратегия, позволяющая победить своим вторым ходом при любой игре Вани, но нет стратегии, позволяющей победить первым ходом. Ответы запишите в порядке возрастания.
Решение.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом. Среди позиций, где в первой куче 8, опорных нет — они появляются только после первых ходов, их находим по ходу разбора.
Пример: из (8; 30) Петя партию сразу не заканчивает, но ходит в опорную позицию (24; 30), и на любой ответ Вани Петя заканчивает партию: (26; 30) → (26; 90), (24; 32) → (24; 96), (72; 30) → (216; 30), (24; 90) → (26; 90).
Все подходящие значения: из каждого Петя ставит Ваню в опорную позицию, а сам первым ходом не побеждает. В ответ идут 30 и 35.
Ответ: 30 35
Условие.
В куче монет (). Коля и Лиза ходят по очереди, первым ходит Коля. За один ход разрешено убрать из кучи одну монету или уменьшить количество монет в куче вдвое (при нечётном количестве в куче остаётся на одну монету больше, чем забирают). Побеждает тот, после чьего хода в куче осталось меньше 67 монет. Найдите два наибольших значения , при которых Коля не может выиграть первым ходом, но может выиграть своим вторым ходом, как бы ни играла Лиза. Ответы запишите в порядке возрастания.
Решение.
Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче осталось не больше 66 монет). Из 132 ход «вдвое» даёт 66 — партия окончена, а из 133 ни один ход до конца не доводит. Значит, это все кучи от 67 до 132.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.
Пример: из 265 Коля партию сразу не заканчивает, но ходит в опорную позицию 133, и на любой ответ Лизы Коля заканчивает партию: 132 → 66, 67 → 66.
Все подходящие значения: из каждого Коля ставит Лизу в опорную позицию, а сам первым ходом не побеждает. В ответ идут 265 и 266.
Ответ: 265 266
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.