Решение задачи 26 (2016 г.)
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


Решение задачи 26 на примере официальной демо-версии КИМ ЕГЭ 2016 г.




Решение задачи 26 на примере официальной демо-версии КИМ ЕГЭ 2016 г.

Текст задачи. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

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

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

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


Решение. Данная задача относится к первому типу (см. Теоретическое введение), поскольку в ней говорится о том, что "выигрывает игрок, делающий ход…" Значит, при построении дерева игры будем маркировать как противоречащие условию такие результаты ходов, осуществление которых приведёт впоследствии хотя бы к одной возможности выигрыша другого игрока.

Выполним первое задание.

Проанализируем сначала следствия первой начальной позиции.

I633
733
1233
634
666

Заметим на всякий случай, что любая комбинация, рассматриваемая в данной задаче, представляет собой неупорядоченную пару (см. соответствующие определения в §2 раздела "Дискретная математика"/"Элементы теории множеств", а также пример получения неупорядоченных пар в том же параграфе). Это означает, что для определения стратегии не важно, сколько камней в какой именно куче (первой или второй, правой или левой) имеется.

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

I633
733
1233
634
666

Итак, для начальной позиции (6, 33) выигрышную стратегию имеет Ваня.

Ещё одна начальная позиция — (8, 32). Построим дерево для неё и сразу маркируем его узлы:

I832
932
1632
833
864

Мы видим, что и здесь Петя выиграть не сможет ни при каком развитии игры.

Итак, для начальных позиций (6, 33) и (8, 32) выигрышную стратегию имеет Ваня. Чтобы выиграть, ему достаточно сделать один ход, удвоив число камней в большей куче (во всех случаях).

Выполним второе задание.

Проанализируем начальную позицию (6, 32):

I632
732
1232
633
664

Как видно, здесь Петя может не проиграть. Хотя… нужно достроить дерево игры до конца. Вот все варианты первого хода Вани (второй ход игры):

II732
832
1432
733
764
633
733
1233
634
668

Варианты развития игры из позиции (6, 33), впрочем, были описаны при выполнении Задания 1, так что можно было сделать ссылку на её анализ, а не переписывать фрагмент схемы (дерева). На данный момент видно, что Ваня проигрывает, если Петя своим первым ходом увеличит количество камней во второй куче на один (см. первый ход игры). Конечно, Петя не будет делать другой ход!

Итак, для начальной позиции (6, 32) выигрышную стратегию имеет Петя.

Рассмотрим течение игры для ещё одной начальной позиции, (7, 32).

I732
832
1432
733
764

Варианты осуществления хода из позиции (8, 32) были описаны при выполнении Задания 1, анализ позиции (7, 32) пришлось повторить (хотя делать это не обязательно, достаточно сослаться на него). Конечно, Петя увеличит число камней в меньшей куче на один, ведь тогда он не проиграет, а проиграет, как видно из анализа позиции (8, 32), его соперник. Так что для начальной позиции (7, 32) выигрышную стратегию имеет также Петя.

Вот и последняя начальная позиция второго задания, (8, 31). Построим схему возможных вариантов первого хода (Пети):

I831
931
1631
832
862

Как видно, чтобы не проиграть, Петя должен получить один из раскладов (9, 31) или (8, 32). Мы уже показывали выше, что игрок, перед ходом которого в одной куче 8 камней, а в другой 32, проигрывает. Так что Петя должен получить именно такой расклад, т. е. увеличить количество камней во второй куче на один.

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

И, наконец, третье задание. Проанализируем указанную в нём позицию (7, 31):

I731
831
1431
732
762

Чтобы не проиграть, Петя, как видно из маркеров (цветов), должен добавить 1 камень в любую кучу. Рассмотрим все возможные варианты первого хода Вани (второй ход игры):

II831
931
1631
832
862
732
832
1432
734
768

Чтобы не проиграть, Ваня должен получить комбинацию (8, 32), ведь тогда проигрывает соперник Вани (анализ вариантов ходов из такой начальной позиции был проведён выше). Как видно, Ваня может получить такую комбинацию в любом случае.

Следовательно, Ваня выигрывает игру своим вторым ходом, т. е. имеет выигрышную стратегию.

Построим дерево всех вариантов развития игры (об этом нас просят в третьем задании), представим его в виде схемы. Обратим внимание, что следственные комбинации по отношению к комбинации (9, 31), которую может получить Ваня на своём первом ходе, рассматривать не требуется, ибо его выигрышная стратегия уже установлена, и она не включает комбинацию (9, 31). Если есть время и желание, определите самостоятельно, является ли возможной частью выигрышной стратегии Вани получение этой комбинации, но при решении задания в условиях реального экзамена делать это не требуется.

I731
831
1431
732
762
II831
931
1631
832
862
732
832
1432
734
768
III832
932
1632
833
864

Решение завершено. Мы подробно и последовательно (что важно) ответили на все вопросы задачи.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика