Question

4. Есть 2 кучки камней - в одной 20, в другой 31. За ход можно взять 1 камень из любой кучки или по 1 камню из обеих. Играют двое, выигрывает тот, кто забирает последний камень. Кто победит при правильной игре обоих игроков?

Answer 1

Ответ:

Выигрывает первый игрок

Пошаговое объяснение:

Для выигрыша первому игроку достаточно сохранять чётное кол-во камней в обеих кучках. Для этого он первым своим ходом должен взять один камень из кучки в которой 31 камней. Далее, второй игрок своим ходом должен будет сделать нечётным кол-во камней либо в одной,  либо в обеих кучках. Следующим ходом первый игрок опять может добиться того чтобы в обеих кучках стало по чётному кол-во камней. Продолжая такую стратегию первый игрок выиграет, потому что после последнего хода кол-во камней в каждой кучке 0, то есть чётное кол-во

Answer 2

Для того чтобы определить, кто победит при правильной игре обоих игроков, можно использовать стратегию обратной игры (backward induction).

Посмотрим на возможные состояния игры:

1. Когда в первой кучке 20 камней, а во второй 31 камень.
2. Когда в первой кучке 19 камней, а во второй 31 камень.
3. Когда в первой кучке 20 камней, а во второй 30 камней.
4. Когда в первой кучке 19 камней, а во второй 30 камней.

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

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

Итак, при правильной игре обоих игроков победит тот, кто начинает игру, имея в первой кучке 19 камней и во второй кучке 31 камень.