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

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

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

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

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

Таблица 1.

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

Ходы первого игрока	Ходы второго игрока
(6,5)	(12,5)
	(6,10)
	(9,5)
	(6,8)
(3,10)	(6,10)
	(3,20)
	(6,10)
	(3,13)
(3,8)	(6,8)
	(3,16)
	(6,8)
	(3,11)

Таблица 2.

Выделенные ходы являются выигрышем для второго игрока. Но по условию задачи - игра безошибочная. Соответственно ходы (3,10) и (3,8) являются проигрышными для первого игрока. Их он на первом ходу не совершит. Таким образом первый ход первого игрока будет (6,5).

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

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

Таблица 3.

Выделенные ходы являются выигрышем для первого игрока. То есть, как бы на втором ходу не походил второй игрок, он всё равно проиграет. Ответом на первый вопрос будет - при безошибочной игре выигрывает игрок, делающий первый ход. На третьем ходу первый игрок выигрывает. 
Ответом на второй вопрос будет - первый ход выигрывающего игрока (6,5), так как именно этот ход приводит к проигрышным ходам для второго игрока на втором ходу.