Задача №2 (Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию)

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

Решение: Рассмотрим все потенциальные ходы игроков.

1 ход - первый игрок.

Начальная позиция	Ходы первого игрока
(3,2)	(6,2)
	(3,4)
	(6,2)
	(3,5)

Таблица 1.

2 ход - второй игрок.
Повторяющиеся ходы первого игрока не рассматриваем.

Ходы первого игрока	Ходы второго игрока
(6,2)	(12,2)
	(6,4)
	(9,2)
	(6,5)
(3,4)	(6,4)
	(3,8)
	(6,4)
	(3,7)
(3,5)	(6,5)
	(3,10)
	(6,5)
	(3,8)

Таблица 2.

3 ход - первый игрок.
Повторяющиеся ходы второго игрока не рассматриваем.

Ходы второго игрока	Ходы первого игрока
(12,2)	(24,2)
	(12,4)
	(15,2)
	(12,5)
(6,4)	(12,4)
	(6,8)
	(9,4)
	(6,7)
(9,2)	(18,2)
	(9,4)
	(12,2)
	(9,5)
(6,5)	(12,5)
	(6,10)
	(9,5)
	(6,8)
(3,8)	(6,8)
	(3,16)
	(6,8)
	(3,11)
(3,7)	(6,7)
	(3,14)
	(6,7)
	(3,10)
(3,10)	(6,10)
	(3,20)
	(6,10)
	(3,13)

Таблица 3.

Первый игрок не совершит ходы (24,2) и (3,20), так как они приведут его к проигрышу.

4 ход - второй игрок.
Повторяющиеся и проигрышные ходы первого игрока не рассматриваем.

Ходы первого игрока	Ходы второго игрока
(12,4)	(24,4)
	(12,8)
	(15,4)
	(12,7)
(15,2)	(30,2)
	(15,4)
	(18,2)
	(15,5)
(12,5)	(24,5)
	(12,10)
	(15,5)
	(12,8)
(6,8)	(12,8)
	(6,16)
	(9,8)
	(6,11)
(9,4)	(18,4)
	(9,8)
	(12,4)
	(9,7)
(6,7)	(12,7)
	(6,14)
	(9,7)
	(6,10)
(18,2)	(36,2)
	(18,4)
	(21,2)
	(18,5)
(12,2)	(24,2)
	(12,4)
	(15,2)
	(12,5)
(9,5)	(18,5)
	(9,10)
	(12,5)
	(9,8)
(6,10)	(12,10)
	(6,20)
	(9,10)
	(6,13)
(3,16)	(6,16)
	(3,32)
	(6,16)
	(3,19)
(3,11)	(6,11)
	(3,22)
	(6,11)
	(3,14)
(3,14)	(6,14)
	(3,28)
	(6,14)
	(3,17)
(3,10)	(6,10)
	(3,20)
	(6,10)
	(3,13)
(3,13)	(6,13)
	(3,26)
	(6,13)
	(3,16)

Таблица 4.

Второй игрок не совершит ходы: (24,4), (30,2), (24,5), (12,10), (6,16), (18,4), (36,2), (21,2), (18,5), (24,2), (6,20), (3,19), (3,22), (3,28), (3,20), (3,26), так как они приведут его к проигрышу.
Если обратиться к таблице 2, то ходы (9,2), (3,8) являются проигрышными для второго игрока, так как на 4-м ходу при безошибочной игре они принесут победу первому игроку.

5 ход - первый игрок.
Повторяющиеся и проигрышные ходы второго игрока не рассматриваем.

Ходы второго игрока	Ходы первого игрока
(12,8)	(24,8)
	(12,16)
	(15,8)
	(12,11)
(15,4)	(30,4)
	(15,8)
	(18,4)
	(15,8)
(12,7)	(24,7)
	(12,14)
	(15,7)
	(12,10)
(18,2)	(36,2)
	(18,4)
	(21,2)
	(18,5)
(15,5)	(30,5)
	(15,10)
	(18,5)
	(15,8)
(9,8)	(18,8)
	(9,16)
	(12,8)
	(9,11)
(6,11)	(12,11)
	(6,22)
	(9,11)
	(6,14)
(12,4)	(24,4)
	(12,8)
	(15,4)
	(12,7)
(9,7)	(18,7)
	(9,14)
	(12,7)
	(9,10)
(6,14)	(12,14)
	(6,24)
	(9,14)
	(6,17)
(6,10)	(12,10)
	(6,20)
	(9,10)
	(6,13)
(15,2)	(30,2)
	(15,4)
	(18,2)
	(15,5)
(12,5)	(24,5)
	(12,10)
	(15,5)
	(12,8)
(9,10)	(18,10)
	(9,20)
	(12,10)
	(9,13)
(6,13)	(12,13)
	(6,26)
	(9,13)
	(6,16)
(3,14)	(6,14)
	(3,28)
	(6,14)
	(3,17)
(3,13)	(6,13)
	(3,26)
	(6,13)
	(3,16)
(3,16)	(6,16)
	(3,32)
	(6,16)
	(3,19)

Таблица 5.

Первый игрок не совершит выделенные ходы, так как они приведут его к проигрышу. Ходы: (12,8), (15,4), (12,7), (18,2), (15,5), (6,14), (9,10), (6,13), (3,16) являются выигрышными для второго игрока. Обратимся к таблице 4. Ходы: (12,4), (15.2), (12,5), (6,8), (6,7), (6,10), (9,5), (3,14), (3,13) являются проигрышными для первого игрока, так как на 5-м ходу они приведут его к проигрышу. По условию задачи, эти ходы первый игрок не совершит. Ответ на первый вопрос - выигрывает первый игрок при безошибочной игре обоих партнёров.
Если обратиться к таблице 2, то выигрышным ходом для первого игрока будет (3,4). Этот ход не позволяет первому игроку на 3-м ходу сделать выигрышные ходы: (9,4) и (3,10).
Ответ на второй вопрос - выигрышный ход для первого игрока - (3,4).