Центр индивидуальной подготовки
школьников и студентов
40-33-54

ЗАДАНИЕ 19 - 87

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

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

Для скольких слов из набора {ПАТРОНИМ, ПАУЗОК, ПАЯЦ, ПАТРОНИРОВАТЬ, ПАТРОНЕССА, ПАШНЯ, ПАТРОНТАШ, ПАТРОННИК, ПАЯСНИЧАТЬ} выиграет Петя, независимо от того, как будет ходить Ваня?





Задание 20

Для игры, описанной в 19 задании, определите, сколько букв содержит самое длинное слово из набора {ЗЕМЛЯНИКА, ЗЕМЛЯНКА, ЗЛАК, ЗЛАТО, ЗИМНИК, ЗИМОВЬЕ}, при записи которого, выигрывает Ваня, независимо от того, как будет ходить Петя?





Задание 21

Из букв «А» и «Б» составляются две символьные последовательности (два слова). Первое слово длиною 3 символа, второе длиною 6 символов.

Для игры, описанной в задании 19, определите, какое количество различных пар слов можно составить, чтобы всегда выигрывал Ваня, независимо от того, как будет ходить Петя?

Например, для пары слов АБА и АААААА выигрывает Ваня. Его выигрышная стратегия заключается в том, чтобы первым ходом написать букву «А».