Решение: Стратегии в игре со словами
Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при этом ни одно из заданных слов не является началом другого. Игроки составляют слово из набора, приписывая по очереди буквы к его концу. Каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получит одно из заданных слов целиком. Первый ход делает Петя.
Стратегия игрока — это правило, указывающее ему ход в любой ситуации, которая может встретиться при игре противника. Стратегия называется выигрышной, если игрок выигрывает при любой игре противника. Множество всех партий, которые могут получиться при данной стратегии, представляется в виде дерева всех партий.
Задание 1.
а) Для набора слов {АБВГДАБВГДХ, ДГВБАДГВБА} определите, у кого есть выигрышная стратегия. Опишите эту стратегию. Укажите количество различных партий при этой стратегии и конечное слово в каждой партии.
б) Для набора слов {ТРИТРИ…ТРИ, РИТАРИТА…РИТА}, где первое слово состоит из 33 повторений слова ТРИ, а второе — из 44 повторений слова РИТА, определите, у кого есть выигрышная стратегия и опишите её.
Задание 2.
В задании 1а поменяйте местами две буквы в более коротком слове так, чтобы выигрышная стратегия была у другого игрока. Запишите полученный набор слов, опишите выигрышную стратегию, укажите количество различных партий при этой стратегии и конечное слово в каждой партии.
Задание 3.
Для набора слов {СОЛНЦЕ, СОВА, СОВЕТ, ТРАВА, ТРАССА, ТРАНСПОРТ} определите, у кого есть выигрышная стратегия. Приведите в виде таблицы дерево всех партий, возможных при этой стратегии.
Решение по шагам
13 шаговВ задании 1а длина слова АБВГДАБВГДХ равна 11, а длина слова ДГВБАДГВБА равна 10. Петя первым ходом может выбрать начальную букву А или Д.
Если Петя пишет А, далее буквы определяются однозначно, и получается слово длины 11. Последнюю букву записывает Петя, поэтому он выигрывает.
Если Петя пишет Д, далее получается слово ДГВБАДГВБА длины 10. Последнюю букву записывает Ваня, поэтому эта ветвь приводит к победе Вани. Следовательно, выигрышная стратегия Пети — первым ходом написать А.
При стратегии Пети возможна только одна партия: АБВГДАБВГДХ. В конце написано слово АБВГДАБВГДХ.
В задании 1б длина слова ТРИ, повторённого 33 раза, равна $3 \cdot 33 = 99$. Длина слова РИТА, повторённого 44 раза, равна $4 \cdot 44 = 176$.
Петя первым ходом пишет Т и переводит игру на ветвь длины 99. Последнюю букву этой ветви записывает Петя, поэтому его выигрышная стратегия состоит в первом ходе Т.
Для задания 2 поменяем местами первую и последнюю буквы короткого слова ДГВБАДГВБА. Получим слово АГВБАДГВБД. Новый набор: {АБВГДАБВГДХ, АГВБАДГВБД}.
Теперь Петя вынужден первым ходом написать А. После этого Ваня может выбрать букву Б или Г. Ваня выбирает Г, после чего продолжение однозначно и заканчивается словом АГВБАДГВБД длины 10. Последнюю букву записывает Ваня.
При выигрышной стратегии Вани возможна одна партия: АГВБАДГВБД. Ваня выигрывает.
В задании 3 рассмотрим сначала ветвь, начинающуюся с С. После ходов Пети и Вани получается СО. Петя может выбрать Л или В.
Если Петя выбирает Л, получается ветвь СОЛНЦЕ, заканчивающаяся на шестом ходе Вани. Если Петя выбирает В, получается СОВ. В этой позиции Ваня выбирает А, и слово СОВА заканчивается на четвёртом ходе Вани.
На ветви, начинающейся с Т, после обязательных ходов получается ТРА. Ваня выбирает букву С, затем Петя вынужден написать вторую С, а Ваня завершает слово ТРАССА. Поэтому Ваня имеет выигрышную стратегию для всего набора.
Дерево всех партий при стратегии Вани можно записать так: П: С → В: О → П: Л → В: О → П: Н → В: Ц → П: Е, конечное слово СОЛНЦЕ; либо П: С → В: О → П: В → В: А, конечное слово СОВА; либо П: Т → В: Р → П: А → В: С → П: С → В: А, конечное слово ТРАССА.
1а) Выигрышная стратегия есть у Пети: первым ходом написать А. Возможна 1 партия, заканчивающаяся словом АБВГДАБВГДХ. 1б) Выигрышная стратегия есть у Пети: первым ходом написать Т; длина выбранного слова равна 99. 2) После обмена первой и последней буквами короткого слова получаем {АБВГДАБВГДХ, АГВБАДГВБД}. Выигрышная стратегия есть у Вани: после первого хода А написать Г. Возможна 1 партия, заканчивающаяся словом АГВБАДГВБД. 3) Выигрышная стратегия есть у Вани. Возможные партии при его стратегии: СОЛНЦЕ, СОВА, ТРАССА.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Ошибочно считать, что игрок всегда может выбирать любую букву, не проверяя, является ли полученное слово началом заданного слова.
Путать длину слова с номером хода и неверно определять игрока, записывающего последнюю букву.
В задании 2 менять буквы не внутри короткого слова или получать слово, которое не соответствует обмену двух букв.
В задании 3 включать в дерево партии, в которых Ваня отклоняется от своей выигрышной стратегии.
Забывать, что в позиции СОВ ход делает Ваня, а в позиции ТРА также ход делает Ваня.