Задание 26 ЕГЭ по информатике · F088DC
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч по своему выбору один камень или увеличить количество камней в куче в два раза. Например, из позиции (10,7) можно получить позиции (11,7), (20,7), (10,8) и (10,14). Игра завершается, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 5 камней, во второй — S камней, где 1≤S≤69. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. В описание стратегии не следует включать ходы, не являющиеся безусловно выигрышными.
Выполните задания 1–3:
1а) Укажите все значения S, при которых Петя может выиграть за один ход.
1б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором это возможно.
2) Укажите значение S, при котором Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Опишите стратегию Пети.
3) Укажите значение S, при котором Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
В начальный момент в первой куче было 5 камней, во второй — S камней, где 1≤S≤69. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. В описание стратегии не следует включать ходы, не являющиеся безусловно выигрышными.
Выполните задания 1–3:
1а) Укажите все значения S, при которых Петя может выиграть за один ход.
1б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором это возможно.
2) Укажите значение S, при котором Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Опишите стратегию Пети.
3) Укажите значение S, при котором Ваня может выиграть первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Рассматривайте отдельно сумму камней и результат удвоения каждой из куч. Для немедленной победы после хода сумма должна стать не меньше 75.
- Из позиции (a,b) возможны позиции (a+1,b), (2a,b), (a,b+1) и (a,2b). Для выигрыша следующим ходом ищите позиции, из которых любой ход соперника приводит к возможности немедленной победы.
- Ответы: в задании 1а 35≤S≤69; в задании 1б минимально S=33; в задании 2 подходит S=32 и первый ход Пети — удвоение первой кучи; в задании 3 подходит S=31.
Решение
1. 1а. Из начальной позиции (5,S) Петя может выиграть одним ходом, если удвоение второй кучи даёт сумму не менее 75: 5+2S≥75. Отсюда S≥35. Удвоение первой кучи требует 10+S≥75, то есть S≥65, что уже входит в найденный диапазон. 35≤S≤69 2. 1б. Петя может сделать невыигрышный ход, удвоив первую кучу: (5,S)→(10,S). Ваня затем удваивает вторую кучу. Для победы Вани нужно 10+2S≥75, поэтому S≥32,5. Минимальное целое значение — S=33. 3. 2. Возьмём S=32. Петя не может выиграть первым ходом, поскольку после удвоения второй кучи сумма равна 69. Петя удваивает первую кучу и получает позицию (10,32). Ваня может получить одну из позиций (11,32), (20,32), (10,33) или (10,64). В первых трёх случаях Петя удваивает вторую кучу, а из (10,64) добавляет один камень. Во всех случаях Петя выигрывает вторым ходом. 4. 3. Возьмём S=31. Если Петя делает ход (5,31)→(6,31), Ваня удваивает первую кучу и получает (12,31). Если Петя получает (10,31) удвоением первой кучи, Ваня добавляет камень во вторую кучу и получает (10,32). Если Петя увеличивает вторую кучу и получает (5,32), Ваня удваивает первую кучу и получает (10,32). Если Петя удваивает вторую кучу и получает (5,62), Ваня удваивает вторую кучу и немедленно выигрывает. 5. Из позиций (12,31) и (10,32) любой ход Пети создаёт Ване возможность выиграть следующим ходом. Например, из (12,31) после ходов Пети (13,31), (24,31), (12,32) или (12,62) Ваня соответственно удваивает вторую кучу, удваивает вторую кучу, удваивает вторую кучу или добавляет камень. Из (10,32) после ходов Пети (11,32), (20,32), (10,33) или (10,64) Ваня соответственно удваивает вторую кучу, удваивает вторую кучу, удваивает вторую кучу или добавляет камень. 6. Таким образом, при S=31 Ваня выигрывает своим первым ходом после хода Пети (5,62), а во всех остальных случаях — своим вторым ходом. Гарантированно выиграть первым ходом Ваня не может, поскольку после хода Пети (5,31)→(6,31) ни один ход Вани не даёт сумму не менее 75.
Частые ошибки
- Указывать $S=65$ как единственный ответ в задании 1а и не учитывать удвоение второй кучи.
- Считать выигрышным ходом позицию с суммой 74: игра заканчивается только при сумме не менее 75.
- Включать в стратегию Пети или Вани ходы, которые не гарантируют победу при любом ответе соперника.
- Строить полное дерево игры вместо дерева, соответствующего выбранной выигрышной стратегии Вани.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока, Петя и Ваня, по очереди приписывают буквы к концу составляемого слова. Каждое промежуточное слово…Игровая стратегия с обоснованием · D4C4D126Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · D9D88826Два игрока, Петя и Ваня, играют в игру. На табличке записана пара неотрицательных целых чисел — позиция.…Игровая стратегия с обоснованием · DBC2CE26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди…Игровая стратегия с обоснованием · E0A14626Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · F3DA8C26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Первый ход делает Петя. За один ход игрок может…Игровая стратегия с обоснованием · F5FB6E26Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при…Игровая стратегия с обоснованием · FAA6DB26Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · FC5679
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.