Дано:
имеются две кучи камней, в одной из которых 1, а в другой – 4 камня. Двум игрокам предлагается игра по следующим правилам. Каждый игрок обеспечивается неограниченным запасом камней. Игроки ходят по очереди. Ход состоит в том, что игрок производит одно из возможных действий: или утраивает число камней в одной из куч, или увеличивает на 3 количество камней в какой-либо куче.

Выигрывает тот игрок, после хода которого суммарное число камней в двух кучах становится равным 22 или  более камней.

Вопрос:
кто выиграет при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

I этап: анализ условия задачи.

В игре принимает участие два игрока, для которых допустимы следующие операции:

• утраивание количества камней в какой-либо куче;

• добавление ровно трех камней в любую из куч.

Условие победы в игре: суммарное количество камней в обеих кучах становится не менее 22 штук.

II этап: алгоритмизация задачи

Для решения поставленной задачи (для разбора игры) рассмотрим полное дерево игры, оформленное в виде табличной структуры, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа будут соответствовать количеству камней на каждом этапе игры в первой и второй кучах соответственно.

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

На заметку: если среди допустимых ходов игрока встречается возможность произвести увеличение количества камней в три раза, то, как правило, требуется совсем немного ходов для всей игры, чтобы выявить победителя. Потому что операция утроения очень интенсивно увеличивает общее количество камней. Например, если в одной куче хранится хотя бы 7 камней, то очевидно, если произвести утроение, то данный игрок побеждает.

Рассмотрим стартовую позицию и все возможные ходы первого игрока:

Очевидно, что после первого хода первого игрока, данный игрок далек от победы. Максимальная сумма камней составляет всего 13 (1 + 12) штук, а для победы необходимо набрать минимум 22 камня.

Рассмотрим все возможные ответы второго игрока на ход первого игрока:

Как видно из неполного дерева игры, второй игрок имеет несколько выигрышных комбинаций (выигрышные комбинации показаны подчеркиванием). То есть, если первый игрок первым ходом сходит (1, 12) или (1, 7), то второй игрок побеждает на втором ходе всей игры.

Рассмотрим все возможные ходы первого игрока (происходит третий ход всей игры):

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

Давайте проведем окончательный генеральный анализ сформированного дерева игры и ответим на вопросы, поставленные в условии задания.

Общий вывод: как видно из полного дерева игры, при безошибочной игре побеждает игрок №1. Для победы, ему необходимо увеличить количество камней в первой куче в три раза (получить состояние (3, 4)) или увеличить количество камней в первой кучи на три камня (получить состояние (4, 4)). При любых ответах второго игрока, игра будет закончена победой первого играющего не позднее третьего хода.

1. провели анализ условия задачи;

2. визуализировали полное дерево игры и провели соответствующие умозаключения.