Е19-21.9 Демонстрационный вариант ЕГЭ 2016 по информатике – задание №26

Демонстрационный вариант ЕГЭ 2016 по информатике – задание №26

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 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) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. Опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.

Решение:

Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)
Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31). Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом. Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.Примечание для эксперта. Последняя фраза в приведённом решении избыточна. Не будет ошибкой, если экзаменуемый просто напишет, например, «При выбранной стратегии партия длится не более двух ходов».В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом.
Положения после очередных ходов Исходное положение 1-й ход Пети (разобраны все ходы, указана полученная позиция) 1-й ход Вани (только ход по стратегии, указана полученная позиция) 2-й ход Пети (разобраны все ходы, указана полученная позиция) 2-й ход Вани (только ход по стратегии, указана полученная позиция) (7, 31) Всего: 38 (7, 31+1) =(7, 32)Всего: 39 (7+1, 32) =(8, 32)Всего: 40 (8+1, 32) = (9, 32) Всего: 41 (9, 32*2) = (9, 64) Всего: 73 (8, 32+1) = (8, 33) Всего: 41 (8, 33*2) = (8, 66) Всего: 74 (8*2, 32) = (16, 32) Всего: 48 (16, 32*2) = (16, 64) Всего: 80 (8, 32*2) = (8, 64) Всего: 72 (8, 64*2) = (8, 128) Всего: 136 (7+1, 31) = (8, 31) Всего: 39 (8, 31+1) = (8, 32) Всего: 40 (8+1, 32) = (9, 32) Всего: 41 (9, 32*2) = (9, 64) Всего: 73 (8, 32+1) = (8, 33) Всего: 41 (8, 33*2) = (8, 66) Всего: 74 (8*2, 32) = (16, 32) Всего: 48 (16, 32*2) = (16, 64) Всего: 80 (8, 32*2) = (8, 64) Всего: 72 (8, 64*2) = (8, 128) Всего: 136 (7*2, 31) = (14, 31) Всего: 45 (14, 31*2) = (14, 62) Всего: 76 (7, 31*2) = (7, 62) Всего: 69 (7, 62*2) = (7, 124) Всего: 131
Примечание для эксперта. Дерево всех партий может быть также изображено в виде ориентированного графа – так, как показано на рисунке, или другим способом. Например, вершины дерева, соответствующие одной и той же позиции, на рисунке могут быть «склеены». Важно, чтобы множество полных путей в графе находилось во взаимно однозначном соответствии с множеством партий, возможных при описанной в решении стратегии.
Рис. 1. Дерево всех партий, возможных при описанной стратегии Вани. Ходы Пети показаны пунктирными стрелками, ходы Вани показаны сплошными стрелками. Заключительные позиции обозначены прямоугольником. Примечание для эксперта. В некоторых позициях у Вани есть и другой способ выигрыша: например, в позиции (8, 64) можно добавить один камень в любую кучу. То, что это не указано, не является ошибкой. Экзаменуемый не должен указывать все возможные выигрышные стратегии
Указания по оцениванию	Баллы
В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом
Выполнены все три задания. Здесь и далее в решениях допускаются арифметические ошибки, которые не искажают сути решения и не приводят к неправильному ответу	3
Не выполнены условия, позволяющие поставить 3 балла, и выполнено хотя бы одно из следующих условий. Выполнено задание 3. Выполнены задания 1 и 2	2
Не выполнены условия, позволяющие поставить 2 или 3 балла, и выполнено хотя бы одно из следующих условий. Выполнено задание 1. Выполнено задание 2	1
Не выполнено ни одно из условий, позволяющих поставить 1, 2 или 3 балла	0
Максимальный балл	3