趣题:庄家的秘密序列

    下面是 2013 年 9 月 IBM Ponder This 的谜题。

    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 次胜利的情况仍然是唯一的(即上面提到的那种情况),但我们很难证明这一点(如果你想到了很好的证明方法,请记得告诉我)。因而,上述答案中实际采用的是一个看上去更加曲折复杂的策略,它的好处就是实施过程会更有规律,更有利于后面的分析。

发表评论

80  +    =  81