О задании
В прошлой статье мы познакомились с зарождением теории игр и узнали, как она используется в реальной жизни. Но сейчас настало время для еще одного её применения — в заданиях 19-21 ЕГЭ по информатике!
Да, по большому счёту, из теории игр нам здесь понадобится только логика «предугадывания» стратегии вашего оппонента. Но всё же, чтобы понять суть наших дальнейших рассуждений, крайне рекомендуем ознакомиться с материалом, изложенным ранее.
Теперь же к заданию. Тут мы имеем необычное комбо: сразу три задания в одном. Дело в том, что решения 20 и 21 заданий целиком опираются на результаты, полученные в 19 задании.
Привнесём немного больше конкретики. В этих заданиях перед нами предстоит банальная игра: два парня — Петя и Ваня — кидаются камнями. Не друг в друга, а в абстрактную кучу. Суть игры проста — нужно набрать в этой куче определённое количество камней, используя заранее оговоренные ходы: добавить один камень, два камня, увеличить количество камней в N раз и так далее.
Сразу отметим, что именно по количеству куч и типизируются эти задания:
- К первому типу будем относить задания с одной кучей
- А ко второму — с двумя
Правда, что касаемо программного решения, то отличия будут не столько в самих кучах, сколько в одной интересной формулировке. Но это нас ждёт в следующих статьях. Сегодня посвятим себя ручному решению 19-21 заданий с одной кучей.
Алгоритм решения
Начнём мы разбор с абстрактной задачи, чтобы лучше понять каждый шаг решения. Представим: есть два игрока, всё те же Петя и Ваня, и есть куча камней. Изначально в ней находится некоторое количество камней.
У игроков есть две опции:
- Увеличить количество камней в куче на 2
- Увеличить количество камней на 5
И нам нужно будет рассмотреть несколько выигрышных стратегий. Начнём с простой, которая обычно используется в 19 задании: нужно найти исходное количество камней в куче, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
То есть нам нужна победа вторым ходом всей игры.
Погрузимся в роль Вани. Нам нужно кинуть камни так, чтобы в куче было 20 и более камней. Давайте думать, сколько должно быть камней до нашего хода, чтобы мы одержали победу.
Проще всего будет применить к минимальному необходимому для победы числу (20) обратные операции: -2 и -5. Получим два числа: 18 и 15.
То есть, если в куче осталось 15 камней и больше — победа у нас в кармане. Мы сразу кидаем 5 камней и оставляем нашего визави испытывать горечь поражения.
Распишем подробнее, для большего понимания:
- В куче 19 камней → добавляем 2 → 21 = победа
- В куче 18 камней → добавляем 2 → 20 = победа
- В куче 17 камней → добавляем 5 → 22 = победа
- В куче 16 камней → добавляем 5 → 21 = победа
- В куче 15 камней → добавляем 5 → 20 = победа
- В куче 14 камней → добавляем 5 → 19 = поражение
Итак, нам нужно, чтобы после своего хода Пётр оставил в куче не менее 15 камней. Какими способами он может получить такое число? Здесь снова применяем логику с обратными операциями:
Значит, если на начало игры в куче 13 или 10 камней, то Петя может получить из них 15. Но давайте рассуждать логически, зачем Пете подставляться?
Какой смысл при 10 камнях в куче делать из них 15 и дарить победу оппоненту?
А вот если в куче было 13 камней, то иных решений нет. Либо кидаем еще 2 камня, получаем 15, после чего Ваня вырывает победу своим броском 5 камней.
Либо кидаем аж 5 камней и 100% отдаём победу Ивану.
Видите логику? Как бы Петя не походил, если в куче 13 камней — это приговор. Любой ход ведёт к поражению, при правильной игре Вани.
Тогда можем дать ответ на вопрос, поставленный в условии: при 13 камнях в куче Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Для наглядности покажем все возможные ходы на рисунке.
То есть, как бы не походил Петя, Ваня выиграет в 3 из 4 случаев. Но важнее здесь другое: в каждой из веток (15 и 18) есть хотя бы один исход, ведущих к победе. Акцент здесь именно на «хотя бы один», поверьте, это позже найдёт своё отражение в программном решении.
Переходим к классической формулировке 20 задания:
«Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.»
Значит, настала очередь Петра побеждать. Победную стратегию для последнего игрока мы уже знаем: надо, чтобы в куче осталось не менее 15 камней. То есть теперь уже Ваня должен оставить нам 15 и более камней. Как-то так это будет выглядеть при самом пессимистичном сценарии (15 камней в куче после хода Вани):
У Пети все еще остаётся шанс победить, докинув 5 камней. Теперь нам нужно найти такую стратегию, чтобы Ваня своим ходом оставил Пете 15 камней.
Такое количество можно получить двумя способами:
- Из 10 камней, добавив 5
- Из 13 камней, добавив 2
Давайте будем благоразумными, Ваня ни за что не будет делать из 10 камней 15. Значит остаётся только один вариант: Пётр должен оставить ему именно 13 камней в куче.
Тогда стратегия такая:
- В куче S камней, из которых Петя своим первым ходом делает 13
- Из 13 Ваня может сделать либо 15 (+2), либо 18 (+5)
- Если Ваня оставил Пете 15 камней, то он добавляет еще 5 и выигрывает; если же Ваня поддался и оставил целых 18 камней, то Петя — победитель в любом случае
Дело за малым — найти два возможных значения для S. Не будем тянуть резину, минимальное число, из которого можно получить 13 — это 8 (8 + 5 = 13). В ответ просят два числа, значит, пишем 8 и следующее по возрастанию — 9.
Проверим наши ответы:
- В куче 8 камней → ход Пети +5 = 13 камней
- Ход Вани +2 = 15 камней (при ходе +5, получаем 18, всё равно победа Пети следующим ходом)
- Ход Пети +5 = 20 камней → победа
И второе число:
- В куче 9 камней → ход Пети +5 = 14 камней
- Ход Вани +2 = 16 камней (при ходе +5, получаем 19, всё равно победа Пети следующим ходом)
- Ход Пети +5 = 21 камней → победа
И снова выделим главное. Если в прошлой формулировке нам нужен был «хотя бы один» исход, то здесь требуется, чтобы любой (читай «все») ход оппонента привёл нас к победе.
То есть, как бы не походил Ваня, все его ходы принесут нам победу. А у Пети должен быть хотя бы один выигрышный ход (в каждой из веток).
Заключительное, 21 задание:
«Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Снова победителем должен стать Ваня. И теперь вы понимаете, почему эти три задания связаны. Ведь, как в прошлом задании мы продолжали строить дерево решений до восьмёрки, так и теперь будем еще сильнее его углублять.
Но уже без таких подробностей. Суть ясна:
- Победитель делает лучший для себя ход (приближающий его к победе)
- Проигравший должен делать худший для победителя ход (оттягивающий его поражение)
В прошлой задаче мы выяснили, что победная стратегия тянется от числа 8. При таком количестве камней можно победить нечётным ходом: Петя – 1, Ваня – 2, Петя – 3 (победил). Но в данной задаче нужно победить вторым ходом Вани, то есть чётным ходом всей партии:
- Петя
- Ваня
- Петя
- Ваня = победа
То есть, нужно, чтобы после первого хода Пети в куче осталось 8 или 9 камней. Пока остановимся на 8. Столько камней Петя может нам оставить ходом на +2 из числа 6. Давайте сначала это визуализируем:
Что мы тут видим? Если изначально было 6 камней, то Петя может оставить после себя либо 8, либо 11.
И Ваня, как грамотный стратег, из этих двух чисел в любом случае может получить 13. А дальше мы уже знаем по опыту прошлых задач, что при таком раскладе побеждает игрок через один ход после 13 камней в куче. Коим и является Ваня.
То есть суть хода Вани была как раз в том, чтобы из всех возможных вариантов выбрать именно число 13, после чего Пётр оказался обречён на поражение.
Пример 1
Теперь аналогичным образом решим реальное задание ЕГЭ. Формулировка будет такая:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
— убрать из кучи два камня;
— уменьшить количество камней в куче в два раза (количество камней при делении округляется до меньшего)
Игра завершается в тот момент, когда количество камней в куче становится не более 87.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 87 камней или меньше. В начальный момент в куче было S камней; S > 88.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Команды у нас следующие:
- Отнять 2
- Разделить на 2
Победа наступит, когда в куче будет 87 камней и меньше.
Да, теперь предстоит двигаться не на увеличение, а на уменьшение камней. Но сути это не меняет.
Здесь самой «ценной» операцией для победителя будет деление на 2, когда как для проигравшего — минус 2. То есть Пете не имеет смысла делить какое-то исходное число камней на 2, чтобы еще больше приблизить победу Вани.
По той же самой стратегии, что и ранее, мы применяем к нужному количеству камней в куче (87) инвертированную самую «ценную» операцию, то есть умножаем на 2, вместо деления. Получаем число 174. Это максимальное число камней в куче, которое должен оставить для нас Петя.
А Пётр же будет применять, наоборот, наименее ценную операцию, то есть «-2».
Значит, минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети, Ваня может выиграть своим первым ходом будет равняться 176. А стратегия будет выглядеть следующим образом:
Переходим к заданию 20. Всё по той же логике нужно, чтобы Ваня оставил для Пети 174 камня.
Теперь уже Петя оставляет Ване 176 камней. Но какой операцией? Логично, что наименее ценной, то есть «-2». Тогда изначально в куче должно находиться 178 камней.
Вторым числом для ответа возьмём 179:
И ответ на задание 20 будет таким: 178, 179.
Что же, осталась последняя часть. Что нам уже известно?
Есть рабочая стратегия победить, если мы оставляем сопернику 176 камней. Он либо отнимает 2, после чего мы делим количество камней вдвое и побеждаем. Либо оппонент сам делим 176 на 2, совершая глупость, после чего мы его наказываем поражением.
Чтобы оставить 176 камней мы можем либо отнять 2 от 178, либо поделить какое-то неважное для нас число на 2. Намёк понятен (мы ищем наименьшие числа по условию), Петя должен оставить нам ровно 178 камней в куче.
А наименьшее число, из которого можно получить 178 — 180.
Вот именно его мы и запишем в ответ.
Соберём все ответы в кучу:
19 задание — 176, 20 задание — 178 и 179, 21 задание — 180.
Пример 2
Для закрепления разберём решение еще одного задания:
«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может:
— добавить в кучу один камень;
— добавить в кучу три камня;
— увеличить количество камней в куче в два раза;
Игра завершается в тот момент, когда количество камней в куче становится не менее 39.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 39 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 38.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.»
Предстоит работать сразу с тремя операциями! Но ничего страшного. Давайте снова определим их «ценность». Самой ценной для победителя будет умножение на 2, для проигравшего — плюс 1.
Строим возможные пути получения 39 камней.
Нас интересует, конечно же, путь с наиболее ценной операцией. То есть, если противник оставит нам 20 и более камней, мы их с легкостью превратим в нечто большее, чем 39 в абсолютно любом случае.
Но, побудить Петю оставить нам 20 камней может только безвыходная ситуация. А именно — если в куче уже 19 камней. Тогда ему не остается ничего иного, как подкинуть еще один и смириться с поражением.
Для ясности, он, конечно, может походить любым другим способом, но ему от этого легче не будет. Ведь если в куче окажется 20 и более камней — победа в кармане у игрока, чей ход будет следующим.
Всю стратегию уже вырисовывать не будем, ответ на 19 задание — 19 камней.
Идём дальше. Теперь победить должен Петя. Следовательно, у Вани должны остаться эти несчастные 19 камней. Как Пётр должен этого добиться? Всё просто, изначально в куче должно быть 18, 16 или 10 камней.
Стратегии будут такие:
- В куче 18 камней → ход Пети +1 = 19 камней
- Ход Вани +1 = 20 камней (при остальных ходах, всё равно победа Пети следующим ходом)
- Ход Пети ×2 = 40 камней → победа
С 16 камнями будет аналогично:
- В куче 16 камней → ход Пети +3 = 19 камней
- Ход Вани +1 = 20 камней (при остальных ходах, всё равно победа Пети следующим ходом)
- Ход Пети ×2 = 40 камней → победа
А число 10 даже не имеет смысла проверять, ведь в ответ нужно дать только 2 числа: 18 и 16.
И заключительная часть. Снова обойдёмся без рисунков. Логика здесь будет такая же. Ваня должен свести количество камней в свою пользу: либо 18, либо 16. В таком случае в двух рассмотренных выше стратегиях Ваня просто займёт место Пети.
Вы уже могли уловить некую связь между числами 18, 16 и командами +3 и +1. Да, это наводит на мысль, что изначально в куче должно быть 15 камней. Тогда:
Вариант 1:
- Ход Пети +1 = 16 камней
- Ход Вани +3 = 19 камней
- Ход Пети +1 = 20 камней (при остальных ходах, всё равно победа Вани следующим ходом)
- Ход Вани ×2 = 40 камней → победа
Вариант 2:
- Ход Пети +3 = 18 камней
- Ход Вани +1 = 19 камней
- Ход Пети +1 = 20 камней (при остальных ходах, всё равно победа Вани следующим ходом)
- Ход Вани ×2 = 40 камней → победа
Итоги
В заключение выведем шаблонный алгоритм ручного решения 19-21 заданий с одной кучей.
Подготовка. Находим наиболее и наименее ценные операции.
- Самая ценная (для победителя) — операция, которая быстрее всего приближает к победе (умножение на 2, деление на 2, прибавление наибольшего числа и т.д.).
- Наименее ценная (ход проигравшего / «упрямый» ход) — операция, которая меньше всего приближает к победе (±1, ±2 и т.п.). Именно этот ход будет делать проигрывающий игрок, чтобы максимально оттянуть своё поражение.
Цель победителя: сделать так, чтобы сумма стала больше или равна пороговому значению.
Цель проигрывающего: как можно дольше не давать сумме достичь порогового значения.
Пороговое значение — то количество камней, которое приносит победу.
Задание 19: Ваня выигрывает после «неудачного» хода Пети
Нам нужно найти такое S, при котором у Пети есть хотя бы один ход, подставляющий его под удар Вани.
- Берем пороговое значение (например, 39).
- Применяем к нему обратную наиболее ценную операцию. Пример: 39 / 2 = 19,5. Значит, если в куче 20 и более — это зона победы за один ход.
- Чтобы Петя «подставился», он должен из своего числа S попасть в эту зону (в 20+).
- Применяем к числу 20 обратную наименее ценную операцию. Пример: 20 — 1 = 19.
- Ответ: 19 (Петя делает «+1», получает 20, Ваня бьет «×2» и побеждает).
Задание 20: Петя выигрывает своим 2-м ходом
Петя должен первым ходом сделать так, чтобы Ваня оказался в безвыходном положении (в точке из задания 19).
- Берем ответ из Задания 19 (например, 19, но далее обозначим его за S19) — это «проигрышная ловушка» (кто оставляет сопернику эту позицию — тот побеждает через один ход).
- Теперь Петя должен своим первым ходом загнать Ваню в эту ловушку, т.е. оставить после своего хода ровно S19 камней.
- Применяем к нему все обратные операции, которые есть в задаче. Пример (ход +1, +3, ×2):
19 — 1 = 18
19 — 3 = 16
19 / 2 = 10 - Отбросим те значения, из которых Петя мог бы вместо ловушки сделать что-то другое и проиграть (то есть оставим только те, из которых единственный разумный путь — попасть в S19, или из которых любой ход Вани после S19 всё равно ведёт к победе Пети).
- Ответ: числа 18 и 16.
Лучше всего будет сделать проверку для каждого найденного числа:
- Петя не выигрывает за один ход.
- Петя делает ход → попадает в S19.
- Любой ход Вани из S19→ Петя побеждает (для каждой ветки Вани у Пети есть хотя бы один выигрышный ход).
Задание 21: Победа Вани вторым ходом
Ваня должен сделать так, чтобы любой ход Пети привел его в «ловушку» из Задания 20.
- Из задания 20 мы знаем два значения (назовём их S20), при которых побеждает игрок, делающий первый ход. Теперь Ваня должен занять позицию этого «первого игрока», а значит Петя должен оставить Ване одно из этих значений.
- Нужно найти такое количество камней, из которого любой ход Пети оставляет Ване позицию из S20 или другую выигрышную позицию из зоны победы за один ход
- Чаще всего можно к меньшему из значений S20 применить обратную наименее ценную операцию. Пример: S20 = {16, 18}. Применяем операцию: 16 − 1 = 15. Проверяем: 15 + 1 = 16, 15 + 3 = 18 — оба попадают в выигрышные позиции.
Обязательно сделайте проверку:
- При найденном значении (назовём его S21) у Вани нет гарантированной победы первым ходом (т.е. не выполняется условие задания 19).
- Любой ход Пети из S21 ведёт в позицию, из которой Ваня побеждает (первым или вторым ходом).
Ответом на 21 задание будет наименьшее такое число S21.
И некоторые универсальные принципы ручного решения заданий 19-21:
- Победитель выбирает самую ценную операцию (максимально приближающую к победе).
- Проигравший выбирает наименее ценную операцию (максимально оттягивающую поражение).
- На каждом уровне дерева решений: у активного стратега (того, кто должен победить) достаточно хотя бы одного выигрышного хода; у противника должны проигрывать все ходы.
- Двигаемся от победы назад: применяем обратные операции, чередуя «ценные» и «дешёвые» в зависимости от того, чей ход рассматриваем.
На этом мы закончим с ручным методом. А в следующей статье мы рассмотрим уже программный метод решения этих заданий.
<<< Предыдущая статья Следующая статья >>>