В заданиях 19–21 описывается одна и та же игра. В ней участвуют два игрока — Петя и Ваня. Они ходят по очереди, причём первый ход всегда делает Петя. Петя и Ваня — условные имена. У них нет особых способностей или скрытых правил. Они нужны только для того, чтобы мы понимали, кто ходит первым, а кто отвечает (П — Петя — Первый, с Ваней аналогично) .
Перед игроками лежит одна или две кучи камней. За один ход разрешено изменить одну из куч одним из способов, указанных в условии: например, добавить камни, убрать их или умножить количество.
После каждого хода проверяется условие окончания игры. Если нужное количество камней уже получено, игра сразу завершается, а сделавший этот ход игрок становится победителем.
Что означает число S
Буквой S обозначают начальное количество камней в куче. Это не отдельная команда и не результат хода. Именно такое количество камней игроки видят перед первым ходом Пети.
Значение S обычно неизвестно: его и требуется найти. Мы перебираем возможные начальные позиции и определяем, при каких из них выполняется условие задания.
Если куч две, начальная позиция записывается парой чисел, например (7, S). Тогда в первой куче изначально 7 камней, а количество камней во второй куче нужно определить.
Что такое выигрышная стратегия
Выигрышная стратегия — это план, который гарантирует победу при любых допустимых действиях соперника. Одного удачного хода недостаточно: нужно заранее знать, что делать после каждого возможного ответа.
Поэтому мы считаем, что оба игрока действуют разумно. Петя не станет специально помогать Ване, а Ваня не выберет удобный для Пети ход, если у него есть более выгодный вариант.
Как связаны задания 19, 20 и 21
Во всех трёх заданиях используются одни правила и одно начальное число S. Меняется только вопрос: кто может гарантировать победу и на каком по счёту своём ходу она должна произойти.
В задании 19 обычно требуется позиция, в которой Петя не выигрывает сразу, а Ваня побеждает своим первым ходом после любого ответа Пети.
В задании 20 победить должен Петя своим вторым ходом. Ему нужно выбрать такой первый ход, чтобы после любого ответа Вани сохранился завершающий ход.
В задании 21 победу снова гарантирует Ваня, но уже первым или вторым своим ходом. При этом отдельно сказано, что гарантированной победы именно первым ходом у него нет.
Сначала разберём игру с одной кучей. На ней проще увидеть общий ручной алгоритм. Для двух куч используются те же уровни позиций, но сама позиция записывается уже парой чисел.
Алгоритм решения
Учебная игра
Возьмём простую игру с одной кучей. В начале в ней находится S камней. Петя ходит первым, затем игроки по очереди добавляют в кучу 2 или 5 камней.
Побеждает игрок, после хода которого в куче становится 20 камней или больше. Поэтому значения 20, 21 и далее — уже не позиции для нового хода: к этому моменту игра уже закончилась.
Наша задача — определить, что произойдёт при разных начальных значениях S, если оба игрока выбирают лучшие для себя ходы.
Что такое позиция
Позиция — это состояние игры перед очередным ходом. В игре с одной кучей позицию задаёт одно число: текущее количество камней. Например, позиция 13 означает, что сейчас в куче 13 камней.
Из позиции 13 можно перейти в 15 ходом +2 или в 18 ходом +5. Эти переходы называют ветвями дерева игры. В каждой новой позиции ход уже принадлежит сопернику.
Удобнее говорить не только о Пете и Ване, а о текущем игроке — том, кто должен ходить из рассматриваемой позиции. Тогда одна и та же разметка подходит обоим участникам.
Уровни выигрышных и проигрышных позиций
Буква В означает выигрышную позицию для текущего игрока, а буква П — проигрышную. В обозначении В цифра показывает ход победы текущего игрока, а в обозначении П — ход победы его соперника.
В1 — позиция, из которой текущий игрок может закончить игру одним ходом. Здесь достаточно найти хотя бы один выигрывающий ход.
П1 — позиция, из которой все допустимые ходы ведут в В1 для соперника. Что бы текущий игрок ни сделал, соперник получит позицию с немедленной победой.
В2 — позиция, из которой существует ход в П1. Текущий игрок передаёт сопернику проигрышную позицию, а после любого ответа завершает игру своим вторым ходом.
П2 — позиция, из которой все ходы ведут соперника в В1 или В2, причём хотя бы один ход ведёт в В2. Соперник победит не позднее второго хода, но победа первым ходом не гарантирована.
Если игроку достаточно выбрать один удачный ход, мы ищем хотя бы одну подходящую ветвь. Именно так находятся позиции В1 и В2.
Если в условии сказано «при любом ходе противника», нужно проверить каждую ветвь. Одна удобная ветвь ничего не доказывает: соперник выберет другой ход, если он разрушает нашу стратегию.
Общий ручной алгоритм
Выпишите начальную позицию, все команды игроков и точное условие окончания игры.
Отметьте конечные значения: если они уже достигнуты, следующий ход не выполняется.
Найдите В1 — неконечные позиции, из которых существует ход, сразу завершающий игру.
Найдите П1 — неконечные позиции, из которых каждый ход передаёт сопернику В1.
Найдите В2 — позиции вне В1, из которых существует ход в П1.
Найдите П2 — позиции вне П1, из которых каждый ход ведёт соперника в В1 или В2, а хотя бы один ведёт в В2.
Сопоставьте найденный уровень с вопросом задания и выберите минимальное или максимальное S, если этого требует условие.
Задание 19
В нашей учебной игре требуется минимальное S, при котором Петя не может победить за один ход, а после любого его хода Ваня выигрывает своим первым ходом.
Сначала найдём В1. Из позиций 15–19 можно одним ходом получить не менее 20 камней: к 15, 16 или 17 прибавляем 5, а к 18 или 19 достаточно прибавить 2. Далее на рисунках будем отмечать «крайние» точки — здесь это 15 (для хода +5 камней) и 18 (для +2). Цветовую маркировку будем использовать такую:
голубой — позиция, которую сейчас проверяем: начальное S, знак ? или раскрываемый узел;
зелёный — число или ветвь, которые подтверждают рассматриваемую стратегию;
оранжевый — исключённый вариант: ход ломает стратегию или число не удовлетворяет проверяемому условию.
Позиция 14 ещё не относится к В1: после +5 получится только 19. Значения от 20 уже конечные, поэтому их также не включаем в В1.
Теперь ищем П1. Оба хода из начальной позиции должны привести Ваню в диапазон 15–19. Значит, одновременно должны выполняться два условия: S + 2 и S + 5 входят в этот диапазон.
Для хода +2 подходят S от 13 до 17. Для хода +5 подходят S от 10 до 14. Общая часть этих диапазонов — 13 и 14.
Проверим S = 13. Петя получает 15 или 18 камней. Из 15 Ваня добавляет 5, а из 18 — 2. В обеих ветвях Ваня достигает 20 камней.
При S = 14 рассуждение такое же: Петя оставляет 16 или 19 камней, после чего Ваня завершает игру. Подходят два значения, но в задании требуется минимальное, поэтому ответ равен 13.
Мы нашли позиции П1. Их смысл легко проверить словами: текущий игрок ещё не может победить, а каждый его ход передаёт сопернику позицию В1.
Задание 20
Теперь Петя должен гарантированно выиграть своим вторым ходом, но не первым (это третий ход всей игры). Значит, начальная позиция должна относиться к В2: из неё существует первый ход Пети в П1.
Позиции П1 уже известны: это 13 и 14. Найдём, откуда Петя может получить одно из этих чисел. В 13 можно перейти из 11 ходом +2 или из 8 ходом +5.
В 14 можно перейти из 12 ходом +2 или из 9 ходом +5.
Получаем четыре позиции В2: 8, 9, 11 и 12. В задании нужны два наименьших значения, поэтому предварительные ответы — 8 и 9.
Проверка должна охватывать всё дерево. Сначала существует удачный ход Пети в П1. Затем рассматриваются все ответы Вани. После каждого из них у Пети должен существовать завершающий ход.
Коротко эту логику можно записать так: существует ход Пети — любой ход Вани — существует ответ Пети.
Для S = 8 Петя добавляет 5 и оставляет Ване 13 камней. Если Ваня получает 15, Петя добавляет 5. Если Ваня получает 18, Петя добавляет 2. В обеих ветвях получается 20.
Для S = 9 Петя также добавляет 5 и оставляет Ване 14 камней. После ответа Вани получается 16 или 19, и Петя завершает игру следующим ходом.
Значения 8 и 9 не входят в В1, поэтому Петя действительно не может выиграть сразу. Оба условия задания 20 выполнены.
Задание 21
В задании 21 выигрывает Ваня. Он должен победить первым или вторым своим ходом после любой игры Пети, но гарантированной победы именно первым ходом быть не должно.
Мы ищем позицию П2. После каждого хода Пети Ваня должен получить В1 или В2. При этом хотя бы одна ветвь должна вести в В2, иначе Ваня выигрывал бы первым ходом при любой игре Пети.
При S = 6 Петя может оставить 8 камней ходом +2 или 11 камней ходом +5. Обе позиции относятся к В2, поэтому Ваня гарантированно победит своим вторым ходом.
Из 8 или 11 Ваня ещё не может сразу получить 20 камней. Следовательно, стратегии с гарантированной победой первым ходом у него нет. Дополнительное условие задания выполнено.
Число 5 не подходит: после ходов Пети получаются 7 и 10, а эти позиции не относятся ни к В1, ни к В2. Поэтому минимальный ответ задания 21 — 6.
Теперь у нас есть полная разметка учебной игры: В1 — 15–19, П1 — 13–14, В2 — 8, 9, 11 и 12, а минимальная П2 — 6. А ответами на все три задания будут числа 13; 8 и 9; 6.
На реальных задачах будем повторять те же шаги.
Пример 1
Теперь аналогичным образом решим реальное задание ЕГЭ. Формулировка будет такая:
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
— убрать из кучи два камня;
— уменьшить количество камней в куче в два раза (количество камней при делении округляется до меньшего)
Игра завершается в тот момент, когда количество камней в куче становится не более 87.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 87 камней или меньше. В начальный момент в куче было S камней; S > 88.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Победа наступит, когда в куче будет 87 камней и меньше.
Игра идёт на уменьшение, но принцип остаётся тем же: сначала отмечаем позиции победы в один ход, затем двигаемся по дереву назад.
Победа в один ход возможна из чисел 88–175: деление пополам даёт не более 87, а число 88 позволяет еще и команду «-2» использовать. Но всё же область нужно проверить целиком, а не сводить рассуждение к «самой ценной» команды (у нас это деление).
Теперь ищем минимальную позицию, из которой оба хода Пети ведут в диапазон 88–175. Чтобы Ваня за один ход любой командой получил кучу из 87 и менее камней.
Для S = 176 получаем 174 после хода −2 и 88 после деления пополам. Обе позиции выигрышные для Вани.
Поэтому минимальный ответ задания 19 — 176.
Задание 20
В задании 20 Петя должен гарантированно победить своим вторым ходом, но не первым. Значит, первым ходом он должен оставить Ване позицию П1.
В задании 19 мы нашли минимальную позицию П1 — 176. Но теперь одного минимального значения недостаточно: нужно найти все ближайшие позиции П1.
Проверим 177. После хода −2 останется 175, а после деления пополам — 88. Оба числа входят в диапазон В1 88–175.
Следовательно, 177, как и 176, относится к П1. Какой бы ход ни сделал текущий игрок, соперник получит позицию немедленной победы.
Теперь ищем В2: позиции, из которых Петя может одним ходом оставить Ване 176 или 177.
Команда −2 даёт два ближайших значения: из 178 получается 176, а из 179 — 177.
Делением пополам получить 176 или 177 можно только из 352–355. Эти значения тоже относятся к В2, но в ответе нужны два наименьших S. Поэтому проверяем 178 и 179.
При S = 178 Петя не может выиграть сразу: после его ходов остаются 176 или 89 камней, а оба числа больше 87. По понятным причинам оставлять Ване 89 камней он не будет (если не понятно, то тогда Ваня сразу выиграет ходом «:2»).
Значит, Петя выбирает ход −2 и оставляет Ване 176. Ваня может получить 174 или 88. После любого его хода Петя делит кучу пополам и получает 87 или 44 камня. А если Ваня зачем-то оставил 88 камней, то тогда подойдёт и ход «-2».
При S = 179 Петя также не может выиграть первым ходом: после команд остаются 177 или 89 камней.
Петя вычитает 2 и оставляет Ване 177. Ваня получает 175 или 88, после чего Петя делит кучу пополам и завершает игру.
Вот и всё, поздравляем Петра с заслуженной победой и записываем ответ на задание 20: 178, 179.
Задание 21
В задании 21 после любого первого хода Пети Ваня должен выиграть первым или вторым ходом. При этом у него не должно быть стратегии победы именно первым ходом.
Мы уже разметили ближайшие позиции: 176 и 177 относятся к П1, а 178 и 179 — к В2. Поэтому следующее значение для проверки — 180.
Петя может оставить 178 камней ходом −2 или 90 камней делением пополам. Разберём обе ветви.
Если Петя оставил 90, Ваня делит кучу пополам, получает 45 камней и выигрывает своим первым ходом. Для компактности на рисунке вовсе опустим эту ветвь.
Если Петя оставил 178, Ваня вычитает 2 и передаёт Пете позицию 176. Петя может получить 174 или 88, после чего Ваня делит кучу пополам и выигрывает своим вторым ходом, как это уже было рассмотрено ранее.
После любого хода Пети Ваня побеждает не позднее своего второго хода. Ветвь через 178 показывает, что победа Вани первым ходом не гарантирована (ветвь с гарантированной победой 180 → 90 → 45 мы не отображали на рисунке).
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится не менее 39. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 39 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 38.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Победа наступает, когда в куче становится не менее 39 камней. Игра идёт на увеличение, поэтому начинаем с позиций, из которых можно закончить игру за один ход.
Чтобы найти В1, проверим каждую команду. Ходом +1 можно выиграть из 38, ходом +3 — из 36–38, а удвоением — из 20–38.
Объединяем найденные значения. Позиции В1 образуют непрерывный диапазон от 20 до 38. Из любого такого числа текущий игрок может получить не менее 39 камней одним ходом.
Задание 19
По условию Петя не должен выиграть первым ходом, но после любого его хода Ваня должен победить сразу. Значит, ищем позицию П1: все ходы из неё должны вести в диапазон В1 20–38.
Рассмотрим границы диапазона. После команды +1 должно получиться хотя бы 20, поэтому S должно быть не меньше 19.
После удвоения результат не должен превысить 38, иначе Петя сам закончит игру. Поэтому S должно быть не больше 19.
Оба ограничения одновременно выполняются только при S = 19.
Проверим все ходы Пети. Из 19 получаются 20, 22 и 38. Все три числа входят в В1, поэтому после любого решения Пети Ваня выигрывает следующим ходом.
Например, из 20 Ваня получает 40 удвоением, из 22 — 44 удвоением, а из 38 — 39 командой +1.
При S = 18 условие уже нарушается: Петя может добавить 1 и оставить Ване 19, из которого нельзя выиграть сразу. Поэтому минимальный ответ задания 19 — 19.
Задание 20
Теперь Петя должен гарантированно выиграть своим вторым ходом, но не первым. Значит, первым ходом ему нужно передать Ване найденную позицию П1 — число 19.
Получить 19 командой +1 можно из 18, а командой +3 — из 16. Удвоением получить нечётное число 19 нельзя.
Так мы находим две ближайшие позиции В2: 16 и 18. Обе меньше 20, поэтому Петя не может закончить игру первым ходом: из 16 максимум получается 32, а из 18 — 36.
При S = 16 Петя добавляет 3 и оставляет Ване 19 камней.
При S = 18 он добавляет 1 и также оставляет Ване 19 камней.
Дальше Ваня может получить 20, 22 или 38. После любого его хода Петя завершает игру: 20 * 2 = 40, 22 * 2 = 44, а 38 + 1 = 39.
Следовательно, Петя выигрывает своим вторым ходом независимо от решения Вани. Ответ задания 20: 16, 18.
Задание 21
В задании 21 после любого первого хода Пети Ваня должен выиграть первым или вторым ходом. При этом Ваня не должен иметь гарантированной победы именно первым ходом.
Мы ищем позицию П2. Все ходы Пети должны вести в В1 или В2, причём хотя бы один ход должен вести в В2. Такая ветвь не позволит Ване закончить игру сразу.
Проверим S = 15. Петя может получить 16 командой +1, 18 командой +3 или 30 удвоением.
Числа 16 и 18 относятся к В2 (дерево для них мы уже рисовали ранее). Из них Ваня переводит игру в 19 и гарантирует победу своим вторым ходом.
Число 30 относится к В1: Ваня удваивает его, получает 60 камней и выигрывает своим первым ходом.
Значит, после любого хода Пети у Вани есть победная стратегия не позднее второго хода.
Победа первым ходом не гарантирована. Петя может добавить 1 и оставить Ване 16 камней. Из 16 за один ход получаются только 17, 19 и 32 — все эти числа меньше 39.
Меньшие значения S не подходят. Если S ≤ 14, Петя может добавить 1 и оставить не более 15 камней. Такая позиция не относится ни к В1, ни к В2.
Ручной метод строится от конца игры к началу. Сначала мы отмечаем позиции с немедленной победой, а затем выясняем, какие позиции передают сопернику уже известный выигрышный или проигрышный уровень.
Перед решением выпишите игроков, начальное значение S, все допустимые ходы и условие окончания игры. Отдельно отметьте, увеличивается количество камней или уменьшается.
В1 означает победу текущего игрока за один ход. П1 означает, что любой ход отдаёт сопернику В1. В2 содержит хотя бы один ход в П1, а П2 всеми ходами передаёт сопернику В1 или В2.
В задании 19 обычно ищется позиция П1. В задании 20 нужны позиции В2. В задании 21 ищется П2, причём условие об отсутствии победы первым ходом требует хотя бы одной ветви в В2.
Всегда различайте слова «существует ход» и «при любом ходе». В первом случае достаточно одной подходящей ветви. Во втором нужно проверить все действия соперника.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
