Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 21.
Будем говорить, что игрок имеет выигрышную стратегию , если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1.
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём

• Петя не может выиграть за один ход, и

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

3. Укажите значение S, при котором:

• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

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

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

Решение:

часть 1

а) Петя может выиграть за один ход.

При S≥22 игра завершается. Пети может:

• добавить в кучу один камень (+1),
• увеличить количество камней в куче в два раза (*2).

Рассмотрим каждый вариант:

• (+1):S= 22 −1=21
• (*2): S=22\2=11 =>S∈

11*2=22
12*2=24 (>22 )
...
21*2=42 (>22 )
Получим следующие стратегии:

• при S∈ надо удвоить количество камней

• при S=21 надо добавить один камень или удвоить количество камней

б) Ваня может выиграть за один ход при любом ходе Пети.
Используем решение предыдущей задачи. Ваня может выиграть при S≥11. Но Ваня ходит 2-м, а Петя 1-м.
Нам нужно подобрать S.
11 можно получить следующим образом:
10 +1
Построим дерево решений для S=10 :

Получили, S= 10 .
Стратегия будет такой:

часть 2
Петя не может выиграть 1-м ходом, он может выграть за 2 хода при любом ходе Вани:
Используем решение задачи части 1 (б).
Дерево решений имеет вид:

Нам нужно подобрать S.
10 можно получить следующим образом:

Получаем следующие деревья решений при S=5 и S=9 :

Красным крестом обозначена проигрышная ветка для Пети. При S=5 такая ветка приведет к тому, что никто не выиграет. При s=9 такая ветка приведет к тому, что Выиграет Ваня первым ходом, получая 36. В решении проигрышные стратегии указывать не нужно. Здесь они приведены для наглядности.
Получим следующие выигрышные стратегии:

Получили, S=5 и S=9 .
часть 3
Ваня может выиграть за 1 или 2 хода при любых ходах Пети. Ваня не может гарантированно выйграть 1-м ходом.
Используем решение части 2. Стратегии, приведенные выше гарантируют выйгрыш 2-м ходом.
Нам нужно подобрать S.
5 можно получить следующим образом:

9 можно получить следующим образом:Построим деревья решений.
Дерево для S=4 :

Здесь и в задачах для тренировки условие записано в сокращенном виде для экономии места. Полную форму записи условия см. в первой разобранной задаче.

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

1. При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

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

3. При каких S Ваня выигрывает своим первым или вторым ходом?

Решение (способ 2, математический, Г. Сергеев , г. Москва):

1. Вопрос 1а. Петя выигрывает первым ходом:

Петя должен правильно выбрать один из трёх возможных вариантов действий (+1 ИЛИ +3ИЛИ *2), которое переведет кучу камней к состоянию≥30. Таким образом, получаем совокупность неравенств:

1. Вопрос 1б. Ваня выигрывает первым ходом

Любое действие Пети (И +1И +3И *2) должно привести кучу камней к состоянию . Только этоможет обеспечить выигрыш Вани на следующем ходу. Таким образом, получаемсистему :

Назовите три значения S, при которых Петя может выиграть своим вторым ходом?

Петя должен выиграть, а это значит, он должен правильно выбрать один из трёх возможных вариантов действий (+1 ИЛИ +3ИЛИ *2), которое переведет кучу камней к состоянию . Только это может обеспечить ему выигрыш при любом действии его противника Вани. Таким образом, получаем совокупность:

1. Вопрос 3.При каком s Ваня выигрывает своим первым или вторым ходом?

Сначала найдем, при каком S Ваня выигрывает своим вторым ходом.

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

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

итак, ответ на вопрос 3 : S = 10 или 12.

Построим дерево игры для S= 10. Обратите внимание, что после ходов Пети +1 и +3 Ваня своим следующим ходом сводит игру к одной и той же проигрышной (для Пети) позиции S = 14.

Ещё пример задания:

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

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

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

Для каждого указанного значения S опишите выигрышную стратегию Пети.

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

Для указанного значения S опишите выигрышную стратегию Вани.

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

Решение (способ 1, таблица ) :

Вопрос 1а. Последним ходом может быть «+1» или «*2». Выиграть последним ходом «+1» можно, если S = 21. Ходом «*2» можно выиграть из любой позиции при S > 10 (сюда входит и 21!). Можно составить таблицу, в которой «В 1 » обозначает выигрыш за один ход:

«1а.Петя может выиграть за один ход при любом S > 10. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 22 камней. »

Вопрос 1б. Для ответа на этот вопрос нужно найти позицию, из которой все возможные ходы ведут к выигрышу за 1 ход, то есть к позиции, отмеченной в таблице как «В 1 ». Например, это позиция при S = 10: ход «+1» ведёт в выигрышную позицию S = 11, а ход «*2» ведёт в выигрышную позицию S = 20. Поэтому позицию S = 10 отметим в таблице как «×­ 1 » (проигрыш за 1 ход):

×­ 1

Ответ на вопрос 1б должен быть такой:

«1б. При S = 10 Петя не может выиграть в один ход, потому что при его ходе «+1» число камней в куче становится равно 11 (меньше 22), а при ходе «*2» число камней в куче становится равно 20 (также меньше 22). Других возможных ходов у Пети нет. Из любой позиции после одного хода Пети (это может быть 11 или 20), Ваня может выиграть своим первых ходом, удвоив количество камней в куче. »

Вопрос 2 . Пете, для того, чтобы гарантированно выиграть на втором ходу, нужно из начальной позиции перевести игру в проигрышную позицию, отмеченную знаком «× 1 ». Пока мы нашли одну такую позицию: S = 10. Петя может перевести игру в эту позицию из позиций

S= 9 (ходом «+1») иS= 5 (ходом «*2»)

В таблице отмечаем эти положения как «В­­ 2 » – гарантированный выигрыш за 2 хода:

× 1

Поэтому ответ должен быть такой:

«2. Из позиций S = 9 и S = 5 Петя не может выиграть в один ход, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. При S = 9 ходом «+1» Пете нужно перевести игру в позицию S = 10, которая является проигрышной (см. ответ на вопрос 1б). При S = 5 Петя переводит игру в ту же позицию ходом «*2». »

Вопрос 3 . Нужно найти такую позицию, из которой оба возможных хода Пети ведут в позиции, отмеченные в таблице как «В­ 1 » (выигрыш в 1 ход) и «В­ 2 » (выигрыш в 2 хода). Например, это позиция S = 8, из которой можно «попасть» только в S = 9 («В 2 ») и S = 16 («В 1 »). Отмечаем эту позицию как «× 2 » – проигрыш в два хода:

× 2

×­ 1

Поэтому ответ должен быть такой:

«3. В позиции S = 8 у Вани есть выигрышная стратегия, которая позволяет ему выиграть первым или вторым ходом. Если Петя выбирает ход «+1», в куче становится 9 камней и Ваня выигрывает на 2-м ходу (см. ответ на вопрос 2). Если Петя выбирает ход «*2», Ваня выигрывает первым ходом, удвоив число камней в куче. »

Остается нарисовать дерево возможных вариантов игры из позиции S = 8. Для этого используем построенную таблицу:

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

Обратите внимание, что на каждом шаге мы рассматриваем все возможные ходы Пети и только один лучший ход Вани. Например, в позиции S = 11 Ваня может сделать ход «+1» и получить 12 камней в куче, но тогда он проиграет (Петя следующим ходом удвоит число камней и получит 24 камня). Этот ход мы не рассматриваем, потому что мы хотим доказать, что у Вани есть выигрышная стратегия – ему достаточно хода «*2», после которого он выиграет. В то же время нужно рассмотретьвсе возможные ответы Пети , чтобы доказать, что у него нет шансов на выигрыш при правильной игре Вани. В этом суть теории игр – добиться лучшего результата в худшем случае, то есть при безошибочной игре соперника.

Построенное дерево можно записать и в другой форме, например, «положив его на бок»:

Ещё один вариант – представить дерево в виде таблицы:

Начальная позиция	1-й ход Пети (все варианты)	1-й ход Вани (ход по стратегии)	2-й ход Пети (все варианты)	2-й ход Вани (ход по стратегии)
				22 (выигрыш)
				40 (выигрыш)
		32 (выигрыш)

Задача Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 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 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)

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

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

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, учитель информатики