趣题：庄家的秘密序列

A 和 B 在赌场玩一个游戏，他们要协同作战与庄家对抗。游戏一轮一轮地进行，每一轮的规则都是一样的：首先 A 赌 0 和 1 当中的某个数字，然后 B 再赌 0 和 1 当中的某个数字，最后庄家给出 0 和 1 当中的某个数字；如果所有的三个数字都相同，则 A 和 B 获胜，否则庄家获胜。游戏前， A 和 B 可以商量一个对策，但游戏一旦开始，除了下赌注本身之外，两人不能再有其他任何形式的交流了。

容易看出，如果 A 和 B 都随机下注，他们只有 25% 的获胜概率。然而，如果两人事先约定，在每一轮中， B 总是跟着 A 下注， A 赌什么 B 就赌什么，那么他们获胜的概率就会提高到 50% 。但是，不管采用哪种方案，在最坏情况下，两人都有可能一次也不能获胜。

有意思的事情出现了。在游戏开始前两人商量策略的时候，两人突然意识到， B 有办法偷到庄家将会在游戏中使用的 01 序列。也就是说，游戏开始后，每一轮里庄家要出什么， B 都将会知道。但是，一旦 B 拿到了这个 01 序列， B 就不能和 A 交流了。在这样的条件下，两人能做得比刚才更好吗？能！比如说，两人可以保证在最坏情况下也有至少 50% 的获胜次数： B 可以在第 1, 3, 5, 7, … 轮游戏中赌下一轮庄家将会出的那个数（这相当于暗示了 A 下一轮赌什么），两人便能保证在第 2, 4, 6, 8, … 轮游戏中获胜了。

我们的问题是：假设游戏一共有 9 轮，设计一种策略使得 A 和 B 能够保证至少 6 次胜利。

下面是 Michael Brand 给出的答案。

首先，我们将给出一种这样的策略，使得当游戏共有 n = 3k + 1 轮的时候，两人可以保证至少 m = 2k 轮获胜。我们把这 3k + 1 轮游戏分成 k + 1 节：第一轮单独一节，接下来每三轮一节。只要 A 和 B 能做到每一节最多只错一个，就能保证 2k 轮的胜利了。 A 和 B 的基本策略就是，如果某一轮中 A 赌的数字和庄家相同，那么 B 就跟着 A 赌一样的，从而在本轮获胜；仅当 A 赌的数字和庄家不同，此轮已经必败无疑了的时候， B 才利用这一机会向 A 发信号。两人约定，此时 B 赌的数字就是下一节里出现得更多的数字。等这一轮结束后，如果 A 发现自己赌的数字是错误的，他就知道了 B 刚才是在发信号；在下一节游戏里， A 就全赌 B 刚才说的那个数字。容易看出，如果第一轮中 A 瞎赌的数字正好与庄家不符，并且今后每一节里庄家都会出两个 0 一个 1 或者两个 1 一个 0 ，那么每一节都会恰好输一次。

麻烦就麻烦在，如果 A 瞎猜猜对了，依照策略 B 也会跟着往对的猜，则他们可能会毫无准备地进入全新的、还没被暗示过的一节，这反而会打乱我们的计划。不过没关系，只要每节里面仍然只有最多一个错误就行。因此，如果两人在新的一节中继续瞎猜并且实现了三连胜，这对我们没有影响；即使两人靠瞎猜赢得了前两轮，这对我们也没有影响。但是，如果 A 在本节的第一轮或者第二轮就出错了，问题就麻烦了。如果发生了这种情况，则 B 立即修改策略：利用此次错误向 A 发送信号，告诉 A这一节还剩下的两轮或者一轮中哪个数字出现得更多（如果这一节还剩下两轮，并且庄家会出两个不同的数字，此时无所谓哪个数字出现得更多，那么 B 就随便告诉 A 一个数字）。不过，这样一来，本节里可能会出现多达两次的错误。

不过，想一想，两人是怎么走到这一节的：两人是因为在前一节里全猜对了，才走到这一节的。因此，虽然这一节里会出现两次错误，但前一节里是全对的，因而平均每节的错误次数仍然不超过 1 ，这对我们仍然没有影响。有可能这一节的前一节也发生过错误吗？有可能！但只有这样一种可能：前一节本身也是事先没被暗示过的，他们在那一节里发生了一次错误，并且 B 宣布了那一节剩下几轮里出现得更多的数字，但由于剩下几轮里庄家的数字都是相同的，因而两人在剩下的几轮里全对。然而，走到这个前一节也是由于更前一节发生了类似的情况，等等等等，不断倒推过去，最终总能找到某个全对的一节（有可能是第一节），是它引发了这条特殊的链。在这条链中，各节的错误次数是 0, 1, 1, 1, …, 2 ，平均每节的错误次数仍然不超过 1 。

这样，我们就有了一种在 n = 3k + 1 轮中保证 m = 2k 轮获胜的策略，它可以适用于任意情形。事实上，当 n = 3k + 2 时， m = 2k + 1 也是可以保证的。我们可以把最后多出来的那一轮看作是新的一节，那么两人走到这一节时，要么这一节已经被暗示过了（两人便会在这一节里取胜），要么这一节没被暗示过（两人便有可能在这一节里出错）。然而，如果这节没被暗示过，那么两人最多只会发生一次错误（因为这一节总共就只有一轮），因而它所在的链中，各节的错误次数依次是 0, 1, 1, 1, …, 1 。不管怎样，我们都能做到每节最多一处错误，且存在某一节全对。考虑到当 n = 3k + 2 时如此分节能得到 k + 2 节，因而错误数最多 k + 1 个，获胜的次数也就有至少 2k + 1 次了。

好了，现在回到 n = 9 ， m = 6 的情形。目前，它不属于我们之前解决过的任意一种情形。我们还是把这 9 轮游戏分成 4 节，第 1 轮一节，第 2 到 4 轮一节，第 5 到 7 轮一节，第 8 轮和第 9 轮一节。我们还能像刚才那样，保证 4 节当中只有 3 节会出错（且最多出一次错），剩余一节全对吗？这回不行了。刚才的最后一节只含一轮，如果有暗示则必然全对；但现在的最后一节包含两轮，这两轮的数字相同的话还好说，如果正好是有一个 0 有一个 1 的话，暗示了也拿不到全对。

不过，只要之前出现过某一节全对的情况，事情都是可以弥补的。比方说，如果两人在第一节就全对了，两人就可以把剩余的 8 轮看作是一次新的游戏，利用 n = 3k + 2 时的策略保证 5 次胜利，加上第一节猜对的那一个，一共就是 6 次胜利了；或者，两人在第二节首次全对，两人便能利用 n = 3k + 2 时的策略在剩余的 5 轮中获得 3 次胜利，加上刚才第二节里的 3 连胜，于是又得到了 6 次胜利。如果两人在第三节才出现全对呢？两人将会在无暗示的情况下闯入最后一节，他们可以在这一节中赢得至少一轮，加上第二节的 2 次胜利和第三节的 3 次胜利，总共依然是 6 次胜利。

怕就怕这样的情况：最后一节是两个相异的数字，并且每一节都已经在上一节中暗示过了。换句话说，现在唯一解决不了的情况是： A 在第一轮猜错了，并且第 2 到 4 轮的三个数字不全相同，并且第 5 到 7 轮的三个数字也不全相同，并且第 8 轮和第 9 轮是两个不同的数字。在这种情况下，两人会在每一节都出错一次，无法保证 6 次胜利。

怎么办呢？最强大的部分就来了：此时， B 通过违背策略来给 A 发信号！如果 A 发现 B 违背了策略， A 就知道两人现在正处于这种唯一无法处理的情况；究竟是怎么违背策略的，这本身就会构成一种暗示。两人具体的做法如下。

如果在第 5 到 7 轮中，只出现了一次的数字是第 5 轮中的数字，那么 B 就在第 2 到 4 轮里本来可以获胜的两轮中故意搞错一次（这一轮结束后 A 将会立即发现 B 违背了策略）。 B 可以选择在哪一轮里搞错，从而暗示第 8 轮和第 9 轮的两个数字是 01 还是 10 。结合目前两人所处的情形， A 就能推出第 5 轮到第 9 轮的全部数字。

如果在第 5 到 7 轮中，只出现了一次的数字是第 6 轮中的数字，那么 B 在第 1 轮中改为发送第 2 到 4 轮中出现次数更少的数字（第 4 轮后 A 将会发现 B 违背了策略）。在第 2 轮到第 4 轮中， B 跟着 A 一道把只出现了一次的那个数字弄对，另外两轮则用来发信号，分别指示第 5 到 7 轮中出现次数更多的是哪个数字，以及第 8 到 9 轮是 01 和 10 中的哪种情况。

如果在第 5 到 7 轮中，只出现了一次的数字是第 7 轮中的数字（这说明第 5 轮和第 6 轮是本来应该获胜的两轮），那么 B 就在第 5 轮和第 6 轮当中故意搞错一次，究竟在哪一次搞错，则暗示了第 8 到 9 轮的数字是 01 还是 10 。 A 将会立即知道 B 违背了策略，并且根据已有信息，推出第 7 轮到第 9 轮的正确数字。

不管是哪种情况，两人都能保证 6 次胜利。

在写这篇文章时， Michael Brand 本人给予了很大的帮助，特此感谢。

[附注] 在答案当中，“怕就怕这样的情况”之前的部分其实完全可以替换成一些更简单的方案，比如说：如果某一轮中 A 赌对了， B 就跟着赌一样的；如果某一轮中 A 出错了， B 就在该轮里暗示最近的还没被暗示过的三轮中出现次数更多的数字（如果剩下还没被暗示过的轮数只有一轮或者两轮了，那么就暗示这一轮或者两轮里出现次数更多的数字）。这意味着，当 A 进入瞎猜的状态时，如果他碰巧猜错了， B 暗示的将会是接下来的三轮中出现得更多的数字。这种方案会简单得多，并且由此带来的胜率往往会大于 2/3 。但是，它的不足之处就在于，在轮数有限的情况下，这种策略的实施情况捉摸不定，变数太多。当 n = 9 时，不能实现 6 次胜利的情况仍然是唯一的（即上面提到的那种情况），但我们很难证明这一点（如果你想到了很好的证明方法，请记得告诉我）。因而，上述答案中实际采用的是一个看上去更加曲折复杂的策略，它的好处就是实施过程会更有规律，更有利于后面的分析。