Back to Posts

庄家的谜题

Posted in 决策判断

题目大意

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, … 轮游戏中获胜了。

我们的问题是:假设游戏一共有 3k+1 轮,设计一种策略使得 A 和 B 能够保证至少 2k 次胜利。

Solution

考虑先把这些比赛分成3个一组,然后第1场单独一组:

然后就很显然了:因为B知道庄家的所有决策,所以第一轮B出第一组(即2~4轮)庄家出的次数多的那种决策,这样就保证了下一组至少能赢2轮,在下一组输的那一轮B再提示下下组庄家出的次数多的那种决策。

那如果在某一组里全赢了呢?无所谓,随便挑一轮提示就好了。

Read Next

[USACO15JAN]电影移动Moovie Mooving