Precettore

Задание 26 ЕГЭ по информатике · 06BC06

Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается, когда суммарное количество камней в кучах становится не менее 71. Побеждает игрок, сделавший последний ход.
Задание 1. Для каждой из начальных позиций (4, 33), (6, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 2. Для каждой из начальных позиций (4, 32), (5, 32), (6, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Задание 3. Для начальной позиции (5, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии.

Развёрнутый ответ: проверяется по критериям ФИПИ.

Подсказки (3)
  1. Рассматривайте позицию как выигрышную, если из неё можно одним ходом перейти в проигрышную позицию. Проигрышная позиция — та, из которой любой ход ведёт в выигрышную.
  2. Для позиции (5, 31) выгодно первым ходом получить позицию (6, 31). Для позиций (4, 32), (5, 32) и (6, 31) проверьте все четыре возможных хода.
  3. Петя выигрывает из (5, 31), добавив один камень в первую кучу. После хода Вани из (6, 31) возможны позиции (7, 31), (12, 31), (6, 32), (6, 62). В каждом случае у Пети есть ответный выигрышный ход.
Решение
1. Из позиции (4, 33) Петя удваивает вторую кучу и получает позицию (4, 66), в которой сумма камней равна 70. После любого хода Вани Петя получает возможность завершить игру, а непосредственно из (4, 33) также можно удвоить вторую кучу до (4, 66), после чего Ваня вынужден сделать ход.

2. Однако более сильный непосредственный ход из позиции (4, 33) — удвоить вторую кучу: получается (4, 66), сумма равна 70. Ваня может добавить камень или удвоить одну из куч, после чего сумма станет не менее 71. Поэтому Петя выигрывает первым ходом.

3. Из позиции (6, 32) Петя удваивает вторую кучу и получает (6, 64), после чего сумма равна 70. Любой следующий ход Вани приводит к сумме не менее 71, поэтому победителем становится Ваня, а не Петя. Следовательно, этот ход не является выигрышным для Пети; нужно рассматривать все ходы.

4. Позиция (6, 32) является выигрышной для Пети: он удваивает первую кучу и получает (12, 32), после чего применяет стратегию сведения к проигрышной позиции для Вани. При полном переборе ходов видно, что у Пети существует выигрышная стратегия.

5. Для позиции (4, 32) Петя добавляет один камень в первую кучу и получает позицию (5, 32). Позиция (5, 32) является проигрышной для игрока, которому предстоит ходить: каждый возможный ход из неё переводит игру в выигрышную позицию для соперника. Поэтому из (4, 32) выигрывает Петя.

6. Позиция (5, 32) является проигрышной. Ваня выигрывает из неё при любой игре Пети, отвечая на ход так, чтобы сохранить для Пети выигрышную позицию. В частности, все четыре возможных перехода из (5, 32) ведут в позиции, из которых следующий игрок имеет выигрышный ход.

7. Позиция (6, 31) также является проигрышной. Поэтому в начальной позиции (5, 31) Петя добавляет один камень в первую кучу и переводит игру в (6, 31). После этого Ваня вынужден сделать ход из проигрышной для него позиции.

8. Если Ваня из (6, 31) получает (7, 31), Петя удваивает вторую кучу и получает (7, 62). Если Ваня получает (12, 31), Петя удваивает вторую кучу и получает сумму не менее 71. Если Ваня получает (6, 32), Петя удваивает вторую кучу и также немедленно заканчивает игру. Если Ваня получает (6, 62), Петя удваивает первую кучу и немедленно заканчивает игру.

9. В ветви (7, 31) после хода Пети в (7, 62) сумма равна 69. Ваня может получить (8, 62), (7, 63), (14, 62) или (7, 124). В первых двух случаях Петя добавляет один камень в соответствующую кучу и получает сумму не менее 71; в последних двух случаях игра заканчивается сразу после хода Вани.
Частые ошибки
  • Считать позицию с суммой 70 уже оконченной: игра заканчивается только при сумме не менее 71.
  • Включать в стратегию ходы, которые не гарантируют победу независимо от ответа соперника.
  • Строить полное дерево игры вместо дерева партий, совместимых с выигрышной стратегией.
  • Путать игрока, который создал позицию с суммой не менее 71, с игроком, которому предстоит следующий ход.

Источник: Открытый банк ФИПИ

ПредыдущееСледующееВсе задания №26

Похожие задания

26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826Два игрока, Петя и Ваня, играют в следующую игру. У игроков есть табличка, на которой записана пара…Игровая стратегия с обоснованием · 07474E26Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 2 или 3 камня…Игровая стратегия с обоснованием · 09074E26Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно…Игровая стратегия с обоснованием · 0A0E9526Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · 0BEB2926Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно добавить в…Игровая стратегия с обоснованием · 1226B926Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 19C1EE26Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно добавить в…Игровая стратегия с обоснованием · 268C0A

Нужен репетитор по информатике?

Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.

Репетиторы по информатике

Подбор репетитора

Напишите, что нужно, — команда Precettore подберёт репетитора и свяжется с вами.

Готовьтесь к ЕГЭ по информатике в Precettore

Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.

Начать бесплатноЯ репетитор