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