ЕГЭ 19, 20, 21 Теория игр

1.

ЕГЭ 19, 20, 21 Теория игр
Основные понятия:
Выигрышная стратегия (ВС) одного из игроков – означает, что у этого игрока есть
такие варианты ходов, делая которые он будет выигрывать при любой игре
другого игрока.
Правильный ход игрока – это ход, который приведет игрока к победе на
следующем ходе игры
Описание ВС: для игрока, который имеет ВС, необходимо указывать только
правильные варианты хода, а для игрока, который проигрывает, необходимо
указывать все варианты хода

2.

Пример игры (для ознакомления с правилами игры и терминологией):
Ходы:
+1
*3
Выигрыш:
>=46
S – количество камней в куче в начальный момент

3.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос а): Кто из игроков имеет ВС при S=15
Строим полное дерево игры (все варианты ходов всех игроков):
S
исходная
позиция
15
П
1-й ход игры
В
2-й ход игры
П
3-й ход игры
В
4-й ход игры
1-й ход второго
игрока
1-й ход второго
игрока
2-й ход первого
игрока
2-й ход второго
игрока
+1=
*3=

4.

Ходы:
+1
*3
Выигрыш:
>=46
Описание выигрышной стратегии игры: (основа для задания 19)
S
S=15
П
В
(все варианты
хода) <46
(выигрышный
ход) >=46
+1=16
*3=48
выигрыш
+1=46
выигрыш
*3=135
выигрыш
*3=45
П
В
Делаем вывод, что при количестве камней s=15 В (второй игрок) имеет
выигрышную стратегию. Он выигрывает своим 1-м ходом на 2-м ходе игры при
любой игре (т.е. после любого хода) П (первого игрока)

5.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос б): Кто из игроков имеет ВС при S=14
Полное дерево игры (все варианты ходов всех игроков)
S
исходная
позиция
П
1-й ход игры
В
2-й ход игры
П
3-й ход игры
В
4-й ход игры
1-й ход первого 1-й ход второго 2-й ход первого 2-й ход второго
игрока
игрока
игрока
игрока
14
+1=
+1=
*3=
*3=

6.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос б): Кто из игроков имеет ВС при S=14
Полное дерево игры (все варианты ходов всех игроков)
S
исходная
позиция
П
1-й ход игры
В
2-й ход игры
П
3-й ход игры
В
4-й ход игры
1-й ход первого 1-й ход второго 2-й ход первого 2-й ход второго
игрока
игрока
игрока
игрока
14
+1=15
*3=42
+1=16
*3= 48
выигрыш
*3=45
*3= 135
выигрыш
*3= 126
выигрыш
>=46

7.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос б): Кто из игроков имеет ВС при S=14
ВС у П (первого игрока), она заключается в том, что П своим 1-м ходом должен
пойти в 15, то есть должен сделать правильный ход.
П (первый игрок) выигрывает на 3-м ходе игры (своим 2-м ходом)
П выиграет своим вторым ходом при любой игре В (второго игрока)
Описание выигрышной стратегии игры (основа для задания 20) :
S
П (только
правильный ход)
В (все варианты)
<46
П (выигрышный
ход) >=46
14
+1=15
+1=16
*3=48 выигрыш
*3=45
*3=135 выигрыш
В

8.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос в): Кто из игроков имеет ВС при S=5
Полное дерево игры (все варианты ходов всех игроков):
S
5
П
+1=
*3=
В
+1=
П
*3=
+1=
*3=
*3=
+1=
*3=
*3=
+1=
*3=
В

9.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос в): Кто из игроков имеет ВС при S=5
Полное дерево игры (все варианты ходов всех игроков):
S
5
П
В
+1=6
П
В
+1=8
и т.д.
*3=21
*3=63
выигрыш
+1=7
*3=18
*3=15
+1=16
*3=45
*3=54
выигрыш
*3=48
выигрыш
+1=46
выигрыш
*3=135
выигрыш

10.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос в): Кто из игроков имеет ВС при S=5
ВС у П (первого игрока), она заключается в том, что П своим ходом должен пойти
ходом *3 и получить 15 камней, то есть должен сделать правильный ход.
П (первый игрок) выигрывает своим 2-м ходом на 3-м ходе игры при любой игре В
(второго игрока)
Описание выигрышной стратегии игры (основа для задания 20) :
S
5
П (только
правильный ход)
В (все варианты)
<46
П (выигрышный
ход) >=46
*3=15
+1=16
*3=48
выигрыш
*3=45
+1=46
выигрыш
*3=135
выигрыш
В

11.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос г): Кто из игроков имеет ВС при S=13
Полное дерево игры (все варианты ходов всех игроков):
S
13
П
+1=14
В
+1=15
*3=42
*3=39
*3= выигрыш
>=46
П
В
+1=16
*3=48 (>=46)
выигрыш
*3=45
+1=46 (>=46)
выигрыш
+1=46
выигрыш
*3=135
выигрыш

12.

Ходы:
+1
*3
Выигрыш:
>=46
Вопрос г): Кто из игроков имеет ВС при S=13
ВС у В (второго игрока), она заключается в том, что В своим первым ходом должен пойти в 15, то есть
должен сделать правильный ход.
В выиграет своим первым или вторым ходом (в зависимости от первого хода П), то есть на 2-м или 4-м
ходе игры
Описание выигрышной стратегии игры (основа для задания 21) :
S
13
П (все
В (только
П (все
В
варианты)
правильный
ход)
варианты) <46
(выигрышный
ход) >=46
один ход П:
+1=14
один ход В:
+1=15
+1=16
*3=48 (>=46)
выигрыш
+1=46 (>=46)
выигрыш
*3=45
другой ход П: *3=
*3=39
выигрыш
>=46

13.

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

14.

15.

16.

17.

18.

19.

20.

21.

22.

Пример 1.
Ходы:
+1
*2
Выигрыш:
>=29

23.

Ходы:
+1
*2
Выигрыш:
>=29