Упр.3.47 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Задача

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

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

Рассмотрим все возможные первые ходы из начального положения $$(1,2)$$.

Исходное положение	1-й ход 1-го игрока	1-й ход 2-го игрока	2-й ход 1-го игрока	2-й ход 2-го игрока
$$1,2$$	$$3,2$$	$$9,2$$	$$5,4$$	$$15,4$$
	$$1,6$$	$$3,6$$	$$3,6$$
	$$3,2$$	$$5,2$$	$$9,4$$
	$$1,4$$	$$3,4$$	$$3,12$$

После первого хода 1-го игрока нужно проверить, может ли 2-й игрок сразу выиграть. Если 1-й игрок сделает ход в положение $$1,6$$, то 2-й игрок получает возможность выиграть следующим ходом. Аналогично опасны и другие ходы, кроме одного.

Единственное положение, из которого 2-й игрок не может сразу довести сумму камней до $$17$$, — это $$3,4$$. Значит, первый игрок должен сделать ход, после которого получится именно $$3,4$$.

Такой ход — увеличить первую кучку в 3 раза:

$$1,2 \rightarrow 3,2$$

После этого 2-й игрок может перевести игру только в одно безопасное для себя положение, а затем 1-й игрок уже не успевает выиграть первым. Следовательно, при безошибочной игре выигрывает 2-й игрок.