Задание 26 ЕГЭ по информатике · 9E5F1B
Игровая стратегия с обоснованиемВысокаяКЭС 2.13КЭС 2.14
Два игрока, Петя и Ваня, играют в игру с кучей камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу 1 или 3 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 36. Побеждает игрок, сделавший последний ход. В начальный момент в куче было S камней, где 1≤S≤35. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника.
Выполните задания: 1а) укажите все значения S, при которых Петя может выиграть одним ходом; 1б) укажите значение S, при котором Петя не может выиграть одним ходом, но после любого его хода Ваня выигрывает первым ходом, и опишите стратегию Вани. 2) укажите два значения S, при которых Петя не может выиграть одним ходом, но может гарантированно выиграть своим вторым ходом, и опишите его стратегию. 3) укажите значение S, при котором Ваня может гарантированно выиграть первым или вторым ходом, но не может гарантированно выиграть именно первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Выполните задания: 1а) укажите все значения S, при которых Петя может выиграть одним ходом; 1б) укажите значение S, при котором Петя не может выиграть одним ходом, но после любого его хода Ваня выигрывает первым ходом, и опишите стратегию Вани. 2) укажите два значения S, при которых Петя не может выиграть одним ходом, но может гарантированно выиграть своим вторым ходом, и опишите его стратегию. 3) укажите значение S, при котором Ваня может гарантированно выиграть первым или вторым ходом, но не может гарантированно выиграть именно первым ходом. Опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Какие позиции позволяют игроку завершить игру одним ходом? Рассмотрите условия S+1≥36, S+3≥36 и 2S≥36.
- Для анализа позиций отметьте выигрышные за один ход позиции 18,19,…,35. Затем ищите позиции, из которых все возможные ходы переводят игру в такие позиции.
- Ответы: в задании 1а подходят все S от 18 до 35; в задании 1б — S=17; в задании 2 — S=14 и S=16; в задании 3 — S=4. Для задания 3 используйте ответы Вани 5→10, 7→14, 8→16.
Решение
1. Следовательно, в задании 1а все значения S имеют вид 18≤S≤35. 2. Для S=17 Петя может получить позиции 18, 20 или 34. Из каждой из них Ваня выигрывает одним ходом удвоением. Поэтому Петя не выигрывает сразу, а Ваня выигрывает своим первым ходом после любого хода Пети. 17→18, 20, 34 3. Чтобы Петя гарантированно выиграл вторым ходом, ему нужно первым ходом перевести игру в позицию 17: из позиции 17 любой ход Вани даёт 18, 20 или 34, после чего Петя выигрывает удвоением. 14→(+3)17,16→(+1)17 4. Таким образом, в задании 2 подходят S=14 и S=16. В обоих случаях Петя первым ходом получает 17, а затем отвечает на любой ход Вани удвоением: 18→36, 20→40, 34→68. 5. Для задания 3 подходит S=4. Петя не может выиграть первым ходом и может сделать ходы в позиции 5, 7 или 8. Ваня переводит их соответственно в позиции 10, 14 или 16. 4→5→10,4→7→14,4→8→16 6. Из позиции 10 после ходов Пети 11, 13 или 20 Ваня удваивает количество камней и выигрывает. Из позиции 14 после ходов 15, 17 или 28 Ваня также удваивает количество камней. Из позиции 16 после ходов 17, 19 или 32 Ваня выигрывает удвоением. 10→11,13,20;14→15,17,28;16→17,19,32 7. Ваня не может гарантированно выиграть именно первым ходом при S=4, поскольку после хода Пети 4→5, 4→7 или 4→8 позиции 5, 7 и 8 ещё не позволяют Ване немедленно получить 36 камней. Однако после второго хода Вани выигрыш гарантирован. 8. Дерево партий при стратегии Вани: после 4→5 Ваня делает 5→10, после чего возможны 10→11→22, 10→13→26 и 10→20→40. После 4→7 Ваня делает 7→14, после чего возможны 14→15→30, 14→17→34 и 14→28→56. После 4→8 Ваня делает 8→16, после чего возможны 16→17→34, 16→19→38 и 16→32→64.
Частые ошибки
- Указывать только одну позицию из диапазона $18\ldots35$ в задании 1а.
- Считать, что при $S=17$ Петя может выиграть одним ходом.
- Для задания 2 выбирать позиции 14 и 16, но не объяснять перевод в позицию 17.
- Строить полное дерево игры вместо дерева партий, совместимых со стратегией Вани.
- Не указывать ходы Вани после каждого возможного хода Пети.
Источник: Открытый банк ФИПИ
Похожие задания
26Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по…Игровая стратегия с обоснованием · 65C59126Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. Первый ход делает Петя. За один…Игровая стратегия с обоснованием · 69B05B26Два игрока, Петя и Ваня, играют в игру со словами. Дан набор слов русского алфавита, причём ни одно заданное…Игровая стратегия с обоснованием · 9105FD26Два игрока, Петя и Ваня, играют в игру с парой неотрицательных целых чисел. За один ход игрок заменяет одно…Игровая стратегия с обоснованием · 94108326Два игрока, Петя и Ваня, составляют слово из заданного набора слов, по очереди приписывая буквы справа.…Игровая стратегия с обоснованием · AA6D4926Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй — 2…Игровая стратегия с обоснованием · AC676E26Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из букв русского алфавита, при…Игровая стратегия с обоснованием · ADE39726Два игрока, Петя и Ваня, играют с парой неотрицательных целых чисел. Первый ход делает Петя. За один ход…Игровая стратегия с обоснованием · C86EC3
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.