庄家的秘密序列

31018

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 次胜利。

22568

以前看过,当时大概看那个答案就不想看下去了..
先给个有答案的门..
http://www.matrix67.com/blog/archives/5523

21457

不知道为什么，看了二楼之后就没有设计的动力了

35508

好长。。。

35285

没有看答案，感觉这是个学信息的哥们想出来的题：
核心是有限比特下如何传递尽量多的信息量。
首先B看A的选择行事：如果Ａ和庄家相同，那么就先得一局，不提供信息量。
如果Ａ和庄家不同，那么不论Ｂ出什么都输了，但是B的答案能够给Ａ传递一个bit的信息量，这个时候什么最重要？显然是后面0和1的数目谁多。
知道了这个信息，全猜那个多的，至少能对4次。所以第一次错误的时候一定是说明庄家后续序列中0和1哪个多。而且，这个信息会持续有效。因为此后的庄家信息都是已知的，A可以推算出后续的01比例是否有了变化。
A会按照B给的信息猜多的那个，万一再出错，就又出现了一次传递信息的机会。这一个bit应该传递什么呢？
以首两次出错例，后面可能是7：0，6：1这两种情况下只要坚持猜那个多的，肯定能赢。对于5：2或者4：3的情况，就比较困难，所以这个bit是告诉A按照原定方案猜还是需要具体分析。设定给出和第一次出错的相同数字代表继续猜此数字，相反代表其它情况（注意对于4：4的情况，B肯定给出的马上紧跟的那个数）
在这种情况下，分情况考虑：
如果A运气好，连胜三局，后续就可以按照题中的策略，每次提示下一个，保证6次以上胜利。
如果A连胜两局，第三局错，那么剩余6个序列至少取得三次以上胜利。不失一般性，后面1和0可能是6：0 5：1，4：2 和3：3，如果是前三种，确认多的后全猜可直接胜利，对于3：3情况，肯定提示的是接下来的那个。然后比例变为2：3，此时再出错的话，就会提示反转。而对于这种情况，细心的A会发现，一定是因为出现了比例相同的情况，这时可以计算出另一种的数目已经反居上了，最后全猜另一种即可。最多有三次错误。所以也能胜利。
如果A第一局胜利，第二局错，后面7个可能是6：1，5：2，4：3。同样前两种必胜。后面4：3的时候可能出现猜对变成4胜+1：3。此时出错就会反转，全猜另一种会有两胜。也可能3胜+2：3时出错，此时反转全猜另一种会有3胜。同理分析其它情况。
如果第一局出错，后面8个可能是7：1 6：2，5：3 ，4：4，前两者必胜，后面的4：4和首局胜的4：3一样，具体细节不一一阐述。

总之，策略就是，第一次出错时告诉A庄家剩下的0和1那种多，第二次出错时要告诉A是否继续坚持原决定，如果需要反转数字，那么根据可能需要反转的情况具体分析应该采取什么策略，并推测剩下的数字是几比几，然后决定猜什么。

35285

恩 刚看了链接，感觉他们非要用归纳法进行证明，似乎是不那么直接。感觉B暗示A在必胜情况下的暴力猜法能省去很多多余分支。
恩 再好好研究研究 这题很有意思呀