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