[原创]兔斯基保护协会提供“街机少年”玩家必胜操作存在性数学证明

3小时前 185

[原创]兔斯基保护协会提供“街机少年”玩家必胜操作存在性数学证明

关注解的存在性，解的有效性。

括号里的描述都可以删除，不影响证明的有效性，只是当注释方便阅读。

Proof:

我们构造状态机：

S(1) <-> S(0)

S(1) 代表所有数字的亦或和不是0，

S(0) 代表所有数字的亦或和是0.

起始状态，是 S(1)，玩家先手。

现在证明在 S(1) 下存在操作，使得游戏状态变为 S(0)

玩家求当前状态求亦或和为sum，sum的二进制形式为000...0001XXX...XXX, 其中X为占位符，有nx个X，nx >= 0，

（占位符是符号，代表改位是0或者是1，不是变量，两个X彼此之间不相等。不同数据使用同一占位符代表对应数位相等）

则存在某一堆上的数字A[i]为 ZZZ...ZZZ1YYY...YYY，其中Y为占位符, 有ny个Y, ny=nx, Z为占位符, 有nz个Z，nz >= 0。否则，对sum的形式矛盾。（不然不会在该位算出一个1来）

令 T[i] = sum ^ A[i] = ZZZ...ZZZ0WWW...WWW，其中W为占位符，有nw个W, nw=nx。

A[i] - T[i] = 000...0001VVV...VVV > 0， 有nv个V, nv=nx。

所以存在操作，使得玩家可以把 A[i] 变成 T[i]。

玩家执行此操作时，新的亦或和 sum_new = sum ^ A[i] ^ T[i] = sum ^ A[i] ^ sum ^ A[i] = 0，位于状态 S(0)

现已证明在 S(1) 下存在操作，使得游戏状态变为 S(0)。

不失一般性，假设 S(0) 状态下把 S[i] 变为 T[i]，可以留在 S(0)，则 sum_new = sum ^ A[i] ^ T[i] = 0.

由于亦或构成交换群，所以 T[i] = S[i]，违反规则。

所以 S(0) 下任何操作，都会使游戏状态变为 S(1).

玩家从 S(1) 开始操作，每次都将游戏状态变为 S(0)，而 AI 只能把游戏状态变为 S(1)，胜利条件数据全 0 位于 S(0).

证毕！

[公告]安全测试和项目外包请将项目需求发到看雪企服平台：https://qifu.kanxue.com

最后于 1小时前 被kanxue编辑 ，原因：