Шешімі: Стратегии в игре со словами
Два игрока, Петя и Ваня, составляют слово из заданного набора слов, по очереди приписывая буквы справа. Каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получает одно из заданных слов целиком. Первый ход делает Петя. Стратегия игрока должна описывать ход в любой ситуации, которая может встретиться при игре противника.
Решите три части задания. В задании 1а проанализируйте набор {АБВГДАБВГДХ, ДГВБАДГВБА}: определите игрока с выигрышной стратегией, опишите стратегию, укажите количество партий при этой стратегии и конечное слово в каждой партии. В задании 1б проанализируйте набор {ТРИТРИ…ТРИ, РИТАРИТА…РИТА}, где первое слово состоит из 33 повторений ТРИ и имеет длину 99 букв, а второе — из 44 повторений РИТА и имеет длину 176 букв.
В задании 2 в более коротком слове из задания 1а поменяйте местами две буквы так, чтобы выигрышная стратегия оказалась у другого игрока. Приведите полученный набор слов, опишите стратегию, укажите число партий и конечное слово каждой партии.
В задании 3 рассмотрите набор {ВОРОНА, ВОЛК, ВОЛНА, МОРИС, МОРЯНА, МОРКОВЬ}. Определите игрока с выигрышной стратегией и представьте дерево всех партий, возможных при этой стратегии, в виде таблицы или текстовой схемы.
Шешімін қадамдап көрсету
12 қадамВ задании 1а первое слово начинается с А, а второе — с Д. Поэтому после первого хода Пети выбор ветви полностью определяется его первой буквой.
Слово АБВГДАБВГДХ имеет длину 11. Если Петя начинает с буквы А, все последующие буквы определяются однозначно, и на одиннадцатом ходу слово получает Петя.
$$11 \equiv 1 \pmod 2$$Стратегия Пети в задании 1а: первым ходом написать А. После этого он каждый раз дописывает единственную букву, продолжающую текущий префикс до слова АБВГДАБВГДХ. При этой стратегии возможна одна партия, заканчивающаяся словом АБВГДАБВГДХ.
В задании 1б длина слова ТРИ, повторённого 33 раза, равна 99, а длина слова РИТА, повторённого 44 раза, равна 176. Петя первым ходом выбирает букву Т и далее вынужден дописывать буквы слова длины 99.
$$99 \equiv 1 \pmod 2$$Следовательно, в задании 1б выигрышная стратегия есть у Пети: он начинает с Т и каждый раз продолжает слово единственным возможным образом. Ваня не может перевести игру на ветвь, начинающуюся с Р.
Для задания 2 поменяем местами первую и шестую буквы короткого слова ДГВБАДГВБА. Получим слово АГВБАДГВБД. Новый набор: {АБВГДАБВГДХ, АГВБАДГВБД}.
Теперь Петя вынужден первым ходом написать А, поскольку оба слова начинаются с А. После этого Ваня выбирает вторую букву Г и переводит игру на слово АГВБАДГВБД. Его длина равна 10, поэтому последний ход делает Ваня.
$$10 \equiv 0 \pmod 2$$Стратегия Вани в задании 2: после первого хода Пети А написать Г, а затем каждый раз дописывать единственную букву слова АГВБАДГВБД. При этой стратегии возможна одна партия, заканчивающаяся словом АГВБАДГВБД.
В задании 3 после первого хода Пети В или М Ваня вынужден написать О. Затем анализируются ветви префиксного дерева.
При выборе Петей буквы В возможны ветви ВОРОНА и ВОЛК/ВОЛНА. Ваня выбирает после ВОЛ ветвь ВОЛК, имеющую чётную длину 4. При ветви ВОР продолжение единственное: ВОРОНА имеет длину 6 и также заканчивается ходом Вани.
$$4 \equiv 0 \pmod 2, \quad 6 \equiv 0 \pmod 2$$При выборе Петей буквы М после обязательного О и буквы Р Ваня выбирает букву Я, переводя игру к слову МОРЯНА длины 6. Ветвь МОРИС имела бы нечётную длину 5, а ветвь МОРКОВЬ — нечётную длину 7, поэтому Ваня их не выбирает.
$$6 \equiv 0 \pmod 2$$Таким образом, в задании 3 выигрышная стратегия есть у Вани. Дерево партий при этой стратегии: В → О → (Р → О → Н → А; Л → К) и М → О → Р → Я → Н → А.
1а) Выигрывает Петя: первым пишет А. Возможна 1 партия, конечное слово АБВГДАБВГДХ. 1б) Выигрывает Петя: первым пишет Т и продолжает слово длины 99. 2) Например, после обмена первой и шестой букв короткое слово становится АГВБАДГВБД. Выигрывает Ваня: после первого хода А пишет Г. Возможна 1 партия, конечное слово АГВБАДГВБД. 3) Выигрывает Ваня. Дерево его стратегии: В—О—Р—О—Н—А; В—О—Л—К; М—О—Р—Я—Н—А.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Қате считать длину слова АБВГДАБВГДХ: в нём 11 букв.
Забывать, что первый ход делает Петя, поэтому слова нечётной длины заканчиваются ходом Пети.
В задании 2 менять буквы так, чтобы короткое слово всё равно начиналось с Д: тогда Петя сохраняет выигрышную стратегию на длинной ветви.
В задании 3 выбирать ветви МОРИС или МОРКОВЬ, хотя при правильной стратегии Ваня переводит игру на слово МОРЯНА.