Та же игра, что в задании 19. Высокий уровень: нужно найти значение, при котором Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантировать победу именно первым ходом; ответ — число, 1 балл.
Ответ
число в поле ответа
Баллы
1 балл
Проверяет
умение построить дерево игры и найти выигрышную стратегию второго игрока
Сколько времени закладывать
около 10 минут по спецификации ФИПИ
Какие бывают подтипы
Наименьшее значение — Одна куча, ходы «добавить камень» и «удвоить»: найти наименьшую подходящую кучу.
Другие ходы — Прибавлять можно больше одного камня, например четыре, и проигрышных позиций рядом с зоной победы становится несколько.
Две кучи — Позиция — пара чисел, из каждой позиции четыре хода, цель — по сумме камней в обеих кучах.
Пример с полным разбором
Условие. В куче S камней, 1≤S≤29. Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней вдвое. Игра заканчивается, когда в куче становится 30 камней или больше; победил тот, кто сделал последний ход. Найдите наименьшее S, при котором у Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая гарантирует победу первым ходом.
Разметка позиций для того, чей сейчас ход (она найдена в разборах заданий 19 и 20): из 15–29 он выигрывает одним ходом; из 14 любой его ход проигрывает; из 7 и 13 он выигрывает своим вторым ходом, оставив сопернику 14.
Ване нужна куча, из которой любой ход Пети ведёт в позицию, выигрышную для Вани: в зону 15–29 или в 7 и 13.
Куча 12: если Петя делает 13, Ваня добавляет камень, оставляет Пете 14 и выигрывает следующим ходом; если Петя делает 24, Ваня сразу удваивает до 48. Все ходы Пети проигрывают.
Гарантии победить первым ходом у Вани нет: после хода Пети на 13 одним ходом до 30 не дотянуться.
Для куч меньше 12 у Пети всегда есть ход, после которого Ваня за два хода не выигрывает: например, из 11 Петя сам ставит Ваню перед кучей 12. Это удобно проверить короткой программой-перебором.
Ответ: 12
Частые ошибки
Забывают, что «первым или вторым ходом» включает и победу первым ходом: отсекать нужно только гарантированную победу первым.
Проверяют не все ходы Пети, хотя стратегия Вани должна работать против каждого.
Путают ответ с соседней кучей, из которой ходящий проигрывает сразу: они отличаются на один-два камня.
Строят дерево дальше конца партии, хотя ветку обрывают, как только кто-то выиграл.
Путают, чей ход в стартовой позиции: первым ходит Петя, а вопрос — о победе Вани.
Что нужно знать для задания 21
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.
Один, если число совпало с верным. Уровень у задания высокий, но оценивается оно, как и все задания 1–25, одним баллом.
Нужно ли рисовать дерево игры в ответе?
Нет: проверяют только число в поле ответа. Дерево — способ решения на черновике, а записи в черновике не оцениваются.
Что такое дерево игры?
Схема возможных партий: из начальной позиции стрелки ведут к позициям после каждого хода, из них — к позициям после ответа соперника и так далее, пока кто-нибудь не выиграет.