Номер 5.73, страница 185 - гдз по алгебре 9 класс учебник Шыныбеков, Шыныбеков

5.73. Решите предыдущую задачу для трех игроков.

Для решения задачи для трех игроков, которых мы назовем Игрок 1, Игрок 2 и Игрок 3, воспользуемся теорией беспристрастных игр. Состояние игры с двумя кучками камней размеров $n$ и $m$ можно охарактеризовать одним числом — ним-суммой, которая вычисляется как побитовое исключающее ИЛИ (XOR) размеров кучек: $S = n \oplus m$.

Согласно теореме Шпрага–Гранди, любая беспристрастная игра эквивалентна игре Ним с одной кучкой определенного размера. В данном случае, игра с двумя кучками $(n, m)$ эквивалентна игре с одной кучкой размера $S = n \oplus m$. Ход в исходной игре соответствует изменению размера этой эквивалентной кучки. Важным свойством является то, что из состояния с ним-суммой $S$ всегда можно сделать ход в состояние с любой ним-суммой $S' < S$.

Таким образом, задача сводится к анализу более простой игры: три игрока (Игрок 1, Игрок 2, Игрок 3) по очереди изменяют количество камней в одной кучке размера $S$. За один ход игрок обязан уменьшить количество камней. Проигрывает тот, перед чьим ходом кучка оказывается пустой ($S=0$), так как он не может сделать ход. Два других игрока считаются выигравшими.

Рассмотрим два случая в зависимости от начальной ним-суммы $S_0 = n \oplus m$.

1. Начальная ним-сумма равна нулю: $S_0 = n \oplus m = 0$.
Эта ситуация возникает, когда размеры кучек равны, то есть $n=m$. Эквивалентная игра начинается с кучкой размера 0. Ход принадлежит Игроку 1. Поскольку кучка пуста, Игрок 1 не может сделать ход и немедленно проигрывает. Выигрывают Игрок 2 и Игрок 3.

2. Начальная ним-сумма не равна нулю: $S_0 = n \oplus m > 0$.
Эта ситуация возникает, когда размеры кучек не равны, то есть $n \neq m$. Эквивалентная игра начинается с кучкой размера $S_0 > 0$. Ход принадлежит Игроку 1. У него есть возможность уменьшить размер кучки до любого значения $S_1 < S_0$. Рациональный игрок, стремящийся не проиграть, выберет ход, который приводит к проигрышу другого игрока. Игрок 1 может уменьшить размер кучки до 0 (то есть выбрать $S_1=0$), так как $0 < S_0$.
Сделав такой ход, Игрок 1 оставляет после себя пустую кучку. Ход переходит к Игроку 2. Игрок 2 оказывается перед пустой кучкой, не может сделать ход и, следовательно, проигрывает. Игрок 1, обеспечив проигрыш другого игрока, сам выживает. Игрок 3 также выживает. Таким образом, выигрывают Игрок 1 и Игрок 3.
Стратегия Игрока 1 в случае $n \neq m$ заключается в том, чтобы сделать ход в позицию с нулевой ним-суммой. Это всегда возможно. Для этого Игрок 1 вычисляет $S=n \oplus m$ и изменяет одну из кучек, например, размера $n$, до нового размера $n' = n \oplus S$. Известно, что такой ход всегда корректен (то есть $n' < n$). Новая ним-сумма будет равна $n' \oplus m = (n \oplus S) \oplus m = (n \oplus m) \oplus S = S \oplus S = 0$.

Таким образом, исход игры полностью определяется начальными размерами кучек.

Ответ: Исход игры зависит от ним-суммы размеров кучек $S = n \oplus m$.

• Если $n \oplus m = 0$ (что эквивалентно $n=m$), то первый игрок проигрывает. Второй и третий игроки выигрывают.
• Если $n \oplus m \neq 0$ (что эквивалентно $n \neq m$), то у первого игрока есть выигрышная стратегия. Он делает ход в позицию с нулевой ним-суммой, что приводит к проигрышу второго игрока. Выигрывают первый и третий игроки.