Подготовка к ЕГЭ и олимпиадам по информатике 2020 / Тренировочные варианты ЕГЭ

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант № EGE_INF_1701

Добавлен 18 мая 2017 г. в 0:11. Изменён 24 декабря 2017 г. в 22:53.Скачать PDF
1Р 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Задание

Марина и Дарья не могли поделить конфеты, лежавшие на столе, и решили поиграть в следующую игру. Девочки ходят по очереди, первый ход делает Марина. За один ход каждая девочка может взять со стола либо 5 конфет (или все имеющиеся конфеты, если их осталось меньше 5), либо половину от имеющегося количества, если оно чётное.

Игра завершается в тот момент, когда конфет на столе не останется. Победителем считается девочка, сделавшая последний ход, то есть забравшая со стола все оставшиеся конфеты. В начальный момент было \(S\geq 1\) конфет.

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

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

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

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

Решение

1) \(6\leq S\leq 10\). Своим первым ходом Марина может взять 5 или половину имеющихся конфет (если их 6, 8 или 10), после чего на столе останется не более 5 конфет. Своим первым ходом Дарья заберёт все конфеты (5 или менее) и выиграет. При \(S<6\) первым ходом выиграет Марина.

2) \(11\leq S\leq 15\) или \(S=16\), \(S=18\) и \(S=20\). При \(11\leq S\leq 15\) Марина заберёт 5 конфет, при \(S=16\), \(S=18\) и \(S=20\) — заберёт половину имеющихся конфет. После этого на столе останется не менее 6, но не более 10 конфет. Данная ситуация рассмотрена в предыдущем пункте.

3) \(S=17\), \(S=19\), \(S=21\), \(S=23\) или \(S=25\). Марина возьмёт 5 конфет, после чего их останется 12, 14, 16, 18 или 20. Дарья заберёт половину конфет, их останется 6, 7, 8, 9 или 10 соответственно, дальнейшие ходы рассмотрены в пункте 1.

Подробнее...

Ответ

1) \(6\leq S\leq 10\);

2) \(11\leq S\leq 15\) или \(S=16\), \(S=18\) и \(S=20\);

3) \(S=17\), \(S=19\), \(S=21\), \(S=23\) или \(S=25\).

Подробнее...