斯普拉格心胸狭窄的人定理

的Sprague-Grundy定理一份声明是否公正<一个href="//www.parkandroid.com/wiki/combinatorial-games-definition/" class="wiki_link" title="游戏" target="_blank">游戏．

在<一个href="//www.parkandroid.com/wiki/combinatorial-games-winning-positions/" class="wiki_link" title="组合游戏-获胜的位置" target="_blank">组合游戏-获胜的位置，分析了公平博弈的获胜位置。在试图找出一组nim堆是赢仓还是输仓的一般特征时，出现了几个问题。在这里，我们通过给出nim的赢和输的位置的完整描述来回答这些问题。

索赔

假设我们有各种大小的nim堆 $(a_1, a_2， \ldots, a_n)$．让 $b_i$以2为底表示 $ai$．如果把所有的数字都加进去，nim的位置就输了 $\ {b_i \} _ {i = 1} ^ {n}$，则每个二进制位置上1的个数为偶数，否则为赢。

在我们证明这个说法之前，让我们看一个例子，看看我们的意思。如果nim桩有尺寸 $(3、6、8)$，那么我们可以把这些数写成 $11 _2, 110 _2, 1000 _2$．我们想要看看这些数字的每个二进制位置，所以让我们把它们排列在一个表格中:

$开始\{数组}{预备}& & 1 & 1 \ \ & 1 & 1四维\ \ 1 & 0 & 0 & 0 \ \ \{数组}结束$

我们可以构造一个数字来表示每个二进制位置上的1的奇偶性。我们称之为nim-sum这些数字。看看表中的每一列，我们可以看到1的一列有一个1,10的一列有两个1,100和1000的一列都有一个1。我们的求和是 $1101 _2 \ = 13$．

如果桩有尺寸 $7日,9日,14岁$，那么我们可以把这些数写成 $111 _2, 1001 _2, 1110 _2$．我们想要看看这些数字的每个二进制位置，所以让我们把它们排列在一个表格中:

$开始\{数组}{预备}& 1 & 1 & 1 \ \ 1 & 0四维& 1 \ \ 1 & 1 & 1 & 0 \ \ \线0 & 0 & 0 & 0 \ \ \{数组}结束$

最后一行表示的是1的奇偶性，这让我们知道这些数的尼姆和是0。

我们将对获胜位置的描述进行修改，使其为桩大小的尼姆和不为0，这与原始定义等价。为了验证这准确地描述了一组赢和输的位置，我们检查了3件事。

首先，很明显，没有石头的游戏是输的，nimsum为0。

第二，如果我们处于亏损的位置，我们的尼姆和为0。如果我们从一堆石头中移走，我们改变了1在一列中的位置，这将使nimsum不再为0。

第三，如果我们处于有利地位，我们就有nimsum的形式 $1 x_2$,在那里 $x$是一个二进制字符串。我们选择一堆，其中1的位置和最左边的1的位置相同。我们通过翻转每一位在nimsum中对应位置上有1的数字来改变这个数。这些新数字的总和将是0，这是一个亏损的位置。这是一个练习，以表明新数字小于原始数字，因此构成一个有效的移动。 $_ \广场$

比起判断一个头寸是赢是输，nimsum实际上给了我们更多的信息;它还为该位置赋值。如果一个头寸有nimsum $k$，然后从那个位置总是有可能移动到一个具有nimsum的位置 $j$对于任何 $j < k,$而且不可能换到一个有“尼姆和”的职位 $k$．为了理解这一点，考虑任何获胜的位置都可以达到0的证明，并用任何更小的数字替换0。所描述的方法将扩展到这一点。

我们花了很多时间来研究一个公正的博弈，尼姆。事实上，这就是我们理解任何公平游戏所需要的全部理论!我们有以下令人惊讶的结果:

Sprague-Grundy定理

公平游戏中的任何位置都相当于一定大小的尼姆堆。 $_ \广场$

我们可以通过在小情况下按顺序建立，为任何公正博弈中的位置分配一个尼姆和。的位置的和最小的非负整数是多少 $k$这样我们就不能移动到一个带有nimsum的位置 $k$．这就要求我们计算每个移动位置的尼姆和。因为游戏总是会结束，所以这种计算是有限的。然而，它可能会得到计算密集型，一台计算机可能是有用的。

斯普拉格- grundy定理的证明和我们之前的证明是一样的，我们检查了3个陈述。

两个玩家玩一个游戏，从一堆 $n$石头。在每个回合，一个玩家从堆中移出 $1,2,3，\ldots， \mbox{或}k$石头。谁拿走最后一块石头谁就赢。用…来决定 $n$和 $k$，即每个头寸的总和。

---

为 $j \ leq k$，这个游戏的nimsum $j$石头将会 $j$．这很容易归纳出来 $j = 0$．当 $j = k + 1$，这是一个亏损的位置，所以nim-sum将是0。如果我们重复这个，我们可以归纳出 $我$和 $I + k + 1$都是一样的。所以nim和 $n$我们最多能移走的地方 $k$是 $N \pmod{k + 1}。$ $_ \广场$

奇尼姆和尼姆很像，只是你只能从一堆石头中移走奇数块。确定一堆的尼姆和 $n$石头。

---

因为我们只能从一堆石头中取出奇数的石头，所以如果石头的数量是偶数，游戏将永远是一个失败的位置，如果石头的数量是奇数，游戏将永远是一个胜利的位置。从一个赢的位置，我们只能到0，所以所有赢的位置都是和1。因此，尼姆和是 $n \ pmod {2}$． $_ \广场$