反常游戏
反常游戏、反 Nim 游戏的 定义。
以反 Nim 游戏为例,这里给出反 Nim 游戏的结论以及证明:
规定:字母 N 和 P 分别代表先手必胜与必败。
一个局面为 N 态的充要条件是有至少一条出边连接至 P 态。
一个局面为 P 态的充要条件是每一条出边都连接到 N 态。
反 Nim 游戏
为方便书写,用字母
结论:
-
当全部
,如果有奇数堆石子就为 P 态,有偶数堆则为 N 态。 -
当至少一个
, 时为 N 态,否则为 P 态。
证明 1:显然。
证明 2:
情况 A:若只有一个
故这种情况 是 N 态。
情况 B:(不考虑
小情况 B1:
小情况 B2:
一方面可以转移到至少
另一方面随着游戏进行(B1, B2 循环),数量大于 1 的堆会逐渐减少,最终只剩一堆,这就变成了情况 A,为 N 态。
观察情况 B,小情况 B2 能给对面 N 态或至少
所以在情况 B 下,小情况 B2 为 N 态,B1 为 P 态。
也就是说 当至少
综合情况 A 和情况 B 的结论,结论 2 得证。
综上,结论 1 和 2 皆得证。结论得证。
本页面最近更新:2023/5/4 18:17:30,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:2008verser, Backl1ght, billchenchina, Enter-tainer, FFjet, Ir1d, Molmin, ouuan, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用