Разбор задачи C3 (демо ЕГЭ 2006)

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.

Решение:

Введем обозначения:

х - первая куча,

у - вторая куча.

Старт: (х, у).

Варианты хода игроков: (х*2,у), (х,у*2), (х+4,у), (х, у+4).

Игрок выйграет, когда число камней в 2-х кучах станет ≥22 (х+у≥22). Изобразим ход игры в виде дерева решений. Необходимо ветвить дерево до того момента, когда все варианты последнего хода станут выйгрышными.

После первого хода дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2006 первый ход

На дереве изображены все возможные варианты ходов.

После первых 2-х ходов дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2006 второй ход

Одним цветом в строке подчертнуты одинаковые значения количества камней в кучах. По ходу игры будем ветвить только разные координаты.

Когда 2-й игрок совершает 2-й ход, он выигрывает, когда попадает в позицию: (20,3), т.к. сумма х и у в этих случаях больше 22. На рисунке выйгрышная позиция 2-го игрока выделена сплошной рамкой.

Мы не рассматривали остальные позиции (обозначены как "..."), если встречали выйгрышную позицию. Игроки играют безошибочно, поэтому 2-й игрок пойдет только по выйгрышной ветке. Соответственно, нет смысла рассматривать все позиции. Например, из позиции (10,3) 2-й игрок обязательно пойдет в (20,3), а не в (10,6), например.

Смотрим предыдущий ход. Чтобы 2-й игрок не выйграл, 1-й игрок на 1-м ходе не должен идти в позицию (10,3). Он может идти в остальные позиции. Запретная позиция для 1-го игрока перечеркнута красным:

Задача С3 ЕГЭ по информатике 2006 запретная позиция 1-го игрока

Рассматривая дальнейшие ходы не будем ветвить позиции, которые идут из позиции (10,3). После 3-х ходов дерево будет выглядеть так:

Задача С3 ЕГЭ по информатике 2006 третий ход

Из рисунка видно, что любой ход 1-ого игрока на 3-м ходу будет выйгрышным. Поэтому, выигрывает 1-й игрок.

Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):

	1 ход	2 ход	3 ход
Старт	1-й игрок (выйгрышный ход)	2-й игрок (все ходы)	1-й игрок (выйгрышный ход (один из вариантов))
5,3	5,6	10,6	20,6
		5,12	10,12
		9,6	18,6
		5,10	5,20
	9,3	18,3	36,3
		9,6	18,6
		13,3	26,3
		9,7	18,7
	5,7	10,7	20,7
		5,14	10,14
		9,7	18,7
		5,11	5,22

Выигрывает 1-й игрок.
Он выигрывает своим 2-м ходом.

Перейти к другим задачам.

infoegehelp.ru

Разбор задачи C3 (демо ЕГЭ 2006)