разбор С3
Выигрышная стратегия
- для того чтобы найти выигрышную стратегию в несложных играх, достаточно использовать метод перебора всех возможных вариантов ходов игроков;
- для решения задач 26 задания чаще всего для этого применяется метод построения деревьев;
- если от каждого узла дерева отходят две ветви, т.е. возможные варианты хода, то такое дерево называется двоичным (если из каждой позиции есть три варианта продолжения, дерево будет троичным);
Выигрышные и проигрышные позиции
Кто выиграет при стратегически правильной игре?
- все позиции в простых играх делятся на выигрышные и проигрышные
- выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, обязательно выиграет при любых действиях соперника, если не допустит ошибки; при этом говорят, что у данного игрока есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть
- если игрок, делающий первый ход, находится в проигрышной позиции, то он обязательно проиграет, если ошибку не сделает его оппонент; в этом случае говорят, что у данного игрока нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для оппонента
- выигрышные и проигрышные позиции характеризуются так:
- позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
- позиция, из которой хотя бы один из последующих возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для оппонента) позицию.
- для того, чтобы определить, какой из игроков выиграет при стратегически правильной игре, необходимо ответить на вопросы:
- Может ли какой-либо из игроков выиграть, независимо от ходов других игроков?
- Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков?
Рассмотрим пример:
Игра: в кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку
Решение:
проанализируем ход игры:
- Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:
- если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
- если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
-
- если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока
- итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу
- тогда как второй игрок не может выиграть, независимо от действий первого: потому что если первый игрок сначала убрал одну спичку, второй всегда проиграет
Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.
Разбор 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? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.
Решение:
Дерево возможных партий:
* Для Вали отображены только ходы по стратегии
** красный круг означает выигрыш
*** фиолетовый круг — конец игры (проигрыш)
- а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S=27, тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22), тогда необходимо удвоить количество камней в куче.
б) При S=26 выигрышная стратегия у Вали. Паша ходит первым, у него есть возможность удвоить количество камней в куче, и тогда количество камней превысит 44, — выигрывает Валя, либо возможность увеличить количество на один камень, станет 27 камней, следующий ход за Валей — она может положить один камень и выиграть.
При S=25 выигрышная стратегия у Паши. Паша ходит первым: удваивать количество камней нет смысла, т.к. количество камней превысит 44, значит Паша добавит один камень, станет 26 камней, следующий ход за Валей, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.
При S=24 выигрышная стратегия у Вали. Паша ходит первым: удваивать количество камней нет смысла, т.к. количество камней превысит 44, значит Паша добавит один камень, станет 25 камней, следующий ход за Валей, — она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной ситуации, см. пункт при S=26).
- При S=13 или S=12 выигрышная стратегия у Паши. Паша ходит первым: удваивает количество камней и в куче остается 26 камней или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
- При S=11 выигрышная стратегия есть у Вали. Паша ходит первым: в куче остается либо 22 камня, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S=12 ход игры описан в пункте 2, а при S=22 — в пункте 1а.
Подробное объяснение данного практического задания ЕГЭ смотрите на видео:
Разбор 26 задания ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):
Петя и Ваня играют в игру: есть набор слов, необходимо последовательно называть буквы этих слов. Побеждает тот игрок, который называет последнюю букву любого слова из набора. Петя ходит первым.
Например, есть набор слов {Волк, Информатика, Страшно}; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя — В, Ваня — О, Петя — Л, Ваня — К).
Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ, НМЛКИНМЛКИ}. Определить выигрышную стратегию.
Б) Даны 2 слова {ТРИТРИТРИ…ТРИ, РИТАРИТАРИТАРИТА…РИТА}. В первом слове 99 букв, во втором 164. Определить выигрышную стратегию.
Задание 2
Необходимо поменять две буквы местами из набора пункта 1а в слове с наименьшей длинной так, чтобы выигрышная стратегия была у другого игрока. Объяснить выигрышную стратегию.
Задание 3
Дан набор слов {Ворона, Волк, Волна, Производная, Прохор, Просо}. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий.
Решение:
А) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что первым ходом он должен выбрать букву И. Вторым ходом Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.
Б) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, чтобы выбрать слово с нечетным количеством букв, т.к. при такой стратегии последнюю букву в любом случае записывает Петя. Петя должен выбрать букву Т первым ходом, т.к. в первом слове 99 букв.
Дерево возможных партий:
-
- Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:
{ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
Для данного набора выигрышная стратегия есть у Вани. Так как Петя в любом случае для выбора выигрышной позиции должен будет выбрать букву И, то Ваня следующим ходом может перевести игру в проигрышную позицию для Пети, т.е. перейти на второе слово, назвав букву М. Такая стратегия приведет Ваню к выигрышу, так как последнюю букву слова — И — выберет именно он.
- Выигрышная стратегия есть у Вани, так как при любом выборе Пети, Ваня может перевести игру в проигрышную позицию для Пети, т.е. «перейти» на слово с четным количеством букв. Такая стратегия позволит Ване делать последний ход и тем самым выиграть игру.
* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш
Подробней с решением ознакомьтесь в видеоуроке: https://youtu.be/ov4w6PuAvQs
|
