Question

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

Answer 1

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

Answer 2

Это классическая задача на комбинаторную игру, известная как "Игра в камни" или "Ним". Для определения выигрышной стратегии, давайте рассмотрим ситуацию, когда на очереди первый ход.

1. Если в начале игры в кучке 6 камней, то первый игрок может взять 1, 2 или 3 камня. Независимо от выбора, у второго игрока всегда будет возможность взять оставшиеся камни и победить. Таким образом, при безошибочной игре обоих игроков выиграет ВТОРОЙ игрок.

2. Если у первого игрока была бы возможность оставить в кучке 4 камня после своего хода, то он мог бы выиграть. Это обеспечивало бы симметрию ситуации и вынуждало бы второго игрока оставить в кучке 1, 2 или 3 камня. Тогда первый игрок мог бы сделать так, чтобы на следующем ходе у него оставалось ровно 4 камня и т.д. Таким образом, выигрышный первый ход - взять 2 камня.

Таким образом, если игроки играют безошибочно, выигрывает второй игрок. А если первый игрок хочет выиграть, то его первый ход должен быть взятие 2 камней.