Задание 26 ЕГЭ информатика разбор (вторая часть)

На уроке рассмотрен разбор 26 задания ЕГЭ по информатике: дается подробное объяснение и решение задания 2017 года

Объяснение задания 26 ЕГЭ по информатике

26-е задание — «Теория игр, поиск выигрышной стратегии» — характеризуется, как задание высокого уровня сложности, время выполнения – примерно 30 минут, максимальный балл — 3
* Некоторые изображения и примеры страницы взяты из материалов презентации К. Полякова

  

Теория игр. Поиск выигрышной стратегии

Для решения 26 задания необходимо вспомнить следующие темы и понятия:

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

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

    Кто выиграет при стратегически правильной игре?
  • для того чтобы определить, какой из игроков выиграет при стратегически правильной игре, необходимо ответить на вопросы:
  • Может ли какой-либо из игроков выиграть, независимо от ходов других игроков?
  • Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков?

Рассмотрим пример:

Игра: в кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку

Решение:

  • Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:
  • пример 26 задания егэ по информатике

  • если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
  • дерево ходов

  • если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
  • дерево игры
    проанализируем стратегию игры:

  • если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока;
  • итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу;
  • тогда как второй игрок не может выиграть, независимо от действий первого: потому что, если первый игрок сначала убрал одну спичку, второй всегда проиграет.

Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.

Решение 26 заданий ЕГЭ по информатике


Разбор 26 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 7 камней, за один ход можно получить кучу из 14 или 8 камней. У каждого игрока, чтобы сделать ход, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27.

Задание 1
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24? Опишите выигрышные стратегии для этих случаев.

Задание 2
У кого из игроков есть выигрышная стратегия при S = 13, 12? Опишите соответствующие выигрышные стратегии.

Задание 3
У кого из игроков есть выигрышная стратегия при S = 11? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.


✍ Решение:

  1. а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S = 27: тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22): тогда необходимо удвоить кучу.

    S=27
    Паша: 27 + 1 = 28 - Выигрыш!
    
    27 - выигрышная позиция
    

    б) При S = 26 выигрышная стратегия есть у Вали. Паша делает ход первым, у него есть возможность либо удвоить количество камней в куче, и тогда количество превысит 44, — выигрывает Валя; либо увеличить количество на один камень, станет 27 камней: следующая Валя, — она может положить один камень и выиграть.

    S=26
    Паша: 26 * 2 = 52   Валя выигрывает! или:
    Паша: 26 + 1 = 27
    Валя: 27 + 1 = 28 - Выигрыш! 
    
    26 - проигрышная позиция
    

    При S = 25 выигрышная стратегия есть у Паши. Удваивать количество камней нет смысла, т.к. количество превысит 44, значит, Паша добавит один камень, их станет 26, следующая Валя, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.

    S=25
    Паша: 25 + 1 = 26
    Валя: 26 ...  проигрышная позиция (см. выше) Паша выигрывает!
    
    25 - выигрышная позиция
    

    При S = 24 выигрышная стратегия есть у Вали. Паша делает ход первым: удваивать кучу нет смысла, т.к. в ней станет более 44, значит, Паша добавит один камень, их станет 25; следующая — Валя: она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной позиции, см. пункт при S = 26).

    S=24
    Паша: 24 + 1 = 25 
    Валя: 25 ...  выигрышная позиция (см. выше) Валя выигрывает!
     
    24 - проигрышная позиция
    
  2. При S = 13 или S = 12 выигрышная стратегия есть у Паши. Паша удваивает количество и в куче остается 26 или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
  3. При S = 11 выигрышная стратегия есть у Вали. Паша делает первый ход: в куче остается либо 22, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S = 12 последовательность игры описана в пункте 2, а при S = 22 — в пункте .

      
    Дерево возможных партий:
    задание 26 егэ дерево игры

    * Для Вали отображены только ходы по стратегии
    ** красный круг означает выигрыш
    *** фиолетовый круг — конец игры (проигрыш)

Подробное объяснение 26 задания ЕГЭ смотрите на видео:


Разбор 26 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

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

Например, есть набор слов {Волк, Информатика, Страшно}; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя — В, Ваня — О, Петя — Л, Ваня — К).

  
Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ, НМЛКИНМЛКИ}. Определить выигрышную стратегию.

Б) Даны 2 слова {ТРИТРИТРИ…ТРИ, РИТАРИТАРИТАРИТА…РИТА}. В первом слове 99 букв, во втором 164. Определить выигрышную стратегию.

Задание 2
Необходимо поменять две буквы местами из набора пункта в слове с наименьшей длинной так, чтобы выигрышная стратегия была у другого игрока. Объяснить выигрышную стратегию.

Задание 3
Дан набор слов {Ворона, Волк, Волна, Производная, Прохор, Просо}. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий для выигрышной стратегии.


✍ Решение:

  1. А) Для выигрыша Пете достаточно выбрать первую букву слова с нечетным количеством букв, тогда последний ход делает Петя. При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что своим первым ходом он должен выбрать букву И (слово ИКЛМНИКЛМНХ из 11 букв). Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.

    Б) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, чтобы выбрать слово с нечетным количеством букв, т.к. при такой стратегии последнюю букву в любом случае записывает Петя. Т.о., Петя должен выбрать букву Т, т.к. в первом слове 99 букв.

  2. Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:
    {ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
    

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

  3. Выигрышная стратегия есть у Вани, так как при любом выборе Пети, Ваня может перевести игру в проигрышную позицию для Пети, т.е. «перейти» на слово с четным количеством букв. Такая стратегия позволит Ване написать последнюю букву и тем самым выиграть игру.
  4. Дерево возможных партий:
    дерево партий

* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш

Подробней с решением задания про слова ознакомьтесь в видеоуроке:


Решение 26. Демоверсия ЕГЭ 2018 информатика:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

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

Задание 1
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.

Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции

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


✍ Решение:

    Задание 1.

  • а) Петя может выиграть, если S = 15, … 28
  • 15, ..., 28 - выигрышные позиции с первого хода
    
  • б) Ваня может выиграть первым ходом (как бы ни играл Петя), если в куче будет S = 14 камней. Тогда после первого хода Пети в куче будет 15 или 28 камней. В обоих случаях Ваня удваивает кучу и выигрывает в один ход.
  • S = 14
    Петя: 14 + 1 = 15  выигрышная позиция (см. п. а). Выигрывает Ваня
    Петя: 14 * 2 = 28   выигрышная позиция (см. п. а). Выигрывает Ваня
    
    14 - проигрышная позиция
    

    Задание 2.

  • Возможные значения S: 7, 13. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 14 камней: в первом случае удвоением, во втором — добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
  • S = 7
    Петя: 7 * 2 = 14  проигрышная позиция (см. п. 1 б). Выигрывает Петя
    S = 13
    Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя
    
    7, 13 - выигрышные позиции со второго хода
    

    Задание 3.

  • Возможные значения S: 12. После первого хода Пети в куче будет 13 или 24 камня. Если в куче их станет 24, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 13 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
  • S = 12
    Петя: 12 + 1 = 13  
    Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!
    

    В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчеркнуты. На рисунке это же дерево изображено в графическом виде.
    таблица выигрышных стратегий
    Дерево всех партий, возможных при стратегии Вани:
    дерево выигрышных стратегий
    * красный круг означает выигрыш


Досрочный егэ по информатике 2018, вариант 1. Задание 26:

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

Задание 1.
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
  
б)Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Вася может выиграть своим первым ходом. Опишите выигрышную стратегию Васи.
  
Задание 2. Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.
 
Задание 3. Укажите хотя бы одно значение S, при котором у Васи есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, и у Васи нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Васи. Постройте дерево всех партий, возможных при этой выигрышной стратегии Васи (в виде рисунка или таблицы).


✍ Решение:

    1.
    а) S ≥ 14. При количестве камней в куче от 14 и выше Паше необходимо увеличить их количество в пять раз, тем самым получив 70 или более камней.

    S ≥ 14 выигрышные позиции
    

     
    б) S = 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.

    S = 13 
    Паша 1 ход: 13 + 1 = 14
    Паша 1 ход: 13 + 4 = 17
    Паша 1 ход: 13 * 5 = 65
    
    Ваня 1 ход: [14, 17, 65] * 5 = S ≥ 14  Ваня выигрывает
    
    13 - проигрышная позиция
    

    2. S = 9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
    После чего игра сводится к стратегии, описанной в пункте .

    S = 13 
    Паша 1 ход: 9 + 4 = 13  Паша выигрывает
    Паша 1 ход: 12 + 1 = 13 Паша выигрывает
    
    9, 12 - выигрышные позиции со второго хода
    

    3. S = 8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
    Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.

    S = 8 
    Паша 1 ход: 8 + 1 = 9   Ваня Выигрывает (см. п.2)
    Паша 1 ход: 8 + 4 = 12  Ваня Выигрывает (см. п.2)
    Паша 1 ход: 8 * 5 = 40  
    

    дерево решение 26 задание егэ

Решение 26 задания смотрите на видео:


Тренажер егэ по информатике 2018, контрольный вариант 1. Задание 26 (Крылов С., Ушаков Д.):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
 
Задание 1.
Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
  
Задание 2.
Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.
  
Задание 3.
Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.


✍ Решение:

  • Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани.
  • Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
  • Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани.
  • дерево выигрышной стратегии

Видео решения 26 задания с двумя кучами:

Поделитесь уроком с коллегами и друзьями:
5 комментариев

    Ирина

    Спасибо!

    dMb

    В последнем примере ошибка в решении задания 3: не (16,31), а (14,31).

      admin

      Спасибо! исправлено

    Timofey

    В номере с наборами слов в задании 3 показано неверное дерево ВСЕХ возможных партий. Игра может закончиться комбинацией п-р-о-с-о или п-р-о-и-з-В-… (где далее можно перейти на слова ВОРОН, ВОЛК ,ВОЛНА или продолжить начальное слово). В условии не уточнено, что нужно написать дерево всех партий с ПОБЕДНОЙ СТРАТЕГИЕЙ.

      admin

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить