Задание 116 ГДЗ Семенов Рудченко 6 класс (Информатика)

Задача

116. Найди выигрышную стратегию в игре Камешки (начальная позиция 15, разрешается брать 1, 3, 4 камешка). Выясни, у кого из игроков есть выигрышная стратегия. Построй последовательность такой партии, в которой этот игрок следует выигрышной стратегии, а его противник на каждом ходу берет один камешек.
Выигрышная стратегия есть у Первого, он начинает игру из выигрышной позиции.
Ситуация после хода Первого помечена синим, после хода Второго красным
15 – 14 – 13 – 9 – 8 – 7 – 6 – 2 – 1 – 0

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

Определим выигрышные и проигрышные позиции для игры, где можно брать $$1$$, $$3$$ или $$4$$ камешка.

Если из позиции можно сделать ход в проигрышную позицию соперника, то эта позиция выигрышная.

Проверим числа от $$0$$ до $$15$$:

$$0$$ — проигрышная;
$$1$$ — выигрышная, так как можно взять $$1$$ и перейти в $$0$$;
$$2$$ — проигрышная, потому что из неё можно перейти только в $$1$$, а это выигрышная позиция;
$$3$$ — выигрышная, можно перейти в $$2$$;
$$4$$ — выигрышная, можно перейти в $$0$$;
$$5$$ — выигрышная, можно перейти в $$2$$;
$$6$$ — проигрышная;
$$7$$ — выигрышная;
$$8$$ — проигрышная;
$$9$$ — выигрышная;
$$10$$ — выигрышная;
$$11$$ — проигрышная;
$$12$$ — выигрышная;
$$13$$ — проигрышная;
$$14$$ — выигрышная;
$$15$$ — выигрышная.

Значит, начальная позиция $$15$$ — выигрышная, и выигрышная стратегия есть у Первого игрока.

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

$$15 \to 14 \to 13 \to 9 \to 8 \to 7 \to 6 \to 2 \to 1 \to 0$$

Здесь Первый делает ходы $$15 \to 14$$, $$13 \to 9$$, $$8 \to 7$$, $$6 \to 2$$, $$1 \to 0$$, а Второй каждый раз берёт по одному камешку.