今年我为北京世纪坛的数学益智游戏展贡献了不少内容。我打算在这里记录一些自己的创作、发现、收获和心得。这是该系列的第三篇。
今年的数学益智游戏展有一个特色，就是到访者可以购买一个小册子，这可以为自己的参展体验加分。我们内部把它叫作“任务单”。任务单里有很多任务，对应了展会中的各种项目。完成任务可以获得印章，赢取奖励。为了增加任务单的附加价值，任务单上还附赠了很多简单展品的高级玩法说明。这里举一个有趣的例子。
展会现场有很多冰糕棍，可以用来做冰糕棍炸弹。任务单上给出了冰糕棍的另一种玩法——Nim 游戏。将冰糕棍从左到右摆成若干堆。两人轮流从其中一堆冰糕棍中取走任意数量的冰糕棍（可以全部取走，但不能不取）。取走最后一根冰糕棍的玩家获胜。
考虑到任务单的读者可能已经熟悉 Nim 游戏了，因此为了让所有人都能有新的收获，我补充了一些不太常见的 Nim 游戏变种。我一共准备了 10 条补充规则。游戏开始前，双方可以任选其中一条来玩。
- 每次只能从最左端或者最右端的那一堆中取冰糕棍。
- 每次只能从冰糕棍数最多的那一堆中取冰糕棍（如果冰糕棍数最多的堆出现了并列的情况，任选其中一堆即可）。
- 每次只能从冰糕棍数最少的那一堆中取冰糕棍（如果冰糕棍数最少的堆出现了并列的情况，任选其中一堆即可）。
- 第一个人可以从任意一堆中取冰糕棍，今后每个人只能从和刚才不同的堆中取冰糕棍。
- 第一个人可以从任意一堆中取冰糕棍，今后每个人只能从和刚才相邻的堆中取冰糕棍。
- 第一个人可以从任意一堆中取冰糕棍，今后每个人只能从和刚才相同的堆中取冰糕棍（除非刚才那一堆被取完了）。
- 每次取完后，还可以再从另一堆中取走同样多的冰糕棍。
- 每次取冰糕棍的数目改为最多 3 根。
- 取走最后一根冰糕棍的玩家算输。
还差一条，应该写什么呢？我有三个备选方案。大家可以猜一猜，我最后用了哪个方案。
- 游戏双方各有一次“跳过”的机会。
- 游戏中有一次“跳过”的机会，任意玩家使用后该机会作废。
- 每次对方取完后，如果他还有别的取法，你便能要求他该轮换一种取法。
这三条补充规则都挺有意思，它们都在一个更底层的层面修改了游戏规则。我们都来分析一下。Nim 游戏里局面信息透明，不含运气成分，不会有平局产生中，所以一定有一个人拥有必胜策略。对于有的开局，先手拥有必胜策略。对于另外的开局，后手拥有必胜策略。
如果游戏双方各有一次“跳过”的机会，整个游戏跟原版其实没啥区别。对于任意一种开局，在原版中不管是先手必胜还是后手必胜，这个人在新版中仍然能够必胜。他只需要在对方选择跳过时也立即选择跳过（自己绝不主动跳过），就能把对方的跳过机会给抵消掉。一切就变回成传统的 Nim 游戏了。所以，我没有采用第一个方案。
如果整个游戏只有一次“跳过”的机会呢？情况会变得更有意思。如果一个局面在原版的 Nim 游戏中是后手必胜的，那么在新版的 Nim 游戏中，先手上来就选择跳过，从而变成后手，便能赢得胜利。
如果一个局面在原版的 Nim 游戏中是先手必胜的？让我们看看 (1, 2) 这个局面。在原版的 Nim 游戏中，它是先手必胜的。先手可以拿走后一堆中的一根冰糕棍，接下来只能是每人各拿一根，从而先手获胜。在新版的 Nim 游戏中，先手显然不会上来就用“跳过”，把必胜局面拱手让给对方；先手也不会把其中一堆取光，不然直接就输了。所以，他只能像刚才一样，把 (1, 2) 变成 (1, 1)。接下来，两人本该一人拿一根，但后手可以用一次“跳过”，从而取得最后一根。所以胜负关系也交换了。
两版 Nim 游戏的胜负关系总是颠倒的吗？不是。(1, 3) 这个局面在两版游戏中都是先手必胜的。原版中，先手直接把 (1, 3) 变成 (1, 1)，就也必胜了。新版中，先手把 (1, 3) 变成 (1, 2)，他就成了上一段讨论的开局中的后手，从而获得胜利。
所以，第二个方案看上去很不平凡。但是我也没采用。原因很简单——在普通玩家看来，“跳过”这个行为似乎没啥价值，正面反馈不够大。游戏时，大家可能会想：我明明可以多拿些冰糕棍，为什么想要跳过呢？因而，游戏为啥变得不一样了，这并不显然。
最终我选择了方案三。每轮对方首次取完后，只要对方还有别的取法，你都可以要求他换成新的取法。这种推翻对方取法的权力会给人一种兴奋感，让人跃跃欲试。它给游戏带来的变化也很明显：策略上变得更宏观，更复杂了。我的一步好棋可能会被对方否决掉，而我故意先走一步不好的，对方就直接接受了！
我把这个游戏叫作“带有否决的 Nim 游戏”。游戏灵感来自于 Erich Friedman 提出的 Veto Nim。但是我对否决的理解肯定跟 Erich Friedman 不一样，因为我们算出来必胜必败局面不相符。Erich Friedman 的否决是啥意思，我现在还没弄清楚。
我把带有否决的 Nim 游戏做成了一个小游戏。大家可以在游戏中体验这个规则给游戏带来的变化。详细的分析我就不写了。大家边玩儿边思考吧。
有的变种看起来很经典（比如 9）。这些变种都有快速判定必胜/必败态的方法吗 /yiw
我说一下我知道的。8显然是对3取模然后异或。9如果只有一堆比1多就把它取到1，否则按正常版本玩。7貌似是Wythoff博弈的强化，应该也和黄金比例有关。3排序后变成只能从小端取。
若干icg的拼接是这样的：最后一个游戏为normal play；如果它后手胜，则倒二个亦为normal play；否则为misere play，依此类推。因此3中>1个的所有堆等效为1个1，然后如果有奇数堆则先手胜，反之亦然。
6：一直取一堆只可能是先手或后手先取完两种结局。先手要想控制结局，要么取完（放弃先手），要么只剩一个（保持先手）。如果每堆只有1个，先手胜当且仅当有奇数堆。否则先手先取>1的堆，在前几堆让自己保持先手；取最后一个>1的堆时，看看有多少1个的堆，如果有奇数个则仍然保持先手，反之则放弃先手。至此3689均解决。
刚刚在洛谷上看到有人讨论 ARC137C 中的「决策包容性」（https://www.luogu.com.cn/discuss/572379），发现和第 2 题的策略很像。
「决策包容性」是指一个状态若能到达它所能到达的状态所能到达的状态，则这个状态必然是必胜态（引自 https://www.luogu.com.cn/blog/ZillionX/solution-at-arc137-c）。
如果只有一个最大堆，我们考虑把它减小到次大堆的大小之后的局面，如果为 P-position，则走到这个局面；否则这个局面必然可以走到一个 P-position，且原局面也可以走到，那就走到那里。总之可以确定原状态是 N-position。
接下来可以发现，一个状态为 N-position 当且仅当有奇数个最大堆。当取到只剩一个最大堆时，下一步次大变最大，需要确保移动后最大堆有偶数个，为 P-position。因此移动前次大堆如果有奇数个则需要把最大堆减小到次大堆的大小，否则随便减小到更小的数即可。（有不止一个时随便取都不影响结果。）至此 23689 均解决。
10.2 貌似很难分析。如果允许在全取完时换位，就把 SG 值异或一，很无聊。但是这里不允许，就很不一样了。
我把二维的 SG 值输出成图像，把三维每一组 P-position 的 x, y, z 变成函数 f(x, y, z)（容易证明 (x, y) -> z 构成满射），再输出成图像，发现它们完全一样（我不会证，大家试试看可不可以证明）。
图片地址：https://cdn.luogu.com.cn/upload/image_hosting/vplmw5no.png
（图片说明：原点在左下角，从左下到右上，x, y 的值递增。颜色越深， SG 或 z 值越大。）
更正：把三维每一组 P-position 的 x, y, z 变成函数「f(x, y, z)」→「f(x, y) = z」。
1 是洛谷 P2599（https://www.luogu.com.cn/problem/P2599）。
那个链接里面有「查看题解」，讲得很清楚了，可以去看一下。
证明是考虑 P-N 之后是否总是可以回到 P。考虑到 (0,0,x) 总是 N，相当于多了一个选择，因此仍按 sg 定理的证法。（但是总的 sg 值可能有变。）这可以推广到多元。
4 按照普通 nim 玩。因为 P-N 后不可能再取同一堆回到 P，就算在普通 nim 中走同一堆也不会是必胜。
7 比较难。图明天发。
话说保存个人信息的选项好像不管用，博主能来修一下吗？
9 其实是 anti-nim，胜利条件有一个叫做 SJ 定理的东西，大概是零几年的集训队论文里讲的，就是除了所有堆大小都为 1 时胜利条件相反外其余情况胜利条件与普通 nim 相同。
❤️ 最新看黃魸【 33km.xyz 】ㄖ韩、欧羙、啯产、黑咝、偸啪 【 33km.xyz 】 手机浏览噐打开 【 33km.xyz 】佬呞机～你慬的⚡➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖➖❤️➖
Erich Friedman 的否决可能是说走的人同时提出两种走法，然后对手否掉其中一种？不知道有没有区别。
可能是少于2种选择自动认输？
Matrix67 大佬您好，请教一个问题：定义一个进制用一个完系表示，例如十进制 0 1 2 … 9，平衡三进制 0 1 -1。它们都可以表示全体正整数，还有 0 1 -2 -1，0 1 -2 3，1 2 这三种进制也可以。但是 0 3，0 -2 2 这样的不行（不能表示 1）。怎么判断哪些进制可以，哪些不行？
艹，这才发现您就是 U 群里面一直问这个问题的那位群友
关于“带有否决的 Nim 游戏”，稍微试了一下，只有一堆时，只有2个石子先手必败；只有2堆时，当且仅当两堆数量差2时先手必败；三堆及以上的情况我没有分析出一个简单的判定方法，写了一个搜索过了关。
2堆时还有可能是两堆都是1个，先手同样必败 三维及以上还没研究
那里提出的 Veto Nim 与此处提出的否决的区别在于边界条件：仅剩一堆一个石子，即只剩一种操作方式时，此处的规则认为对方不能否决掉唯一的操作方式，因此先手胜；那里的规则认为对方可以否决掉唯一的操作方式，导致先手不能操作，因此先手败。
很久没来了，看到你又更新博客我可太开心了！！！！
10.2好像是一种很新的组合博弈加法，在Aaron的书里没提，粗略查了一圈至少Games of No Chances五本论文集里好像也没提。感觉是个很值得深入挖掘的东西。
你写得非常清晰明了，让我很容易理解你的观点。
听话水/乖乖水/催情/迷昏/迷幻/迷情药出售QQ微信同号343116263乙醚七氟烷 日本，美国代购。乖乖水，听话水，开心水，迷幻，媚药，FM2，三唑仑，GHB，唛可奈因，催情，喷雾型，失忆型，无记忆型，伪装型催情口香糖，咖啡，香水等，正品进口日本性素，男用壮阳，延迟，情趣器具等各类成人情趣用品（详情讯息咨询）全海外代购正品货源，日本欧美av专用等产品。所有属情趣产品，请勿用于非法用途！QQ微信同号343116263帮你搞定女神搞定小可爱
其实，把”跳过“加进游戏里也是挺有趣的，楼主刚刚分析了“跳过”的作用不大，但是我们可以对”跳过“进行一些限制。比如：不允许连续的两次跳过（即A跳过了，B不允许也跳过，即抵消A的跳过）。不允许第一次取的时候就跳过。
好厉害的博客！不知道该如何订阅呢？