Выигрышная стратегия (решение задания ЕГЭ №26)
Автор: Сафиуллова Лариса Егоровна (учитель информатики, МБУ лицей 57 г.о. Тольятти Самарской области)
Тип документа: Конспект. Аудитория: Учителя информатики и учащиеся сдающие ЕГЭ по информатике. Дата публикации: 25.01.2015
Описание: Лекция позволит: научиться строить дерево игры по заданному алгоритму и обосновать выигрышную стратегию.


                                                  Сафиуллова Лариса Егоровна
                                МБУ лицея №57 г. Тольятти Самарской области.
                                                         Учитель информатики

                            Выигрышная стратегия
                (построение дерева игры и поиск лучшего хода)

На первом занятии мы должны научиться строить дерево игры по заданному
алгоритму и обосновать выигрышную стратегию, то есть научиться выполнять
задание 26 ЕГЭ. На  мой взгляд это наиболее простое задание  ЕГЭ, за
которое можно получить 3 первичных балла . Задачи выигрышной стратегии не
требуют глобальной теоретической подготовки. Для решения этих задач вам
потребуется внимательность и смекалка.
Такие задачи обычно решают с помощью дерева решений или графов.
Обыкновенное дерево состоит из корня, ветвей, узлов (мест разветвления),
листьев. Точно также дерево решений состоит из узлов (называемых также
вершинами), обозначаемых окружностями или прямоугольниками ( в них
указывают один из вариантов решения) ; ветвей, обозначаемых отрезками,
соединяющими узлы. Для удобства дерево решений изображают обычно слева
направо или сверху вниз. Самая первая (левая или верхняя) вершина
называется корнем.
Разберем одну из задач.

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

Определимся когда же игра закончиться (расстояние по прямой от фишки до
точки с координатами (0,0) больше 12 единиц ), для этого вспомним немного
математику.
 Расстояние от точки 0 до искомой точки это длина гипотенузы прямоугольного
треугольника у которого координаты x и y будут длинами катетов.
Или рассмотрим круг радиусом 12 и центром в точке (0,0) играем пока
находимся в пределах круга, выиграет то кто первый переставит фишку за
границы круга.


Условие окончания игры
                                                                     [pic]
или X2+Y2 >144









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



                                                           В начале игры
фишка стоит в точке (0,-4)







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

Все возможные варианты первого хода второго игрока. Посмотрев на них
внимательно глазами второго игрока мы увидим , что некоторые шаги приведут
к проигрышу. (Первый игрок своим вторым ходом сможет добиться условия
окончания игры X2+Y2 >144 то есть, если первый игрок из проигрышных точек
8,-4 ; 8,0; 8,4 переведет фишку в точку 12,-4 или 12,4 он выиграет.)
Зачеркнем проигрышные ходы. Второй игрок не допустит ошибки и так не
пойдет. Проверим для каждого ли варианта первого игрока, есть не
проигрышный ход второго игрока. Все в порядке. Второй игрок оставит после
себя один из двух вариантов  4,0 или 0,4.








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








Посмотрим на игру глазами второго игрока и поймем шансов не осталось он
проиграл.

Задача решена, осталось записать правильно ответ.
Вспомним, что с нас спрашивали- «Кто выигрывает при безошибочной игре обоих
игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким
должен быть первый ход выигрывающего игрока? Ответ обоснуйте».
Отвечаем: выиграет первый игрок и его первый ход (4,-4) ( в общем-то  его
ход может быть любым но в ответе указываем один ход, чтоб меньше
обосновывать).
 А обоснованием может быть неполное дерево игры в котором для выигрывающего
игрока указываются только выгодные ходы, а для проигравшего нужно указать
все возможные варианты, тем самым демонстрируя ,что у проигравшего не было
другого выхода. Это дерево игры можно оформить таблицей или с помощью
графов.
Рассмотрим первый вариант.
Для доказательства рассмотрим неполное дерево игры, оформленное в виде
таблицы, где в каждой ячейке координаты фишки на каждом этапе игры.

|1ход        |2 ход       |3 ход        |4 ход            |5 ход            |
|Позиция     |II-й игрок  |I-й игрок    |II-й игрок       |I-й игрок        |
|после       |(все        |(выигрышный  |(все варианты    |(один из         |
|первого     |варианты    |ход)         |хода)            |вариантов)       |
|хода        |хода)       |             |                 |                 |
|4,-4        |8,-4        |12,-4        |Выигрыш первого игрока             |
|            |            |             |                                   |
|            |            |             |                                   |
|            |            |             |                                   |
|            |            |             |                                   |
|            |8,0         |12,4         |Выигрыш первого игрока             |
|            |4,0         |4/4          |8,4              |12,8             |
|            |            |             |                 |                 |
|            |            |             |                 |                 |
|            |            |             |4,8              |8,12             |
|            |            |             |8,8              |12,12            |

Второй  вариант

























-----------------------
12

X

Y

0

0,-4

4,-4

0,0

4,0

8,0

4,0

8,-4

8,4

0,4

8,0

8,4

0,4

4,0

0,4

4,0

4,8

0,8

4,4

8,4

4,4

8,0

8,4

4,8

8,8

4,4

8,12

12,4

8,-4

4,0

8,0

4,-4

12,-4

4,4

Первый ход первого игрока

Все возможные варианты первого хода второго игрока

Выигрышные ответы первого игрока на ходы второго возможные варианты первого
хода второго игрока

8,4

Все возможные варианты второго  хода второго игрока

4,8

8,8

12,4

Первый выигрывает в любом случае

12,8