Главная / Задания ЕГЭ / Задание 21
Задание 21 ЕГЭ по информатике
Теория игр: стратегия Вани. Нужно найти S, при котором у Вани есть стратегия выиграть первым или вторым ходом, но нет стратегии выиграть гарантированно первым.
Как решать
- Для каждого хода Пети проверьте, может ли Ваня выиграть за 1 или 2 своих хода.
- Исключите S, где Ваня всегда выигрывает первым ходом.
Частые ошибки
- Забывают второе условие — «не гарантированно первым ходом».
Пример задания
Два игрока, Петя и Ваня, играют в следующую игру. Игроки ходят по очереди, первый ход делает Петя. Перед игроками лежат две кучи камней. За один ход игрок может по своему выбору выполнить одно из действий с одной из куч:
• добавить 3 камня;
• увеличить количество камней в 3 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 137. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 6 камней, во второй — S камней; 1 ≤ S ≤ 130.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Для игры, описанной выше, найдите наименьшее значение S, при котором одновременно выполняются два условия:
• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
• добавить 3 камня;
• увеличить количество камней в 3 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 137. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 6 камней, во второй — S камней; 1 ≤ S ≤ 130.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Для игры, описанной выше, найдите наименьшее значение S, при котором одновременно выполняются два условия:
• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Показать ответ и разбор
Ответ: 36
Ваня гарантированно выигрывает первым или вторым ходом, но не всегда первым, при S = 36, 41. Наименьшее — 36.
В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.
Все задания ЕГЭ
1Граф и таблица2Таблица истинности3Базы данных4Условие Фано5Алгоритм6Черепаха7Звук и изображения8Комбинаторика9Электронные таблицы10IP-адреса11Количество информации12Исполнитель МТ13Количество программ14Системы счисления15Логика с параметром16Рекурсия17Последовательности18Робот и таблица19Теория игр20Теория игр21Теория игр22Процессы23Взвешенный граф24Символьные строки25Делители и маски26Сортировка и жадные алгоритмы27Кластеры
Нужна помощь с ЕГЭ?
На пробном уроке посмотрим ваш уровень по 2–3 темам ЕГЭ по информатике и составим план подготовки.
Записаться на пробный урок