Задание 26 ЕГЭ по информатике · 9105FD
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в игру со словами. Дан набор слов русского алфавита, причём ни одно заданное слово не является началом другого. Игроки по очереди приписывают буквы справа, и каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получает одно из заданных слов целиком. Первый ход делает Петя.
Стратегия игрока — правило, указывающее ход игрока в любой возможной ситуации. Стратегия является выигрышной, если игрок выигрывает при любой игре противника. Множество всех партий при заданной стратегии представляется деревом всех партий.
1. Для набора слов {АБВГДАБВГДХ, ДГВБАДГВБА} определите игрока с выигрышной стратегией, опишите стратегию, укажите количество возможных партий и конечное слово в каждой партии.
2. Для набора слов {ТРИ..., РИТА...}, где слово ТРИ повторено 33 раза и имеет длину 99 букв, а слово РИТА повторено 44 раза и имеет длину 176 букв, определите игрока с выигрышной стратегией и опишите её.
3. В задании 1 измените перестановкой двух букв в более коротком слове так, чтобы выигрышная стратегия была у другого игрока. Запишите полученный набор слов, опишите стратегию, укажите число возможных партий и конечное слово в каждой партии.
4. Для набора слов {СОЛНЦЕ, СОВА, СОВЕТ, ПРОСО, ПРОХОР, ПРОИЗВОДНАЯ} определите игрока с выигрышной стратегией и представьте дерево всех партий, возможных при этой стратегии.
Стратегия игрока — правило, указывающее ход игрока в любой возможной ситуации. Стратегия является выигрышной, если игрок выигрывает при любой игре противника. Множество всех партий при заданной стратегии представляется деревом всех партий.
1. Для набора слов {АБВГДАБВГДХ, ДГВБАДГВБА} определите игрока с выигрышной стратегией, опишите стратегию, укажите количество возможных партий и конечное слово в каждой партии.
2. Для набора слов {ТРИ..., РИТА...}, где слово ТРИ повторено 33 раза и имеет длину 99 букв, а слово РИТА повторено 44 раза и имеет длину 176 букв, определите игрока с выигрышной стратегией и опишите её.
3. В задании 1 измените перестановкой двух букв в более коротком слове так, чтобы выигрышная стратегия была у другого игрока. Запишите полученный набор слов, опишите стратегию, укажите число возможных партий и конечное слово в каждой партии.
4. Для набора слов {СОЛНЦЕ, СОВА, СОВЕТ, ПРОСО, ПРОХОР, ПРОИЗВОДНАЯ} определите игрока с выигрышной стратегией и представьте дерево всех партий, возможных при этой стратегии.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Рассматривайте каждую позицию как вершину дерева префиксов. Если из позиции можно сразу получить заданное слово, ходивший выигрывает.
- Для единственной цепочки длины n победитель определяется чётностью n: при нечётной длине выигрывает Петя, при чётной — Ваня.
- В пункте 1 Петя выбирает первую букву А и получает слово АБВГДАБВГДХ за 11-й ход. Во втором наборе он выбирает ветвь ТРИ... длины 99.
Решение
1. В первом наборе слова начинаются с разных букв: А и Д. Если Петя начинает с А, все последующие буквы однозначно определены, и слово АБВГДАБВГДХ получается на 11-м ходу. Нечётный номер хода означает победу Пети. 11≡1(mod2) 2. Если Петя начинает с Д, слово ДГВБАДГВБА получается на 10-м ходу, поэтому победил бы Ваня. Следовательно, выигрышная стратегия Пети — первым написать А, затем каждый раз приписывать единственную возможную букву. 10≡0(mod2) 3. При этой стратегии возможна ровно одна партия: А → АБ → АБВ → АБВГ → АБВГД → АБВГДА → АБВГДАБ → АБВГДАБВ → АБВГДАБВГ → АБВГДАБВГД → АБВГДАБВГДХ. 4. Во втором наборе длина слова ТРИ... равна 99, а длина слова РИТА... равна 176. Петя первым пишет Т, после чего все ходы однозначны. Слово длины 99 завершается ходом Пети, поэтому он выигрывает. 99≡1(mod2) 5. В пункте 4 Петя может начать с буквы С. После этого Ваня получает префикс С. Единственное продолжение — О, затем Петя получает префикс СО. 6. Из позиции СО Петя может выбрать Л или В. При выборе Л получается цепочка СОЛНЦЕ, которая завершается на 6-м ходу и приносит победу Ване. Поэтому в выигрышной стратегии Петя выбирает В. 7. После префикса СОВ Ваня может выбрать А или Е. При выборе А слово СОВА завершается на 4-м ходу и выигрывает Ваня. При выборе Е слово СОВЕТ завершается на 5-м ходу и выигрывает Петя. Следовательно, стратегия Пети в этой ветви — на втором ходу написать В; далее результат зависит от выбора Вани. 4 — победа Вани,5 — победа Пети 8. Полное дерево при стратегии Пети, начинающейся с С: С → СО → СОЛ → СОЛН → СОЛНЦ → СОЛНЦЕ; либо С → СО → СОВ → СОВА; либо С → СО → СОВ → СОВЕ → СОВЕТ. Если Ваня на позиции СОВ выбирает А, он выигрывает; если выбирает Е, выигрывает Петя. 9. Таким образом, в пункте 4 у Пети есть выигрышная стратегия, но дерево всех партий при этой стратегии содержит партию, заканчивающуюся победой Вани, если Петя ошибочно выбирает Л. Поэтому корректное дерево выигрышной стратегии Пети должно исключать переход СО → СОЛ и включать только ветвь СО → СОВ.
Частые ошибки
- Определять победителя только по длине слова, не учитывая выбор первой буквы.
- Забывать, что Петя может выбирать между несколькими начальными буквами.
- В пункте 4 считать ветвь СОЛНЦЕ частью выигрышной стратегии Пети.
- В пункте 3 утверждать, что одной перестановкой можно получить выигрыш Вани, не проверив первые две буквы общего префикса.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 5787DA26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · 64BBD826Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · 65C59126Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. Первый ход делает Петя. За один…Игровая стратегия с обоснованием · 69B05B26Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно…Игровая стратегия с обоснованием · 94108326Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За…Игровая стратегия с обоснованием · 9E5F1B26Два игрока, Петя и Ваня, составляют слово из заданного набора слов, по очереди приписывая буквы справа.…Игровая стратегия с обоснованием · AA6D4926Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй — 2…Игровая стратегия с обоснованием · AC676E
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.