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


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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

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

Выполните следующие задания.

Задание 1

а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.

б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16? Опишите выигрышные стратегии для этих случаев.

Задание 2

У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.

Задание 3

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


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

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

SРезультат хода

В столбец S внесём все возможные начальные значения количества камней в куче:

SРезультат хода
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 

Если изначально в куче находится 1 камень, то игрок своим ходом может получить 2 (или 2) камня:

SРезультат хода
12
 

А если S = 2, то 3 или 4 камня:

SРезультат хода
12
23, 4
 

Заполним таблицу целиком:

SРезультат хода
12
23, 4
34, 6
45, 8
56, 10
67, 12
78, 14
89, 16
910, 18
1011, 20
1112, 22
1213, 24
1314, 26
1415, 28
1516, 30
1617, 32
1718, 34
1819, 36
1920, 38

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

SРезультат хода
 
1020
1122
1224
1326
1428
1530
 

При некоторых других S осуществляющий ход игрок может проиграть. Согласно выигрышной стратегии, выделенные далее ходы игрок не сделает:

SРезультат хода
 
1617, 32
1718, 34
1819, 36
1920, 38

Выделенные в последнем фрагменте таблицы результаты ходов тоже следует удалить.

С учётом проведённого анализа, полная таблица ходов, в которой учитывается выигрышная стратегия для обоих игроков, выглядит так:

SРезультат хода
12
23, 4
34, 6
45, 8
56, 10
67, 12
78, 14
89, 16
910, 18
1020
1122
1224
1326
1428
1530
1617
1718
1819
1920

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

1. а) Паша начинает игру, следовательно, в таблице нужно найти все строки, в столбце "Результат хода" которых указаны значения от 20 до 30 включительно. Таких строк — 7, приведём их в качестве фрагмента таблицы:

SРезультат хода
 
1020
1122
1224
1326
1428
1530
 
1920

В столбце "S" этих строк содержатся числа от 10 по 15, а также 19: 10 ≤ S ≤ 15, S = 19. При 10 ≤ S ≤ 15 Паша должен увеличить S в два раза и получить 20 или более камней, а при S = 19 он должен добавить 1 камень и получить 20 камней.

1. б) О том, что такое выигрышная стратегия, подробно описано в Теоретическом введении.

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

Рис. 1. Дерево игры при S = 18

При S = 17 Паша увеличивает число камней на 1 (камней стало 18), а схема дальнейшей игры уже видна из анализа предыдущего состояния. Чтобы чёрный и красный цвета по-прежнему относились к Паше и Вале соответственно, сделаем новый рисунок (см. рис. 2):

Рис. 2. Дерево игры при S = 17

Из рис. 2 видно, что при S = 17 выигрышную стратегию имеет Паша.

При S = 16 Паша увеличивает число камней на 1 (камней стало 17), а схема дальнейшей игры уже видна из анализа предыдущего состояния. Чтобы чёрный и красный цвета по-прежнему относились к Паше и Вале соответственно, сделаем ещё один рисунок (см. рис. 3):

Рис. 3. Дерево игры при S = 16

Из рис. 3 видно, что при S = 16 выигрышную стратегию опять имеет Валя.

2. Проследим по таблице, сколько камней будет в куче, если изначально в ней было 9 камней (S = 9).

SРезультат хода
 
910, 18
1020
 
1819
1920

Рис. 4. Дерево игры при S = 9

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

Из рис. 4 видно, что при S = 9 выигрышную стратегию имеет Паша.

Также проследим, сколько камней будет в куче, если изначально в ней было 8 камней (S = 8).

SРезультат хода
 
89, 16
910, 18
1020
 
1617
1718
1819
1920

Рис. 5. Дерево игры при S = 8

Начинающий игру Паша не станет получать после своего первого хода 9 камней в куче, ведь проиграть он не хочет (см. анализ предыдущей ситуации). По этой причине имеет смысл рассмотреть игру, последовательные результаты ходов которой выделены в приведённом фрагменте таблицы. Рис. 5 иллюстрирует показанные записи таблицы за исключением прямо противоречащих чьей-либо выигрышной стратегии.

Из рис. 5 видно, что при S = 8 выигрышную стратегию снова имеет Паша.

3. Пусть теперь в куче есть 7 камней (S = 7). Проследим по таблице ход игры для такого начального условия.

SРезультат хода
 
78, 14
89, 16
910, 18
1020
1122
1224
1326
1428
1530
1617
1718
1819
1920

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

Рис. 6. Дерево игры при S = 7

Из рис. 6 видно, что при S = 7 выигрышную стратегию имеет Валя. Подписи подсказывают, какие именно ходы он должен осуществить.

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



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


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

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

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



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