-
-
[原创]兔斯基保护协会提供“街机少年”玩家必胜操作存在性数学证明
-
2019-12-9 20:00
4037
-
[原创]兔斯基保护协会提供“街机少年”玩家必胜操作存在性数学证明
关注解的存在性，解的有效性。
括号里的描述都可以删除，不影响证明的有效性，只是当注释方便阅读。
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).
证毕！
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
最后于 2019-12-10 10:59
被hugetotoro编辑
，原因：
