斯普拉格-格朗迪定理

这个Sprague-Grundy定理这是一份关于公正的声明游戏．

解释

在里面组合博弈-获胜位置，我们分析了公正比赛的获胜位置。在试图找到一组nim桩是赢桩还是输桩的一般特征时，出现了几个问题。在这里，我们通过给出nim的得失位置的完整描述来回答这些问题。

索赔

假设我们有nim大小的堆 $（a_1，a_2，a_2，a_n）$ . 让 $b_i$ 以2为底表示 $阿尤伊$ ．如果把所有的数字都加进去，nim的位置就输了 $\ {b_i \} _ {i = 1} ^ {n}$ ，则每个二进制位置中的1数为偶数，反之亦然。

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

$\开始{array}{cccc}&&1&1\\&1&0\\1&0&0\\\结束{array}$

我们可以构造一个数字来表示每个二进制位置上的1的奇偶性。我们称之为尼姆森在这些数字中。查看表中的每一列，我们看到1的列有一个1，10的列有两个1，100的列和1000的列都有一个1。我们的最低金额是 $1101 _2 \ = 13$ ．

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

$\开始{array}{cccc}&1&1\\1&0&0&1\\1&1&1&0\\\ hline 0&0&0&0\\\结束{array}$

最后一行表示1个数的奇偶性，这使我们知道这些数的nim和为0。

我们将对获胜位置的描述修改为桩尺寸的nim和不为0，这与原始定义相同。为了验证这是否准确地描述了一组赢和输的位置，我们检查了3件事。

首先，很明显，没有石头的游戏是输的，并且nim sum为0。

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

第三，若我们处于一个胜利的位置，我们有形式的nim和 $1x_2$ 哪里 $x$ 是一个二进制字符串。我们选择一个1与nim总和中最左边的1位于同一位置的桩。我们通过翻转nim和中相应位置上有1的每个数字来改变这个数字。这些新数字的nim和将为0，这是一个亏损的位置。这是一个练习，表明新的数字小于原来的数字，因此构成一个有效的移动。 $_ \广场$

比起判断一个头寸是赢是输，nimsum实际上给了我们更多的信息;它还为该位置赋值。如果一个头寸有nimsum $K$ ，则从该位置始终可以移动到具有nim sum的位置 $J$ 无论如何 $j < k,$ 不可能移动到具有nim sum的位置 $K$ . 要想看到这一点，可以考虑任何获胜位置都可以达到0位的证据，并用任何较小的数字替换0。所描述的方法将扩展到此。

我们花了很多时间为一个公正的游戏，尼姆，发展理论。事实上，这就是我们理解任何一般公平博弈所需要的全部理论！我们得到了以下令人惊讶的结果：

斯普拉格-格朗迪定理

公平博弈的任何位置都相当于一定大小的nim堆。 $_ \广场$

我们可以通过小案例依次建立，为任何公平博弈中的位置分配nim总和。这个nim位置和最小的非负整数是多少 $K$ 这样我们就不能移动到nim sum的位置 $K$ . 这要求我们计算每个位置的nim和。因为游戏总是会结束，所以这个计算是有限的。然而，它可能需要大量的计算，计算机可能会很有用。

Sprague-Grundy定理的证明与我们之前的证明相同，我们检查了3条语句。

工作的例子

两个玩家玩一个游戏，从一堆 $N$ 石头。在每一回合中，一名玩家将从牌堆中移出 $1,2,3，\ldots， \mbox{或}k$ 石头。拿最后一块石头的人获胜。根据 $N$ 和 $K$ ，每个位置的nim和。

为 $j \ leq k$ ，游戏的nim和 $J$ 石头将会 $J$ . 这是很容易看到的感应开始于 $j = 0$ . 什么时候 $j=k+1$ ，这是一个亏损头寸，因此nim和将为0。如果我们重复这一点，我们可以归纳地看到 $我$ 和 $i+k+1$ 永远都是一样的。所以nim的总和 $N$ 我们最多可以搬走的石头 $K$ 是 $n\pmod{k+1}。$ $_ \广场$

奇数尼姆和尼姆一样，只是你只能从一堆石头中取出奇数块石头。确定单个桩的nim总和 $N$ 石头。

由于我们只能从这堆石头中取出奇数块石头，所以如果石头的数量是偶数，游戏将始终是一个失败的位置，如果石头的数量是奇数，游戏将始终是一个胜利的位置。从一个获胜的位置，我们只能到达0位置，因此所有获胜的位置都有nim和1。因此，nim金额为 $n\pmod{2}$ ． $_ \广场$

有关……

目录

两个玩家玩一个游戏，从一堆 N N N石头。在每一回合中，一名玩家将从牌堆中移出 1. , 2. , 3. , … , 或 K 1,2,3，\ldots， \mbox{或}k 1.,2.,3.,…,或K石头。拿最后一块石头的人获胜。根据 N N N和 K K K，每个位置的nim和。

奇数尼姆和尼姆一样，只是你只能从一堆石头中取出奇数块石头。确定单个桩的nim总和 N N N石头。

两个玩家玩一个游戏，从一堆 $N$ 石头。在每一回合中，一名玩家将从牌堆中移出 $1,2,3，\ldots， \mbox{或}k$ 石头。拿最后一块石头的人获胜。根据 $N$ 和 $K$ ，每个位置的nim和。

奇数尼姆和尼姆一样，只是你只能从一堆石头中取出奇数块石头。确定单个桩的nim总和 $N$ 石头。