Упр.47 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)

Задача

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

Подробный ответ

Обозначим состояние игры как $$a,b$$, где $$a$$ — число камней в первой куче, $$b$$ — во второй.

Начальное положение: $$1,2$$.

Возможные ходы первого игрока:

$$1,2 \to 3,2$$
$$1,2 \to 1,6$$
$$1,2 \to 3,2$$
$$1,2 \to 1,4$$

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

Положение после 1-го хода	Возможные ходы 2-го игрока	Есть ли выигрыш сразу?
$$3,2$$	$$9,2$$, $$3,6$$, $$5,2$$, $$3,4$$	Нет
$$1,6$$	$$3,6$$, $$1,18$$, $$3,6$$, $$1,8$$	Да, при ходе $$1,18$$ сумма равна $$19$$
$$3,2$$	$$9,2$$, $$3,6$$, $$5,2$$, $$3,4$$	Нет
$$1,4$$	$$3,4$$, $$1,12$$, $$3,4$$, $$1,6$$	Нет

Из положения $$1,4$$ второй игрок может перевести игру в состояние $$1,12$$, после чего сумма камней становится $$13$$, а затем следующим ходом он выигрывает. Аналогично, из других невыигрышных для второго игрока позиций он может выбрать ход, после которого у первого игрока не будет выигрыша сразу, но в дальнейшем второй игрок всё равно получает выигрышную ситуацию.

Следовательно, при безошибочной игре выигрывает второй игрок.