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