Сюрприз ЕГЭ 2017 по информатике

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

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

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

Задание 1.

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

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

Задание 2

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

Задание 3

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

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

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

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

Это задание было новым при подготовке такого задания не разбирали. Чтобы вникнуть и разобрать условие задачи нужно не меньше 30 минут, а решить и записать решение  ещё 30 минут.
 Решение можно посмотреть на сайте Полякова- смотри здесь