Два игрока, Коля и Саша, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Коля. Выигрывает тот, кто первый составит слово из заданного набора.
Пример. Пусть заданы слова КОТ, КЛОН, ЛЕТО, ЛЕВ. За первый ход Коля может написать букву К или Л. Пусть он написал букву К. В ответ Саша может написатьОили Л. В первом случае получается КО, и Коля, дописав букву Т, получает слово КОТ из заданного набора и выигрывает. Во втором случае получается КЛ, Коля должен дописать О и Саша выиграет вторым ходом, дописав Н и получив слово КЛОН.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит указать, какую букву он должен дописать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие три задания.
Задание 1. Определите, у кого из игроков есть выигрышная стратегия для набора слов ПЛАМЯ, МАШИНА. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.
Задание 2. В наборе слов, приведённом в задании 1, поменяйте местами две буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.
Задание 3. Дан набор слов ЛАТУНЬ, ЛАТИНИЦА, ЛАТКА, РАДУГА, РАДАР, РАБОТА. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.
Задание 1. Для набора слов ПЛАМЯ, МАШИНА выигрышная стратегия есть у Коли.
Своим первым ходом он пишет букву П. Далее в результате следующих ходов игроков будет получено слово ПЛАМЯ. Так как количество букв в этом слове нечётно, то выиграет Коля (первый игрок).
Заданные слова начинаются с разных букв, и в одном из слов чётное количество букв, а в другом—нечётное, поэтому стратегия Коли заключается в том, что он должен своим первым ходом записать первую букву того слова, в котором количество букв нечётно. Тогда своим последним ходом он допишет последнюю букву этого слова. Для предложенных в задании слов Коля должен записать букву В.
При указанной стратегии возможна только одна партия.
В результате этой партии получится слово ПЛАМЯ.
Задание 2. Для набора слов, указанных в задании 1а, выигрывает Коля (первый игрок). Чтобы выиграл Саша (второй игрок), слова должны начинаться с одной буквы и у Саши должна быть возможность записать букву, после которой игроки будут записывать только буквы слова, состоящего из чётного количества букв.
Для заданных слов ПЛАМЯ, МАШИНА это возможно, если в слове ПЛАМЯ поменять местами буквы П и М. В этом случае исходными будут слова МЛАПЯ,МАШИНА.
Стратегия Саши заключается в том, что он должен своим первым ходом дописать к Мбукву А.
При указанной стратегии возможна только одна партия.
В результате этой партии получится слово МАШИНА.
Задание 3. Для набора слов выигрышная стратегия есть у Саши—второго игрока.
Ниже представлена таблица выигрышных стратегий Саши.
В таблице показаны все ходы Коли и только выигрышные ходы Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| Коля | Л | Р | ||
| Саша | ЛА | РА | ||
| Коля | ЛАТ | РАБ | РАД | |
| Саша | ЛАТУ | ЛАТИ | РАБО | РАДУ |
| Коля | ЛАТУН | ЛАТИН | РАБОТ | РАДУГ |
| Саша | ЛАТУНЬ | ЛАТИНИ | РАБОТА | РАДУГА |
| Коля | — | ЛАТИНИЦ | — | — |
| Саша | — | ЛАТИНИЦА | — | — |