Алгоритм решения заданий 19-21 ЕГЭ по информатике

Навигация по странице

О задании

Задания 19-21 ЕГЭ по информатике посвящены теории игр и анализу стратегий в логических играх. Эти три задания всегда рассматриваются вместе ввиду того, что само описание игры формулируется в 19 задании, а в двух оставшихся – 20 и 21 – содержатся лишь дополнительные вопросы к 19 заданию.

Суть задания заключается в следующем: есть два игрока – Петя и Ваня, которые добавляют в одну или две кучи определённое количество камней. Победителем в такой игре становится тот, на чьем ходу количество камней превысит заданное количество.

Нам же необходимо определить, при каком изначальном количестве камней в куче может победить тот или иной игрок. Таким образом, все эти задания требуют умения анализировать ходы игры, строить деревья возможных ходов и определять выигрышные стратегии.

В этой статье мы познакомимся с понятием «теория игр», рассмотрим некоторые концепции из теории игр, на примерах из жизни разберёмся, как добиваться выигрышной стратегии, и выведем алгоритм решения задания 19-21 программным методом.

Теория игр

Часть материалов для данной статьи взята из лекций российского математика, д.ф.-м.н. и кандидата экономических наук Алексея Савватеева. Рекомендуем ознакомиться с его работами.

Теория игр – это раздел математики, изучающий модели принятия оптимальных решений в условиях конфликта интересов. Эта дисциплина анализирует взаимодействие сторон, каждая из которых стремится максимизировать свой выигрыш, учитывая возможные действия других участников.

Истоки теории игр можно проследить с начала XX века, хотя некоторые идеи высказывались ещё в XVIII-XIX веках. Первые математические исследования оптимальных стратегий в играх были проведены французским математиком Эмилем Борелем в 1920-х годах. Однако настоящий прорыв в этой области произошёл благодаря работам Джона фон Неймана.

Вклад фон Неймана и Моргенштерна

В 1928 году фон Нейман опубликовал статью, в которой доказал фундаментальную теорему о минимаксе для антагонистических игр с нулевой суммой. Эта теорема утверждает, что в таких играх всегда существует оптимальная стратегия для обоих игроков, причём значение игры одинаково, независимо от того, кто делает ход первым.

Игра с нулевой суммой – это такая игра, в которой выигрыш одной стороны точно уравновешивается проигрышем другой. Яркий пример такой ситуации представлен в фильме «Уолл-стрит» 1987 года.

В этом фильме главный герой, Гордон Гекко, занимается биржевыми спекуляциями. Его стратегия часто строится на том, чтобы выиграть за счёт проигрыша других. Например, когда Гекко скупает акции компании, чтобы затем продать их по более высокой цене, его выигрыш напрямую связан с потерями других инвесторов или самой компании. Это классический пример игры с нулевой суммой: выигрыш одного участника (Гекко) равен проигрышу другого (других инвесторов или компании).

Противоположностью игре с нулевой суммой является стратегия игры «выигрыш-выигрыш» (win-win). При такой стратегии участники работают вместе, чтобы достичь максимального результата. То есть по окончании игры обе стороны останутся в выигрыше.

Зачастую такая стратегия применяется при переговорах в бизнесе. Представьте, что две компании конкурируют на одном рынке. Вместо того чтобы снижать цены и вредить друг другу (что характерно для игры с нулевой суммой), они могут договориться о сотрудничестве.

Например, если вы специализируетесь на производстве какого-нибудь товара, а ваш партнёр – на маркетинге и продажах, то вам будет выгоднее не конкурировать, а объединить усилия. Такой подход поможет увеличить общую прибыль, что будет выгодно обеим сторонам. В этом и заключается win-win стратегия.

Но мы отвлеклись от нашего повествования. Вернёмся к истории становления теории игр.

В 1944 году Джон фон Нейман в соавторстве с экономистом Оскаром Моргенштерном опубликовал монографию «Теория игр и экономическое поведение». Эта книга считается фундаментальным трудом, заложившим основы математической теории игр.

В ней авторы впервые представили математический аппарат для анализа стратегического взаимодействия между рациональными игроками. Фон Нейман и Моргенштерн сосредоточились на изучении игр с нулевой суммой, где выигрыш одного игрока равен проигрышу другого, и ввели концепцию минимаксной стратегии, которая позволяет игроку минимизировать максимальный возможный проигрыш.

Книга также предложила новый подход к моделированию экономических процессов, рассматривая их как игры, где участники стремятся максимизировать свою выгоду. Это позволило применять теорию игр не только в математике, но и в экономике, политологии и других социальных науках.

Концепция равновесия Джона Нэша

Новый виток развития теория игра получила благодаря работам американского математика Джона Нэша. Возможно, вы знаете о нём из книги Сильвии Назар «Игры разума» (англ. «A Beautiful Mind. The Life of Mathematical Genius and Nobel Laureate John Nash») или одноимённого фильма Рона Ховарда с Расселом Кроу в главной роли.

Еще в студенчестве теория игр заинтересовала гениального математика. В 21 год, учась в Принстонском университете, Нэш написал диссертацию о теории игр, за которую спустя 45 лет получил Нобелевскую премию по экономике «за фундаментальный анализ равновесия в теории некооперативных игр».

В 1950-53 годах учёный погрузился в изучение игр с ненулевой суммой. По этой теме он опубликовал четыре революционные работы, на основе которых впоследствии вывел одну из ключевых концепций в теории игр – концепцию равновесия, которая впоследствии стала называться его именем.

Равновесие Нэша – это набор стратегий, при котором ни один из участников не может улучшить свой результат, односторонне изменив свою стратегию, если стратегии других участников остаются неизменными.

Нэш пришёл к этой концепции, изучая ситуации, где интересы игроков не обязательно прямо противоположны (как в играх с нулевой суммой). Он доказал, что в любой игре с конечным числом игроков и конечным числом стратегий существует хотя бы одно равновесие (возможно, в смешанных стратегиях).

К этой идее Нэш пришёл, размышляя над тем, что можно считать «рациональным» поведением участников, если каждый из них действует независимо и в собственных интересах. Его концепция описывает точку стабильности, своеобразного «ментального соглашения» между участниками.

Давайте подробнее разберём эту концепцию на практике. В фильме, о котором мы говорили выше, вы найдёте описание того, как Джон Нэш пришёл к этой концепции. Мы же этот эпизод рассматривать не будем, дабы не испортить впечатление тем, кто еще не ознакомился с этим произведением.

Поэтому разберём не менее классический пример на равновесие Нэша – дилемму заключённого. Представим, что есть два человека, которые совершили какое-то преступление. Их поймали, но весомых улик против них нет. Поэтому если ни один из заключённых не признается, то им предъявят менее тяжёлое обвинение и отпустят на свободу раньше.

Заключённых разводят по разным камерам и объявляют правила игры:

Если ты дашь показания против своего подельника, то он получит 10 лет, а тебя отпустят на свободу
Если оба признаются и дадут показания против друг друга, то оба получат по 3 года.
Если оба будут хранить молчание, то выйдут на свободу уже через год.

Можно составить такую таблицу с результатами выбора каждого заключённого.

Здесь числа в скобках показывают время заключения первого и второго обвиняемого. Слева выборы первого, справа – второго обвиняемого.

Как бы вы поступили в такой ситуации?

Логично предположить, что самым выгодным способом для обоих обвиняемых будет хранить молчание. Чистейшая win-win ситуация, оба выйдут всего через год.

Но на деле такой выбор совершают крайне редко. Можем убедиться, что стратегия «дать показания» доминирующая: наш обвиняемый либо садится на 3 года, либо выходит на свободу.

Если же он будет отпираться, то в зависимости от его компаньона, можно получить либо 10 лет заключения, либо год.

То есть вне зависимости от того, как будет действовать сообщник, заключённому лучше будет признать вину. Даже если стратегия «хранить молчание» была бы выгодна для обоих игроков, каждый из них, действуя в своих интересах, предпочтёт сдать другого.

Это приводит к парадоксу: рациональные действия отдельных игроков приводят к нерациональному исходу для группы в целом.

Следовательно, выбор стратегии «дать показания» приведёт к некоторому паритетному варианту для обоих: оба не в выигрыше, но и не проиграли. В этом и заключается равновесие Нэша: ни один из игроков не может улучшить свой результат, изменив стратегию, если другой игрок сохраняет свою.

Дилемма заключённого находит применение во многих областях науки. Например, она может использоваться в экономике, где фирмы устанавливают цены на конкурентных рынках, в биологии для понимания эволюционных стратегий животных (см. «Ястребы и голуби») и в политологии.

В политологии особо ярким примером дилеммы заключённого является политика ядерного сдерживания. Так, сама доктрина США по ядерному сдерживанию как раз и появилась в результате исследований Джона Нэша и Томаса Шеллинга в области теории игр.

Рассматривая концепцию равновесия Нэша, нельзя не привести в пример модель олигополии Курно. Это экономическая модель, предложенная французским математиком и экономистом Огюстеном Курно в 1838 году. Она описывает поведение фирм на рынке, где доминирует небольшое количество производителей (это и называется олигополией).

В модели Курно фирмы решают, какой объём продукции производить, зная, что прибыль зависит и от решений конкурентов. В этой модели равновесие достигается, когда каждая фирма выбирает оптимальный объём производства, учитывая объёмы производства других фирм, и ни одна из них не может увеличить свою прибыль, изменив свой объём производства при условии, что другие фирмы сохраняют свои объёмы неизменными. Это и есть равновесие Нэша.

Теория игр в повседневной жизни

Несмотря на все абстрактные модели и математический характер, теория игр имеет прямое отношение к повседневным ситуациям в нашей жизни. Методы оптимального принятия решений в условиях взаимодействия с другими людьми пронизывают практически все сферы деятельности человека.

Например, рассмотрим такую ситуацию: на одном районе находятся два магазина. Они оба вовлечены в игру, где каждый пытается привлечь покупателей. Если в такой ситуации один магазин неожиданно начинает занижать цены (это еще называется демпинг цен), то второй магазин вынужден следовать этой стратегии, чтобы не потерять клиентов.

Результатом таких действий может стать ценовая война, невыгодная не одному из продавцов. Равновесие Нэша в такой ситуации часто достигается путем неявного соглашения держать цены на определенном уровне, что мы можем наблюдать, например, на рынке бензина, где цены на соседних заправках редко существенно различаются.

В семейных отношениях теория игр также может найти своё применение. Например, есть семейная пара Алисы и Боба. Они каждые выходные устраивают киновечера.

Алисе нравятся драмы, а Бобу комедии. Но оба они согласны смотреть документальные фильмы, хоть и не особо любят этот жанр. Естественно, выбрать фильм на вечер – та еще задача, неудачное решение которой может привести к печальным последствиям.

В таком случае, если Алиса с Бобом – рациональные люди, то единственный выбор у них – смотреть документальный фильм. Именно этот компромиссный вариант они выберут, исходя из понимания, что другая сторона выберет то же самое. Это не лучший исход для каждого из них, но наиболее оптимальный, исходя из концепции равновесия Нэша.

В сфере образования мы часто можем наблюдать ситуации, когда студенты должны выбрать, сколько времени они могут уделить подготовке к экзамену. Каждый студент стремится получить высокую оценку, но также ценит свободное время.

Если оценка выставляется по кривой (то есть относительно результатов других студентов, а не абсолютной шкалы), то формируется игра, где результат каждого напрямую зависит от усилий всех.

Часто в таких ситуациях студенты тратят на подготовку больше времени, чем было бы оптимально при абсолютной шкале оценок, поскольку каждый опасается, что другие будут учиться усерднее.

Алгоритм решения

Теперь вернёмся к рассматриваемым заданиям 19-21 ЕГЭ по информатике. Все прототипы этого задания имеют один шаблон. Для начала вспомним, как формулируется 19 задание: есть два игрока Петя и Ваня и есть одна или две кучи. Ходят они по очереди: сначала Петя (первый), затем – Ваня (второй).

В эту кучу добавляются (а иногда убавляются) камни в разном количестве, пока размер кучи не достигнет определённого значения.

В 19 задании требуется определить изначальное количество камней в куче, при котором Петя не может выиграть своим первым ходом, а Ваня может.

В задании 20 на основе этих данных нам нужно рассмотреть уже другую ситуацию: Петя не может выиграть своим первым ходом, но может выиграть вторым, независимо от того, как походит Ваня.

В задании 21 же требуется, чтобы Ваня выиграл либо своим первым ходом, либо вторым.

То есть сначала нужно определить, что победа будет во второй ход (ход Вани) затем, что победа будет в третий (второй ход Пети), а в конце найти победу во втором или четвёртом ходе.

Мы здесь акцентируем внимание именно на порядке ходов: чётный, нечётный, чётный (второй) или чётный (четвёртый). Это найдёт своё отражение в программном методе решения заданий.

Далее мы будем оперировать некоторыми терминами, которые используются как в формулировках задания, так и в теории игр в целом. Давайте познакомимся с ними.

Первым здесь будет термин «стратегия игрока». Он означает некий набор правил или алгоритмов, которые определяют действия игрока в зависимости от текущей ситуации в игре. Стратегия может быть как простой (например, всегда выбирать одно и то же действие), так и сложной (учитывать предыдущие ходы и возможные реакции противника).

Далее идет «выигрышная стратегия». Выигрышной будет называться такая стратегия игрока, которая гарантирует ему победу или достижение наилучшего возможного результата независимо от действий противника. Если игрок следует выигрышной стратегии, он всегда выиграет при условии, что не допустит ошибок.

А показывать все возможные решения, которые могут принять наши игроки, мы будем на дереве решений. Это графическое представление всех возможных последовательностей ходов в игре, начиная с начальной позиции и заканчивая всеми возможными исходами.

Каждая ветвь дерева соответствует одному из возможных ходов, а листья дерева представляют конечные состояния игры (выигрыш, проигрыш или ничью).

Теперь, зная все термины, можем смело приступать к разбору решения данных заданий. Сразу отметим, что существует всего 2 типа заданий 19-21. Они отличаются количеством куч камней: одна куча или две кучи.

Начнём наш разбор с первого типа, в котором игроки используют только одну кучу камней.

Тип 1

Задания первого типа можно решать вручную, анализируя возможные ходы игроков. Давайте рассмотрим такую формулировку:

Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 20 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 19.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом»

Итак, на месте Вани у нас есть два варианта получить минимальное число камней, при котором будет засчитана его победа. Это либо 10 камней удвоить, либо к 19 камням добавить еще 1.

Естественно, рассматривать вариант с прибавлением одного камня мы не будем – в этом нет смысла. При любом числе камней большем 10 можно просто удвоить их количество и праздновать победу.

Хорошо, нам нужно, чтобы на ходе Вани было 10 камней в куче. Значит, Петя должен получить это число также двумя путями: добавить один камень к 9 или удвоить 5 камней.

Но Петя-то у нас не дурак и, если в куче будет всего 5 камней, он просто добавит туда 1, зачем же ему умножать на 2 и дарить победу оппоненту? А в случае, если игра начинается с 9 камней, выхода у Пети нет – придётся терпеть поражение, как бы он не походил.

А давайте смоделируем такую ситуацию и покажем её на дереве решений. Представим, что изначально в куче 9 камней. Первым ходит Пётр:

Если он добавит один камень, то получится 10, если удвоит количество камней в куче, то получит аж 18 камней.

Далее ход за Иваном:

И мы видим, что проиграть Ваня может только в двух случаях из четырёх, и то, если специально подставится.

Какой вывод можно сделать из этого? Для победы Вани необходимо, чтобы все ходы Пети вели к «победным значениям» (здесь это любые числа, большие 10), а также для победы Вани достаточно хотя бы одного исхода для каждого из ходов Пети, который приведёт к победе.

Да, звучит очевидно, но здесь акцент сделан на слова «все ходы Пети» и «хотя бы один исход Вани», опять же, чтобы решение кодом было понятнее (помните же, что в Python есть операции all() и any() с таким же смыслом, как и в этих высказываниях?).

Теперь перейдём на реальные задания ЕГЭ, где нам предстоит анализировать игру не на одну выигрышную стратегию, как здесь, а на все 3, если хотим верно решить каждое из заданий 19-21.

Рассмотрим такую формулировку:

Задание 1900

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится не менее 51. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 51 камней или больше. В начальный момент в куче было S камней; 1 ≤ S ≤ 50.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом

Задание 20.

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.

Задание 21.

Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них»

Да, формулировки этих заданий обширные, но не стоит пугаться – они всегда типовые. Здесь нужно уяснить следующее:

Победа достигается при количестве камней в куче от 51 включительно
Есть три операции: +1, +4 и х2

Давайте строить дерево решений. В число 51, используя операции +1, +2 и х2, можно попасть из трёх других чисел: 50, 47 и 26 (тут, правда, получим 52, но это нас все равно устроит).

Минимальное подходящее нам число – это 26. Значит, нам нужно, чтобы именно такое количество камней осталось в куче после первого хода Пети. Давайте подумаем, как можно «заставить» Петю оставить после себя в куче 26 камней.

Также имеем три пути: из чисел 25, 22 и 13.

И единственное число, которое точно приведёт к гарантированной победе Вани – это 25.

Ведь если в начальный момент в куче 25 камней, у Петра имеются три опции:

Добавить один камень (победа Вани, по рассмотренной выше стратегии)
Добавить 4 камня (получаем число 29, которое Ваня удваивает и забирает победу)
Умножить количество камней на 2 (тут сразу получаем кучу из 50 камней, в которую Ваня может вальяжно кинуть всего один камень и выиграть)

Следовательно, мы получаем ответ на 19 задание – 25.

Теперь переходим к 20 заданию. В этом случае мы болеем за Петю. Но мы уже знаем выигрышную стратегию 25 → 26 → 51. Только теперь надо, чтобы куча в 26 камней досталась не Ивану, а Петру.

Следовательно, 25 камней должно быть перед ходом Вани, тогда у него будет только один путь – кинуть один камень и смириться с поражением.

Итак, из каких чисел мы можем гарантированно получить 25? Тут опции всего две: либо 21, либо 24.

Тогда в первом случае мы добавляем в кучу 4 камня и следуем уже проверенной стратегии, во втором же случае можем добавить всего один камень, и дальше опять все будет складываться по запланированной стратегии.

Записываем ответ на 20 задание: 21, 24.

Осталось найти минимальное количество камней в куче, при котором Ваня может выиграть своим первым или вторым ходом.

Опять же, основываясь на уже рассмотренных стратегиях, можем утверждать, что для того, чтобы Ваня выиграл вторым ходом (с числа 26), нужно чтобы он оставил Пете 25 камней, а Петя ему – 24 или 21.

Тогда нам остаётся определить, с какого числа мы можем гарантированно получить числа 21, 24 или число, большее 26.

Для этого нужно рассмотреть, из каких чисел получаются 24 и 21 и найти среди них одно общее число.

Как видим, в нашем случае таким числом является 20. То есть имея 20 камней в куче, Петя может получить:

Число 21. Тогда Ваня добавляет 4 камня, получая 25. Любой ход Пети приводит к победе Вани: в куче остаётся 26, 29 или 50 камней (Ваня умножает на 2 и побеждает)
Число 24. Стратегия аналогична пункту 1, только Ваня может добавить только 1 камень (другие операции приведут к проигрышу).
Число 40. Здесь Ваня побеждает своим первым ходом, просто удваивая количество камней.

В итоге получаем ответ на 21 задание: 20.

Давайте теперь для этого же задания составим программное решение. В основе нашего подхода будет лежать рекурсивная функция, вычисляющая значения на каждом ходе игроков.

Назовём функцию f(), принимать она будет два аргумента: s – количество камней в куче и m – количество ходов (moves).

Для начала будем проверять, что достигнуто требуемое значение количества камней в куче (51 и больше). Если это так, то проверяем, что ход чётный (2 или 4).

def f(s, m):
    if s >= 51:
        return m % 2 == 0

Далее идёт условие, которое проверяет, что все возможные ходы исчерпаны:

    if m == 0:
        return False

Теперь сформируем список h, в который передадим все возможные операции с камнями в таком виде:

Элемент списка – это возвращаемое значение от вызова функции с текущей операцией и уменьшением шага на 1.

Здесь, соответственно, будет три вызова функции с операциями: +1, +4 и х2.

h = [f(s + 1, m - 1),
     f(s + 4, m - 1),
     f(s * 2, m - 1)]

И переходим к возврату значения из функции. Вспоминаем, что мы говорили в начале разбора алгоритма про «все ходы Пети» и «хотя бы один исход Вани». Если у нас ход чётный (Вани), то нам нужно, чтобы хотя бы одна функция вернула истину, в противном случае (для ходов Пети) – все функции должны вернуть истину.

Выглядит это так:

return any(h) if (m + 1) % 2 == 0 else all(h)

Вся функция выглядит следующим образом:

def f(s, m):
    if s >= 51:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(s + 1, m - 1),
         f(s + 4, m - 1),
         f(s * 2, m - 1)]
    return any(h) if (m + 1) % 2 == 0 else all(h)

Давайте подробнее разберём строку с возвратом значения. Вызовем эту функцию с аргументами 25 и 2: то есть будем проверять, можно ли выиграть за 2 хода, если начать со значения 25.

Функция нам вернёт True, это мы и так знаем. Но давайте визуализируем каждый её вызов (например, здесь):

То есть что нужно, чтобы функция вернула истину? Нужно, чтобы на нечётном ходу (первом, где числа 26, 29 и 50) все исходы удовлетворяли победной стратегии.

Сначала у нас m = 2, вычисляются числа 26, 29 и 50 условие (m+1) %2 == 0 ложно, значит, все значения, возвращенные от вызовов функции f() должны быть истинны (all(h)).

А на втором ходе (m=1) должен быть хотя бы один победный исход (any(h)) в каждом из предыдущих ходов.

Таким образом, мы проверяем, что последний ход чётный (второй ход всей игры или первый ход Вани), в этом ходе нам нужно хотя бы одно истинное значение, которое будет означать, что мы дошли до нужного числа и победили.

Но получить такой исход мы можем только в том случае, если функция, проверяющая любой ход нашего противника, возвращает истинное значение.

То есть любой его ход, приводящий к числам 26, 29 или 50, должен привести к хотя бы одному нашему победному ходу:

Числу 52 из 26
Числу 58 из 29
Числам 51, 54 или 100 из числа 50

Вручную подставлять в функцию все возможные исходные значения мы не будем. Составим для этой цели списочное включение, в котором будем передавать в функцию числа от 1 до 51:

print('19:', *[s for s in range(1, 51) if f(s, 2)])

И получаем ответ на 19 задание – 25.

Аналогично получаем ответ на два других задания:

print('20:', *[s for s in range(1, 51) if f(s, 3) and not f(s, 1)])
print('21:', min([s for s in range(1, 51) if f(s, 4) and not f(s, 2)]))

Также перебираем все возможные значения, но для 20 задания требуем, чтобы победа была достигнута на третьем ходе, но не на первом.

Для 21 победа должна быть на четвёртом ходе, но не на втором.

Весь код для решения этого задания будет следующий:

def f(s, m):
    if s >= 51:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(s + 1, m - 1), 
         f(s + 4, m - 1), 
         f(s * 2, m - 1)]
    return any(h) if (m + 1) % 2 == 0 else all(h)


print('19:', *[s for s in range(1, 51) if f(s, 2)])
print('20:', *[s for s in range(1, 51) if f(s, 3) and not f(s, 1)])
print('21:', min([s for s in range(1, 51) if f(s, 4) and not f(s, 2)]))

Пример 1

Формулировка будет следующая:

Задание 1902

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи два или пять камней либо уменьшить количество камней в куче в три раза (количество камней, полученное при делении, округляется до меньшего). Например, из кучи в 20 камней за один ход можно получить кучу из 18, 15 или 6 камней. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится не более 19. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 19 камней или меньше. В начальный момент в куче было S камней; S ≥ 20.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом

Задание 20.

Задание 21.

Теперь игроки каждым ходом убавляют количество камней в куче. Также выделим основные моменты из условия:

Победа достигается при количестве камней в куче до 19 включительно
Есть три операции: -2, -5 и //3

Решать сразу будем программным методом. В коде отличий будет немного:

В первом условии будем требовать, чтобы количество камней s было меньше или равно 19
Диапазон для s установим от 20 и до 100, например.

Тогда весь код для решения этого задания будет такой:

def f(s, m):
    if s <= 19:
        return m % 2 == 0

    if m == 0:
        return False

    h = [f(s - 2, m - 1), 
         f(s - 5, m - 1), 
         f(s // 3, m - 1)]
    return any(h) if (m + 1) % 2 == 0 else all(h)


print('19:', min([s for s in range(20, 100) if f(s, 2)]))
print('20:', *[s for s in range(20, 100) if f(s, 3) and not f(s, 1)])
print('21:', *[s for s in range(20, 100) if f(s, 4) and not f(s, 2)])

>>>19: 60
>>>20: 62 63 65 66
>>>21: 64 67 68

Из этих значения формируем ответы на 19, 20 и 21 задания: 60, 62 и 63, 64.

Тип 2

Сразу начнём с формулировки:

Задание 1901

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 81 камень или больше.
В начальный момент в первой куче было 7 камней, во второй куче — S камней; 1 ≤ S ≤ 73.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Задание 20.

Задание 21.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них»

Что необычного вы заметили в этой формулировке по сравнению с предыдущими двумя? Конечно, помимо слов про две кучи камней.

Обратить внимание здесь следует на это предложение: «Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети». Что это означает?

Во-первых, что Петя не умеет играть в эту замечательную игру, а во-вторых, что мы теперь точно знаем, что ход Пети неудачный для него, но удачный для нас.

То есть нам больше не нужно проверять, что победа Вани существует во всех возможных ходах, она уже существует хотя бы в одном из них. Значит, для 19 задания с двумя кучами мы можем вовсе избавиться от функции all().

Давайте напишем функцию для решения этого задания:

def f(s_1, s_2, m):
    if s_1 + s_2 >= 81:
        return m % 2 == 0

    if m == 0:
        return False

    h = [f(s_1 + 1, s_2, m - 1),
         f(s_1, s_2 + 1, m - 1),
         f(s_1 * 2, s_2, m - 1),
         f(s_1, s_2 * 2, m - 1)]

    return any(h)

В ней мало отличий от функции для решения заданий с одной кучей. Мы все так же проверяем, что количество камней больше или равно требуемому. Только теперь будем считать сумму камней в двух кучах.

Список с возможными операциями также поменяется: будем поочерёдно применять каждую операцию сначала к одной кучу, затем к другой.

В блоке кода с возвратом значения можем избавиться от проверки чётности хода и от функции all().

Теперь формируем списочное выражение, в котором в функцию f() будем передавать числа от 1 до 74. Обратите внимание, что в функции первым аргументом будет число 7 – количество камней в первой куче.

print('19:', min([s for s in range(1, 74) if f(7, s, 2)]))

После запуска программы мы увидим на экране ответ на 19 задание – число 19.

Но теперь, для решения заданий 20-21 нам предстоит вернуть на место блок кода с возвратом значения:

if (m + 1) % 2 == 0:
    return any(h)
else:
    return all(h)

Больше функцию f() не меняем. В конце по уже отработанной схеме выводим ответы на 20 и 21 задания.

print('20:', *[s for s in range(1, 74) if f(7, s, 3) and not f(7, s, 1)])

print('21:', min([s for s in range(1, 74) if f(7, s, 4) and not f(7, s, 2)]))

Полный код для решения этого задания будет следующим (часть кода для решения именно 19 задания закомментирована):

def f(s_1, s_2, m):
    if s_1 + s_2 >= 81:
        return m % 2 == 0

    if m == 0:
        return False

    h = [f(s_1 + 1, s_2, m - 1), 
         f(s_1, s_2 + 1, m - 1), 
         f(s_1 * 2, s_2, m - 1),
         f(s_1, s_2 * 2, m - 1)]

    # Для 19
    # return any(h)

    if (m + 1) % 2 == 0:
        return any(h)
    else:
        return all(h)


# print('19:', min([s for s in range(1, 74) if f(7, s, 2)]))

print('20:', *[s for s in range(1, 74) if f(7, s, 3) and not f(7, s, 1)])

print('21:', min([s for s in range(1, 74) if f(7, s, 4) and not f(7, s, 2)]))

Ответами на задания 19-21 будут следующие числа: 19, 33 и 36, 32.

Пример 2

Формулировка в этот раз будет такой:

Задание 1903

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество суммарное камней в кучах становится не менее 65. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах находится 65 камней или больше.
В начальный момент в первой куче было 6 камней, во второй куче — S камней; 1 ≤ S ≤ 58.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Задание 20.

Задание 21.

Выделим ключевые моменты:

Победа достигается при количестве камней в куче от 65 включительно
Есть две операции: +1 и х3

Подробно останавливаться на разборе кода уже не будем. Для 19 задания напишем следующую программу:

def f(s_1, s_2, m):
    if s_1 + s_2 >= 65:
        return m % 2 == 0

    if m == 0:
        return False

    h = [f(s_1 + 1, s_2, m - 1), 
         f(s_1, s_2 + 1, m - 1), 
         f(s_1 * 3, s_2, m - 1),
         f(s_1, s_2 * 3, m - 1)]

    return any(h)


print('19:', min([s for s in range(1, 59) if f(6, s, 2)]))

В ответе получаем число 7.

Для заданий 20-21 перепишем код следующим образом:

def f(s_1, s_2, m):
    if s_1 + s_2 >= 65:
        return m % 2 == 0

    if m == 0:
        return False

    h = [f(s_1 + 1, s_2, m - 1), 
         f(s_1, s_2 + 1, m - 1), 
         f(s_1 * 3, s_2, m - 1),
         f(s_1, s_2 * 3, m - 1)]

    if (m + 1) % 2 == 0:
        return any(h)
    else:
        return all(h)


print('20:', *[s for s in range(1, 59) if f(6, s, 3) and not f(6, s, 1)])

print('21:', min([s for s in range(1, 59) if f(6, s, 4) and not f(6, s, 2)]))

В результате получим числа 10 и 19, а также 18.