Precettore

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

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

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

Подсказки (3)
  1. Разметьте позиции как выигрышные и проигрышные для игрока, которому предстоит ходить. Позиция выигрышная, если из неё можно сделать ход в проигрышную позицию.
  2. Если сумма камней после хода становится не менее 74, игра сразу заканчивается. Для остальных позиций проверяйте четыре возможных хода: увеличение каждой кучи на 1 и утроение каждой кучи.
  3. Для позиции (4, 23) любой первый ход Пети позволяет Ване немедленно выиграть следующим ходом. Аналогично проверяются позиции (7, 22), (4, 22), (6, 22) и (5, 22); результаты нужно обосновать перечислением ответных ходов и построением дерева.
Решение
1. Для каждой позиции рассматриваются четыре возможных хода: (a+1,b), (3a,b), (a,b+1), (a,3b). Если после хода сумма не менее 74, ход является немедленно выигрышным.

2. В позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. После любого хода Пети Ваня получает возможность закончить игру или перевести её в позицию, из которой Петя вынужден открыть Ване немедленную победу.
W(4,23)=W(7,22)=Ваня

3. В позиции (4,22) Петя утрачивает преимущество первого хода: любой его ход позволяет Ване применить выигрышный ответ. То же верно для позиции (6,22). Следовательно, в обеих позициях выигрышная стратегия есть у Вани.
W(4,22)=W(6,22)=Ваня

4. В позиции (5,22) Петя имеет выигрышную стратегию: первым ходом он увеличивает первую кучу на один камень и получает позицию (6,22). Далее Петя использует выигрышные ответы, соответствующие позиции (6,22), не допуская перехода в позицию, где Ваня может завершить игру.
(5,22)→(6,22)

5. Дерево партий строится только по ходам, совместимым с этой стратегией Пети. В каждой вершине указываются все возможные ходы Вани, а для каждого такого хода — единственный безусловно выигрышный ответ Пети. Ветки, в которых Петя делает невыигрышный ход, в дерево не включаются.
Частые ошибки
  • Считать выигрышной любую позицию, из которой существует хотя бы один удачный ход, не проверяя все возможные ответы противника.
  • Включать в дерево партии, в которых игрок, обладающий стратегией, сам выбирает невыигрышный ход.
  • Забывать, что игра заканчивается сразу после достижения суммы 74 и более.
  • Путать позицию, выигрышную для игрока, которому предстоит ходить, с позицией, выигрышной для игрока, который ходил последним.

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

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

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

26Два игрока, Петя и Ваня, играют с двумя кучами камней. За один ход игрок может добавить в одну из куч один…Игровая стратегия с обоснованием · 2A0A1926Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 3BC11226Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 5787DA26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · 64BBD826Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. Первый ход делает Петя. За один…Игровая стратегия с обоснованием · 69B05B26Два игрока, Петя и Ваня, играют в игру со словами. Дан набор слов русского алфавита, причём ни одно заданное…Игровая стратегия с обоснованием · 9105FD26Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно…Игровая стратегия с обоснованием · 94108326Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За…Игровая стратегия с обоснованием · 9E5F1B

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

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

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

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

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

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

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

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