Изучение информатики или подготовка к ЕГЭ?

Продолжение. См. № 17–24/2008; № 1–8/2009

В этом номере:

· Анализируем задание С3

· “Сдаем экзамен” за 5-й класс

· Поиграем — погадаем?

Добрый день, уважаемые коллеги!

Анализируем задание С3

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

Однако если обратиться к имеющимся программам обучения, то вопросы теории игр можно найти только в программе профильного курса: “Детерминированные игры с полной информацией (4 часа). Деревья. Выигрышная стратегия в игре”. Именно такая формулировка приводится в “Примерной программе профильного уровня”, при этом говорится, что “курсивом выделен материал, который подлежит изучению, но не включается в «Требования к уровню подготовки выпускников»”. Вот такое задание предстоит одолевать выпускникам, выбравшим информатику в качестве экзамена по выбору, — изучить должны, а знать вроде бы и не обязаны.

Найти изложение вопроса в имеющихся школьных учебниках для 9–11-х классов оказалось делом непростым. Во всяком случае, мне его найти не удалось.

Неожиданно ответ на этот вопрос дали учебники по информатике для начальной и средней школы. Все они являются учебниками серии “Информатика 1–7”, одним из авторов которых является А.Л. Семенов [1, 2]. Посмотрите только на перечень отдельных тем уроков 4-го класса:

· Дерево игры. Ветка дерева игры.

· Выигрышные и проигрышные позиции.

· Выигрышные стратегии в игре “Камешки”.

· Выигрышные стратегии и большие числа.

Как вам показались процитированные темы? Заманчиво? Если в 4-м классе мы займемся подобными проблемами, то к 11-му, наверное, можно достичь очень многого :).

Этот курс предполагает возможность начала изучения информатики и в 5-м классе: его программа наряду с другими вопросами в очень концентрированном виде повторяет материал начальной школы. И, несмотря на это обстоятельство, вопросам, связанным с теорией игр, посвящается достаточно и времени, и страниц учебника. Вот, например, задача из раздела “Повторение”, которую должен решить ученик 5-го класса (текст сокращен):

“Найди выигрышную стратегию для игры Двадцать пять.

Начальная позиция. Число 0.

Возможные ходы. На каждом ходу игрок прибавляет к имеющемуся числу 1, 2, 3 или 4.

Победа. Игра заканчивается, если позиция оказывается равной 25. Выигрывает тот, кто добавил последнее число”.

В учебнике рассмотрены разнообразные игры: “Камешки”, “Две кучи камешков”, “Ползунок”, “Сотня”, “Минусы”, шахматные игры: “Ладья”, “Король”, “Ферзь”, “Пешка” и другие. Это не все рассмотренные в указанных учебниках игры, их множество, и, думаю, ученикам совсем не скучно на уроках, посвященных анализу игр :).

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

В учебнике седьмого класса глава с подобным содержанием имеет название “Игровые алгоритмы”. Здесь разбираются задачи не про камешки, а про конфеты J, что, впрочем, можно считать удачной возрастной адаптацией. И целенаправленно ведется разговор о стратегиях игры, о построении дерева игры.

Интересным способом анализа выигрышных позиций является диаграмма позиций: графическое изображение состояний игры и выявление выигрышных и проигрышных позиций. Аналогичный прием используется в [3]. Непосредственно в заданиях ЕГЭ использовать эти способы не придется, однако в решении разных задач подобной тематики они будут весьма полезны. Об этом в конце публикации.

А сейчас обратим наше внимание на задачи типа С3, предлагавшиеся в демонстрационных вариантах, тренировочных заданиях разных лет. Отдельные задачи приводятся в различных изданиях достаточно регулярно, иные приводятся без ответов. Надеюсь, что подробный и обширный разбор одного из “весомых” заданий экзаменационной работы, а также возможность быстро соотносить свои решения с другими будут полезны читателям. Может быть, даже в процессе подготовки к экзамену 2009 г.

Данный материал не является копией решений, предлагаемых авторами. Более того, в некоторых моментах имеется расхождение с решениями, ранее предоставленными в печати. Поэтому смотрите, решайте, сравнивайте, критикуйте.

Для удобства работы примем сокращения: ДВ**** — задача демонстрационного варианта ЕГЭ соответствующего года; ОС — открытый сегмент федерального банка заданий; УТМ — учебно-тренировочные материалы, приводящиеся в сборниках ФИПИ разных лет изданий.

Задача. Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 1, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то кучке, или добавляет 3 камня в какую-то кучку. Выигрывает игрок, после хода которого в одной из кучек становится не менее 24 камней. Кто выигрывает при безошибочной игре — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

В таблице приведены различные модификации этой задачи с указанием ссылки на источник.

Вариант 1

Начнем анализ результата игры с конца. Победителю необходимо, чтобы в одной из куч было 24 камня или больше. Достичь этого можно, утроив количество камней, поэтому в одной из куч количество камней перед этим ходом должно быть не меньше восьми. Это соответствует точкам вне границ квадрата 8 ґ 8.

Идея победы: желающий выиграть должен искать такой ход (он будет его предпоследним ходом), который не выводит его за пределы квадрата 8 ґ 8, но “выталкивает” следующим ходом противника за границы этого квадрата.

Ход игры на клеточном поле будем описывать следующим образом:

(i, J) — координаты клетки, где i (номер строки) соответствует количеству камней в 1-й куче, J (номер столбца) соответствует количеству камней во 2-й куче;

содержимое клетки —

0 — начальное состояние куч,

1 — все возможные состояния после первого хода, т.е. после хода первого игрока,

2 — все возможные состояния после второго хода, т.е. после хода второго игрока, и т.д.

№	1-я куча	2-я куча	3-я куча	Правило 1	Правило 2	Правило 3	Критерий победы	Источник
1	1	2		x 3	+ 3		24 (в любой куче)	ОС [4]
2	3	2		x 3	+ 3		24 (в любой куче)	ОС [4]
3	5	3		x 2	+ 4		22 (в любой куче)	ДВ2006
4	3	6		x 2	+ 2		24 (в сумме)	УТМ [5]
5	3	2		x 3	+ 1		16 (в сумме)	ДВ2007
6	4	3		x 3	+ 2		24 (в сумме)	ДВ2005
7	1	2		x 3	+ 2		17 (в сумме)	ДВ2008
8	2	3	4	x 2	+ 2		25 (в сумме)	ДВ2004
	X	Y
9	5	2		X + 3	Y + 3	Y + 4	Расстояние от (0,0) больше 13	ДВ2009

Очевидно, что первый ход второго игрока за пределы квадрата 8 x 8 является проигрышем для него. Необходимо проанализировать 6 состояний после возможных ходов второго игрока, которые “попали” внутрь квадрата 8 x 8: (3,5), (3,6), (4,5), (4,6), (6,2), (7,2). Для того чтобы остаться в указанных пределах, можно сделать ходы прибавлением трех камней и переместиться в одну из точек: (6,5), (7,5), (6,6), (7,6). В эти ячейки можно попасть из шести положений, указанных выше.

Таким образом, первый игрок остается в пределах квадрата 8 x 8, но следующий ход второго игрока ведет к выходу за пределы этого квадрата. Тем самым, к выигрышному ходу первого игрока.

Этот же результат можно получить, записывая дерево игры и используя обозначения:

В1 — выигрыш первого игрока, В2 — выигрыш второго игрока.

Сочетая запись дерева с графическим представлением, можно аккуратно анализировать возникающие ситуации, учитывать все возможные положения, а значит, решать подобные задачи.

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

Вариант 2

Условие задачи отличается от варианта 1 только начальным состоянием куч.

Аналогично предыдущей задаче ход (9, 2) — проигрышный для 1-го игрока. Это выход за пределы квадрата 8 ґ 8.

Ход (6,2) будет также проигрышным для 1-го игрока, так как второй может ответить ходом (6,5), из которого первый вынужден выйти за пределы квадрата, второй выиграет.

На ход (3,5) второй может ответить ходом (6,5), который аналогично приведет к победе второго игрока.

На ход (3,6) второй может ответить ходом (6,6), после которого первый игрок неизбежно выходит за пределы квадрата 8 x 8, т.е. следующим ходом второй игрок выигрывает.

Таким образом, вне зависимости от хода первого игрока второй игрок добивается победы на втором или четвертом ходу.

Запись неполного дерева игры будет выглядеть так:

Ответ. Выигрывает 2-й игрок, независимо от первого хода, действуя соответственно дереву игры. Первый ход второго игрока 6,6 или 6,5.

Вариант 2а. Исходные данные отличны от предыдущего варианта.

Следует рассматривать квадрат для “предвыигрышного” хода не 8 x 8, а 6 x 6:

Очевидно, что первый ход за пределы квадрата 6 x 6 означает выигрыш второго игрока. Поэтому для первого игрока разумно сделать один из ходов: (4,2) или (3,3).

Второй игрок для выигрыша может ответить только одним из трех ходов: (5,2), (4,3) или (3,4). 5 других ходов, выводящих за границы квадрата 6 ґ 6, ведут к следующему победному ходу первого игрока.

Чтобы не потерять шансы на победу, первый игрок третьим ходом должен отвечать так (чтобы остаться внутри квадрата): (3,5), (4,4) или (5,3).

После этого второй игрок может попытаться не выходить за рамки 6 x 6 ходами: (4,5) или (5,4).

В результате для первого игрока остается единственный ход с гарантированной победой: (5,5). Таким образом, при разумном сопротивлении второго игрока первый выигрывает на 7-м ходу:

Ответ. Выигрывает второй игрок. Первым ходом победителя должен быть один из ходов: 5,2; 4,3; 3,4.

Вариант 3

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

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

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

Ответ. Выигрывает 1-й игрок, начиная ходом 5,6.

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

Вариант 4

Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 3, а во второй — 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте [5].

Таблица содержит все варианты ходов. Повторяющиеся комбинации не расписаны.

Ответ. Гарантированный выигрыш имеет первый игрок, делая первый ход 5,6. В этом случае:

· второй, не желая проиграть, должен ответить 7,6
или 5,8. В этих ходах есть возможность выигрыша второго;

· первый должен сделать ход 7,8;

· какой бы ход не сделал второй, следующим ходом первый выигрывает.

Вариант 5

Рецепт решения тот же — составляем дерево игры, экономим на одинаковых позициях, расписывая только одну из них.

Из приведенной таблицы (сокращенной записи дерева игры) видно, что выигрыш за вторым игроком.

На любой первый ход (из четырех возможных) второй игрок или отвечает сразу победным ходом, или переводит игру в ситуацию (4,3) или аналогичную (3,4), после которой любой ответ первого игрока ведет к победному ходу второго на 4-м шаге.

Ответ. Выиграет второй игрок. Его первым ходом должен быть ход (4,3) или (3,4).

Вариант 6

В этой задаче по дереву игры видно, что второй игрок выигрывает после любого хода первого игрока: либо ходом 3,4, с любым последующим ходом первого и победным ответом; либо ходом 1,18.

Ответ. Выигрывает второй игрок, начиная либо ходом 3,4, либо ходом 1,18.

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

Вариант 7

Из дерева игры видно, что первый игрок наверняка выиграет при одном из возможных первых ходов (4,5,6).

При других ходах первого есть выигрышные ходы у второго игрока. Поэтому первый игрок не должен делать первый ход, отличный от (4,5,6).

Ответ. Первый игрок выигрывает первым ходом 4,5,6.

Вариант 8

ДВ2009. Задача этого года имеет чуть отличную формулировку от задач предыдущих лет. Однако способ решения будет тем же: построение дерева игры.

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

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

Анализ дерева игры показывает, что второй игрок может ответить на любой первый ход так, что выиграет четвертым ходом.

Необходимыми ответными ходами являются ходы в точки (8,6), (8,5), (5,8). Координаты двух последних точек преобразуются аналогично, однако это разные точки на плоскости, для полноты картины имеет смысл указать каждую из них (в отличие от игры в камешки).

В повторяющихся случаях последующие ходы повторно не расписывались.

Ответ. Выигрывает второй игрок, начиная любым ходом: 8,6; 8,5 или 5,8.

“Сдаем экзамен” за пятый класс

В источнике [6], кроме разобранных вариантов 2006–2008 гг., есть подборка различных по характеру задач на игровые стратегии. Конечно, при ограниченном времени для подготовки к экзамену в первую очередь знакомишься с вариантами экзаменационных задач. Но они отнюдь не исчерпывают все множество задач по теме.

Действительно, одним из основных методов решения задач, посвященных играм с полной информацией, является метод построения дерева всех возможных позиций игры. Однако есть два других хорошо известных метода решения “игровых” задач. Это очень полезное “отвлечение” от сугубо экзаменационных проблем. Предложите ребятам решить и такие задачи.

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

Очевидно, что последняя позиция проигрышная. Это следует из правил: выигрывает тот, кто добавил последнее число. Также ясно, что позиции 21, 22, 23, 24 выигрышные, поскольку из них всегда можно сделать последний ход.

Позиция 20 — проигрышная. При любом ходе игрока противник выигрывает следующим ходом.

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

Поиграем — погадаем?

Второй тип задач — это задачи, решение которых связано с использованием симметрии. В учебнике 7-го класса [2] разобрана следующая задача.

У ромашки 12 лепестков. Ход состоит в том, что игрок обрывает один или два растущих рядом лепестка. Выигрывает тот, кто обрывает последний лепесток. Кто выигрывает при правильной игре — тот, кто начинает, или его противник?

Решение начинаем с анализа ромашки, имеющей 1, 2, 3, … лепестка, и выясняем, какие положения будут выигрышными.

Ключевым моментом является анализ ходов для ромашки с четырьмя лепестками. 2 лепестка срывать нельзя — это очевидный проигрыш на следующем ходу. Что можно сделать, если сорван 1 лепесток? Какие могут быть варианты?

· сорвать 2 подряд — проигрыш, остается 1 лепесток;

· сорвать 1, рядом с сорванным лепестком на преды­дущем ходу — проигрыш, так как остается 2 лепестка рядом;

· сорвать 1, но не рядом, а симметрично и разъединить оставшиеся 2 лепестка! Вот главный момент.

Таким образом, появляется основная идея — использование симметрии. Продолжим анализ.

Если лепестков 5, то при любом ходе первого игрока второй может оставить ему 2 разрозненных лепестка, а значит, выиграть.

Если лепестков 6 и первый игрок оторвал 2 лепестка, второму имеет смысл поступить аналогично случаю с четырьмя лепестками — оторвать 2 симметричных. Останется 2 пары разрозненных симметричных лепестков. Как бы ни ходил первый игрок, второй выиграет.

Если первый оторвет 1 лепесток, остается 5 лепестков. Второй должен сделать ромашку симметричной, значит, оторвать лепесток, противоположный первому.

И так действуем на всех последующих ходах: ответ должен быть симметричным. Независимо от количества лепестков, второй игрок (при разумных ходах) будет победителем.

Впрочем, решив эту задачу, можно приступать к решению задач из сборника [6]. Теперь не должно оставаться проблем с камешками, сосисками, да и шоколадка должна разделиться :).

Всем вам, дорогие читатели, выигрышных стратегий!

Список литературы

1. Семенов А.Л., Рудченко Т.А. Информатика: учебник для 5-х классов общеобразовательных учреждений. М.: Просвещение: Институт новых технологий, 2006.

2. Ландо С.К., Семенов А.Л., Вялый М.Н. Информатика: алгоритмика: учебник для 7-х классов общеобразовательных учреждений. М.: Просвещение, 2008.

3. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004.

4. ЕГЭ-2009. Информатика. Сборник экзаменационных заданий. М.: Эксмо, 2009.

5. Единый государственный экзамен-2008. Информатика. Учебно-тренировочные материалы для подготовки учащихся. / ФИПИ. М.: Интеллект-Центр, 2007.

6. Сафронов И.К. Готовимся к ЕГЭ. Информатика. СПб.: БХВ–Петербург, 2009.

Продолжение следует…