Задание 26 ЕГЭ по информатике · FAA6DB

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

1. В задании 1а слова начинаются с разных букв: А и Д. Петя выбирает букву А. После этого все ходы однозначны, и будет написано слово АБВГДАБВГДХ длины 11. Последний, 11-й ход делает Петя, поэтому Петя выигрывает. При этой стратегии возможна одна партия.

2. В задании 1б Петя выбирает букву Т. Далее продолжение однозначно: ТРИ повторяется 33 раза, длина слова равна 99. Последнюю букву пишет Петя, поэтому выигрышная стратегия есть у Пети.

3. Для задания 2 поменяем местами первую букву Д и первую из букв А в коротком слове ДГВБАДГВБА. Получим набор {АБВГДАБВГДХ, АГВБДДГВБА}. После первого хода Петя пишет А. Ваня выбирает букву Г, после чего продолжение однозначно и заканчивается словом АГВБДДГВБА длины 10. Последнюю букву пишет Ваня. Возможна одна партия.

4. В задании 3 рассмотрим ветвь, начинающуюся с Б. После ходов Б, Р, О на позиции БРО ходит Ваня. Он может выбрать С, Ш или Н. В каждом случае Петя получает последнее слово: БРОСЬ, БРОШКА или БРОНХИТ. Следовательно, при первом ходе Б Петя гарантированно выигрывает.

5. Ветвь, начинающаяся с С, не даёт Пете выигрышной стратегии: после образования СОВА последнюю букву получает Ваня, а на ветви СОЛНЦЕ последнюю букву также получает Ваня. Поэтому Петя выбирает начальную букву Б.

6. Дерево партий при стратегии Пети в задании 3: Б → Р → О, после чего Ваня выбирает одну из трёх букв: С → Ь, Ш → К → А, Н → Х → И → Т.