Категория C3 • задача №1
Условие задачи
Дано:
два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 6 камней. У каждого игрока неограниченное количество камней.
Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу.
Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней.
Найти:
кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение
I этап: анализ условия задачи.
В игре принимает участие два игрока, для которых допустимы следующие операции:
удвоение количества камней в какой-либо куче;
добавление ровно два камня в любую из куч.
Условие победы в игре: суммарное количество камней в обеих кучах становится не менее 24 штук.
II этап: алгоритмизация задачи
Для решения поставленной задачи (для разбора игры) рассмотрим полное дерево игры, оформленное в виде табличной структуры, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа будут соответствовать количеству камней на каждом этапе игры в первой и второй кучах соответственно.
Надо учесть тот факт, что у текущего игрока имеется четыре варианта хода, следовательно, на каждом ходе, количество вариантов будет возрастать в четыре раза. Но, также следует учесть, что среди комбинаций будут встречаться и дублирующие наборы, в этом случае, дубликаты можно опустить и не терять на их анализ время.
Первый ход осуществляет игрок под №1. У него на выбор четыре варианта хода. Ниже представлено схема развития дерева игры для варианта, когда первый игрок увеличил вдвое количество камней в первой куче.
Подчеркнутая пара чисел означает победу соответствующего игрока (то есть, игрок совершил ход и получил победную комбинацию). То есть, если первый игрок сходит (6, 6), то второй игрок непременно ответит (8, 6) и победит не позднее четвертого хода игры.
Рассмотрим схему развития дерева игры для варианта, когда первый игрок увеличил вдвое количество камней во второй куче.
Если первый игрок сходит (3, 12), то второй игрок непременно отвечает победным набором (3, 24).
Рассмотрим схему развития дерева игры для варианта, когда первый игрок добавил два камня в первую кучу.
Если второй игрок отвечает на ход первого игрока комбинацией (7, 6) или (5, 8), то игрок №1 побеждает не позднее V хода игры. Если второй игрок ходит как (10, 6) или (5, 12), то первый игрок побеждает не позднее III хода игры. То есть, в данной ветви игры всегда побеждает игрок под номером один.
Рассмотрим схему развития дерева игры для варианта, когда первый игрок добавил два камня во вторую кучу.
Как видно из вышеприведенного фрагмента дерева игры, на ход первого игрока (3, 8), второй игрок отвечает ходом (3, 10) и побеждает не позднее IV хода игры.
Выведем полное дерево игры:
Промежуточный вывод: как видно из дерева игры, побеждает игрок, делающий ход первым. Победным ходом является прибавление к первой куче двух камней. При любых ответах второго игрока, игра будет закончена не позднее пятого хода.
Вывод: |
при верной игре победит игрок №1. Для победы ему необходимо первым ходом прибавить два камня к первой куче |
Резюме
провели анализ условия задачи;
дифференцировали развитие полного дерева игры на четыре направления;
визуализировали полное дерево игры и провели соответствующие умозаключения.
Ответ: |
I игрок, добавление двух камней в первую кучу |
Комментарии