上帝擲硬幣的智力題，從 9 勝 6 開始的深入研究

最近看到一道智力題，大意如下：

上帝讓 Alice 和 Bob 兩人玩一個猜硬幣遊戲。猜硬幣共進行 13 輪，每輪上帝將硬幣蓋在手下，讓 Alice 和 Bob 分別猜硬幣是正面還是反面。兩人各自獨立作出猜測並同時公布，上帝隨後揭曉答案，只有 Alice 和 Bob 都猜對才算這一輪勝利，否則就失敗。13 輪猜測依次進行，上一輪結束後 Alice 和 Bob 都能看見上帝的答案和對方的猜測，然後再開始下一輪。
猜硬幣之前，上帝會告訴 Alice 所有 13 輪上帝手握硬幣的正反，也就是說 Alice 知道上帝每一輪出正面還是反面，但 Bob 不知道這些資訊。
在上帝告訴 Alice 這些資訊之前，Alice 和 Bob 可以互相交流制定策略（當然二人完全知悉以上所有規則，包括上帝告密的事情），但在上帝開始告密之後，雙方便不能交流。
問：Alice 和 Bob 能否保證必勝 9 局？
（我們假設 Alice 和 Bob 被封閉於不同的兩個房間內，只能透過一台顯示終端做出猜測，並且不能不猜測。規定時間到後，機器同時公布兩人猜測並驗證答案是否正確，以保證雙方絕對不能透過手勢、口音、猜測時間等變量互相傳遞資訊。雙方只能透過自己的猜測給對方後續的猜測傳遞資訊。）
若此題過於困難，可嘗試簡易版本：總共進行 9 輪猜硬幣，保證必勝 6 局。

此題看似平平無奇，深入研究之後發現作者顯然對此題的結構有深入研究，選取的數值非常巧妙，恰如其分。我們先從簡易版的答案說起。

初探

初見此題，可能先會想到最簡單的方法：奇數局提示偶數局的答案。Alice 在第奇數局猜下一局的正確答案，可保證下一局必然猜對。但這樣保證猜對的局數不超過總局數的一半，顯然是不夠的。

利用分組的思想稍加變通，又可推出另一種稍強的策略：Alice 第 1 局提示第 2~4 局中占多數的正確答案（換言之，2~4 局的正確答案如果正面多，Alice 第 1 局就出正面，否則就出反面）。Bob 第 2~4 局每次都出 Alice 第 1 局猜的答案，Alice 在 Bob 猜對的那兩局也出一樣的答案，保證勝兩局，剩下錯的那局提示第 5~7 局中占多數的正確答案。如果不巧 2~4 局正確答案都相同，則約定 Alice 在第 4 局提示 5~7 局中的多數。此後依次類推。

可以看到這種策略把每 3 次猜測分成一組，每組可勝 2 局；剩下一局提示下一組的多數答案，保證可持續發展。這種策略可以保證 13 局勝 8 局，或者 9 局勝 5 局，但是還差一點。

下面轉述來自智力題吧貼文（7樓）「毒酒滴凍鴨」大神的 9 局勝 6 局的方案：

首先 5 局可以保證勝 3 局：Alice 第 1 局提示 2~4 局多數答案。如果 2~4 局答案都一樣則直接達成勝 3 局；否則 Alice 在錯的那局提示第 5 局答案，拿下第 5 局，同樣可以勝 3 局。
接下來給出 9 局勝 6 局的策略。
Alice 第 1 局提示 2~4 局多數答案，讓 Bob 在 2~4 局每局都選這個答案。如果 2~4 局答案都一樣，則雙方 2~4 局全勝，後面只需執行 5 勝 3 的策略即可。
如果 2~4 局答案不都一樣，則 Alice 在錯的那局可以提示 Bob 一個答案，讓 Bob 在 5~8 局每局都選這個答案。這裏又分幾種情況：
1）若 5~8 局正確答案全都一樣或者成 3:1，則 Alice 提示 5~8 局的多數答案，而 Bob 在 5~8 局都猜這個答案。註意 2~4 局已經勝了 2 局，如果 5~8 局答案都一樣則直接達成勝 6 局；否則 Alice 在錯的那局提示第 9 局答案，拿下第 9 局，同樣可以勝 6 局。
2）若 5~8 局答案為 PPQQ 形，則 Alice 在第 2~4 局中提示 P，然後 Alice 在第 5~6 局 故意答錯 一次，無論在哪局答錯，Bob 在第 7~8 局都改猜 P 的另一面，從而在 5~8 局中獲勝 3 局。同時

< style data-emotion-css="1pr2waf"> .css-1pr2waf{font-size:15px;color:#09408e;} 展開閱讀全文

編輯於 2020-08-19 19:24