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