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

Игроки играют в следующую игру. На игральной доске размером 20 x 20 стоит фишка на клетке (16, 13). Игроки по очереди передвигают фишку в одну из трёх точек: (x - 3, у - 2), либо (x - 4, у), либо (x, у - 4). Выигрывает игрок, первым переместивший фишку за пределы доски. Какой игрок гарантированно выиграет при безошибочной игре? Каким должен быть его первый ход? Ответ обоснуйте.

Решение: Рассмотрим все потенциальные ходы первого и второго игроков. Начальная позиция фишки (16, 13). Выигрышем считается позиция, где одно из чисел будет или больше 20, примет отрицательное значение или 0.

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

Начальная позиция	Ходы первого игрока
(6,13)	(13,11)
	(12,13)
	(16,9)

Таблица 1.

2 ход - второй игрок:

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

Таблица 2.

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

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

Таблица 3.

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

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

Таблица 4.

На 4-м ходу, второй игрок может выиграть, если первый игрок на 3-м ходу пойдёт (13,3) или  (4,13) или (16,1). Но по условию задачи, игра безошибочная, таким образом этими ходами первый игрок не пойдёт. Таблица 4 будет выглядеть так:

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

Таблица 5.

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

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

Таблица 6.

Анализируя, таблицу 6, можно сделать вывод, что ходы (4,5), (3,7), (7,3), (2,9), (10,1), (1,11), (9,3), (4,9), (12,1) являются проигрышными для второго игрока, по условию задачи, он их не сделает, преобразуем таблицу 6:

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

Таблица 7.

Когда на 5-м ходу первый игрок сделает ход, на 6-ходу второй игрок однозначно будет победителем. На первый вопрос задачи мы нашли ответ - при безошибочной игре обоих игроков, выигрывает второй игрок.

Рассмотрев потенциальные ходы двух игроков, вернёмся к таблице 5. 

Ходы, которые первый игрок совершит на 3-м ходу, на 6-м ходу приведут его к проигрышу, за исключением хода (7,7), который на 5-м ходу может привести первого игрока к выигрышу. Но по условию задачи, ход (10,9) (из которого как раз и получается ход (7,7)) на втором ходу, второй игрок делать не будет.
Таким образом, ответом на второй вопрос, будет - выигрышные ходы у второго игрока - (9,11), (13,7), (8,13), (12,9), (16,5).