IBM Ponder This #185 · 2013 年 9 月

每轮 Alice 先宣布一个 0 或 1，Bob 再宣布一个 0 或 1，最后赌场公布本轮数字。三者全相同时 Alice 与 Bob 获胜，否则赌场胜。赌场必须预先固定全部数字，不能看到二人的下注以后再改。

Alice、Bob 可以事先约定策略，但开始后只能通过公开下注传递信息。就在游戏开始前，Bob 会取得赌场的整段秘密序列；他事先知道自己将取得它，但取得后不能再单独告诉 Alice。

若 Alice 随机下注、Bob 复制她，平均可赢一半，但最坏情形仍可能全输。Bob 知道序列后，可以通过“奇数轮报下一轮赌场数字、偶数轮报当前数字，Alice 复制 Bob 上一轮数字”保证至少赢一半。

本题要求在 n=9 轮中，保证至少赢 m=6 轮。给出 Bob 对全部 512 种赌场九位序列的下注，共 512 行，每行九位，赌场序列按二进制顺序对应。Alice 也必须有相容策略，欢迎说明，但不必展开庞大的完整表。

例如 n=2、m=1 的 Bob 答案可写为：

00
11
00
11

附加问题：n 趋于无穷时，能保证比一半更高的获胜比例吗？最坏情形下可保证的最大比例是多少？

解答

认真尝试后再打开

待补充。