上帝掷硬币的智力题，从 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 局。同时 Alice 通过选择答错第 5 局还是第 6 局告诉 Bob 第 9 局的答案，拿下第 9 局，目标达成。
3）若 5~8 局答案为 PQQP 形，则 Alice 在第 2~4 局本该获胜的两局中 故意答错 一次。Alice 用 2~4 局中本该答错的那局告诉 Bob 哪一面是 P，再通过选择答错两局中前一局还是后一局告诉 Bob 第 9 局的答案，于是能保证 5~9 局全胜，目标达成。
4）若 5~8 局答案为 PQPQ 形，则 Alice 在第 1 局 故意告诉 2~4 局中占少数的那一面 。这样 2~4 局中必然答错两局，Alice 在前一局告诉 Bob 哪一面是 P，后一局告诉 Bob 第 9 局的答案，于是能保证 5~9 局全胜，目标达成。

13 局胜 9 局的策略同样可以通过精心安排“故意错某些题传递特定信息”的方法构造，但符合要求的策略非常繁琐；另外，构造策略可以证明 13 局能胜 9 局，却不能证明 13 局不能保证胜 10 局，直接枚举所有策略又明显不可行。我们需要把上帝硬币问题转化为更简单的问题。

首先规定：分别用 表示硬币的正面和反面。

转化问题的关键是利用 最优子结构 。Alice 每局猜测无非是为了两个目的：在这一局获胜，以及向 Bob 传递信息。设总共猜 局硬币，分成前 局和后 局两部分。现在只考虑 Alice 在前 局的行动，而把 Bob 的策略函数以及上帝前 局的正确答案看作是固定的，这样 Alice 有 种选择，每一种选择都对应一个结果：前 局中获胜了多少局。

姑且举一个最简单的例子：取 ，设 Bob 的策略函数是“第一局猜 0，第二局猜 Alice 第一局猜的结果”，上帝前 2 局的正确答案是 10。此时 Alice 在前 2 局有 4 种选择：00, 01, 10, 11，而 Alice 只有选 00 才能胜 1 局，其他三种选择都是一局不胜。若 Alice 选择一局不胜，那么 Alice 有 3 种等价的选择，相当于 Alice 此时可以向 Bob 传递一个范围为 1~3 的整数！整理一下就是：

• Alice 可以选择胜 1 局，不传递额外信息；
• Alice 也可以选择一局不胜，额外传递一个范围为 1~3 的整数。

现在假设我们要在 9 局中胜 6 局，前 2 局的情况如同以上假设的那样，则后 7 局就变成了下面的问题：

• Alice 可以提前看到后 7 局的答案；
• 看到答案后，Alice 可以选择喊出“我们要在 7 局中胜 5 局”（相当于 Alice 前 2 局选 00）；
• Alice 也可以选择喊出“我们要在 7 局中胜 6 局”，同时告诉 Bob 一个 1~3 的整数（相当于 Alice 前 2 局选 01, 10 或 11）。

这样我们把上帝硬币问题一般化，允许 Alice 在事先规定的范围内选择要胜的局数，并告诉 Bob 一个限定范围的整数。我们用一个简练的记号表示这种问题：例如，用 或者 表示“Alice 可以选择胜 5 局，或者选择胜 6 局并告诉 Bob 一个 1~3 的整数”。后面我们经常会把 这种记号看成一个 多重集合 ：集合中有 1 个 5 和 3 个 6。

这里有一个小细节，当讨论问题 时，我们要规定 Alice 的 4 种选择都必须有可能出现 。比如说，如果在任何情况下 Alice 都不报出“胜 6 局，数字为 1”，就视为违规。后面再解释这种奇怪规定的原因。

接下来我们马上会看到，这种问题是有最优子结构的！仍然以 举例（暂时不考虑总局数的条件，总局数未必是 7 局），下一局 Bob 面临 4 种情况：

• Alice 喊出了“我们要胜 5 局”；
• Alice 喊出了“我们要胜 6 局”并报出数字 1；
• Alice 喊出了“我们要胜 6 局”并报出数字 2；
• Alice 喊出了“我们要胜 6 局”并报出数字 3。

此外 Bob 再不知晓任何信息，因此 Bob 只能对每种情况指定一个 0/1 整数作为自己的猜测。先考虑第一种情况，假设 Bob 猜 0，那么在本局结束后又有 4 种分支：

• 上帝的正确答案是 0，Alice 选了 0；
• 上帝的正确答案是 0，Alice 选了 1；
• 上帝的正确答案是 1，Alice 选了 0；
• 上帝的正确答案是 1，Alice 选了 1。

如果是第一个分支，那 Alice 和 Bob 后面只需胜 4 局，否则就需要胜 5 局。请注意，我们在任何时刻总是把 Bob 的策略函数以及 上帝已经揭示的正确答案 看作是固定的，前者当然没有问题，我们没有更改 Bob 的策略，但后者要求我们把前两种分支（上帝的正确答案是 0 ）和后两种分支（上帝的正确答案是 1 ）分开处理。于是目前的状态不能记为 ，而是要记为 ，竖线左边表示上帝本局选 0，右边表示上帝本局选 1。

另外还有一件非常重要的事：这 4 种分支都会出现吗？当然不一定！事实上 Alice 可以随意控制每一种分支是否出现。例如：

• Alice 选择“当上帝本局正确答案是 0 时只猜 0”，就能禁掉第二种分支，将结果变为 ；
• Alice 选择“只在上帝本局正确答案是 0 时才喊出‘我们要胜 5 局’”，则可直接禁掉后两种分支，结果变为 。至于如果上帝出 1 怎么办，当然是喊出“我们要胜 6 局”并报出一个数字了，这属于另外的情况，我们等会再说；
• Alice 选择“只在上帝本局正确答案是 0 时才喊出‘我们要胜 5 局’，并且本局只猜 0”，则可直接禁掉后三种分支，结果变为 ；
• ……

此处只有唯一一条限制： 4 种分支至少要出现 1 种 ，否则 Alice 喊出“我们要胜 5 局”的情况就无法继续下去了。

最后，以上都是讨论 Bob 猜 0 的情况，事实上 Bob 还可以猜 1，此时仍然有 4 种分支，而本局结束后的状态则变为 。当然，Alice 仍然可以随意控制每一种分支是否出现。一般地，正整数 可以分裂为 或 的非空“子集”。作为特殊情况，0 可以分裂为 的非空“子集”，因为若要求 0 胜就根本不需要累加胜局了。

现在我们考虑 的每一种情况，每种情况都 分裂 成 1~4 个分支，例如考虑分裂

• 5 分裂为 ；
• 6 分裂为 ；
• 6 分裂为 ；
• 6 分裂为 。