Доказательство (теорема Шпрага-Гранди для Нима). Обозначим $s = n_1 \oplus n_2 \oplus \ldots \oplus n_k$. Проверим два условия для $P$-позиций: $(1)$ Из терминальной позиции (все кучки пусты) $s = 0$ — верно. $(2)$ Из любой позиции с $s = 0$ любой ход приводит к $s \neq 0$: при ходе в кучку $i$, изменяя $n_i$ на $n_i' < n_i$, новый $\mathrm{XOR} = s \oplus n_i \oplus n_i'$. Так как $s = 0$, новый $\mathrm{XOR} = n_i \oplus n_i' \neq 0$ (ибо $n_i \neq n_i'$). $(3)$ Из любой позиции с $s \neq 0$ существует ход в позицию с $s' = 0$: пусть старший бит $s$ равен 1 в некоторой кучке $n_i$. Положим $n_i' = n_i \oplus s < n_i$ (так как старший бит обнуляется). Тогда новый $\mathrm{XOR} = s \oplus n_i \oplus n_i' = s \oplus s = 0$. Таким образом, $P$-позиции — в точности позиции с $\mathrm{XOR} = 0$, что и требовалось доказать.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!