Категория C3 • задача №4
Условие задачи
Дано:
два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 6, а во второй – 5 камней. У каждого игрока неограниченное количество камней.
Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает в 2, или в три раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 48.
Вопрос:
кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение
I этап: анализ условия задачи.
В игре принимает участие два игрока, для которых допустимы следующие операции:
удвоение количества камней в какой-либо куче;
утроение количества камней в какой-либо куче.
Условие победы в игре: количество камней в обеих кучах становится не менее 48 штук.
II этап: алгоритмизация задачи
Для решения поставленной задачи (для разбора игры) рассмотрим полное дерево игры, оформленное в виде табличной структуры, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа будут соответствовать количеству камней на каждом этапе игры в первой и второй кучах соответственно.
Надо учесть тот факт, что у текущего игрока имеется четыре варианта хода, следовательно, на каждом ходе, количество вариантов будет возрастать в четыре раза. Но, также следует учесть, что среди комбинаций будут встречаться и дублирующие наборы, в этом случае, дубликаты можно опустить и не терять на их анализ время.
На заметку: если среди допустимых ходов игрока встречается возможность произвести увеличение количества камней в три раза, то, как правило, требуется совсем немного ходов для всей игры, чтобы выявить победителя. Потому что операция утроения очень интенсивно увеличивает общее количество камней.
Первый ход осуществляет игрок под №1. У него на выбор четыре варианта хода. Ниже представлена схема развития полного дерева для всей игры.
Выделим в дереве игры победные ходы:
Промежуточный вывод: как видно из полного дерева игры, побеждает игрок, делающий ход вторым независимо от первого хода, сделанного первым игроком. Игра при любых раскладах будет закончена не позднее четвертого хода.
Вывод: |
при безошибочной игре победит игрок №2 не позднее четвертого хода |
Резюме
провели дифференцированный анализ условия задачи;
выбрали метод решения поставленной задачи (построение полного дерева игры);
дифференцировали развитие полного дерева игры на четыре направления;
визуализировали полное дерево игры и провели соответствующие умозаключения.
Ответ: |
II игрок, он победит не позднее четвертого хода всей игры |
Категория C3 • задача №4
Остальные решения из билета №4 для подготовки к ЕГЭ по информатике 2013
Условие задачи (наведите курсор мыши на ссылку) |
Аудиовизуальное решение |
Мультимедийная видеопрезентация |
Решение в формате слайд-шоу |
Текстовое решение |
---|
Комментарии