Та же игра, что в задании 19. Высокий уровень: нужно найти значение, при котором Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантировать победу именно первым ходом; ответ — число, 1 балл.
| Ответ | число в поле ответа |
|---|---|
| Баллы | 1 балл |
| Проверяет | умение построить дерево игры и найти выигрышную стратегию второго игрока |
| Сколько времени закладывать | около 10 минут по спецификации ФИПИ |
Условие. В куче камней, . Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней вдвое. Игра заканчивается, когда в куче становится 30 камней или больше; победил тот, кто сделал последний ход. Найдите наименьшее , при котором у Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая гарантирует победу первым ходом.
Ответ: 12
Условие.
Перед игрой в кучу кладут камней (). Игроки Петя и Ваня ходят по очереди, первым ходит Петя. Каждым ходом можно добавить в кучу один камень или увеличить количество камней в куче вдвое. Игра заканчивается, когда в куче становится 71 камень или больше; победил тот, кто сделал последний ход. При каком наименьшем одновременно верно: Ваня выигрывает первым или вторым ходом, как бы ни играл Петя, но гарантировать победу именно первым ходом Ваня не может?
Решение.
Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче стало не меньше 71 камня). Из 36 ход «×2» даёт 72 — партия окончена, а из 35 ни один ход до конца не доводит. Значит, это все кучи от 36 до 70.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.
Ход Пети в 34: сразу закончить Ваня не может, зато ходит в опорную позицию 35 и побеждает следующим ходом (36 → 72, 70 → 71).
Ход Пети в 66: Ваня сразу заканчивает партию.
На любой ход Пети у Вани есть ответ, а после хода в 34 немедленной победы нет — значит, гарантии победить именно первым ходом нет. Других подходящих значений нет.
Ответ: 33
Условие.
В первой куче 25 жетонов, во второй — жетонов (). Петя и Ваня ходят по очереди, первым ходит Петя. За один ход разрешено добавить в любую из куч один жетон или увеличить количество жетонов в любой из куч втрое. Партия заканчивается, как только в двух кучах суммарно окажется не меньше 145 жетонов; победителем считается тот, кто сделал последний ход. При каком наименьшем одновременно верно: Ваня выигрывает первым или вторым ходом, как бы ни играл Петя, но гарантировать победу именно первым ходом Ваня не может?
Решение.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом. Среди позиций, где в первой куче 25, опорных нет — они появляются только после первых ходов, их находим по ходу разбора.
Ход Пети в (26; 39): сразу закончить Ваня не может, зато ходит в опорную позицию (27; 39) и побеждает следующим ходом ((28; 39) → (28; 117), (27; 40) → (27; 120), (81; 39) → (243; 39), (27; 117) → (28; 117)).
Ход Пети в (25; 40): Ваня сразу заканчивает партию.
Ход Пети в (75; 39): Ваня сразу заканчивает партию.
Ход Пети в (25; 117): Ваня сразу заканчивает партию.
На любой ход Пети у Вани есть ответ, а после хода в (26; 39) немедленной победы нет — значит, гарантии победить именно первым ходом нет. Других подходящих значений нет.
Ответ: 39
Условие.
Перед игрой в кучу кладут шашек (). Игроки Катя и Олег ходят по очереди, первой ходит Катя. Каждым ходом можно взять из кучи три шашки или уменьшить количество шашек в куче вдвое (при нечётном количестве в куче остаётся на одну шашку больше, чем забирают). Побеждает тот, после чьего хода в куче осталось не больше 29 шашек. При каком наибольшем одновременно верно: Олег выигрывает первым или вторым ходом, как бы ни играла Катя, но гарантировать победу именно первым ходом Олег не может?
Решение.
Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче осталось не больше 29 шашек). Из 58 ход «вдвое» даёт 29 — партия окончена, а из 59 ни один ход до конца не доводит. Значит, это все кучи от 30 до 58.
Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.
Ход Кати в 122: сразу закончить Олег не может, зато ходит в опорную позицию 61 и побеждает следующим ходом (58 → 29, 31 → 28).
Ход Кати в 63: сразу закончить Олег не может, зато ходит в опорную позицию 60 и побеждает следующим ходом (57 → 29, 30 → 27).
На любой ход Кати у Олега есть ответ, а после хода в 122 немедленной победы нет — значит, гарантии победить именно первым ходом нет. Подходящих значений 6: 65, 66, 67, 123, 124, 125; наибольшее — 125.
Ответ: 125
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.