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

Задача

После всех возможных первых ходов 1-го игрока, у второго игрока есть только одна ситуация, которая не приведет к победе противника, это 3,4.
У 1-го игрока второй ход самый оптимальный это создать ситуацию 5,4, все остальные явно приводят к победе 2-го игрока.
Но и (5,4) приводит к победе 2-го игрока на втором ходе!
Ответ: при правильной игре игроков, побеждает 2-ой игрок.

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

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

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

Возможные ходы из этого положения:

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

Рассмотрим ответы второго игрока после каждого первого хода.

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



$$ (1,2) $$	$$ (3,2) $$	$$ (9,2) $$	$$ (5,4) $$	$$ (5,12) $$
		$$ (3,6) $$
		$$ (5,2) $$
		$$ (3,4) $$
$$ (1,2) $$	$$ (1,4) $$	$$ (3,4) $$
		$$ (1,12) $$
		$$ (3,4) $$
		$$ (1,6) $$

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

$$5+12=17.$$

Значит, при безошибочной игре выигрывает второй игрок.