下面是 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 次胜利的情况仍然是唯一的（即上面提到的那种情况），但我们很难证明这一点（如果你想到了很好的证明方法，请记得告诉我）。因而，上述答案中实际采用的是一个看上去更加曲折复杂的策略，它的好处就是实施过程会更有规律，更有利于后面的分析。
已阅。
已閱，不過不很懂意思 QQ
“如果在第 5 到 7 轮中，只出现了一次的数字是第 6 轮中的数字” 这段讲的方式, 如果2-4轮数字是一样的, 那么第1轮到第4轮有可能全错, 那就只有5次胜利.
IBM Prond This上的solution没有读懂。 仔细读了很多遍matrix67的文章才理解。 非常感谢。
其实理解了解法以后，我更想知道这么精妙又复杂的解法，是怎么被想出来的 :)
to mysh:这段文字讲的就是在2~4不完全相同时的解法。完全相同的话，如果第一轮猜对，那2~9就可以当做3k+2型；若第一轮错误，B给出2~4的提示，2~4可以全对，之后的5轮又可以当做3k+2型。
对于正整数 M，总可以找到最大的整数 N，使得按照题述规则，AB可以保证至少获胜 N轮。记这个N为f(M)
容易知道：f(1)=0, f(2)=1, f(3)=1, f(4)=2,…,f(9)=6
一个有趣的猜想是， 当M趋于无穷时，f(M)/M 是否有极限2/3 ？
很牛很 暴力
老大，说说比特币呗？
Hi,
我觉得你给的答案只能保证在理想情况下可行，但不可能保证在最坏的情况下可以有50%以上的成功率（最多只能有50%）。因为庄家的序列是无序的。
假设庄家的序列是：0 1 0 1 0 1 0 1 0 这样的情况。当A在第一轮猜错，那B要在第一轮给他提醒，第一节只有一轮就是0，在B提醒之下，A在第二节（101）会出1，在第二节之中，A在第二轮猜错，B给A第三节的提醒是0，进入第三节（010），A会出0，在第三节的第二轮中A猜错，B给他提醒，但是第四节只有两个数，提醒什么都一样，最后A还是只猜中了5个。
Hi Matrix,
我觉得你给的答案只能保证在理想情况下可行，但不可能保证在最坏的情况下可以有50%以上的成功率（最多只能有50%）。因为庄家的序列是无序的。
假设庄家的序列是：0 1 0 1 0 1 0 1 0 这样的情况。当A在第一轮猜错，那B要在第一轮给他提醒，第一节只有一轮就是0，在B提醒之下，A在第二节（101）会出1，在第二节之中，A在第二轮猜错，B给A第三节的提醒是0，进入第三节（010），A会出0，在第三节的第二轮中A猜错，B给他提醒，但是第四节只有两个数，提醒什么都一样，最后A还是只猜中了5个。
@Even 你没看完文章吧…
@Evan 你没看完文章吧…
@Evan 没看到文章后面吗…
hi Matrix,
如果是5-7轮数字全是一样的， 最后2位不一样，如何猜中6个数呢？
目前博客提供的解法，好像实现不了。
hi,
上面的补充说明下。如010100010。
因为制定了违反策略的规则，所以不管是B在 第1轮，第2-4轮，第5-7轮中任何一个位置违反，都会被认为5-7轮是2+1的情况（2个1,1个0或者2个0,1个1），导致5-7轮最多能对2个，又由于违反规则的原因，在第8轮前最多只能对3个。 8、9轮全对，也才5个。
如果B不违反规则，第1轮猜错，2-4轮对2个，5-7轮对3个，8、9轮会因为没有提示，可能全错。这样也只有5个能对。
坑~
15楼，
010100010 不属于“需要违反策略”的情形。
违反策略只会发生在如下情形：2-4不完全相同，5-7也不完全相同，8和9不同
你的这个序列，5-7是相同的，因此不需要违反策略。
按照原策略，2-4会对两个，5-7会全对，8，9至少会对一个，总共至少对6个。
可以从信息论角度分析，
假设游戏进行充分多论（所以信息论才有用）
A 每轮猜中的概率为 p,
given A 猜中，B 给出正确答案的概率为 q。
同时不妨设庄家是 i.i.d. 均匀分布。
(否则，AB可以实现共享一个充分长的随机串… xor … detail不细说了)
现在从 A 的立场来看，为了以 p 概率和庄家出的相同，没轮需要消耗 1-h(p) bit 的信息量。
假如 A 猜对(以概率 p),则通过读 B 的回答，A 得到了 h(q) bit 的信息量；假如 A 猜错(以概率 1-p) ,则通过读 B 的回答，A 得到了 1 bit 的信息量。故平均每回合获得 p h(q) + (1-p) bit 的信息量。
以此为基础的策略，可以实现 pq 的胜率，需满足信息量的约束，即
max pq
c.t. p h(q) + (1-p) > 1-h(p)
解得 pq 最大值超过了 0.806。
故有一种方法可以大概率实现 0.8 的胜率。
根据我做信息论题目的经验，应该会有一种确定性策略，其胜率达到 0.8，只是需要的轮数可能很多。
偶然发现Michael Brand就是UyHiP管理员吧。IBM Ponder This 和UyHiP就是一对好基友呀。
很牛 很暴力
唔~~~看不懂。。。。
这个问题是不是有毛病？为什么一定要B跟着A下注？不能A跟着B下注？
可以做到9轮至少赢7次。
1.因为第一次是A先下注，B无法提供信息，又是考虑最坏情况，所以第一次A，B一定输；
2.把第一次B和庄家下注的数看成一个二进制数a（a=2*B出的数+庄家出的数），则其可能情况为00,01,10,11；我们希望用a来提示庄家出的第1~3个数中1的个数；遗憾的是，庄家的第一个数是给定的，比如说庄家第1~3个数为101，这样a只能取11或01，而第1~3个数中1的个数是10（即2）。因此我们需要令a的含义模糊一点。
当a=11：庄家第1~3个数可能有2或3个1；
当a=10：庄家第1~3个数有2个1；
当a=01：庄家第1~3个数有1个1；
当a=00：庄家第1~3个数可能有0或1个1；
（解释：设庄家出的第一个数为b
当b=1，1的个数为1,3时，a=01,11是确切数值，1的个数为2时，a=11是模糊数值，与真实值相差1；
当b=0，1的个数为0,2时，a=00,10是确切数值，1的个数为1时，a=00是模糊数值，与真实值相差1；）
即我们总能保证a与真实值相差<=1
当a=11，A第2、3注下1，至少赢1次；
当a=10，A第2、3注下1，赢2次；
当a=01，A第2、3注下0，赢2次；
当a=00，A第2、3注下0，至少赢1次；
即最坏情况下，前三次输2次，注意到，此时我们仅仅用到了B第一次下注时的信息！所以B第2次下注庄家第4次的数，第3次下注庄家第5次的数……则从第4注开始A必胜。
可以看出，无论n多大，均至少可赢n-2次。
（不正之处请指教，上面博文答案的篇幅很长，没来得及看）
你好，，针对你发表的赌局策略的一些见解，我觉得很有独到之处，想和你详细聊聊切磋一下。我的QQ1772425659，方便告诉我你的QQ号码吗？期待你加我
可把题解换种表达方式：
*0.0. 把9轮分为4节，各节轮数依次为1-3-3-2；初定常规规则为：
B在首节信号轮/前一轮的错轮或清一色时的末轮/出示下节的多数，
A则在下节总出B上节的信号数。
*1.1. 当第二节为混色，末尾节为清一色时，不论第三节混色或清色，
B首节出示第二节的多数，第二节中2轮，
第二节于错轮出示第三节的多数，第三节中>=2轮，
第三节若混色于错轮/若清色于末轮出示末尾节的清色，
末尾节中 2轮。
*1.2. 当第二节为混色，末尾节混色，第三节为清一色时，
B首节出示第二节的多数， 第二节中2轮，
第二节于错轮出示第三节的清色，第三节中3轮，
末尾节A总出上节数， 末尾节中1轮。
*2.0. 当第二节为清一色时，不论其它是否清一色，
B首节出示第二节的清色， 第二节中3轮，
此时AB依赛前约定，变节为1-3-1-3-1，第三节为单轮信号轮，
B第三节出示第四节的多数，第四节中>=2轮，
第四节若混色于错轮/若清色于末轮出示末尾节的数，末尾节中1轮。
*3.0. 当第二三四节都是混色时，B需要故意错示：
*3.1. 当第三节的少数在第7轮时，B在第三节的第5或6轮错示，
*3.1.1. 第5轮错示，
按事先约定A明白了是第7轮是少数，第三节中2轮，
按事先约定A也明白了是89轮是01， 末尾节中2轮；
*3.1.2. 第6轮错示，
按事先约定A明白了是第7轮是少数，第三节中2轮，
按事先约定A也明白了是89轮是10， 末尾节中2轮；
而第二节已中2轮！
*3.2. 当第三节的少数在第5轮时，B在第二节的两个正确轮错示，
*3.2.1. 若前轮错示，
按事先约定A明白了是第5轮是少数， 第二节中1轮，
加上A根据第二节A错轮时的B示，可第三节中3轮，
按事先约定A也明白了89轮是01， 末尾节中2轮；
*3.2.2. 若后轮错示，
按事先约定A明白了是第5轮是少数， 第二节中1轮，
加上A根据第二节A错轮时的B示，可第三节中3轮，
按事先约定A也明白了89轮是10， 末尾节中2轮；
*3.3. 当第三节的少数在第6轮时，B在首节错示为第二轮的少数，
第二节能在少数轮中1轮，
*3.3.1. B在第二节的两个多数位出示0-0，
按事先约定A于第二节结束后明白了是第6轮是少数，
也明白了第三节多数为0，第三节为010，末尾节为01，
*3.3.2. B在第二节的两个多数位出示0-1，
按事先约定A于第二节结束后明白了是第6轮是少数，
也明白了第三节多数为0，第三节为010，末尾节为10，
*3.3.3. B在第二节的两个多数位出示1-0，
按事先约定A于第二节结束后明白了是第6轮是少数，
也明白了第三节多数为1，第三节为101，末尾节为01，
*3.3.4. B在第二节的两个多数位出示1-1，
按事先约定A于第二节结束后明白了是第6轮是少数，
也明白了第三节多数为1，第三节为101，末尾节为10，
以上4种情况均做到第三节中3轮，
末尾节中2轮。
@evan 你没有看完巴
费脑子…
没看完
假球网:http://www.67ssc.com
美垂克斯六七先生赶紧更新一篇吧，我快死了。
在3k+1保证2k中
在全对的环节,B其实可以故意出错一个 来暗示下一轮？
如果说B在第一轮故意出错 那A得到暗示 下一轮为0
如果B在第二轮故意出错 那A得到暗示 下一轮为1
这样行么？
这一招漂亮
更新，the sooner,the better.
更新吧！the sooner,the better.
很喜欢博主的文章，刚刚用豆约翰博客备份专家备份了您的全部博文。
再不更新活不下去了。
求更新！
好久没更新了。
还是每次心情不好就来找乐子结果你没更新…… 然后我看到一个带声音的算法图示笑死了。。。orz
snrtdmty
我认为3k+1,2k情况的描述有一处错误。
按您的描述方式，在A猜错两次的一节，B没法给A做出暗示。下一节有可能仍然猜错两次。
实际上，如果A第一次就猜错，而且后面两次一个0一个1，B可以直接暗示下一节，进入下一节时，A已经经历了标准答案的一次0和一次1，就知道了那次暗示。
我認為其實有更簡單的方法，如將第一局為一組，第2至6為一組，7-9為一組；第一局B暗示2-6局中出現最多的數字，并在A必然錯誤的第一局中暗示7-8是01或是10，再在A必然錯誤的第二局中暗示第9局的數字，這樣就可以保證至少對6局，從而贏得勝利