首先介绍 “一加一碰手游戏”。
具体规则是这样的:
游戏有两个玩家,每个玩家有两只手。
初始所有手上的数字都为 \(1\)。
两个玩家轮流行动,轮到一个玩家时他可以选择对方任意一只手上的数字,将自己任意一只手上的数字加上这个数后对 \(10\) 取余数。
若有一只手上的数字为 \(0\) 则收回这只手,这只手不再参与下面的游戏。
先收回两只手的玩家胜。
我们定义一个满足无论双方如何行动都会循环出现的局面为平局。
那么该游戏状态数量有限,信息完备,且没有运气成分参与其中,适用 \(\text{Zermelo}\) 定理。
一对一时,双方均只有一种行动方式,结局仅与初始局面有关,设初始双方的数分别为 \(a,b\),那么仅当存在 \(i(i>0)\) 使得 \(f_ia+f_{i+1}b\equiv 0\pmod{10}\) 时,其中 \(f\) 为斐波那契数列,才能够分出胜负,否则都为和局。
\((a,b)=(1,3),(1,8),(2,1),(2,6),(3,4),(3,9),(4,2),(4,7),(6,3),(6,8),(7,1),(7,6),(8,4),(8,9),(9,2),(9,7)\)( \(a\) 方先手)时为和局。
设一只手的玩家为 \(A\),两只手的玩家为 \(B\),\(A=\{a\}\),\(B=\{c,d\}\),\(B\) 先手,下证 \(B\) 存在策略使得 \(A\) 无法直接胜利,局面一定可以进入到一对一。
首先证明一个引理,设 \(a,b\) 都是手上的数,则有 \(a+b\not\equiv a\pmod{10}\)。这点从 \(b\not\equiv 0\pmod{10}\) 来看显然。
接下来有另一个引理,\(B\) 永远都可以保持 \(c\not\equiv d\pmod{10}\),这点也显然。所以接下来我们默认 \(c\not\equiv d\pmod{10}\)。
然后我们考虑 \(A\) 直接胜利时的的局面 \(F\),它满足 \(a+c\equiv 0\pmod{10}\) 或者 \(a+d\equiv 0\pmod{10}\),且轮到 \(A\) 行动。不妨设 \(d\) 满足上式。
倒退回上一局面 \(F'\),此时 \(B=\{c,d'\},A=\{a\}\),若局面要变成 \(F\),则 \(B\) 一定选择将 \(d'\) 变为 \(d'+a\),否则有 \(d'=d\),\(a+d'\equiv 0\pmod{10}\),在 \(F'\) 上一局面时 \(A\) 就会获胜。
那么我们有 \(d=d'+a\),则 \((d'+a)+a\equiv 0\pmod{10}\),由上面引理我们得到
\[d'+a\not\equiv 0\pmod{10} \]又由于 \(c\not\equiv d'\pmod{10}\),所以得到
\[(c+a)+a\not\equiv 0\pmod{10} \]注意上两个式子,这说明 \(B\) 如果在 \(F'\) 时不选择将 \(d'\) 变为 \(d'+a\) 而是将 \(c\) 变为 \(c+a\) 就可以避开局面 \(F\),而在这个新的局面中,\(A\) 无法直接胜利。
这样就证完了,由于二对一的局面要么变为一对一,要么 \(A\) 直接赢,我们已经证明了 \(B\) 存在策略规避后者,也就是说一定可以进入到一对一,此时的胜负取决于初始数字。
显然,在经过有限次行动后只会变为二对一。
根据上面的结论,游戏胜负其实取决于一对一时的初始数字,就目前来看,双方皆没有策略来确定进入一对一时的数字,那么根据 \(\text{Zermelo}\) 定理,双方不存在必胜策略,但存在必不败策略。
实际上,我们并没有找出一个必不败的策略,这个有点难,不过我们可以打出一个 \(10\times 10\times 10\times 10\) 的表,确定下一步该如何行动,局面数 \(\leq 10^4\),可以接受。
如果你想稳定进入一对一的情况,那么有一个策略:二对二时可以随意出,当对面收回一只手时,你只需要保证两只手的任意一只都满足加上两倍的对面数字不为 \(0\) 即可。
或许还可以穷举局面后算胜率后统计更优秀的行动方法,如果有空明天我会继续补。