Задания 20, 21 ЕГЭ по информатике: Аналитическое решение демоварианта

Задачи на теорию игр (20 и 21) являются одними из наиболее сложных на ЕГЭ по информатике. Несмотря на возможность их решения при помощи компьютерного перебора, изначально разработчики демоварианта предлагали ручное (аналитическое) решение. Цель данной статьи – показать методы выполнения аналитического решения названных задач.

В демоварианте в заданиях 20 и 21 используется одна и та же игра. Если сократить её описание, отбросив пояснения и примеры, получим следующие правила.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.

В задании 20 требуется найти два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 20 ЕГЭ Информатика: решение.

Пусть после первого хода Пети образовались две кучи из t и b камней, причём t < b. Теперь должно выполняться t + 2b < 77, иначе Ваня выиграет, удвоив кучку из b камней, что не удовлетворяет условию. Также должно выполняться t + 1 + 2b ≥ 77, иначе Ваня может прибавить 1 камень к меньшей кучке. Тогда, даже добавив наибольшее возможное число камней (удваивая кучку b), Петя не сможет выиграть вторым ходом, что также не удовлетворяет условию.

Следовательно, после первого хода Пети должно выполняться равенство t + 2b = 76.

Отдельно следует рассмотреть случай t = b после первого хода Пети. По аналогии с предыдущими рассуждениями получим неравенства 3t < 77 и 3t + 2 ≥ 77, откуда t = 25. Введём термин полуход – ход одного игрока. Позиция (25, 25) недостижима за один полуход (и даже за два полухода, что понадобится в задаче 21), поэтому случай t = b может быть здесь и далее отброшен.

Итак, после первого хода Пети t < b и t + 2b = 76. Отсюда, в частности, следует b ≥ 26 (иначе t + 2b < 3b ≤ 75), что понадобится нам при переборе вариантов.

Так как до хода Пети позиция была (7, s), то возможны 4 варианта первого хода.

1. (8, s). Тогда 8 + 2s = 76; s = 34.

2. (7, s + 1). Тогда 7 + 2(s + 1) = 76. Целых корней нет.

3. (7, 2s). Тогда 7 + 4s = 76. Целых корней нет.

4. (14, s). Тогда 14 + 2s = 76; s = 31.

Ответ (на задачу 20): 31; 34.

В задании 21 требуется найти минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Разбор 21 задания ЕГЭ по информатике.

Как мы уже выяснили, перед последними двумя полуходами выигрывающий игрок (в данном случае Ваня) должен создать особую позицию (t, b), где t < b и t + 2b = 76. Так как Ваня должен выиграть независимо от действий Пети, то указанную особую позицию Ваня должен суметь создать из каждой возможной перед своим ходом: (8, s), (7, s + 1), (7, 2s), (14, s). Также следует учесть, что иногда Ваня может (вместо создания этой особой позиции) просто сразу выиграть, получив 77 и более камней в кучках.

1. (8, s).

1.1. (9, s). Тогда 9 + 2s = 76. Целых корней нет.

1.2. (8, s + 1). Тогда 8 + 2(s + 1) = 76; s = 33.

1.3. (16, s). Тогда 16 + 2s = 76; s = 30.

1.4. (8, 2s). Тогда 8 + 4s = 76; s = 17.

1.5. Быстрый выигрыш при 8 + 2s ≥ 77; s ≥ 35.

Здесь победные для Вани значения s – это {17; 30; 33} ∪ [35; +∞).

2. (7, s + 1).

2.1. (8, s + 1). Тогда 8 + 2(s + 1) = 76; s = 33.

2.2. (7, s + 2). Тогда 7 + 2(s + 2) = 76. Целых корней нет.

2.3. (14, s + 1). Тогда 14 + 2(s + 1) = 76; s = 30.

2.4. (7, 2s + 2). Тогда 7 + 2(2s + 2) = 76. Целых корней нет.

2.5. Быстрый выигрыш при 7 + 2s + 2 ≥ 77; s ≥ 34.

Здесь победные для Вани значения s – это {30; 33} ∪ [34; +∞).

3. (7, 2s).

3.1. (8, 2s). Тогда 8 + 4s = 76; s = 17.

3.2. (7, 2s + 1). Тогда 7 + 2(2s + 1) = 76. Целых корней нет.

3.3. (14, 2s). Тогда 14 + 4s = 76. Целых корней нет.

3.4. (7, 4s). Тогда 7 + 8s = 76. Целых корней нет.

3.5. Быстрый выигрыш при 7 + 4s ≥ 77; s ≥ 18.

Здесь победные для Вани значения s – это {17} ∪ [18; +∞).

4. (14, s).

4.1. (15, s). Тогда 15 + 2s = 76. Целых корней нет.

4.2. (14, s + 1). Тогда 14 + 2(s + 1) = 76; s = 30.

4.3. (28, s). Тогда s + 56 = 76; s = 20.

4.4. (14, 2s). Тогда 14 + 4s = 76. Целых корней нет.

4.5. Быстрый выигрыш при 14 + 2s ≥ 77; s ≥ 32.

Здесь победные для Вани значения s – это {20; 30} ∪ [32; +∞).

Все варианты перебраны. Отметим, что быстрый выигрыш (выигрыш первым ходом Вани) достигается гарантированно при s ≥ 35, поэтому имеет смысл рассматривать только значения s < 35. Так как мы ищем значения s, при которых Ваня выигрывает независимо от действий Пети, то мы должны взять пересечение победных для Вани значений s из всех четырёх веток перебора. А именно взять пересечение четырёх найденных множеств:

1. {17; 30; 33} ∪ [35; +∞).

2. {30; 33} ∪ [34; +∞).

3. {17} ∪ [18; +∞).

4. {20; 30} ∪ [32; +∞).

Видно, что пересечением указанных множеств будет {30; 33} ∪ [35; +∞). А так как значения s ≥ 35 мы отбрасываем, то подходящими значениями s будут только 30 и 33. Так как в условии требовалось найти минимальное подходящее s, то в ответ следует записать число 30.

В заключение следует отметить, что на реальном экзамене не требуется предоставлять подробное решение данной задачи, поэтому выпускник может пропускать очевидные ему рассуждения, сокращая время выполнения рассмотренных задач. В итоге будет оценена только правильность ответа.

Иванов Сергей Олегович,

начальник отдела математики издательства «Легион»


Похожие статьи