兔斯基保护协会应邀提供魔改版“街机少年”必胜玩法和数学证明
2019-12-17 15:38:33 Author: bbs.pediy.com(查看原文) 阅读量:129 收藏

[原创]兔斯基保护协会应邀提供魔改版“街机少年”必胜玩法和数学证明

2019-12-10 11:09 238

[原创]兔斯基保护协会应邀提供魔改版“街机少年”必胜玩法和数学证明

昨天,中娅之戒团队认为如果把街机少年的游戏改成“拿最后一个的输”,会很有意思。

我们进行了深入交流,并且都分别得出了必胜方案(我猜她们找我讨论之前就想到了)

这还不算完!

兔斯基保护协会决定应邀给出严谨的数学证明。

这次证明的是,如果把街机少年的游戏改成“拿最后一个的输”,存在必胜状态,使得从该状态下开始的玩家有必胜操作。

必胜玩法就在证明之中。

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

Proof:

上一篇证明(https://bbs.pediy.com/thread-256391.htm),我们知道

构造状态机:

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

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

S(1) <-> S(0)

Theorem 1:

在 S(1) 下存在操作,使得游戏状态变为 S(0)

Therorem 2:

在 S(0) 下任何操作,使得游戏状态变为 S(1)

我们现在重新构造状态机:

S(0) 代表所有数字的异或和是0,所有数等于1.

S(1) 代表所有数字的异或和是0,且存在至少两个数大于1.

S(2) 代表所有数字的异或和是1,所有数等于1.

S(3) 代表所有数字的异或和不是0,且存在一个数大于1.

S(4) 代表所有数字的异或和不是0,且存在至少两个数大于1.

状态机已经涵盖了所有可能的状态。

必胜起始条件是 S(4)

本次的状态转换复杂一些,我们下文论证一下,再给出。

如果存在操作 S(4) -> S(0), 则 S(4) 至多存在一个大于1的数,与 S(4) 矛盾。

由 Theorem 1 我们知道,在 S(4),存在操作,到达异或和是0的状态。

由于不存在 S(4) -> S(0),所以,存在操作,使得 S(4) -> S(1)

在 S(3),把大于1的那个数改成 1,可能得到 S(2) 或 S(0).

如果得到的是 S(0),则把大于1的那个数改成 0 可得到 S(2).

所以在 S(3),总是存在操作 S(3) -> S(2)

如果存在操作 S(1) - > S(2),则 S(1) 至多存在一个大于1的数,与 S(1) 矛盾。

由 Therorem 2,我们知道在 S(1),任何操作都使得游戏状态变为异或和不为 0 的状态。

由于不存在 S(1) -> S(2),则,任何操作,是的 S(1) -> S(3) or S(4)

我们构造状态机:

S(4) <-> S(1) -> S(3) -> S(2) <-> S(0)

必胜玩家开始于 S(4), 必胜玩家在 S(4) 总是执行 S(4) -> S(1),必胜玩家在 S(3) 总是执行 S(3) -> S(2),

必败玩家只可能处于 S(1), S(2)

由于数字有限,改状态机在有限步内停机,所以最终必败玩家处于 S(2),而必胜玩家获胜!

证毕!

[进行中] 看雪20周年庆典报名通道开启!

最后于 6天前 被kanxue编辑 ,原因:


文章来源: https://bbs.pediy.com/thread-256596.htm
如有侵权请联系:admin#unsafe.sh