Задание 26 ЕГЭ по информатике · D4C4D1
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, по очереди приписывают буквы к концу составляемого слова. Каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получает одно из заданных слов целиком. Первый ход делает Петя. Ни одно из заданных слов не является началом другого.
Стратегия игрока — это правило, указывающее игроку ход в любой встретившейся ситуации. Стратегия называется выигрышной, если игрок выигрывает при любой игре противника. Дерево всех партий для заданной стратегии содержит позиции игры в узлах и ходы на рёбрах; корнем является начальная позиция.
1а) Определите, у кого есть выигрышная стратегия при наборе слов {АБВГДАБВГДХ, ДГВБАДГВБА}. Опишите стратегию. Укажите количество различных партий при этой стратегии и конечное слово каждой партии.
1б) Определите, у кого есть выигрышная стратегия при наборе слов {ТРИ, повторённое 33 раза, РИТА, повторённое 44 раза}. Длина первого слова — 99 букв, длина второго — 176 букв. Опишите стратегию.
2) В задании 1а поменяйте местами две буквы в более коротком слове так, чтобы выигрышная стратегия была у другого игрока. Запишите полученный набор слов, опишите выигрышную стратегию, укажите количество различных партий при этой стратегии и конечное слово каждой партии.
3) Для набора слов {ВОРОНА, ВОЛК, ВОЛНА, КРОНА, КРОШКА, КРОКОДИЛИЩЕ} определите игрока, у которого есть выигрышная стратегия. Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.
Стратегия игрока — это правило, указывающее игроку ход в любой встретившейся ситуации. Стратегия называется выигрышной, если игрок выигрывает при любой игре противника. Дерево всех партий для заданной стратегии содержит позиции игры в узлах и ходы на рёбрах; корнем является начальная позиция.
1а) Определите, у кого есть выигрышная стратегия при наборе слов {АБВГДАБВГДХ, ДГВБАДГВБА}. Опишите стратегию. Укажите количество различных партий при этой стратегии и конечное слово каждой партии.
1б) Определите, у кого есть выигрышная стратегия при наборе слов {ТРИ, повторённое 33 раза, РИТА, повторённое 44 раза}. Длина первого слова — 99 букв, длина второго — 176 букв. Опишите стратегию.
2) В задании 1а поменяйте местами две буквы в более коротком слове так, чтобы выигрышная стратегия была у другого игрока. Запишите полученный набор слов, опишите выигрышную стратегию, укажите количество различных партий при этой стратегии и конечное слово каждой партии.
3) Для набора слов {ВОРОНА, ВОЛК, ВОЛНА, КРОНА, КРОШКА, КРОКОДИЛИЩЕ} определите игрока, у которого есть выигрышная стратегия. Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Рассмотрите дерево префиксов заданных слов. Для каждой позиции определите, кто ходит и является ли позиция выигрышной.
- Если из позиции существует ход в проигрышную для соперника позицию, текущий игрок может выиграть. Если все возможные ходы ведут в выигрышные позиции соперника, позиция проигрышная.
- В задании 1а Петя начинает с буквы А и получает слово длины 11. В изменённом наборе можно поменять местами первую и пятую буквы короткого слова: ДГВБАДГВБА превращается в АГВБДДГВБА. В задании 3 Ваня после КРО может выбрать продолжение Ш и получить КРОШКА.
Решение
1. В задании 1а первое слово начинается с А, второе — с Д. Петя может выбрать любую из этих букв.
2. Если Петя выбирает А, дальнейшее продолжение однозначно и заканчивается словом АБВГДАБВГДХ длины 11. Последнюю, одиннадцатую, букву дописывает Петя, поэтому Петя выигрывает.
3. Если Петя выбирает Д, продолжение однозначно и заканчивается словом ДГВБАДГВБА длины 10. Последнюю букву дописывает Ваня, поэтому выигрывает Ваня. Следовательно, выигрышная стратегия есть у Пети: сразу написать А. При этой стратегии возможна одна партия, заканчивающаяся словом АБВГДАБВГДХ.
4. В задании 1б Петя пишет первую букву Т. Далее продолжение определяется однозначно: Т, Р, И повторяются 33 раза. Длина слова равна 99, поэтому последнюю букву дописывает Петя. Выигрышная стратегия есть у Пети.
5. Для задания 2 поменяем местами первую и пятую буквы короткого слова ДГВБАДГВБА. Получим слово АГВБДДГВБА. Новый набор: {АБВГДАБВГДХ, АГВБДДГВБА}.
6. Петя вынужден начать буквой А. Ваня дописывает Г, после чего продолжение однозначно приводит к слову АГВБДДГВБА длины 10. Последнюю букву дописывает Ваня. Поэтому выигрышная стратегия есть у Вани: после первого хода А написать Г. При этой стратегии возможна одна партия, заканчивающаяся словом АГВБДДГВБА.
7. В задании 3 Петя первым ходом может выбрать В или К. Если он выбирает В, Ваня пишет О. Затем Петя может выбрать Р или Л.
8. При продолжении ВОР дальнейшие буквы определяются однозначно, и получается ВОРОНА. Это слово имеет длину 6, поэтому его последнюю букву пишет Ваня.
9. При продолжении ВОЛ Ваня выбирает К и получает слово ВОЛК длины 4, заканчивая игру своим ходом. Если бы Ваня выбрал Н, Петя получил бы ВОЛНА и выиграл, поэтому выигрышный ход Вани — К.
10. Если Петя начинает с К, продолжение КРО является вынужденным. После этого Ваня выбирает Ш и получает КРОШКА длины 6, заканчивая игру своим ходом. Следовательно, независимо от первого хода Пети Ваня может выиграть.
11. Дерево партий при стратегии Вани содержит три партии: ВОРОНА, ВОЛК и КРОШКА.Частые ошибки
- Определять победителя только по длине слова и не учитывать возможность выбора первой буквы.
- Забывать, что выигрышная стратегия должна работать при любом ходе противника.
- В задании 2 менять буквы не в более коротком слове.
- В задании 3 выбирать ВОЛНА или КРОНА, хотя Ваня может выбрать более выгодное продолжение.
- Не указывать все партии, возможные при заданной стратегии.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй — 2…Игровая стратегия с обоснованием · AC676E26Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при…Игровая стратегия с обоснованием · ADE39726Два игрока, Петя и Ваня, играют с парой неотрицательных целых чисел. Первый ход делает Петя. За один ход…Игровая стратегия с обоснованием · C86EC326Два игрока по очереди дописывают буквы справа, составляя одно из заданных слов. После каждого хода полученная…Игровая стратегия с обоснованием · D4C41926Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · D9D88826Два игрока, Петя и Ваня, играют в игру. На табличке записана пара неотрицательных целых чисел — позиция.…Игровая стратегия с обоснованием · DBC2CE26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · E0A14626Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · F088DC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.