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