Ещё пример задания. Ещё пример задания Петя и ваня играют в следующую игру

В этой задаче наиболее сложная часть — это грамотно и логически корректно записать решение.

Итак, начнём с того, что попытаемся понять условие.

1. У нас есть две кучки камней и два игрока: первый (Петя) и второй (Ваня).
2. Игроки ходят по очереди.
3. За ход в любую из кучек можно либо добавить один камень, либо увеличить количество камней в кучке в два раза.
4. Как только суммарно в кучке стало 73 или более камня, игра заканчивается.
5. Тот, кто ходил последним, выиграл.

Важные замечания

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

Задание 1.

Рассмотрим теперь Задание 1. В кучках — (6, 33) камней (первая часть Задания 1) и (8, 32) камней (вторая часть Задания 1). Нам нужно определить, у кого из игроков имеется выигрышная стратегия. Иными словами, кто из игроков при правильной игре обязательно выиграет вне зависимости от действий соперника.

Здесь и далее мы будем решение разбивать на две части. Вначале будет идти предварительное объяснение (его писать в ЕГЭ не нужно), а затем — "формальное решение", то есть то, что нужно писать в самом бланке ЕГЭ.

Обсуждение.

Давайте подумаем: первый игрок очевидно в один ход выиграть не может, так как что бы он не делал, суммарно 73 не будет. Самое "большое" действие, которое он может сделать, — это увеличить в 2 раза количество камней во второй кучке, сделав их 66. Но (6, 66) — это 72 камня, а не 73. Значит, первый в один ход явно выиграть не сможет. Однако второй — вполне сможет. Первый может сделать потенциально четыре действия: прибавить 1 к первой кучке, увеличить в 2 раза количество камней в первой кучке, прибавить 1 ко второй кучке, увеличить в 2 раза количество камней во второй кучке. Посмотрим, к чему это приведёт:

• (6,33) -> (7,33). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (7, 66). Суммарно — 73. Значит, второй выигрывает.
• (6,33) -> (12, 33). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (12, 66). Суммарно — 78. Значит, второй выигрывает.
• (6,33) -> (6,34). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (6, 68). Суммарно — 74. Значит, второй выигрывает.
• (6,33) -> (6,66). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (6, 132). Суммарно — 138. Значит, второй выигрывает.

Итого: как бы себя не вёл первый игрок, второй выиграет и в один ход.

Аналогично решается и с (8,32).

Формальное решение Задания 1.

Второй игрок имеет выигрышную стратегию. Докажем это и покажем эту стратегию. Для этого построим дерево партии для каждой из начальных позиции. В дереве партий мы будем указывать состояние обеих кучек в формате (a,b), где a — количество камней в первой кучке, b — количество камней во второй кучке. При ходе первого игрока мы будем рассматривать четыре возможных варианта его поведения: прибавить 1 к первой кучке, увеличить в 2 раза количество камней в первой кучке, прибавить 1 ко второй кучке, увеличить в 2 раза количество камней во второй кучке. Для второго игрока мы укажем по одному ходу, приводящему к выигрышу. Ходы будем показывать в виде стрелочек, рядом с которыми писать I в случае хода первого и II в случае хода второго.

Дерево партий для начальной позиции (6, 33).

Дерево партий для начальной позиции (8, 32).

Согласно дереву партий, вне зависимости от ходов первого у второго всегда есть выигрышная стратегия, позволяющая ему выиграть в один ход, описанная в деревьях (суммы после ходов Вани составляют слева-направо 73, 80, 74 и 136 соответственно). При этом, согласно дереву партий, второй игрок может выиграть ровно за один ход.

Задание 2

Формальное решение

Рассмотрим начальную позицию (6,32). Заметим, что она близка к (6,33) из Задания 1. В Задании 1 мы выяснили, что в позиции (6, 33) выигрывает второй, причём в один ход. Можно это условие переформулировать: в позиции (6,33) выигрывает в один ход тот, кто не ходит (то есть, ходит вторым). Или, иными словами, тот, кто ходит, проигрывает в один ход.

В позиции (6,32) выигрывает первый в два хода. Докажем это. Первым своим ходом Петя добавляет +1 ко второй кучке. Таким образом, получается позиция (6,33). Как мы выяснили ранее, в позиции (6,33) тот, кто ходит, проигрывает. В нашем случае будет ход Вани. Поэтому Ваня проиграет в один ход. При этом Пете придётся сделать в сумме два хода: первый (добавить 1 камень во вторую кучку) + второй ход в соответствии с Деревом партий в Задании 1, действуя по стратегии Вани.

Аналогично в позиции (7, 32). Петя своим первым ходом добавляет +1 камень в первую кучку, получая позицию (8, 32). В этой позиции согласно тем же рассуждениям, тот, кто ходит, проигрывает. Будет ход Вани, поэтому Ваня проиграет. Выигрышная стратегия Пети заключается в следующем: Петя добавляет +1 камень в первую кучку, а затем следует стратегии Вани из Задания 1.

Аналогично в позиции (8, 31). Петя своим первым ходом добавляет +1 камень во вторую кучку, получая позицию (8, 32). В этой позиции согласно тем же рассуждениям, тот, кто ходит, проигрывает. Будет ход Вани, поэтому Ваня проиграет. Выигрышная стратегия Пети заключается в следующем: Петя добавляет +1 камень во вторую кучку, а затем следует стратегии Вани из Задания 1.

Задание 3

Обсуждение

Заметим, что из ситуации (7, 31) очень легко попасть либо в ситуации (8, 31) и (7, 32), в которых, согласно предыдущему Заданию, тот, кто ходит, выигрывает, либо в ситуации (14, 31) и (7, 62), в которых тот, кто ходит, может выиграть в один ход, увеличив в два раза количество камней во второй кучке. Таким образом, получается, что у Вани должна быть выигрышная стратегия. При этом он может выиграть как в 2 хода (первые два случая), так и в один ход (вторые два случая).

Формальное решение

В начальной позиции (7, 31) выигрывает Ваня в один или два хода. Докажем это. Для этого построим дерево всех партий.

Дерево всех партий для начальной позиции (7, 31).

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

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

Евгений Смирнов

Эксперт в IT, учитель информатики

Задача Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получившим кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней; 1 S 40. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания. Во всех случаях обоснуйте свой ответ.

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

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

Задание 3. Укажите значения S, при котором одновременно выполняются два условия: У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.

1. а) S=14…40 камней. Утроив количество камней, Петя выиграет с первого хода, получив в куче более 41 камня. б) S=13 камней. После первого хода у Пети будет 14 или 18 или 39 камней. Тогда Ваня своим первым ходом выиграет в любом случае. 1. а) S=14…40 камней. Утроив количество камней, Петя выиграет с первого хода, получив в куче более 41 камня. б) S=13 камней. После первого хода у Пети будет 14 или 18 или 39 камней. Тогда Ваня своим первым ходом выиграет в любом случае.

Задача 2. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 33. В начальный момент в куче было S камней, 1 S При каких S: 1 а) Петя выигрывает первым ходом; 1 б) Ваня выигрывает первым ходом? 2. Назовите два значения S, при которых Петя может выиграть своим вторым ходом. 3. При каком S Ваня выигрывает своим первым или вторым ходом?

26-е задание: «Теория игр, поиск выигрышной стратегии»
Уровень сложности - высокий,
Максимальный балл - 3,
Примерное время выполнения - 30 минут.

Разбор 26 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Два игрока, Паша и Валя, игр

ают в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша один в два раза . Например, имея кучу из 7 камней, за один ход можно получить кучу из 14 или 8 камней. У каждого игрока, чтобы сделать ход, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 28 . Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27 .

Задание 1
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24 ? Опишите выигрышные стратегии для этих случаев.

Задание 2
S = 13, 12 ? Опишите соответствующие выигрышные стратегии.

Задание 3
У кого из игроков есть выигрышная стратегия при S = 11 ? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.

✍ Показать решение:

Разбор 26 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

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

Например, есть набор слов {Волк, Информатика, Страшно} ; для заданного набора слов Петя своим первым ходом может назвать букву В , И или С . Если Петя выберет букву В , то победит Ваня (следующие ходы: Петя — В , Ваня — О , Петя — Л , Ваня — К ).

Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ , НМЛКИНМЛКИ }. Определить выигрышную стратегию.

Б) Даны 2 слова {ТРИТРИТРИ…ТРИ , РИТАРИТАРИТАРИТА…РИТА }. В первом слове 99 букв, во втором 164 . Определить выигрышную стратегию.

Задание 2
Необходимо поменять две буквы местами из набора пункта 1А в слове с наименьшей длинной так, чтобы выигрышная стратегия была у другого игрока. Объяснить выигрышную стратегию.

Задание 3
Дан набор слов {Ворона , Волк , Волна , Производная , Прохор , Просо }. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий для выигрышной стратегии.

✍ Показать решение:

* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш

Решение 26. Демоверсия ЕГЭ 2018 информатика:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза . Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29 . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28 .

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

Задание 1
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

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

Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах - количество камней в позиции

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

✍ Показать решение:

Задание 1.
• а) Петя может выиграть, если S = 15, … 28

15, ..., 28 - выигрышные позиции с первого хода

б) Ваня может выиграть первым ходом (как бы ни играл Петя), если в куче будет S = 14 камней. Тогда после первого хода Пети в куче будет 15 или 28 камней. В обоих случаях Ваня удваивает кучу и выигрывает в один ход.

S = 14 Петя: 14 + 1 = 15 выигрышная позиция (см. п. а). Выигрывает Ваня Петя: 14 * 2 = 28 выигрышная позиция (см. п. а). Выигрывает Ваня 14 - проигрышная позиция

Задание 2.

Возможные значения S: 7, 13 . В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 14 камней: в первом случае удвоением, во втором — добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

S = 7 Петя: 7 * 2 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя S = 13 Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя 7, 13 - выигрышные позиции со второго хода

Задание 3.

Возможные значения S: 12 . После первого хода Пети в куче будет 13 или 24 камня. Если в куче их станет 24, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 13 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

S = 12 Петя: 12 + 1 = 13 Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!

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


Дерево всех партий, возможных при стратегии Вани:

* красный круг означает выигрыш

Досрочный егэ по информатике 2018, вариант 1. Задание 26:

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

Задание 1.
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Вася может выиграть своим первым ходом. Опишите выигрышную стратегию Васи.

Задание 2. Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.

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

✍ Показать решение:

1.
а) S ≥ 14 . При количестве камней в куче от 14 и выше Паше необходимо увеличить их количество в пять раз, тем самым получив 70 или более камней.

S ≥ 14 выигрышные позиции

б) S = 13 . Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.

S = 13 Паша 1 ход: 13 + 1 = 14 Паша 1 ход: 13 + 4 = 17 Паша 1 ход: 13 * 5 = 65 Ваня 1 ход: * 5 = S ≥ 14 Ваня выигрывает 13 - проигрышная позиция

2. S = 9, 12 . Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
После чего игра сводится к стратегии, описанной в пункте 1б .

S = 13 Паша 1 ход: 9 + 4 = 13 Паша выигрывает Паша 1 ход: 12 + 1 = 13 Паша выигрывает 9, 12 - выигрышные позиции со второго хода

3. S = 8 . Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2 .

S = 8 Паша 1 ход: 8 + 1 = 9 Ваня Выигрывает (см. п.2) Паша 1 ход: 8 + 4 = 12 Ваня Выигрывает (см. п.2) Паша 1 ход: 8 * 5 = 40

Тренажер егэ по информатике 2018, контрольный вариант 1. Задание 26 (Крылов С., Ушаков Д.):

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

Задание 1.
(6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2.
Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.

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

✍ Показать решение:

Разбор задания 26 с сайта К. Полякова (№ 31):

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

В начальный момент в первой куче было 5 камней , во второй куче – S камней; 1 ≤ S ≤ 38 .
Задание 1.
При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

Задание 2.
Назовите одно любое значение S , при котором Петя может выиграть своим вторым ходом.

Задание 3.
Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.

Показать решение:

5 + 20*2 = 45 (>44) * 5 - кол-во камней в первой куче, оно не меняется по условию

Соответственно, все значения большие 20 дадут в результате число большее 44 . Укажем это в таблице. + означает выигрышную позицию с первого хода:

Ответ 1 а) : S = (На ЕГЭ пояснить ходы, например: (5; 20) -> (Ход Пети)-> (5;40); 40 + 5 = 45)

Задание 1 б):

Поскольку Ваня будет ходить вторым, то необходимо поменять количество камней и в первой куче. Значит рассмотрим ситуации, что Петя мог бы ходить первым ходом в (7;S) и в (10;S) . Укажем, будут ли эти позиции выигрышные с одного хода: например (7;19) выигрышная позиция, т.к. игрок выполнит ход в (7;38) и выиграет (7 + 38 = 45). Соответственно, выигрышными являются и все позиции (7;больше 19) . Проанализируем таблицу, увеличивая количество камней в первой куче и выполняя поиск выигрышных позиций с одного хода:

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

Находим единственное такое значение — (5; 19). Т.е. S = 19.

Ответ 1 б) : S = 19 (На ЕГЭ пояснить ходы, например: (5; 19) -> (Ходы Пети): (5;21),(5;28);(7;19);(7;28). Везде следующим ходом выиграет Ваня, см. предыдущ. пункт)

Задание 2:

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

Логика рассуждений: Петя сможет выиграть своим вторым ходом, когда своим первым ходом он попадет в проигрышную позицию, т.е. переведет соперника в проигрышную ситуацию. Такие значения: S = 16, 17 или 18. Назовем эти позиции выигрышными со второго хода (2+):

Ответ 2: S = 16, 17 или 18

Задание 3:

Укажем в таблице также позиции, выигрышные с n-го хода: когда игрок может перевести соперника в проигрышную позицию:

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

Логика рассуждений: Ваня сможет выиграть своим первым или вторым ходом, когда Петя своим первым ходом может попасть только либо в позицию выигрышную с первого хода (+), либо в позицию выигрышную со второго хода или n-го хода (2+). Это позиция при S = 14:

Ответ 3: S = 14 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)

Новым было задание №26. Это задание относится к классу (С3)- высокий уровень. Ниже текст задания:

P-08. Два игрока, Петя и Ваня играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого (выполняется условие Фано). Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Пример. Пусть заданы слова {МАК, МЫЛО, РАМА, РАК}. На первом ходу Петя может написать букву М или Р. Пусть он написал букву М. В ответ Ваня может написать А или Ы. В первом случае получается МА, и Петя, дописав букву К, получает слово МАК из заданного набора и выигрывает. Во втором случае получается МЫ, Петя вынужден дописать Л и Ваня выиграет вторым ходом, дописав О и получив слово МЫЛО.

Задание 1.

а) Определите, у кого из игроков есть выигрышная стратегия для набора слов {ВАРЕНЬЕ, КОРОВА}. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

б) Определите, у кого из игроков есть выигрышная стратегия для набора слов {НУБНУБ…НУБ, PUMAPUMA …PUMA }. В первом слове 55 раз повторяется слово НУБ, а во втором – 32 раза повторяется слово PUMA. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 2

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

Задание 3

Дан набор слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА}. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

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

2)Если слов несколько, то стратегия Пети состоит в том, чтобы все время выбирать такое продолжение, при котором в итоге будет получено слово с нечётным количеством букв, а Ваня наоборот должен пытаться перескочить на слово с чётным количеством букв.

3)Задание 1а. В слове ВАРЕНЬЕ – 7 букв (нечётное количество, выиграет Петя), а в слове КОРОВА – 6 букв (чётное количество, выиграет Ваня). Петя ходит первый и может написать букву В. Поскольку слово КОРОВА начинается с другой буквы, Ваня будет вынужден «идти» по слову ВАРЕНЬЕ и проиграет. Этот вариант – единственный, то есть возможна только одна партия, при которой Петя следует своей стратегии, она заканчивается словом ВАРЕНЬЕ.