最近几天看《决胜21天》，看到一个有趣的问题，叫“尼姆博奕”。火树大佬直接知道答案，但我不知道。听了答案之后我觉得形式很奇怪，准备自己推一遍。
在开始探究之前，我们需要先严格地叙述这个问题：
棋盘上有10行，每行分别有1-10个棋子。两个参与者轮流抓取棋子，每次至少抓取1个，至多抓取一整行所有剩余棋子，每次抓取只能在同一行内进行。最后抓取者获胜。有何必胜策略？
上述问题是出现在电视节目中的版本。广义的尼姆博弈问题并不要求有几行，每行有几个棋子，因此可以一般化为有 行，每行有 个棋子。
为了方便研究做如下概念和符号的规定：
（1）将每一种局面（或者称为每一种状态）用一个向量 表示。例如 表示三行，每行各有1,2,3个棋子。其中添加任意多个 或若干个数字交换位置依然表示同一个状态。
（2）若先手方获胜，则总共抓取次数为奇数，存在先手必胜策略的状态称为“奇状态”；若后手方获胜，则总共抓取次数为偶数，存在后手必胜策略的状态称为“偶状态”。
（3）设状态 ， 二者都按从小到大排列，且行数较少的补若干个零至向量规模相同。若 且对所有 不同时取等号，则称 是 的子状态，记作 。若 与 中只有一个不同的元素，则称 为 的相邻子状态。
注：子状态的实际意义是可以经过若干次抓取得到的状态；而相邻子状态表示可以经过1次抓取得到的状态。
按照直觉来讲，这种没有运气成分的游戏是应该是有必胜策略的。但直觉总是不严格的，要下定论还需严格证明。
定理1.1：对于任意给定的一种状态，必为且仅为 奇状态 或 偶状态 其中之一。
上面定理表明，要么先手方要么后手方一定有必胜策略。究竟谁能必胜？这是一个比较复杂的问题，不妨先从简单的情景开始探索。
先研究两行的情景，显然 是一个偶状态。那么 就是奇状态，因为先手方可以通过一次抓取将其变成 。
再看 ：如果先手方抓取2个（即抓完一行），那么后手方只需把另外一行都抓走即可获胜。如果只抓一个，那么剩 又是奇状态。因此后手方是可以必胜的。
依此类推，可以得到如下结论：
定理2.1： 一定是偶状态。
推论2.2： 其中 一定是奇状态。
上述定理2.1的证明中阐述了后手方的策略：无论先手方怎样抓取，后手方只要原封不动地copy到另一行，最终一定能获胜。这种策略称为“跟随策略”。
三行的情景中，若有两行棋子数量一样，那么先手方只要把另一行拿光，就能构成 型的偶状态。若三行的棋子数量各不相同，情景就有些复杂。
首先观察 ，发现他是一个偶状态（读者自证）。那么由此可推得 在 时一定是奇状态。而 是奇状态，因为有两行数量相同。由此发现 若能构成奇状态，则必有 。
定理2.3：对任意给定的 ，有且仅有一个 使 为偶状态。
既然能唯一确定，那么唯一确定到几？从定理2.3中的存在性证明可以得到如下推论：
推论2.4：若 为偶状态，则必有 。
同理也可以得到 。
我经过一一验证，整理出了如下表格：
表中每一行和每一列的表头表示给定的 ，表内的数为与给定 适配的 。
观察这些偶状态有什么共同特征：以 为表头的列依次递增，而以 为表头的列依次递减。即
①对任意 ,均有 是偶状态；
②对任意，均有 是偶状态。
（注：上述规律是根据表格归纳出来的，暂无严格证明。其作用只是激发了下面的想法，并不做论证依据。）
即 与 这两个偶状态叠加后的仍为偶状态，同样 与 叠加后仍为偶状态。事实上，上面两组叠加按照其他方式叠加，即叠加成四行状态 也是偶状态。由此发现，满足特定条件的两种简单的偶状态以任意方式叠加的结果依然是偶状态。
于是不禁想到：是否能通过若干个偶状态叠加的方式，得到更多更复杂的偶状态一般形式？
在上表中，发现很多三行的状态能表示成 的形式（即 与 叠加）。事实上，两行的偶状态 型也可以分为若干个偶状态叠加。
但有些时候按这种方式叠加得到的不是偶状态，比如 。因此并不是两行型偶状态以任意方式叠加都能得到偶状态。那么能否得到更弱的结论：某些两行型偶状态以某些方式叠加一定能得到偶状态？
观察哪些叠加方式破坏了偶状态：
①最小是1的
②最小是2的
③最小是3的
发现他们的共同特征：情景①中，最大数到达某个偶数，但另外两个数没有到达；情景②中，最大数到达某个4的倍数，但另外两个数没到达……
每次到达偶数，状态反转。这个性质让人不禁想到二进制。
任意正整数 可写成若干个不相同的 相加的形式，这就是 的二进制表示，例如 。
将形如 的状态为基本偶状态，那么任意一个两行型的偶状态可以表示成若干个互不相同的基本偶状态叠加（表示方式与二进制相同）。
接下来考察通过若干个基本偶状态形成三行状态的奇偶性。最简单的形式即为 。在这种形式中，若 ，则一定不是偶状态，因为有两行棋子数量相同，这种叠加方式可以理解为打破了原来的二进制拆分方式。如果不打破原有的二进制拆分方式，就能采用类似于两行型中的跟随策略。但如果有 变成一个 ，对方取走 个可能会无法跟随。
不同的基本偶状态叠加形成的三行型一定是偶状态吗？下面进行证明。
定理3.1：设 为两个互不相交的非负整数集，则状态 是偶状态，其中
在这种证明思路下，甚至可以将定理做如下扩充：
定理3.2：设 为三个互不相交的非负整数集，则 一定是偶状态，其中 。
该定理中所述的状态构成的集合即为上述集合 ，其描述了三行偶状态的一般形式。定理3.1是定理3.2的在 其中一个为空集时的特殊情况。
上述②的证明过程中反映了偶状态下后手方的必胜策略。但写成数学语言有些抽象，下面举例子直观地说明：
对于一个三行状态 ，先将其分解为二进制，如下图所示
发现 成分均有奇数个。最大的 ，三行的棋子数都含有该元素，随便挑一堆下手，比如挑第三行。设要抓到剩 个棋子，那么 的二进制首位一定是0，后面几位的选取均为了保持相应的 出现偶数个，因此 的二进制表示应当如下图所示
剩 个。事实上，无论剩多少个，由于第一位从1变成0，因此一定是减少了，可以通过抓取操作得到，而不是需要添加。
定理3.2的证明过程中，事实上并不要求行数为3。可以将上述偶状态的一般形式及后手必胜策略拓展至任意多行。
定理4.1： 行状态是偶状态当且仅当其相当于每种基本偶状态各偶数个进行叠加（即在每个数的二项式分解中，所有 均出现偶数次）。
证明思路与定理3.2相同，具体证明过程略。
注：此处的“叠加”中，同种基本偶状态只分布在不同的行中，不能叠起来，如下图所示：
回到最初的题目情境，他是否偶状态？首先将他们进行二进制分解，如下图所示：
下方红色数字表示每个 出现的个数。本情景中， 均出现奇数次，因此不是偶状态，故先手方有必胜策略。先手必胜策略的第一步如下：
出现奇数次的最高位是 位，因此需要在相关的 中选一行抓取。比方说从 中取，将其变成 ，即可将这个局面变为
由此达到了偶状态。
综上，必胜策略为，每次自己抓取完都将局面控制在各个数的二项式分解中，所有 均出现偶数次的状态即可获胜。
这个问题最早由 Bouton 于1901-1902年解决，他的解决方式是，在整数集上引入了“异或”运算（记做 ）。
异或运算本身是定义在 上的，定义方式如下图所示。
为了将其扩展到任意整数上，需先将整数用 表示。二进制恰好提供了这样一种表示方式。由此两个整数做异或运算定义为写成二进制之后每一位分别作异或运算。例如：
而若干个整数做异或运算可以如下定义：
在上式中，可以证明改变计算次序得到的结果不变（证明略）。
Bouton 证明了状态 为后手必胜状态（即我的探索过程中定义的偶状态）的充要条件是 。
这个问题就算是研究明白了。但他还有一些变式，比如：游戏规则中“最后一次抓取者获胜”改为“最后一次抓取者输”，那么哪一方有必胜策略？
欲知结果如何，自己琢磨去。
