Подготовка ребёнка к ЕГЭ по информатике. Часть шестнадцатая

26 задание часть 2

Поиск выигрышной стратегии

Предисловие

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

Демонстрационный вариант ЕГЭ 2016 г. ИНФОРМАТИКА и ИКТ, 11 класс.

1. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

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

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

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

Задание 1

Для позиции (6, 33) выигрышная стратегия у Вани. Первым ходом Петя может получить один из четырех наборов: (7, 33), (12, 33), (7, 34), (6, 66). Тогда следующим вторым ходом Ваня обязательно выиграет, если при первой стратегии Пети увеличит количество камней во второй куче в два раза и получит (7, 66), при второй стратегии – увеличит количество камней во второй куче в два раза и получит (12, 66), при третьей – увеличит количество камней во  второй куче в два раза и получит (7, 68), при четвертой – увеличит количество камней в первой куче в два раза и получит (12, 66). Эти стратегии ведут к выигрышу, потому что количество камней в обеих кучах становится не менее 73. Победителю Ване максимально потребуется один ход для выигрыша (всего с начала игры пройдет два хода).

Для позиции (8, 32) выигрышная стратегия у Вани. Первым ходом Петя может получить один из четырех наборов: (9, 32), (16, 32), (9, 32), (8, 64). Тогда следующим вторым ходом Ваня обязательно выиграет, если при первой стратегии Пети увеличит количество камней во второй куче в два раза и получит (9, 64), при второй стратегии – увеличит количество камней во второй куче в два раза и получит (16, 64), при третьей – увеличит количество камней во  второй куче в два раза и получит (9, 64), при четвертой – увеличит количество камней в первой куче и получит (16, 64). Эти стратегии ведут к выигрышу, потому что количество камней в обеих кучах становится не менее 73. Победителю Ване максимально потребуется один ход для выигрыша (всего с начала игры пройдет два хода).

Задание 2

Для позиции (6, 32) выигрышная стратегия у Пети. Первым ходом Петя может получить один из четырех наборов: (7, 32), (14, 32), (6, 33), (6, 64). Но второй и четвертый ведут к неминуемому поражению, поэтому он должен выбрать либо (6, 33), либо (7, 32).  Рассмотрим первый вариант. В этом случае Ваня в свой ход может получить (7,  33), (12, 33), (6, 34), (6, 66). И в свой второй ход Петя выигрывает при любой из представленных стратегий. Возможные расклады: (7, 66), (12, 66), (6, 68), (12, 66). Таким образом, его выигрышная стратегия – первым ходом получить (6, 33). Максимально он может победить за два своих хода (с начала игры пройдет три хода).

Для позиции (7, 32) выигрышная стратегия у Пети. Первым ходом должен получить (8, 32). Тогда у Вани есть 4 возможных варианта: (9, 32), (16, 32), (8, 33), (8, 64). Каждый из них приводит к победе Пети следующим ходом: (9, 64), (16, 64), (8, 66), (16, 64). Максимально Петя может победить за два своих хода (с начала игры всего пройдет 3 хода).

Для позиции (8, 31) выигрышная стратегия у Пети. Ему необходимо добавить один камень ко второй куче и получить (8, 32). Тогда Ваня может получить четыре набора: (9, 32), (16, 32), (8, 33), (8, 64). И своим вторым ходом Петя выигрывает: (9, 64), (16, 64), (8, 66), (16, 64). Максимально он может победить за два своих хода (с начала игры пройдет три хода).

Задание 3

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

Демонстрационный вариант ЕГЭ 2015 г. ИНФОРМАТИКА и ИКТ, 11 класс.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 35.

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 34.

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

встретиться при различной игре противника.

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

Задание 1

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

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

Задание 2

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

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

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

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

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

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

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

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

кто делает ход; в узлах – количество камней в позиции.

Задание 1

а) S = [18, 34]. При каждом из этих значений достаточно удвоить количество камней в куче. При меньших S не будет достигаться число не меньше 35.

б) S = 17. Петя в первый ход может получить лишь 18, 20, 34. При любом из этих раскладов Ваня может победить в свой первый ход, просто удвоив число камней в куче (до 36, 40 или 64).

Задание 2

S = 16. Петя кладет в кучу один камень, в ней становится 17. Тогда Ваня может получить 18, 20 или 32 камня. Петя своим вторым ходом может в любом из этих раскладов выиграть (удвоив число камней до 36, 40 или 64).

S = 14. Петя кладет в кучу три камня, в ней становится 17. Тогда Ваня может получить 18, 20 или 32 камня. Петя своим вторым ходом может в любом из этих раскладов выиграть (удвоив число камней до 36, 40 или 64).

Задание 3

Очевидно, что искомое значение S лежит где-то в интервале [1, 13], {15}. Проверим число 15:

Из таблицы решений видно, что при S = 15 Ваня может победить в любом случае, при том выполняются необходимые требования.

Демонстрационный вариант ЕГЭ 2014 г. ИНФОРМАТИКА и ИКТ, 11 класс.

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 26.

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

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

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

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

Опишите выигрышную стратегию Вани.

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

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

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

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

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

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

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

Задание 1

а) S = [14, 26]. Необходимо и достаточно удвоить количество камней в куче. При меньших S количество камней при удвоении будет меньше 27.

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

Задание 2

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

Задание 3

При S = 10 у Вани есть выигрышная стратегия, соответствующая заявленным требованиям. Рассмотрим дерево решений:

Демонстрационный вариант ЕГЭ 2010 г. ИНФОРМАТИКА и ИКТ, 11 класс (с правками).

4. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2, 1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

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

Вывод

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