Question

Постройте дерево перебора вариантов для игры с камнями при S = 6. Выясните, какова начальная позиция — выигрышная или проигрышная. Почему? Постройте неполное дерево игры с доказательством стратегии выигрывающего игрока.​

Answer 1

Хорошо, давайте начнем с построения дерева перебора вариантов для игры с камнями при S = 6.

Камни: 6 НАЧАЛЬНАЯ
/ | \
-1 -2 -3

Пошаговое решение:
1. Изначально у нас есть 6 камней.
2. Игрок может взять 1, 2 или 3 камня.
- Если игрок возьмет 1 камень, останется 5 камней.
- Если игрок возьмет 2 камня, останется 4 камня.
- Если игрок возьмет 3 камня, останется 3 камня.
3. Далее каждый взятый камень приведет к новым веткам дерева.
- Если осталось 5 камней после взятия 1 камня:
- Игрок может взять 1, 2 или 3 камня.
- Если игрок возьмет 1 камень, останется 4 камня.
- Если игрок возьмет 2 камня, останется 3 камня.
- Если игрок возьмет 3 камня, останется 2 камня.
- Если осталось 4 камня после взятия 2 камней:
- Игрок может взять 1, 2 или 3 камня.
- Если игрок возьмет 1 камень, останется 3 камня.
- Если игрок возьмет 2 камня, останется 2 камня.
- Если игрок возьмет 3 камня, останется 1 камень.
- Если осталось 3 камня после взятия 3 камней:
- Игрок может взять 1, 2 или 3 камня.
- Если игрок возьмет 1 камень, останется 2 камня.
- Если игрок возьмет 2 камня, останется 1 камень.
- Если игрок возьмет 3 камня, останется 0 камней.

Теперь давайте выясним, какова начальная позиция - выигрышная или проигрышная.
Для этого нам нужно посмотреть на все возможные конечные состояния игры при условии максимальных ходов от обоих игроков и определить, есть ли выигрышная позиция.

Конечные состояния игры с количеством оставшихся камней:
- 0 камней: Если остается 0 камней, то это означает, что последний игрок, который сделал свой ход, победил. В данном случае, победитель - игрок, который начинает первый ход.
- 1 камень: В этом случае независимо от того, сколько камней первый игрок берет в начале, второй игрок всегда может взять оставшийся 1 камень и победить.
- 2 камня: В этом случае, независимо от того, сколько камней первый игрок берет в начале, второй игрок всегда может взять оставшийся 2 камня и победить.
- 3 камня: В этом случае, независимо от того, сколько камней первый игрок берет в начале, второй игрок всегда может взять оставшийся 3 камня и победить.
- 4 камня: Пусть первый игрок возьмет 1 камень. Тогда останется 3 камня и второй игрок сможет победить в следующем ходу.
- 5 камней: Пусть первый игрок возьмет 2 камня. Тогда останется 3 камня и второй игрок сможет победить в следующем ходу.
- 6 камней: Пусть первый игрок возьмет 3 камня. Тогда останется 3 камня и второй игрок сможет победить в следующем ходу.

Исходя из вышеизложенных конечных состояний, начальная позиция (6 камней) является проигрышной, так как второй игрок всегда может выиграть, независимо от игры первого игрока.

Теперь построим неполное дерево игры с доказательством стратегии выигрывающего игрока:

Камни: 6 ЛУЧШИЙ
/ | \
-1 -2 -3

Пошаговое решение:
1. Игрок может взять 1, 2 или 3 камня, и переходит ход ко второму игроку.
2. Второй игрок выбирает такое количество камней, чтобы оставить в первом ходе кол-во камней, равное 4.
3. Первый игрок берет 1 камень, оставляя во втором ходе кол-во камней, равное 3.
4. Второй игрок берет 2 камня, оставляя в первом ходе кол-во камней, равное 1.
5. Первый игрок берет 1 камень и проигрывает, так как остается 0 камней.

Таким образом, доказано, что при игре с 6 камнями начальная позиция является проигрышной, так как выигрывающая стратегия для второго игрока всегда существует.