Задание 21. Дерево игры и выигрышная стратегия: ЕГЭ по информатике

Задание 21 ЕГЭ по информатике проверяет умение анализировать позиционные игры с двумя кучами камней, строить дерево игры и находить выигрышную стратегию для Вани при условии, что у него есть выигрышная стратегия, позволяющая выиграть первым или вторым ходом, но нет гарантированной победы первым…

Что нужно знать

• Игра завершается, когда суммарное количество камней в двух кучах становится не менее 133.
• Ходы: добавить 4 камня в одну из куч или увеличить количество камней в одной из куч в 2 раза.
• Начальная позиция: (17, S), где 1 ≤ S ≤ 115.
• Первый ход делает Петя, затем Ваня, и т.д.
• Выигрышная стратегия — возможность выиграть при любых ходах противника.
• Задание 21 требует найти наименьшее S, при котором у Вани есть выигрышная стратегия, позволяющая выиграть первым или вторым ходом, но нет гарантированной победы первым ходом.

Термины и понятия

• Позиция: пара чисел (a, b), обозначающая количество камней в первой и второй кучах.
• Ход: добавление 4 камней в одну из куч или удвоение количества камней в одной из куч.
• Выигрышная стратегия: способность игрока гарантировать себе победу при любых действиях противника.
• Дерево игры: граф, вершины которого — позиции, а рёбра — возможные переходы между позициями за один ход.
• Выигрыш первым ходом: ситуация, когда игрок может сделать ход, сразу приводящий к победе (сумма камней ≥ 133).
• Выигрыш вторым ходом: ситуация, когда игрок может гарантировать победу на своём втором ходу, но не обязательно на первом.
• Гарантированная победа первым ходом: наличие стратегии, при которой игрок выигрывает своим первым ходом при любых действиях противника.
• Проигрышная позиция: позиция, из которой все ходы ведут в выигрышные для противника позиции.

Частые ошибки

• Путают условия «выиграть первым или вторым ходом» и «нет гарантированной победы первым ходом»: считают, что достаточно только одного из условий.
• Неверно интерпретируют отсутствие гарантированной победы первым ходом: думают, что Ваня вообще не может выиграть первым ходом, хотя это означает лишь наличие хотя бы одной ветви, где Петя избегает…
• Ошибаются в переборе значений S: начинают не с 1 или пропускают наименьшее подходящее значение.
• Строят неполное дерево игры, не рассматривая все возможные ходы Пети и Вани.

Как пройти тему

В курсе «Информатика» тема «Задание 21. Дерево игры и выигрышная стратегия» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Задание 1. Представление и считывание данных в информационных моделях
• Задание 2. Таблицы истинности и логические схемы
• Задание 3. Поиск информации в реляционных базах данных
• Задание 4. Кодирование и декодирование информации
• Задание 5. Формальное исполнение алгоритма
• Задание 6. Результаты работы алгоритмов управления исполнителями

← Предыдущая тема: Задание 20. в тексте части 3 название навыка не приведено
Следующая тема: Задание 22. Математические модели и архитектура компьютеров

Все темы: ЕГЭ по информатике