Поиск выигрышной стратегии игры

Дерево игры.
Поиск выигрышной стратегии игры.
Гапурова В.Э, учитель информатики МБОУ «Кебратская СОШ»
2022

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

2 игрок
4 ход




1 игрок
1 ход
4,3
6,3
4,9
4,5
12,3
4,7
12,5
4,15
6,5
6,9
18,3
6,5
8,3
6,9
4,11
12,9
12,9
36,3
12,5
14,3
4,27
6,15
18,5
6,7
8,5
12,7
14,5
4,21
12,7
4,9
6,7
12,15
36,5
4,45
12,15
4,17
6,15
8,15
24,5
8,13
10,5
6,21
18,7
6,9
8,7
20,5
18,7
54,5
18,15
6,45
8,15
6,17
18,15

2куча

Выигрышные позиции
X+Y>=24
2куча

Ставим «-» в позиции, которые отделяют от выигрыша в 1 ход
X+Y+2>=24
2куча

Ставим «-» в позиции, которые отделяют от выигрыша в 1 ход
X+Y+2>=24
X+3Y>=24
2куча

Ставим «-» в позиции, которые отделяют от выигрыша в 1 ход
X+Y+2>=24
X+3Y>=24
3x+Y>=24
2куча

Ставим «+» в позиции, из которых все ходы ведут только в позиции, обозначенных знаком «-»
2куча

Ставим «-» в позиции, из которых все ходы ведут только в позиции, обозначенных знаком «+»
в предыдущем шаге
2куча

Ставим «+» в позиции, из которых все ходы ведут только в позиции, обозначенных знаком «-»
в предыдущем шаге
2куча

2куча
Желтые клетки – ходы 1-го игрока первым ходом

Из позиций (4,9) и (12,3) выигрывает 2-ой игрок вторым ходом

Из позиций (6,3) и (4,5) выигрышный ход (6,5) у 2-го игрока

2 игрок
4 ход




1 игрок
1 ход
4,3
6,3
4,9
4,5
12,3
6,5
6,5
36,3
4,27
6,15
18,5
6,7
8,5
24,5
6,21
18,15
18,15
2-й игрок
2 ход
1 игрок
3 ход

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

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

X+Y>=17
2куча

2куча
Ставим «-» в позиции, которые отделяют от выигрыша в 1 ход
X+Y+3>=17

2куча
Ставим «-» в позиции, которые отделяют от выигрыша в 1 ход
X+Y+3>=17
X+2Y>=17
2X+Y>=17

2куча
Ставим «+» в позиции, из которых все ходы ведут только в позиции, обозначенных знаком «-»

2куча
Ставим «-» в позиции, из которых все ходы ведут только в позиции, обозначенных знаком «+»
в предыдущем шаге

2куча

1 игрок
3 ход




5,3
5,6
10,3
5,6
8,3
16,3
5,18
20,3
5,18
2-й игрок
2 ход
1 игрок
1 ход
2,3

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