Теория игр (ЕГЭ Задания 19-21). Теория игр. Теория игр Что такое теория игр
 Скачать 3.18 Mb.
|
Теория игрЧто такое теория игр?Теория игр представляет из себя сложное многоаспектное понятие, поэтому представляется невозможным привести толкование теории игр, используя лишь одно определение Рассмотрим три подхода к определению теории игр1 Теория игр - математический метод изучения оптимальных стратегий в играх. 2 Теория игр - это раздел прикладной математики, точнее - исследования операций. 3 Одна из важнейших переменных, от которой зависит успех организации - конкурентоспособность. Конфликтная ситуация Конфликтной называется ситуация, в которой взаимодействует несколько сторон, и при этом каждый из участников старается достичь своей цели доступным ему способом, а результат взаимодействия зависит от действий каждого участника. Черты конфликтной ситуации: наличие заинтересованных сторон наличие своих интересов (целей) у каждой стороны наличие набора возможных действий у каждой из сторон часто недостаток информации (неопределенность) Примеры Покупатель и продавец Работник и работодатель Спортивные состязания Вооруженные конфликты Игроки – заинтересованные стороны в игре (участники игры) Парная игра – игра, в которой принимают участие два игрока Множественная игра – игра с числом участников более двух Коалиция – объединение игроков коалиции действия, коалиции интересов Стратегия – любое возможное действие (комплекс действий) игрока Ход – выбор действия игроками (личный ход *) Ситуация (исход игры) – состояние, в котором оказываются игроки после очередного хода 1 2 4 3 5 Основные понятия теории игр 6 7 Предполагается, что игра происходит по определенным правилам (без этого не возможна формализация задачи).Правила - система условий, которые описывают: 1 Возможные действия каждого из игроков 2 Объем информации, которую может получить каждая из сторон о возможных действиях противника 3 Исход (результат) игры после каждой совокупности «ходов» противника Цель теории игр – выработка рекомендаций для удовлетворительного поведения игроков в конфликте и выявления для каждого из них оптимальной стратегии.Оптимальная стратегия – такая стратегия, которая при многократном повторении игры гарантирует игроку максимальный возможный средний выигрыш (при условии неопределенности – не зависящий от поведения других участников). Выбор оптимальной стратегии базируется на принципе разумности каждого игрока, т.е. поведение каждого из них направлено на достижение своихЗамечания целей. Оптимальность опирается на некоторый критерий. Поэтому возможны случаи, когда стратегия является оптимальной в смысле одного критерия и не оптимальной в смысле другого. ТЕОРИЯ ИГР. ПОИСК ВЫИГРЫШНОЙ СТРАТЕГИИдля того чтобы найти выигрышную стратегию в несложных играх, достаточно использовать метод перебора всех возможных вариантов ходов игроков;Выигрышная стратегия для решения задач 26 задания чаще всего для этого применяется метод построения деревьев;если от каждого узла дерева отходят две ветви, т.е. возможные варианты хода, то такое дерево называется двоичным (если из каждой позиции есть три варианта продолжения, дерево будет троичным).Выигрышные и проигрышные позициивсе позиции в простых играх делятся на выигрышные и проигрышные; выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, обязательно выиграет при любых действиях соперника, если не допустит ошибки; при этом говорят, что у данного игрока есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть; если игрок, делающий первый ход, находится в проигрышной позиции, то он обязательно проиграет, если ошибку не сделает его оппонент; в этом случае говорят, что у данного игрока нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для оппонента; выигрышные и проигрышные позиции характеризуются так: позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная; позиция, из которой хотя бы один из последующих возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для оппонента) позицию. Кто выиграет при стратегически правильной игре?Для того чтобы определить, какой из игроков выиграет при стратегически правильной игре, необходимо ответить на вопросы: Может ли какой-либо из игроков выиграть, независимо от ходов других игроков? Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков? Игра: В кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; Условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку Решение: Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева: Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну: Если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:проанализируем стратегию игры: Если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока; Итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу; Тогда как второй игрок не может выиграть, независимо от действий первого: потому что, если первый игрок сначала убрал одну спичку, второй всегда проиграет. Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 59 или больше камней. В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 53 Задание 1 Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Задание 2 Найдите минимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Задание 3 Найдите два значения S, при которых одновременно выполняются два условия:
Найденные значения запишите в ответе в порядке возрастания. 1 Для начала найдем все выигрышные позиции для первой строки таблицы, т.е. для первого хода. Обозначим их плюсами (+):Выигрышные позиции для первой строки ищем по принципу увеличения количества камней S в 2 два раза: 5 + S*2 >=59. Получим S>=27 1 Для того, чтобы получить наименьшее значение S, в качестве первого хода Пети необходимо увеличивать в два раза вторую кучу. Т.е. для решения задания необходимо найти такое наименьшее S, при котором Петя походил неверно, и попал своим ходом в выигрышную позицию для своего соперника, т.е. в ячейку с плюсом: S = 14 1 ход Петя: 14*2 = (5,28) 2 ход Ваня: 28*2 = (5,56), Сумма = 61, Выигрыш! 1 Проанализируем таблицу, и для каждой строки найдем выигрышные позиции с одного хода. Т.е. которые позволят игроку, оказавшемуся «на них», выиграть за один ход (получить суммарно 59 и более камней):При заполнении таблицы выигрышными позициями можно проследить закономерность «узора», а заполнять позиции по аналогии. 2 Найдем проигрышные позиции: те, которые ведут только в выигрышные позиции для соперника (ведут только в плюсы)Проигрышные позиции: (6,26) (8,25) (10,24) (12,23) (14,22) 2 В задании требуется найти минимальное S, котором выиграет Петя, но выиграет он НЕ первым своим ходом, а вторым. То есть в нашем случае необходимо найти S, которое может перевести соперника в проигрышную позицию. То есть в минус. Для первой строки (так как первым будет ходить Петя) таких значений два: Наименьшее S = 24 2 Для решения этого задания найдем выигрышные позиции со второго хода, т.е. которые могут перевести соперника в проигрышную позицию (с минусом):3 Чтобы выиграл Ваня, но выиграл не первым ходом, а вторым, необходимо, чтобы Петя находился в такой позиции, которая ведет его только на выигрышные позиции со второго хода:Ответ: 23 25 3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 47 Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 47. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней; 1 меньше или равно S меньше или равно 47. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Найдите минимальное значение S, при котором одновременно выполняются два условия:
Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 31 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 30. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы. Задание № 1 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня или добавить в кучу 3 камня или увеличить количество камней в куче в два раза. Например, имея кучу из 8 камней, за один ход можно получить кучу из 10, 11, 16 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 51. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 51 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 50. При каких минимальных значениях числа S Петя может выиграть первым ходом ? Задание № 1. Решение Распишем при каких значениях S первый игрок может выиграть сразу за один ход. В ответ мы выберем значение 26, потому что оно самое маленькое. Ответ: 26 ЕГЭ по информатике. Задание №19 - 21 Задание № 2 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 47 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 46. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Задание № 2. Решение Известно, что Ваня точно должен выиграть, после Петиного хода. S1 - количество каменей после первого хода. Чтобы найти минимальное значение S, при котором будет выполняться ситуация, описанная в задаче, мы возьмём минимальное значение камней в куче после первого Петиного хода, когда Ваня будет точно выигрывать. Т.е. первым ходом Петя должен получить 24 камня в куче. Как он это может сделать ? Видим, что, если в куче было изначально 12 камней, то возможная ситуация, которая описана в задаче. Значит, ответ будет 12. Ответ: 12 ЕГЭ по информатике. Задание №19 - 21 Задание № 3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Задание № 3. Решение Обозначим первую кучу за a, вторую кучу за b. Блок 1 1. a + 1 + b (Добавляем камень к первой куче) 2. a + b + 1 (Добавляем камень ко второй куче) 3. 2 * a + b (Удваиваем первую кучу) 4. a + 2 * b (Удваиваем вторую кучу) Распишем все комбинации для суммы двух куч для каждого хода: Ⅰ ход Пети. S0 - первоначальное количество камней во второй куче. a=7, b=S0. Находим a и b после хода Пети. 1. a = 8, b = S0 2. a = 7, b = S0 + 1 3. a = 14, b = S0 4. a = 7, b = 2 * S0 ЕГЭ по информатике. Задание №19 - 21 Задание № 3. Решение II ход Вани. Разберём все варианты. 1. a=8, b=S0 Снова подставляем a и b в блок 1. 8 + 1 + S0 => S0 + 9 + 8 + S0 + 1 => S0 + 9 + 2 * 8 + S0 => S0 + 16 + 8 + 2 * S0 => 2 * S0 + 8 + 2. a=7, b=S0+1 Подставляем a и b в блок 1. 7 + 1 + S0 + 1 => S0 + 9 + 7 + S0 + 1 + 1 => S0 + 9 + 2 * 7 + S0 + 1 => S0 + 15 + 7 + 2 * (S0 + 1) => 2 * S0 + 9 + 3. a=14, b=S0 Подставляем a и b в блок 1. 14 + 1 + S0 => S0 + 15 + 14 + S0 + 1 => S0 + 15 + 2 * 14 + S0 => S0 + 28 + 14 + 2 * S0 => 2 * S0 + 14 + 4. a=7, b=2*S0 Подставляем a и b в блок 1. 7 + 1 + 2 * S0 => 2 * S0 + 8 + 7 + 2 * S0 + 1 => 2 * S0 + 8 + 2 * 7 + 2 * S0 => 2 * S0 + 14 + 7 + 2 * 2 *S0 => 4 * S0 + 7 + Теперь возле выражений, у которых коэффициент после переменной S0 равен единице, поставим синим цветом плюсик. Возле выражений, у которых коэффициент после переменной S0 равен двойке, поставим оранжевым цветом плюсик. Возле выражений, у которых коэффициент после переменной S0 равен четвёрки, поставим бордовым цветом плюсик. Выберем из тех выражений, где стоят синие плюсы, то выражение, где к S0 прибавляется наибольшее число. Это выражение S0 + 28. ЕГЭ по информатике. Задание №19 - 21 Задание № 3. Решение Найдём при каком наименьшем S0 это выражение будет больше или равно 77. S0 + 28 ≥ 77 S0 ≥ 77 - 28 = 49 S0 = 49 Аналогично для других цветов. 2*S0 + 14 ≥ 77 S0 ≥ (77 - 14) / 2 = 32 (округляем в большую сторону) S0 = 32 И для последнего выражения. 4*S0 + 7 ≥ 77 S0 ≥ (77 - 7) / 4 = 18 (округляем в большую сторону) S0 = 18 Берём меньшее число среди всех трёх значений. Получается число 18. ЕГЭ по информатике. Задание №19 - 21 Задание № 4. ЕГЭ по информатике. Задание №19 - 21 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней 1 ≤ S ≤ 64. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания без разделительных знаков. Задание № 5. ЕГЭ по информатике. Задание №19 - 21 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Задание № 6. ЕГЭ по информатике. Задание №19 - 21 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 32. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Задание № 7. ЕГЭ по информатике. Задание №19 - 21 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. |