Precettore

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

Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, во второй куче — S камней, где 1≤S≤69.
Выполните задания 1–3: определите значения S, при которых Петя или Ваня имеют выигрышную стратегию, опишите соответствующие стратегии и для задания 3 постройте дерево всех партий, возможных при реализации выигрышной стратегии Вани.

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

Подсказки (3)
  1. Рассмотрите все четыре возможных хода из позиции (a,b): (a+1,b), (2a,b), (a,b+1) и (a,2b).
  2. Позиция выигрышна за один ход, если после удвоения одной из куч или добавления одного камня сумма становится не менее 77.
  3. Для задания 1 получаются ответы: а) 35≤S≤69; б) S=18. Для задания 2 подходит S=31, а для задания 3 — S=30.
Решение
1. Из начальной позиции (7,S) Петя может выиграть первым ходом, если удвоение второй кучи даёт сумму не менее 77: 7+2S≥77, то есть S≥35. Удвоение первой кучи даёт условие 14+S≥77, то есть S≥63, которое уже входит в найденный диапазон. Поэтому ответ к заданию 1а: S=35,36,…,69.

2. Для задания 1б достаточно взять минимальное S, при котором после неудачного хода Пети Ваня выигрывает сразу. При S=18 Петя может удвоить вторую кучу и получить позицию (7,36). Ваня удваивает вторую кучу и получает (7,72), сумма равна 79. При меньших значениях S такой возможности нет. Ответ: S=18.

3. Для задания 2 берём S=31. Петя не выигрывает первым ходом, поскольку после любого его хода сумма остаётся меньше 77. Петя удваивает первую кучу и получает позицию (14,31).

4. После хода Пети из (14,31) Ваня может получить одну из позиций (15,31), (28,31), (14,32) или (14,62). В каждой из них Петя выигрывает следующим ходом: соответственно удваивает вторую кучу, удваивает первую кучу, удваивает вторую кучу или удваивает любую подходящую кучу. Следовательно, при S=31 Петя выигрывает своим вторым ходом независимо от хода Вани.

5. Для задания 3 берём S=30. Петя не может выиграть первым ходом. После каждого возможного первого хода Пети Ваня выбирает ход, после которого любой ответ Пети позволяет Ване выиграть следующим ходом либо Ваня выигрывает сразу.

6. Если Петя получает (8,30), Ваня удваивает первую кучу и получает (16,30). Если Петя получает (14,30), Ваня также удваивает первую кучу и получает (28,30). Если Петя получает (7,31), Ваня удваивает первую кучу и получает (14,31). Если Петя получает (7,60), Ваня сразу удваивает вторую кучу и выигрывает.

7. Из позиций (16,30), (28,30) и (14,31) любой ход Пети создаёт для Вани возможность немедленно получить сумму не менее 77. При этом Ваня не может гарантированно выиграть первым ходом из исходной позиции, поскольку, например, после хода Пети (8,30) сумма ещё меньше 77 и Ваня должен подготовить выигрыш на следующий ход.

8. Дерево партий при стратегии Вани можно представить таблицей. В каждой строке указана позиция после хода Пети, затем ход Вани и позиция после него: (7,30)→(8,30)→(16,30); (7,30)→(14,30)→(28,30); (7,30)→(7,31)→(14,31); (7,30)→(7,60)→(7,120). Из позиций (16,30), (28,30) и (14,31) все возможные ходы Пети приводят к немедленной победе Вани.
Частые ошибки
  • Указывать только один возможный ход противника вместо всех ходов, предусмотренных выигрышной стратегией.
  • Считать выигрышным ход, после которого сумма равна 76.
  • Включать в дерево полное дерево игры, включая ходы, которые не соответствуют выбранной стратегии Вани.
  • Забывать, что игрок, первым получивший сумму не менее 77, сразу выигрывает и дальнейшие ходы из этой позиции не рассматриваются.

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

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

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

26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · D9D88826Два игрока, Петя и Ваня, играют в игру. На табличке записана пара неотрицательных целых чисел — позиция.…Игровая стратегия с обоснованием · DBC2CE26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · E0A14626Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · F088DC26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Первый ход делает Петя. За один ход игрок может…Игровая стратегия с обоснованием · F5FB6E26Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при…Игровая стратегия с обоснованием · FAA6DB26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · FC5679

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

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

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

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

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

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

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

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