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