8. 对三个小游戏的分析

三个小游戏，规则分别如下：

抓棋子：若干堆棋子，双方轮流从任一堆中抓取任意个棋子，取走最后一个者赢。
打木棍：一排木棍，双方轮流击打，一次可以击倒一根或相邻的两根，击倒最后一根者赢。
分硬币：若干堆硬币，两人轮流将任一堆分为数目不等的两堆，首先不能执行此操作者输。

Note

抓棋子就是经典的尼姆 (Nim) 游戏，我竟然独立地研究了它
以上游戏都属于 ICG (Impartial Combinatorial Games), 对此有一个 Sprague-Grundy 定理，内容基本与以下的分析相同

8.1. 分析

这三个看似不同的游戏其实都有着相同的本质，那就是——异或 (exclusive OR). 所谓异或是一种二进制的位运算。运算的规则是：用二进制表示参与运算的数，如果在某位上有奇数个数是 \(1\), 则结果的这一位上就是 \(1\), 反之是 \(0\).

对于抓棋子，操作者面对的局面可以用一些数的集合来表示，每个数代表一堆棋子的数目。这种表示法同样可以用于分硬币。对于打木棍，我们把挨在一起的木棍视为一“堆”，这种表示法也就可以适用了。

然后我们定义一个映射：\(V(x) = n\). \(n\) 是这样确定的：

如果一个数 \(x\) 代表的局面已无法进行下一步操作，\(V(x) = 0\). 比如抓棋子打木棍中 \(x = 0\), 分硬币中 \(x = 0, 1, 2\)
\(V(\Bbb{X})\) 等于组成局面 \(\Bbb{X}\) 的所有数的 \(V\) 值的异或
对于所有 \(k < n\), 都存在一个由 \(x\) 经过一步操作变成的局面 \(\Bbb{X}\), 使得 \(V(\Bbb{X}) = k\)
不存在一个由 \(x\) 经过一步操作变成的局面 \(\Bbb{X}\), 使得 \(V(\Bbb{X}) = n\)

注意一个数经过操作以后可能变成不只一个数，例如在打木棍和分硬币中，一堆可以变为两堆。

如果对一个局面，无论对方如何操作，你均有策略使其输掉，则称这种局面为输局。下面我们将证明 \(V(\Bbb{X}) = 0\) 的局面 \(\Bbb{X}\) 是输局。

首先，设 \(\Bbb{X}\) 经过一步操作后变为 \(\Bbb{Y}\), 则一定有 \(V(\Bbb{Y}) > 0\). 这是因为，游戏规则保证了每次只能对一个数进行操作。根据 \(V\) 值定义的第 4 条，没有一个数经过操作之后能保持 \(V\) 值不变。再根据异或运算的性质，总的 \(V\) 值也一定会变。

然后我们将证明当 \(V(\Bbb{X}) > 0\) 时，总存在一个经由一步操作变成的局面 \(\Bbb{Y}\), 使得 \(V(\Bbb{Y}) = 0\). 此时，我们要在 \(\Bbb{X}\) 中寻找一个数 \(x\), 使得 \(V(\Bbb{X}) \oplus V(x) < V(x)\)（\(\oplus\) 是表示异或的符号）。这样的 \(x\) 总是存在的，这是因为，将 \(V(\Bbb{X})\) 和所有数的 \(V\) 值写成二进制，设 \(V(\Bbb{X})\) 的最高位是第 \(i\) 位，检查所有 V 值的第 \(i\) 位，必然可以找到至少一个是 \(1\) 的，它就是符合要求的数。于是我们操作它使之变为 \(\Bbb{Y}\), 满足 \(V(\Bbb{Y}) = V(\Bbb{X}) \oplus V(x)\), 这样总的 \(V\) 值又变回了 \(0\). 这一操作也总是可行的，由定义的第 3 条保证。

此后，不管对方如何操作，你总可以保持 \(V = 0\) 一直到对方无法操作。

8.2. 映射关系

那么这个神秘的函数 \(V\) 是什么样子呢？

8.2.1. 抓棋子

对于抓棋子，映射关系很简单，\(V(x) = x\).

因为任何一个数都可以经过一步操作变为比它小的任意数，所以它的 \(V\) 值就只能等于它本身。

8.2.2. 打木棍

对于打木棍，一般来说，对于任意非负整数 \(k\):

\[\begin{split} \begin{split} V(12k) &= 4 (k \ne 0, V(0) = 0) \\ V(12k + 1) &= 1 \\ V(12k + 2) &= 2 \\ V(12k + 3) &= 8 (k \ne 0, 1, 3, V(3) = 3, V(15) = 7, V(39) = 3) \\ V(12k + 4) &= 1 (k \ne 2, V(28) = 5) \\ V(12k + 5) &= 4 \\ V(12k + 6) &= 7 (k \ne 0, 1, V(6) = 3, V(18) = 3) \\ V(12k + 7) &= 2 \\ V(12k + 8) &= 1 \\ V(12k + 9) &= 8 (k \ne 0, 1, 4, V(9) = 4, V(21) = 4, V(57) = 4) \\ V(12k + 10) &= 2 (k \ne 1, 2, 5, V(22) = 6, V(34) = 6, V(70) = 6) \\ V(12k + 11) &= 7 (k \ne 0, V(11) = 6) \end{split} \end{split}\]

1 - 99 范围内的数映射如下：

映射值	数
\(0\)
\(1\)	\(1, 4, 8, 13, 16, 20, 25, 32, 37, 40, 44, 49, 52, 56, 61, 64, 68, 73, 76, 80, 85, 88, 92, 97\)
\(2\)	\(2, 7, 10, 14, 19, 26, 31, 38, 43, 46, 50, 55, 58, 62, 67, 74, 79, 82, 86, 91, 94, 98\)
\(3\)	\(3, 6, 18, 39\)
\(4\)	\(5, 9, 12, 17, 21, 24, 29, 36, 41, 48, 53, 57, 60, 65, 72, 77, 84, 89, 96\)
\(5\)	\(28\)
\(6\)	\(11, 22, 34, 70\)
\(7\)	\(15, 23, 30, 35, 42, 47, 54, 59, 66, 71, 78, 83, 90, 95\)
\(8\)	\(27, 33, 45, 51, 63, 69, 75, 81, 87, 93, 99\)

8.2.3. 分硬币

暂未找到规律。1 - 99 范围内的数映射如下：

映射值	数
\(0\)	\(1, 2, 4, 7, 10, 20, 23, 26, 50, 53\)
\(1\)	\(3, 6, 9, 12, 15, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61\)
\(2\)	\(5, 8, 11, 14, 17, 29, 32, 35, 38, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 97\)
\(3\)	\(13, 16, 19, 22, 25, 30, 59, 62, 65, 68, 71, 74, 77, 86, 89, 92, 95, 98\)
\(4\)	\(18, 21, 24, 27, 33, 36, 39, 42, 45, 48, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94\)
\(5\)	\(41, 44, 47, 56, 80, 83, 96, 99\)
\(6\)
\(7\)	\(87, 90, 93\)

8.3. 对打木棍游戏中规律的证明

显然，对于任何非 \(0\) 数，都可以经一步操作使之 \(V\) 值变为 \(0\), 只要将其分为相等的两“堆”即可，所以任何非 \(0\) 数的 \(V\) 值都不等于 \(0\).

8.3.1. \(12k\)

考虑第一行形如 \(12k\) 的数，当 \(k \ne 0\), \(12k = 12(k - 1) + 7 + 3 + 2\), 而 \(V(12(k - 1) + 7) = 2\), \(V(3) = 3\), 所以只要击倒两根使之分为数量分别为 \(3\) 和 \(12(k - 1) + 7\) 的两堆即可使 \(V\) 值变为 \(2 \oplus 3 = 1\).

同理有：

\[\begin{split} \begin{split} 12k = 12(k - 1) + 8 + 3 + 1, V(12(k - 1) + 8) \oplus V(3) = 2 \\ 12k = 12(k - 1) + 8 + 2 + 2, V(12(k - 1) + 8) \oplus V(2) = 3 \end{split} \end{split}\]

存在一步操作使得 \(V < 4\).

关键是证明形如 \(12k\) 的数不可能经一步操作变成 \(V\) 值为 \(4\) 的局面。

\(4 = 1 \oplus 5 = 2 \oplus 6 = 3 \oplus 7\), 如果操作后的局面的 \(V\) 值为 \(4\), 则只可能是这三种情况。

\(V\) 值为 \(1\) 的数除以 \(12\) 的余数属于集合 \(\set{1, 4, 8}\); \(V\) 值为 \(5\) 的数除以 \(12\) 的余数属于集合 \(\set{4}\); 它们加起来以后余数属于集合 \(\set{0, 5, 8}\), 而形如 \(12k\) 的数经过一步操作后剩下的总数除以 \(12\) 的余数应为 \(11\) 或 \(10\), 因此不可能变成这种局面。

以下的证明沿用相同的方法，为了简洁，只写出数字和公式。

这里面，通过分析除以 \(12\) 后的余数排查可能的局面是通用方法，故先将各种可能列出：

\(V\)	可能出现的余数
\(1\)	\(\set{1, 2, 4, 5, 8, 9, 10}\)
\(2\)	\(\set{2, 3, 4, 7, 8, 10, 11}\)
\(3\)	\(\set{0, 2, 3, 4, 6, 8, 10, 11}\)
\(4\)	\(\set{0, 1, 2, 5, 6, 8, 9}\)
\(5\)	\(\set{1, 2, 4, 5, 6, 8, 9, 10}\)
\(6\)	\(\set{0, 2, 3, 4, 7, 10, 11}\)
\(7\)	\(\set{0, 2, 3, 6, 7, 8, 11}\)

其详细推理过程见“余数的推理过程”一节。

在 \(12k\) 的情况下，一步操作后的余数为 \(\set{10, 11}\), 不在 \(V = 4\) 时可能的余数集合里。

至此，我们证明了 \(V(12k) = 4 (k \ne 0)\) 是正确的。

8.3.2. \(12k + 1\)

一步操作后的余数为 \(\set{0, 11}\), 不在 \(V = 1\) 时可能的余数集合里。

8.3.3. \(12k + 2\)

\[ 1: 12k + 2 = 12k + 1 + 1, V(12k + 1) = 1 \]

存在一步操作使得 \(V < 2\).

一步操作后的余数为 \(\set{0, 1}\), 不在 \(V = 2\) 时可能的余数集合里。

8.3.4. \(12k + 3\)

\[\begin{split} \begin{split} 1&: 12k + 3 = 12k + 1 + 2, V(12k + 1) = 1 \\ 2&: 12k + 3 = 12k + 2 + 1, V(12k + 2) = 2 \\ 3&: 12k + 3 = 12(k - 1) + 4 + 10 + 1, V(12(k - 1) + 4) \oplus V(10) = 3, k \ne 0, 3 \\ 4&: 12k + 3 = 12(k - 1) + 2 + 11 + 2, V(12(k - 1) + 2) \oplus V(11) = 4, k \ne 0 \\ 5&: 12k + 3 = 12(k - 1) + 4 + 9 + 2, V(12(k - 1) + 4) \oplus V(9) = 5, k \ne 0, 3 \\ 6&: 12k + 3 = 12k + 2 + 1, V(12k) \oplus V(2) = 6, k \ne 0 \\ 7&: 12k + 3 = 12(k - 2) + 4 + 22 + 1, V(12(k - 2) + 4) \oplus V(22) = 7, k \ne 0, 1, 4 \\ 7&: 12k + 3 = 51 = 16 + 34 + 1, V(16) \oplus V(34) = 7, k = 4 \end{split} \end{split}\]

存在一步操作使得 \(V < 8\).

一步操作后的余数为 \(\set{1, 2}\), 不在 \(V = 8\) 时可能的余数集合（空集）里。

此例中 \(k = 0, 1, 3\) 时为例外，需单独验证。

\(k = 0\) 时以上 \(1, 2\) 仍成立，显然 \(V(3) = 3\)
\(k = 1\) 时以上 \(1 - 6\) 仍成立，考察 \(V = 7\) 时可能的余数集合，出现了 \(2\), 进一步排查发现这是不可能的
\(k = 3\) 时以上 \(1, 2\) 仍成立，考察 \(V = 3\) 时可能的余数集合，出现了 \(2\), 进一步排查发现这是不可能的

8.3.5. \(12k + 4\)

一步操作后的余数为 \(\set{2, 3}\), 考察 \(V = 1\) 时可能的余数集合，出现了 \(2\), 这只能由 \(28 = 11 + 15 + 2\) 造成，需要单独验证：

\[\begin{split} \begin{split} 1&: 28 = 11 + 15 + 2, V(11) \oplus V(15) = 1 \\ 2&: 28 = 22 + 5 + 1, V(22) \oplus V(5) = 2 \\ 3&: 28 = 26 + 1 + 1, V(26) \oplus V(1) = 3 \\ 4&: 28 = 23 + 3 + 2, V(23) \oplus V(3) = 4 \end{split} \end{split}\]

存在一步操作使得 \(V < 5\).

考察 \(V = 5\) 时可能的余数集合，出现了 \(2\), 进一步排查发现这是不可能的。

8.3.6. \(12k + 5\)

\[\begin{split} \begin{split} 1&: 12k + 5 = 12k + 4 + 1, V(12k + 4) = 1, k \ne 2 \\ 1&: 12k + 5 = 29 = 10 + 18 + 1, V(10) \oplus V(18) = 1, k = 2 \\ 2&: 12k + 5 = 12k + 1 + 3 + 1, V(12k + 1) \oplus V(3) = 2 \\ 3&: 12k + 5 = 12k + 1 + 2 + 2, V(12k + 1) \oplus V(2) = 3 \end{split} \end{split}\]

存在一步操作使得 \(V < 4\).

一步操作后的余数为 \(\set{3, 4}\), 不在 \(V = 4\) 时可能的余数集合里。

8.3.7. \(12k + 6\)

\[\begin{split} \begin{split} 1&: 12k + 6 = 12k + 2 + 3 + 1, V(12k + 2) \oplus V(3) = 1 \\ 2&: 12k + 6 = 12k + 1 + 3 + 2, V(12k + 1) \oplus V(3) = 2 \\ 3&: 12k + 6 = 12(k - 1) + 11 + 5 + 2, V(12(k - 1) + 11) \oplus V(5) = 3, k \ne 0, 1 \\ 4&: 12k + 6 = 12k + 5 + 1, V(12k + 5) = 4 \\ 5&: 12k + 6 = 12k + 4 + 2, V(12k) \oplus V(4) = 5, k \ne 0 \\ 6&: 12k + 6 = 12(k - 1) + 1 + 15 + 2, V(12(k - 1) + 1) \oplus V(15) = 6, k \ne 0 \end{split} \end{split}\]

存在一步操作使得 \(V < 7\).

一步操作后的余数为 \(\set{4, 5}\), 不在 \(V = 7\) 时可能的余数集合里。

此例中 \(k = 0, 1\) 时为例外，需单独验证。首先以上 \(1, 2\) 仍成立，考察 \(V = 3\) 时可能的余数集合，出现了 \(4\), 进一步排查发现这是不可能的。

8.3.8. \(12k + 7\)

\[ \begin{split} 1&: 12k + 7 = 12k + 2 + 3 + 2, V(12k + 2) \oplus V(3) = 1 \end{split} \]

存在一步操作使得 \(V < 2\).

一步操作后的余数为 \(\set{5, 6}\), 不在 \(V = 2\) 时可能的余数集合里。

8.3.9. \(12k + 8\)

一步操作后的余数为 \(\set{6, 7}\), 不在 \(V = 1\) 时可能的余数集合里。

8.3.10. \(12k + 9\)

\[\begin{split} \begin{split} 1&: 12k + 9 = 12k + 8 + 1, V(12k + 8) = 1 \\ 2&: 12k + 9 = 12k + 7 + 2, V(12k + 7) = 2 \\ 3&: 12k + 9 = 12k + 7 + 1 + 1, V(12k + 7) \oplus V(1) = 3 \\ 4&: 12k + 9 = 12(k - 2) + 4 + 28 + 1, V(12(k - 2) + 4) \oplus V(28) = 4, k \ne 0, 1, 4 \\ 5&: 12k + 9 = 12(k - 1) + 8 + 12 + 1, V(12(k - 1) + 8) \oplus V(12) = 5, k \ne 0 \\ 6&: 12k + 9 = 12(k - 1) + 7 + 12 + 2, V(12(k - 1) + 7) \oplus V(12) = 6, k \ne 0 \\ 7&: 12k + 9 = 12k + 5 + 3 + 1, V(12k + 5) \oplus V(3) = 7 \end{split} \end{split}\]

存在一步操作使得 \(V < 8\).

一步操作后的余数为 \(\set{7, 8}\), 不在 \(V = 8\) 时可能的余数集合（空集）里。

此例中 \(k = 0, 1, 4\) 时为例外，需单独验证。首先以上 \(1 - 3\) 仍成立，考察 \(V = 4\) 时可能的余数集合，出现了 \(8\), 进一步排查发现这是不可能的。

8.3.11. \(12k + 10\)

\[ \begin{split} 1&: 12k + 10 = 12k + 8 + 2, V(12k + 8) = 1 \end{split} \]

存在一步操作使得 \(V < 2\).

一步操作后的余数为 \(\set{8, 9}\), 考察 \(V = 2\) 时可能的余数集合，出现了 \(8\), 这只能是以下三种情况：

\(22 = 11 + 9 + 2, V(11) \oplus V(9) = 2\)
\(34 = 11 + 21 + 2, V(11) \oplus V(21) = 2\)
\(70 = 11 + 57 + 2, V(11) \oplus V(57) = 2\)

这三种情况下均有：

\[\begin{split} \begin{split} 3&: 12k + 10 = 12k + 7 + 1 + 2, V(12k + 7) \oplus V(1) = 3 \\ 4&: 12k + 10 = 12k + 6 + 3 + 1, V(12K + 6) \oplus V(3) = 4, k \ne 0, 1 \\ 4&: 12k + 10 = 22 = 15 + 6 + 1, V(15) \oplus V(6) = 4, k = 1 \\ 5&: 12k + 10 = 12k + 8 + 2, V(12k) \oplus V(8) = 5 \end{split} \end{split}\]

一步操作后的余数为 \(\set{8, 9}\), 不在 \(V = 6\) 时可能的余数集合里。

8.3.12. \(12k + 11\)

\[\begin{split} \begin{split} 1&: 12k + 11 = 12k + 7 + 3 + 1, V(12k + 7) \oplus V(3) = 1 \\ 2&: 12k + 11 = 12k + 4 + 6 + 1, V(12k + 4) \oplus V(6) = 2, k \ne 2 \\ 2&: 12k + 11 = 35 = 12 + 22 + 1, V(12) \oplus V(22) = 2, k = 2 \\ 3&: 12k + 11 = 12k + 8 + 2 + 1, V(12k + 8) \oplus V(2) = 3 \\ 4&: 12k + 11 = 12k + 6 + 3 + 2, V(12k + 6) \oplus V(3) = 4, k \ne 0, 1 \\ 4&: 12k + 11 = 11 = 9 + 2, V(9) = 4, k = 0 \\ 4&: 12k + 11 = 23 = 21 + 2, V(21) = 4, k = 1 \\ 5&: 12k + 11 = 12k + 5 + 4 + 2, V(12k + 5) \oplus V(4) = 5 \\ 6&: 12k + 11 = 12k + 6 + 4 + 1, V(12k + 6) \oplus V(4) = 6, k \ne 0, 1 \\ 6&: 12k + 11 = 23 = 22 + 1, V(22) = 6, k = 1 \end{split} \end{split}\]

存在一步操作使得 \(V < 6\).

一步操作后的余数为 \(\set{9, 10}\), 不在 \(V = 7\) 时可能的余数集合里。

此例中 \(k = 0\) 时为例外，需单独验证。首先以上 \(1 - 5\) 仍成立，考察 \(V = 6\) 时可能的余数集合，出现了 \(10\), 进一步排查发现这是不可能的。

注意这其实是个数学归纳法，对某个数成立建立在对比它小的所有数都成立的基础上。

证毕。

8.3.13. 余数的推理过程

在打木棍游戏中，某个数经过一次操作后变为两个数。根据前面总结出的规律，这两个数除以 \(12\) 的余数只能是一个或几个值，二者和的余数范围也就可以确定了。

\(1 = 2 \oplus 3 = 4 \oplus 5 = 6 \oplus 7\)

\[\begin{split} \begin{alignat}{3} 2& \set{2, 7, 10}&, 3& \set{3, 6}& \implies& \set{1, 4, 5, 8, 10} \\ 4& \set{0, 5, 9}&, 5& \set{4}& \implies& \set{1, 4, 9} \\ 6& \set{10, 11}&, 7& \set{3, 6, 11}& \implies& \set{1, 2, 4, 5, 9, 10} \end{alignat} \implies \set{1, 2, 4, 5, 8, 9, 10} \end{split}\]

\(2 = 1 \oplus 3 = 4 \oplus 6 = 5 \oplus 7\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 3& \set{3, 6}& \implies& \set{4, 7, 10, 11, 2} \\ 4& \set{0, 5, 9}&, 6& \set{10, 11}& \implies& \set{3, 4, 7, 8, 10, 11} \\ 5& \set{4}&, 7& \set{3, 6, 11}& \implies& \set{3, 7, 10} \end{alignat} \implies \set{2, 3, 4, 7, 8, 10, 11} \end{split}\]

\(3 = 1 \oplus 2 = 4 \oplus 7 = 5 \oplus 6\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 2& \set{2, 7, 10}& \implies& \set{2, 3, 6, 8, 10, 11} \\ 4& \set{0, 5, 9}&, 7& \set{3, 6, 11}& \implies& \set{0, 3, 4, 6, 8, 11} \\ 5& \set{4}&, 6& \set{10, 11}& \implies& \set{2, 3} \end{alignat} \implies \set{0, 2, 3, 4, 6, 8, 10, 11} \end{split}\]

\(4 = 1 \oplus 5 = 2 \oplus 6 = 3 \oplus 7\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 5& \set{4}& \implies& \set{0, 5, 8} \\ 2& \set{2, 7, 10}&, 6& \set{10, 11}& \implies& \set{0, 1, 5, 6, 8, 9} \\ 3& \set{3, 6}&, 7& \set{3, 6, 11}& \implies& \set{0, 2, 5, 6, 9} \end{alignat} \implies \set{0, 1, 2, 5, 6, 8, 9} \end{split}\]

\(5 = 1 \oplus 4 = 2 \oplus 7 = 3 \oplus 6\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 4& \set{0, 5, 9}& \implies& \set{1, 4, 5, 6, 8, 9, 10} \\ 2& \set{2, 7, 10}&, 7& \set{3, 6, 11}& \implies& \set{1, 4, 5, 6, 8, 9, 10} \\ 3& \set{3, 6}&, 6& \set{10, 11}& \implies& \set{1, 2, 4, 5} \end{alignat} \implies \set{1, 2, 4, 5, 6, 8, 9, 10} \end{split}\]

\(6 = 1 \oplus 7 = 2 \oplus 4 = 3 \oplus 5\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 7& \set{3, 6, 11}& \implies& \set{0, 2, 3, 4, 7, 10, 11} \\ 2& \set{2, 7, 10}&, 4& \set{0, 5, 9}& \implies& \set{0, 2, 3, 4, 7, 10, 11} \\ 3& \set{3, 6}&, 5& \set{4}& \implies& \set{7, 10} \end{alignat} \implies \set{0, 2, 3, 4, 7, 10, 11} \end{split}\]

\(7 = 1 \oplus 6 = 2 \oplus 5 = 3 \oplus 4\)

\[\begin{split} \begin{alignat}{3} 1& \set{1, 4, 8}&, 6& \set{10, 11}& \implies& \set{0, 2, 3, 6, 7, 11} \\ 2& \set{2, 7, 10}&, 5& \set{4}& \implies& \set{2, 6, 11} \\ 3& \set{3, 6}&, 4& \set{0, 5, 9}& \implies& \set{0, 3, 6, 8, 11} \end{alignat} \implies \set{0, 2, 3, 6, 7, 8, 11} \end{split}\]