上帝掷硬币的智力题，从 9 胜 6 开始的深入研究

最近看到一道智力题，大意如下：

上帝让 Alice 和 Bob 两人玩一个猜硬币游戏。猜硬币共进行 13 轮，每轮上帝将硬币盖在手下，让 Alice 和 Bob 分别猜硬币是正面还是反面。两人各自独立作出猜测并同时公布，上帝随后揭晓答案，只有 Alice 和 Bob 都猜对才算这一轮胜利，否则就失败。13 轮猜测依次进行，上一轮结束后 Alice 和 Bob 都能看见上帝的答案和对方的猜测，然后再开始下一轮。
猜硬币之前，上帝会告诉 Alice 所有 13 轮上帝手握硬币的正反，也就是说 Alice 知道上帝每一轮出正面还是反面，但 Bob 不知道这些信息。
在上帝告诉 Alice 这些信息之前，Alice 和 Bob 可以互相交流制定策略（当然二人完全知悉以上所有规则，包括上帝告密的事情），但在上帝开始告密之后，双方便不能交流。
问：Alice 和 Bob 能否保证必胜 9 局？
（我们假设 Alice 和 Bob 被封闭于不同的两个房间内，只能通过一台显示终端做出猜测，并且不能不猜测。规定时间到后，机器同时公布两人猜测并验证答案是否正确，以保证双方绝对不能通过手势、口音、猜测时间等变量互相传递信息。双方只能通过自己的猜测给对方后续的猜测传递信息。）
若此题过于困难，可尝试简易版本：总共进行 9 轮猜硬币，保证必胜 6 局。

此题看似平平无奇，深入研究之后发现作者显然对此题的结构有深入研究，选取的数值非常巧妙，恰如其分。我们先从简易版的答案说起。

初探

初见此题，可能先会想到最简单的方法：奇数局提示偶数局的答案。Alice 在第奇数局猜下一局的正确答案，可保证下一局必然猜对。但这样保证猜对的局数不超过总局数的一半，显然是不够的。

利用分组的思想稍加变通，又可推出另一种稍强的策略：Alice 第 1 局提示第 2~4 局中占多数的正确答案（换言之，2~4 局的正确答案如果正面多，Alice 第 1 局就出正面，否则就出反面）。Bob 第 2~4 局每次都出 Alice 第 1 局猜的答案，Alice 在 Bob 猜对的那两局也出一样的答案，保证胜两局，剩下错的那局提示第 5~7 局中占多数的正确答案。如果不巧 2~4 局正确答案都相同，则约定 Alice 在第 4 局提示 5~7 局中的多数。此后依次类推。

可以看到这种策略把每 3 次猜测分成一组，每组可胜 2 局；剩下一局提示下一组的多数答案，保证可持续发展。这种策略可以保证 13 局胜 8 局，或者 9 局胜 5 局，但是还差一点。

下面转述来自智力题吧帖子（7楼）「毒酒滴冻鸭」大神的 9 局胜 6 局的方案：

首先 5 局可以保证胜 3 局：Alice 第 1 局提示 2~4 局多数答案。如果 2~4 局答案都一样则直接达成胜 3 局；否则 Alice 在错的那局提示第 5 局答案，拿下第 5 局，同样可以胜 3 局。
接下来给出 9 局胜 6 局的策略。
Alice 第 1 局提示 2~4 局多数答案，让 Bob 在 2~4 局每局都选这个答案。如果 2~4 局答案都一样，则双方 2~4 局全胜，后面只需执行 5 胜 3 的策略即可。
如果 2~4 局答案不都一样，则 Alice 在错的那局可以提示 Bob 一个答案，让 Bob 在 5~8 局每局都选这个答案。这里又分几种情况：
1）若 5~8 局正确答案全都一样或者成 3:1，则 Alice 提示 5~8 局的多数答案，而 Bob 在 5~8 局都猜这个答案。注意 2~4 局已经胜了 2 局，如果 5~8 局答案都一样则直接达成胜 6 局；否则 Alice 在错的那局提示第 9 局答案，拿下第 9 局，同样可以胜 6 局。
2）若 5~8 局答案为 PPQQ 形，则 Alice 在第 2~4 局中提示 P，然后 Alice 在第 5~6 局 故意答错 一次，无论在哪局答错，Bob 在第 7~8 局都改猜 P 的另一面，从而在 5~8 局中获胜 3 局。同时

< style data-emotion-css="1pr2waf"> .css-1pr2waf{font-size:15px;color:#09408e;} 展开阅读全文

编辑于 2020-08-19 19:24