ГДЗ по информатике 11 класс Босова, номер §11 № 6

§ № Выигрышная стратегия в игре с камнями

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

Решение

Обозначим позицию парой — числом камней в первой и второй кучах. По правилам из неё можно перейти в , , либо . Цель — получить сумму не меньше . Будем, как в разобранном в § примере, отмечать проигрышные для делающего ход позиции и выбирать переход в такую позицию.

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

Ход второго	Ход первого	Почему выбран
		Позиция проигрышна для второго.
		Позиция проигрышна для второго.
		Снова получена проигрышная позиция.
		: победа сразу.

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

Для проверка такая же. Ходы второго дают , , или . Первый отвечает соответственно переходами в , , или . Суммы равны , , , ; все они не меньше .

Итак, после первого хода в при любом ответе соперника первый либо сразу выигрывает, либо передаёт сопернику проигрышную позицию. Выигрывает первый игрок.

Ответ

Первый игрок; его первый ход — из в .

Помогло?

Номер §11 № 6