我的博弈典题物语果然有问题

· · 算法·理论

省流

POJ2315 是假题。对于所有 k-Nim 博弈与其他博弈类型拼在一起的问题（也就是替换 k-Nim 中每一堆石子的选取规则），目前都是 open 的。

前置知识

Nim 游戏，SG 函数，k-Nim 博弈，巴什博弈。

你可能需要大致了解 SG 定理的证明以及 k-Nim 博弈的证明。

经典博弈论题以及错误证法

POJ2315 是一道许多人做过的博弈论题。其题意经过一些简单转化可以变为：

有 n 堆石子，第 i 堆有 a_i 个石子，还有两个常数 k,m。两人轮流操作，每次操作可以选择不超过 m 堆石子，并从每堆里面分别取出不超过 k 个石子（显然也不能超过当前堆剩余石子个数），但至少取走一个石子。每堆之间取走的石子数量无关。无法操作时输，问谁有必胜策略。

如果你在网上搜索这题的题解，你会发现所有人的做法都是一样的：因为 n=1 的时候问题相当于巴什博弈，所以可以把每一堆石子都根据巴什博弈的结论计算其 SG 值，并把问题转化成第 i 堆石子有 SG(a_i) 个的 k-Nim 博弈问题。

甚至还有人给出了像模像样的证明，可惜这些全都是错的。

为什么是错的

首先我们来观察 k-Nim 博弈问题的结论证明：

设 d 为余数不为 0 的最高二进制位，且对应的余数为 k'\le k．那么，必胜策略为，在石子数目二进制第 d 位为 1 的石子堆中，选择 k 堆，并选择移走的石子数目恰好使得对手局面中，每个数位的余数都是 0．唯一需要说明的是，最后取走石子数量的选择总是可行的．

实际上，只要选定 k' 堆石子，每堆都取走 2^d 枚石子，就能使得结果中，第 d 位余数变为 0．对于更低的数位的余数，将这些余数随意摊派给某一个堆即可．

注意在这里的证明中每一堆石子的数量是只会减少的，因此这个证明是对的。但是当我们在内层套了一个其他的问题的时候（例如这道题目中的巴什博弈），就可能会出现一个 SG 值小的状态有可能能够到达一个 SG 值更大的状态的情况，但这个证明中并没有考虑到。

那么在 SG 定理的证明中是怎么处理这一点的呢？由于 SG 定理相当于每次只对一堆石子进行操作，所以如果对方进行了一次操作把一个状态的 SG 值变大了，我们可以再花一次操作把它变回来。因为能够算出 SG 值的状态能到达的状态都是有限的，所以这种操作也只会执行有限次。

当我们尝试把这个操作套到 k-Nim 上的时候，就很容易发现问题。因为现在是对不超过 k 堆进行操作，所以如果对方的一次操作中同时把一些堆的 SG 值减小，另一些堆的 SG 值增大，那么我们就需要在把那些增大的部分降回来的同时处理减小的部分。然而，减小的部分上界其实是 k，因此这个证明是存在问题的，其并不能处理 SG 值可能变大的情况。

Hack

说了这么多废话，还是没法简单的说明这个结论是错的，所以这里就直接给出 Hack 数据了。

在 n=4,m=2,k=2,a=\{1,1,1,3\} 时，根据上述做法的结论，会发现 a 的每一项的 SG 为 1,1,1,0，而对它们使用 k-Nim 博弈会得到总 SG 为 0，因此后手必胜。

但实际上，只要先手将 a_1 取到 0 并将 a_4 取到 1，状态变为 \{0,1,1,1\}，此时容易发现后手必胜，因此原条件是先手必胜的。

如果问题再套一个 Anti-nim 上去，即在其他条件不变的情况下，取走最后一个石子的人输，那么这个做法仍然会错在类似的地方，此时的 Hack 为 n=3,m=2,k=2,a=\{3,1,0\}，实际上仍然为先手必胜。

因此，我们成功说明了这道题目的做法是错误的。经过查询 AI，对于这类问题目前还没有一般性的结论，所以仍然是 open 的。

后面懒得写了，总之欢迎大家来讨论。

致谢

感谢 Fall_X 让我想起来这个问题。

感谢音游 vivid/stasis 提供的精神支持。（？）