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

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

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

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

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

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

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

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

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

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

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

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

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

Подчеркнутая пара чисел означает победу соответствующего игрока (то есть, игрок совершил ход и получил победную комбинацию). То есть, если первый игрок сходит (4, 3), то второй игрок непременно ответит (4, 6) и победит не позднее четвертого хода игры.

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

Если первый игрок сыграет (2, 6), то второй игрок непременно ответит вариантом (6, 6) и победит не позднее четвертого хода всей игры.

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

Если первый игрок первым ходом сходит (6, 3), то второй игрок ответит вариантом (6, 6) и победит не позднее четвертого хода всей игры.

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

Если первый игрок первым ходом сходит (2, 9), то второй игрок сразу ответит (2, 27) и победит в данной игре.

Выведем полное дерево игры:

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

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

2. выбрали метод решения поставленной задачи (построение полного дерева игры);

3. дифференцировали развитие полного дерева игры на четыре направления;

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