Задание 26 ЕГЭ по информатике · 19C1EE
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, как только суммарное количество камней в кучах становится не менее 74. Побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, во второй — S камней, где 1≤S≤67.
Опишите выигрышные стратегии и постройте дерево партий, возможных при выигрышной стратегии Вани.
Опишите выигрышные стратегии и постройте дерево партий, возможных при выигрышной стратегии Вани.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Для выигрыша одним ходом проверьте, может ли после добавления камня сумма стать не менее 74 или может ли утроение одной из куч дать сумму не менее 74.
- Для анализа второго хода рассмотрите все четыре позиции, получаемые после первого хода: (7,S), (18,S), (6,S+1) и (6,3S).
- Петя выигрывает первым ходом при S≥23. При S=8 Петя утроивает вторую кучу и получает позицию (6,24); после любого хода Вани Петя завершает игру следующим ходом.
Решение
1. Из начальной позиции (6,S) Петя может выиграть за один ход утроением второй кучи, если 6+3S≥74. Отсюда S≥23. При меньших значениях утроение первой кучи и добавление одного камня также не дают выигрыша.
6+3S≥74⟺S≥683⟺S≥23
2. Следовательно, в задании 1а подходят все значения S от 23 до 67.
3. Для пункта 1б рассмотрим неудачный ход Пети — утроение второй кучи. При S=8 получается позиция (6,24). Ваня утроением второй кучи получает (6,72) и затем выигрывает добавлением двух камней? Точнее, Ваня сразу утроивает первую кучу и получает (18,24), после чего сумма равна 42; выигрышным является утроение второй кучи до (6,72), после чего следующий ход уже не требуется, поскольку в данной позиции сумма меньше 74. Поэтому минимальный случай определяется проверкой всех ходов и равен S=8.
4. При S=8 Петя не может выиграть сразу, но ходом (6,8)→(6,24) создаёт позицию, после которой любой ход Вани позволяет Пете получить сумму не менее 74: из (7,24) утроением второй кучи, из (18,24) утроением второй кучи, из (6,25) утроением второй кучи, а после (6,72) игра уже заканчивается.
5. Для задания 3 подходит S=18. Ваня после первого хода Пети выбирает ход, переводящий игру в позицию, из которой он гарантированно выигрывает первым или вторым ходом. Стратегия Вани строится разбором четырёх возможных первых ходов Пети.
6+3S≥74⟺S≥683⟺S≥23
2. Следовательно, в задании 1а подходят все значения S от 23 до 67.
3. Для пункта 1б рассмотрим неудачный ход Пети — утроение второй кучи. При S=8 получается позиция (6,24). Ваня утроением второй кучи получает (6,72) и затем выигрывает добавлением двух камней? Точнее, Ваня сразу утроивает первую кучу и получает (18,24), после чего сумма равна 42; выигрышным является утроение второй кучи до (6,72), после чего следующий ход уже не требуется, поскольку в данной позиции сумма меньше 74. Поэтому минимальный случай определяется проверкой всех ходов и равен S=8.
4. При S=8 Петя не может выиграть сразу, но ходом (6,8)→(6,24) создаёт позицию, после которой любой ход Вани позволяет Пете получить сумму не менее 74: из (7,24) утроением второй кучи, из (18,24) утроением второй кучи, из (6,25) утроением второй кучи, а после (6,72) игра уже заканчивается.
5. Для задания 3 подходит S=18. Ваня после первого хода Пети выбирает ход, переводящий игру в позицию, из которой он гарантированно выигрывает первым или вторым ходом. Стратегия Вани строится разбором четырёх возможных первых ходов Пети.
Частые ошибки
- Считать выигрышем позицию, в которой сумма камней ещё меньше 74.
- Рассматривать только добавление одного камня и забывать об утроении кучи.
- Включать в стратегию ходы, которые не гарантируют победу независимо от ответа соперника.
- Строить полное дерево игры вместо дерева партий, совместимых с выигрышной стратегией.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 2 или 3 камня…Игровая стратегия с обоснованием · 09074E26Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно…Игровая стратегия с обоснованием · 0A0E9526Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · 0BEB2926Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно добавить в…Игровая стратегия с обоснованием · 1226B926Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно добавить в…Игровая стратегия с обоснованием · 268C0A26Два игрока, Петя и Ваня, играют с двумя кучами камней. За один ход игрок может добавить в одну из куч один…Игровая стратегия с обоснованием · 2A0A1926Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 3BC11226Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 5787DA
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.