反常游戏
反常游戏、反 Nim 游戏的 定义。
以反 Nim 游戏为例，这里给出反 Nim 游戏的结论以及证明：
规定：字母 N 和 P 分别代表先手必胜与必败。
一个局面为 N 态的充要条件是有至少一条出边连接至 P 态。
一个局面为 P 态的充要条件是每一条出边都连接到 N 态。
反 Nim 游戏
为方便书写，用字母 \(T\) 表示 \(\oplus_{i=1}^{n}a_{i}\)。
结论：
-
当全部 \(a_{i}=1\)，如果有奇数堆石子就为 P 态，有偶数堆则为 N 态。
-
当至少一个 \(a_{i}>1\)，\(T\neq 0\) 时为 N 态，否则为 P 态。
证明 1：显然。
证明 2：
情况 A：若只有一个 \(a_{i}>1\)（此时 \(T\) 一定 \(\neq 0\)），则先手选择转移到全部 \(a_{i}=1\) 的局面，并且先手可以在这次决策中控制转移后堆数的奇偶。
故这种情况 是 N 态。
情况 B：（不考虑 \(T\) 取值）有至少 \(2\) 个 \(a_{i}>1\)。
小情况 B1：\(T\neq 0\)：通过 Nim 游戏可知一定能够转移到 \(T=0\) 的局面（小情况 B2）。
小情况 B2：\(T=0\)：
一方面可以转移到至少 \(2\) 个 \(a_{i}>1,T\neq 0\) 的局面，即情况 B1。
另一方面随着游戏进行（B1, B2 循环），数量大于 1 的堆会逐渐减少，最终只剩一堆，这就变成了情况 A，为 N 态。
观察情况 B，小情况 B2 能给对面 N 态或至少 \(2\) 个 \(a_{i}>1,T\neq 0\) 的局面，而小情况 B1 仅能给对面 \(T=0\) 的局面。
所以在情况 B 下，小情况 B2 为 N 态，B1 为 P 态。
也就是说 当至少 \(2\) 个 \(a_{i}>1,T\neq 0\) 时为 N 态，否则为 P 态。
综合情况 A 和情况 B 的结论，结论 2 得证。
综上，结论 1 和 2 皆得证。结论得证。
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用