Question

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

Answer 1

Первый игрок должен взять 1 камень.

Тогда сколько бы не взял второй (1, 2, 3) первый сможет сыграть так, что всегда будет оставаться 1 камень на столе (т. е. заберет 3, 2 или 1)

— взял 1 — осталось 5

— если второй взял 1, то первый берет 3

— если второй взял 2, то первый берет 2

— если второй взял 3, то первый берет 1

В итоге на столе в любой ситуации остается 1 камень, который должен будет забрать второй игрок.

Answer 2

При анализе этой игры можно использовать метод математической индукции. Пусть $P(n)$ - это утверждение, что при игре с кучей из $n$ камней выигрывает тот, кто делает первый ход. Мы докажем, что $P(n)$ верно для всех $n\geq1$.

Базовый случай: $n=1$. Если в куче всего один камень, то первый игрок обязательно выиграет, так как он заберет этот камень своим первым ходом.

Шаг индукции: предположим, что для любого $k$ от 1 до $n-1$ утверждение $P(k)$ верно. Рассмотрим игру с кучей из $n$ камней. Первый игрок может взять 1, 2 или 3 камня, и оставить второму игроку кучу из $n-1$, $n-2$ или $n-3$ камней соответственно. В каждом из этих трех случаев второй игрок обязан ответить таким образом, чтобы оставить первому игроку кучу из камней такую, чтобы он не мог выиграть, то есть оставить кучу из $k$ камней, где $k$ равно 2 или 3, если первый игрок взял 1, 1 или 2, если первый игрок взял 2, и 1, 2 или 3, если первый игрок взял 3.

Таким образом, после первого хода первого игрока мы получаем игру с кучей из $k$ камней, где $k$ равно 2 или 3, и второй игрок должен играть так, чтобы оставить первому игроку кучу, для которой $P(k)$ верно. Но мы уже знаем, что $P(k)$ верно для всех $k\leq n-1$, поэтому первый игрок, делая первый ход, может выиграть в игре с кучей из $n$ камней. Таким образом, $P(n)$ верно.

Следовательно, при безошибочной игре обоих игроков выигрывает тот, кто делает первый ход. Чтобы выиграть, первый игрок должен сделать первый ход так, чтобы оставить второму игроку кучу из $4$ камней, т.е. взять $2$ камня в свой первый ход.