Задание 6 Параграф 11 ГДЗ Босова 11 класс (Информатика)

Задача

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

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

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

Начальная позиция: $$(2, 3)$$.

После первого хода первого игрока возможны такие позиции:

$$(2, 3 \cdot 3) = (2, 9)$$;
$$(2, 3 + 3) = (2, 6)$$;
$$(2 \cdot 3, 3) = (6, 3)$$;
$$(2 + 3, 3) = (5, 3)$$.

Рассмотрим их.

1) Позиция $$(2, 9)$$. Возможные ходы второго игрока:

$$(2, 9 \cdot 3) = (2, 27)$$;
$$(2, 9 + 3) = (2, 12)$$;
$$(2 \cdot 3, 9) = (6, 9)$$;
$$(2 + 3, 9) = (5, 9)$$.

Из позиций $$(2, 27)$$ и $$(2, 12)$$ первый игрок следующим ходом получает сумму не менее $$35$$ и выигрывает.

2) Позиция $$(2, 6)$$. Возможные ходы второго игрока:

$$(2, 6 \cdot 3) = (2, 18)$$;
$$(2, 6 + 3) = (2, 9)$$;
$$(2 \cdot 3, 6) = (6, 6)$$;
$$(2 + 3, 6) = (5, 6)$$.

Из позиции $$(2, 18)$$ первый игрок следующим ходом выигрывает. Из позиций $$(2, 9)$$, $$(6, 6)$$ и $$(5, 6)$$ у второго игрока нет хода, который сразу лишал бы первого игрока выигрыша: первый игрок после любого ответа сможет довести сумму до $$35$$ или более.

3) Позиция $$(6, 3)$$. Аналогично, любой ход второго игрока приводит к позиции, из которой первый игрок может выиграть следующим ходом.

4) Позиция $$(5, 3)$$. Аналогично, любой ход второго игрока приводит к позиции, из которой первый игрок может выиграть следующим ходом.

Значит, у первого игрока есть выигрышная стратегия: первым ходом он должен увеличить вторую кучу в 3 раза, получив позицию $$(2, 9)$$, а затем делать ходы так, чтобы после его хода сумма камней стала не менее $$35$$.