Мастер-класс по теме «Методика решения задачи № 26 ЕГЭ (Теория игр)»

Мастер-класс учителя информатики МБОУ «СОШ №18» ИГОСК Суглобовой Натальи Николаевны

по теме «Методика решения задачи № 26 ЕГЭ (Теория игр)»

Добрый день, уважаемые коллеги! Я рада встрече с вами. В начале нашего занятия я предлагаю вам поприветствовать друг друга особым способом. (Это упражнение снимет напряжение и активизирует работу психических процессов, в том числе и логического мышления) По цепочке вы должны передавать числа, а если число, которое должны произносить вы кратно  3, то вместо него  говорите любые слова приветствия. Т.е. первый говорит «один»,  второй «два», третий - «здравствуйте», потом  « 4, 5, рада видеть вас» и т. д...

Ну вот, вы уже улыбаетесь. А с  хорошим настроением дело делается в 2 раза быстрее и складнее. Теперь с хорошим настроением приступаем к работе. А какая сегодня тема занятия, вы должны догадаться сами…..

В этом вам поможет фрагмент из телеспектакля  по произведению Николая Васильевича Гоголя «Игроки».

Фрагмент спектакля

Что произошло?  Почему весь город проигрался?

Да! Карты были краплёные. Это чисто теоретико-игровая двухходовка. Мало того, что человек ест и пьёт в своё удовольствие, и ни за что не платит, но он ещё заносит 100 колод краплёных карт, крап которых знают только он и его подельники-жулики. После этого просчитываются действия третьего лица, а именно хозяина, который будет пытаться возместить ущерб, значит, он будет их продавать. Эти действия просчитываются. Где он их продаст? Ну, конечно, где-то в округе. Затем приезжают другие люди и всех обыгрывают, зная крап.

А теперь вопрос: «Скажите, пожалуйста, чему будет посвящено наше занятие?» . Правильно! Теории игр – разделу прикладной математики по поиску выигрышной стратегии.

В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. Во взрослом возрасте, устраиваясь на работу, мы пытаемся найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую пытаемся устроиться. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить.

В информатике особое внимание теории игр уделяют при изучении темы «Моделирование». Игра – это упрощённая формализованная модель конфликтной ситуации.  Дерево или таблица игры - схема, которая отражает всевозможные варианты ходов соперника, начиная с некоторой начальной позиции. Все позиции делятся на выигрышные и проигрышные. Выигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку. При этом говорят, что у него есть выигрышная стратегия — алгоритм выбора очередного хода, позволяющий ему выиграть. Если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник. В этом случае говорят, что у него нет выигрышной стратегии. Таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника. Выигрышные и проигрышные позиции можно охарактеризовать так:

• позиция, из которой все возможные ходы ведут в выигрышные позиции, — проигрышная;

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

Задание по поиску выигрышной стратегии игры включены во вторую часть контрольно-измерительных материалов ЕГЭ под номером 26. Рассмотрим некоторые виды этих заданий.

№ 1 Одна куча камней                  

1)    +2;

2)    Х2.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 24.

1. При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом?

3. При каком S Ваня выигрывает своим первым или вторым ходом?

1	2	3	4	5	6	7	8	9	10	11	12	13	…	24	25
					В2	Х2	Х2	В2	В2	Х1	Х1	В1	В1	В1	*

Оформление решения№ 26 на бланке ответов

Задание № 26

1а)     13≤S≤24

1б)   S=11,  12

2.  S=6, 9, 10

3. S=7,  8

Начальная позиция	1-й ход Пети (все варианты)	1-й ход Вани (ход по стратегии)	2-й ход Пети (все варианты)	2-й ход Вани (ход по стратегии)
8	10	12	13	26 (выигрыш)
			24	48 (выигрыш)
	16	32 (выигрыш)

№ 2 Одна куча камней

1)      +1;

2)      Х2;

3)      Х3.

Игра завершается в тот момент, когда количество камней в куче становится не менее 42. Если при этом в куче оказалось не более 72 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник.  В начальный момент в куче было S камней, 1 ≤ S ≤ 41.

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

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

Задание 2. У кого из игроков есть выигрышная стратегия при S = 13? Опишите соответствующие выигрышные стратегии.

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

12

13

14…

21…

36

37

38

39

40

41

42…

72

73

В3

Х2

В1

В1

В1

В2

Х2

В2

Х1

В1

*

*

пр

Оформление решения№ 26 на бланке ответов

Задание № 26

1а)   14≤S≤36,  S=41

1б) При S=38, 40 – Ваня, S= 37, 39- Петя

2.  При S=13 - Ваня

3. При S=12 – Петя

Начальная позиция	1-й ход Пети (ход по стратегии)	1-й ход Вани  (все варианты)	2-й ход Пети (ход по стратегии)	2-й ход Вани  (все варианты)	3-й ход Пети (ход по стратегии)
12	13	39	40	41	42 (выигрыш)
				80 (проигрыш)
				120 (проигрыш)
		14	42 (выигрыш)
		26	52(выигрыш)

№ 3 Две кучи камней

а) +3 (в любую кучу);

б) х2 (любую кучу).

Победителем считается игрок, первым получивший такую позицию, при которой в двух кучах в сумме будет 61 камень или больше. В начальный момент в первой куче было 7 камней, а во второй – S камней, 1 ≤ S ≤ 53.

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

б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

	19	20	21	22	23	24	25	26	27…	54
7	Х2	Х2	Х2	В2	В2	В2	В2	Х1	В1..	*
8		Х2	В2	В2	В2	В2	Х1	Х1	В1..	*
9		В2	В2	В2	В2	В2	Х1	В1	В1..	*
10	В2	В2	В2	В2	В2	Х1	Х1	В1	В1..	*
11		Х2	В2	В2	В2	Х1	В1	В1	В1..	*
12		В2	В2	В2	Х1	Х1	В1	В1	В1..	*
13		В2	В2	В2	Х1	В1	В1	В1	В1..	*
14		В2	В2	Х1	Х1	В1	В1	В1	В1..	*
15		В2	В2	Х1	В1	В1	В1	В1	В1..	*
16		В2	Х1	Х1	В1	В1	В1	В1	В1..	*
17		В2	Х1	В1	В1	В1	В1	В1	В1..	*
18		Х1	Х1	В1	В1	В1	В1	В1	В1..	*
19		Х1	В1	В1	В1	В1	В1	В1	В1..	*
20	Х1	Х1	В1	В1	В1	В1	В1	В1	В1	*

1б)( 61-7):2:2      (61-7=54,             54:2=27,              27:2=13,5        =>     S=14)

Оформление решения№ 26 на бланке ответов

Задание № 26

1а)   27≤S≤53

1б)   S=14

2.   S = 22, 23, 24 или 25

3.  S = 19, 20 или 21.

Начальная позиция	1-й ход Пети (все варианты)	1-й ход Вани (ход по стратегии)	2-й ход Пети (все варианты)	2-й ход Вани (ход по стратегии)
(7,21)	(10,21)	(10,24)	(13,24)	(13,48) (выигрыш)
			(10,27)	(10,54) (выигрыш)
	(7,24)		(20,24)	(20,48) (выигрыш)
			(10,48)	(10,96) (выигрыш)
	(14,21)	(17,21)	(20,21)	(20,42) (выигрыш)
			(17,23)	(17,46) (выигрыш)
			(24,21)	(24,42) (выигрыш)
			(17,42)	(17,84) (выигрыш)
	(7,42)	(7,84) (выигрыш)

Мастер-класс подходит к концу. И закончить хотелось бы словами Н.В. Гоголя: «Уча других, также  учишься.»

Надеюсь, что мастер-класс был для вас полезен. Спасибо за внимание! Желаю всем творческих успехов..

Краткое описание документа:

Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника. В информатике особое внимание теории игр уделяют при изучении темы «Моделирование».