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