趣题:庄家的秘密序列

    下面是 2013 年 9 月 IBM Ponder This 的谜题。

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    下面是 Michael Brand 给出的答案。

    首先,我们将给出一种这样的策略,使得当游戏共有 n = 3k + 1 轮的时候,两人可以保证至少 m = 2k 轮获胜。我们把这 3k + 1 轮游戏分成 k + 1 节:第一轮单独一节,接下来每三轮一节。只要 A 和 B 能做到每一节最多只错一个,就能保证 2k 轮的胜利了。 A 和 B 的基本策略就是,如果某一轮中 A 赌的数字和庄家相同,那么 B 就跟着 A 赌一样的,从而在本轮获胜;仅当 A 赌的数字和庄家不同,此轮已经必败无疑了的时候, B 才利用这一机会向 A 发信号。两人约定,此时 B 赌的数字就是下一节里出现得更多的数字。等这一轮结束后,如果 A 发现自己赌的数字是错误的,他就知道了 B 刚才是在发信号;在下一节游戏里, A 就全赌 B 刚才说的那个数字。容易看出,如果第一轮中 A 瞎赌的数字正好与庄家不符,并且今后每一节里庄家都会出两个 0 一个 1 或者两个 1 一个 0 ,那么每一节都会恰好输一次。

    麻烦就麻烦在,如果 A 瞎猜猜对了,依照策略 B 也会跟着往对的猜,则他们可能会毫无准备地进入全新的、还没被暗示过的一节,这反而会打乱我们的计划。不过没关系,只要每节里面仍然只有最多一个错误就行。因此,如果两人在新的一节中继续瞎猜并且实现了三连胜,这对我们没有影响;即使两人靠瞎猜赢得了前两轮,这对我们也没有影响。但是,如果 A 在本节的第一轮或者第二轮就出错了,问题就麻烦了。如果发生了这种情况,则 B 立即修改策略:利用此次错误向 A 发送信号,告诉 A 这一节还剩下的两轮或者一轮中哪个数字出现得更多(如果这一节还剩下两轮,并且庄家会出两个不同的数字,此时无所谓哪个数字出现得更多,那么 B 就随便告诉 A 一个数字)。不过,这样一来,本节里可能会出现多达两次的错误。

    不过,想一想,两人是怎么走到这一节的:两人是因为在前一节里全猜对了,才走到这一节的。因此,虽然这一节里会出现两次错误,但前一节里是全对的,因而平均每节的错误次数仍然不超过 1 ,这对我们仍然没有影响。有可能这一节的前一节也发生过错误吗?有可能!但只有这样一种可能:前一节本身也是事先没被暗示过的,他们在那一节里发生了一次错误,并且 B 宣布了那一节剩下几轮里出现得更多的数字,但由于剩下几轮里庄家的数字都是相同的,因而两人在剩下的几轮里全对。然而,走到这个前一节也是由于更前一节发生了类似的情况,等等等等,不断倒推过去,最终总能找到某个全对的一节(有可能是第一节),是它引发了这条特殊的链。在这条链中,各节的错误次数是 0, 1, 1, 1, …, 2 ,平均每节的错误次数仍然不超过 1 。

    这样,我们就有了一种在 n = 3k + 1 轮中保证 m = 2k 轮获胜的策略,它可以适用于任意情形。事实上,当 n = 3k + 2 时, m = 2k + 1 也是可以保证的。我们可以把最后多出来的那一轮看作是新的一节,那么两人走到这一节时,要么这一节已经被暗示过了(两人便会在这一节里取胜),要么这一节没被暗示过(两人便有可能在这一节里出错)。然而,如果这节没被暗示过,那么两人最多只会发生一次错误(因为这一节总共就只有一轮),因而它所在的链中,各节的错误次数依次是 0, 1, 1, 1, …, 1 。不管怎样,我们都能做到每节最多一处错误,且存在某一节全对。考虑到当 n = 3k + 2 时如此分节能得到 k + 2 节,因而错误数最多 k + 1 个,获胜的次数也就有至少 2k + 1 次了。

    好了,现在回到 n = 9 , m = 6 的情形。目前,它不属于我们之前解决过的任意一种情形。我们还是把这 9 轮游戏分成 4 节,第 1 轮一节,第 2 到 4 轮一节,第 5 到 7 轮一节,第 8 轮和第 9 轮一节。我们还能像刚才那样,保证 4 节当中只有 3 节会出错(且最多出一次错),剩余一节全对吗?这回不行了。刚才的最后一节只含一轮,如果有暗示则必然全对;但现在的最后一节包含两轮,这两轮的数字相同的话还好说,如果正好是有一个 0 有一个 1 的话,暗示了也拿不到全对。

    不过,只要之前出现过某一节全对的情况,事情都是可以弥补的。比方说,如果两人在第一节就全对了,两人就可以把剩余的 8 轮看作是一次新的游戏,利用 n = 3k + 2 时的策略保证 5 次胜利,加上第一节猜对的那一个,一共就是 6 次胜利了;或者,两人在第二节首次全对,两人便能利用 n = 3k + 2 时的策略在剩余的 5 轮中获得 3 次胜利,加上刚才第二节里的 3 连胜,于是又得到了 6 次胜利。如果两人在第三节才出现全对呢?两人将会在无暗示的情况下闯入最后一节,他们可以在这一节中赢得至少一轮,加上第二节的 2 次胜利和第三节的 3 次胜利,总共依然是 6 次胜利。

    怕就怕这样的情况:最后一节是两个相异的数字,并且每一节都已经在上一节中暗示过了。换句话说,现在唯一解决不了的情况是: A 在第一轮猜错了,并且第 2 到 4 轮的三个数字不全相同,并且第 5 到 7 轮的三个数字也不全相同,并且第 8 轮和第 9 轮是两个不同的数字。在这种情况下,两人会在每一节都出错一次,无法保证 6 次胜利。

    怎么办呢?最强大的部分就来了:此时, B 通过违背策略来给 A 发信号!如果 A 发现 B 违背了策略, A 就知道两人现在正处于这种唯一无法处理的情况;究竟是怎么违背策略的,这本身就会构成一种暗示。两人具体的做法如下。

    如果在第 5 到 7 轮中,只出现了一次的数字是第 5 轮中的数字,那么 B 就在第 2 到 4 轮里本来可以获胜的两轮中故意搞错一次(这一轮结束后 A 将会立即发现 B 违背了策略)。 B 可以选择在哪一轮里搞错,从而暗示第 8 轮和第 9 轮的两个数字是 01 还是 10 。结合目前两人所处的情形, A 就能推出第 5 轮到第 9 轮的全部数字。

    如果在第 5 到 7 轮中,只出现了一次的数字是第 6 轮中的数字,那么 B 在第 1 轮中改为发送第 2 到 4 轮中出现次数更的数字(第 4 轮后 A 将会发现 B 违背了策略)。在第 2 轮到第 4 轮中, B 跟着 A 一道把只出现了一次的那个数字弄对,另外两轮则用来发信号,分别指示第 5 到 7 轮中出现次数更多的是哪个数字,以及第 8 到 9 轮是 01 和 10 中的哪种情况。

    如果在第 5 到 7 轮中,只出现了一次的数字是第 7 轮中的数字(这说明第 5 轮和第 6 轮是本来应该获胜的两轮),那么 B 就在第 5 轮和第 6 轮当中故意搞错一次,究竟在哪一次搞错,则暗示了第 8 到 9 轮的数字是 01 还是 10 。 A 将会立即知道 B 违背了策略,并且根据已有信息,推出第 7 轮到第 9 轮的正确数字。

    不管是哪种情况,两人都能保证 6 次胜利。

    在写这篇文章时, Michael Brand 本人给予了很大的帮助,特此感谢。

 
    [附注] 在答案当中,“怕就怕这样的情况”之前的部分其实完全可以替换成一些更简单的方案,比如说:如果某一轮中 A 赌对了, B 就跟着赌一样的;如果某一轮中 A 出错了, B 就在该轮里暗示最近的还没被暗示过的三轮中出现次数更多的数字(如果剩下还没被暗示过的轮数只有一轮或者两轮了,那么就暗示这一轮或者两轮里出现次数更多的数字)。这意味着,当 A 进入瞎猜的状态时,如果他碰巧猜错了, B 暗示的将会是接下来的三轮中出现得更多的数字。这种方案会简单得多,并且由此带来的胜率往往会大于 2/3 。但是,它的不足之处就在于,在轮数有限的情况下,这种策略的实施情况捉摸不定,变数太多。当 n = 9 时,不能实现 6 次胜利的情况仍然是唯一的(即上面提到的那种情况),但我们很难证明这一点(如果你想到了很好的证明方法,请记得告诉我)。因而,上述答案中实际采用的是一个看上去更加曲折复杂的策略,它的好处就是实施过程会更有规律,更有利于后面的分析。

41 条评论

  • 陳昭瑋

    已閱,不過不很懂意思 QQ

  • mysh

    “如果在第 5 到 7 轮中,只出现了一次的数字是第 6 轮中的数字” 这段讲的方式, 如果2-4轮数字是一样的, 那么第1轮到第4轮有可能全错, 那就只有5次胜利.

  • EmptyHead

    IBM Prond This上的solution没有读懂。 仔细读了很多遍matrix67的文章才理解。 非常感谢。

    其实理解了解法以后,我更想知道这么精妙又复杂的解法,是怎么被想出来的 :)

  • wuyuup

    to mysh:这段文字讲的就是在2~4不完全相同时的解法。完全相同的话,如果第一轮猜对,那2~9就可以当做3k+2型;若第一轮错误,B给出2~4的提示,2~4可以全对,之后的5轮又可以当做3k+2型。

  • 本因坊算帐

    对于正整数 M,总可以找到最大的整数 N,使得按照题述规则,AB可以保证至少获胜 N轮。记这个N为f(M)
    容易知道:f(1)=0, f(2)=1, f(3)=1, f(4)=2,…,f(9)=6

    一个有趣的猜想是, 当M趋于无穷时,f(M)/M 是否有极限2/3 ?

  • gis

    很牛很 暴力

  • manson

    老大,说说比特币呗?

  • Evan

    Hi,
    我觉得你给的答案只能保证在理想情况下可行,但不可能保证在最坏的情况下可以有50%以上的成功率(最多只能有50%)。因为庄家的序列是无序的。
    假设庄家的序列是:0 1 0 1 0 1 0 1 0 这样的情况。当A在第一轮猜错,那B要在第一轮给他提醒,第一节只有一轮就是0,在B提醒之下,A在第二节(101)会出1,在第二节之中,A在第二轮猜错,B给A第三节的提醒是0,进入第三节(010),A会出0,在第三节的第二轮中A猜错,B给他提醒,但是第四节只有两个数,提醒什么都一样,最后A还是只猜中了5个。

  • Evan

    Hi Matrix,
    我觉得你给的答案只能保证在理想情况下可行,但不可能保证在最坏的情况下可以有50%以上的成功率(最多只能有50%)。因为庄家的序列是无序的。
    假设庄家的序列是:0 1 0 1 0 1 0 1 0 这样的情况。当A在第一轮猜错,那B要在第一轮给他提醒,第一节只有一轮就是0,在B提醒之下,A在第二节(101)会出1,在第二节之中,A在第二轮猜错,B给A第三节的提醒是0,进入第三节(010),A会出0,在第三节的第二轮中A猜错,B给他提醒,但是第四节只有两个数,提醒什么都一样,最后A还是只猜中了5个。

  • minglingmaster

    @Even 你没看完文章吧…

  • minglingmaster

    @Evan 你没看完文章吧…

  • minglingmaster

    @Evan 没看到文章后面吗…

  • aska

    hi Matrix,
    如果是5-7轮数字全是一样的, 最后2位不一样,如何猜中6个数呢?
    目前博客提供的解法,好像实现不了。

  • aska

    hi,
    上面的补充说明下。如010100010。
    因为制定了违反策略的规则,所以不管是B在 第1轮,第2-4轮,第5-7轮中任何一个位置违反,都会被认为5-7轮是2+1的情况(2个1,1个0或者2个0,1个1),导致5-7轮最多能对2个,又由于违反规则的原因,在第8轮前最多只能对3个。 8、9轮全对,也才5个。
    如果B不违反规则,第1轮猜错,2-4轮对2个,5-7轮对3个,8、9轮会因为没有提示,可能全错。这样也只有5个能对。

  • 好大一个

    坑~

  • 本因坊算帐

    15楼,
    010100010 不属于“需要违反策略”的情形。
    违反策略只会发生在如下情形:2-4不完全相同,5-7也不完全相同,8和9不同
    你的这个序列,5-7是相同的,因此不需要违反策略。

    按照原策略,2-4会对两个,5-7会全对,8,9至少会对一个,总共至少对6个。

  • liutianren

    可以从信息论角度分析,
    假设游戏进行充分多论(所以信息论才有用)

    A 每轮猜中的概率为 p,
    given A 猜中,B 给出正确答案的概率为 q。
    同时不妨设庄家是 i.i.d. 均匀分布。
    (否则,AB可以实现共享一个充分长的随机串… xor … detail不细说了)

    现在从 A 的立场来看,为了以 p 概率和庄家出的相同,没轮需要消耗 1-h(p) bit 的信息量。
    假如 A 猜对(以概率 p),则通过读 B 的回答,A 得到了 h(q) bit 的信息量;假如 A 猜错(以概率 1-p) ,则通过读 B 的回答,A 得到了 1 bit 的信息量。故平均每回合获得 p h(q) + (1-p) bit 的信息量。

    以此为基础的策略,可以实现 pq 的胜率,需满足信息量的约束,即
    max pq
    c.t. p h(q) + (1-p) > 1-h(p)
    解得 pq 最大值超过了 0.806。
    故有一种方法可以大概率实现 0.8 的胜率。

    根据我做信息论题目的经验,应该会有一种确定性策略,其胜率达到 0.8,只是需要的轮数可能很多。

  • haojianlv

    偶然发现Michael Brand就是UyHiP管理员吧。IBM Ponder This 和UyHiP就是一对好基友呀。

  • imisslovelove

    唔~~~看不懂。。。。

  • jdbRjsj

    这个问题是不是有毛病?为什么一定要B跟着A下注?不能A跟着B下注?

  • zhangk15

    可以做到9轮至少赢7次。
    1.因为第一次是A先下注,B无法提供信息,又是考虑最坏情况,所以第一次A,B一定输;
    2.把第一次B和庄家下注的数看成一个二进制数a(a=2*B出的数+庄家出的数),则其可能情况为00,01,10,11;我们希望用a来提示庄家出的第1~3个数中1的个数;遗憾的是,庄家的第一个数是给定的,比如说庄家第1~3个数为101,这样a只能取11或01,而第1~3个数中1的个数是10(即2)。因此我们需要令a的含义模糊一点。
    当a=11:庄家第1~3个数可能有2或3个1;
    当a=10:庄家第1~3个数有2个1;
    当a=01:庄家第1~3个数有1个1;
    当a=00:庄家第1~3个数可能有0或1个1;
    (解释:设庄家出的第一个数为b
    当b=1,1的个数为1,3时,a=01,11是确切数值,1的个数为2时,a=11是模糊数值,与真实值相差1;
    当b=0,1的个数为0,2时,a=00,10是确切数值,1的个数为1时,a=00是模糊数值,与真实值相差1;)
    即我们总能保证a与真实值相差<=1
    当a=11,A第2、3注下1,至少赢1次;
    当a=10,A第2、3注下1,赢2次;
    当a=01,A第2、3注下0,赢2次;
    当a=00,A第2、3注下0,至少赢1次;
    即最坏情况下,前三次输2次,注意到,此时我们仅仅用到了B第一次下注时的信息!所以B第2次下注庄家第4次的数,第3次下注庄家第5次的数……则从第4注开始A必胜。
    可以看出,无论n多大,均至少可赢n-2次。
    (不正之处请指教,上面博文答案的篇幅很长,没来得及看)

    • lisaren1109

      你好,,针对你发表的赌局策略的一些见解,我觉得很有独到之处,想和你详细聊聊切磋一下。我的QQ1772425659,方便告诉我你的QQ号码吗?期待你加我

  • 8piano8

    可把题解换种表达方式:
    *0.0. 把9轮分为4节,各节轮数依次为1-3-3-2;初定常规规则为:
    B在首节信号轮/前一轮的错轮或清一色时的末轮/出示下节的多数,
    A则在下节总出B上节的信号数。
    *1.1. 当第二节为混色,末尾节为清一色时,不论第三节混色或清色,
    B首节出示第二节的多数,第二节中2轮,
    第二节于错轮出示第三节的多数,第三节中>=2轮,
    第三节若混色于错轮/若清色于末轮出示末尾节的清色,
    末尾节中 2轮。
    *1.2. 当第二节为混色,末尾节混色,第三节为清一色时,
    B首节出示第二节的多数, 第二节中2轮,
    第二节于错轮出示第三节的清色,第三节中3轮,
    末尾节A总出上节数, 末尾节中1轮。
    *2.0. 当第二节为清一色时,不论其它是否清一色,
    B首节出示第二节的清色, 第二节中3轮,
    此时AB依赛前约定,变节为1-3-1-3-1,第三节为单轮信号轮,
    B第三节出示第四节的多数,第四节中>=2轮,
    第四节若混色于错轮/若清色于末轮出示末尾节的数,末尾节中1轮。
    *3.0. 当第二三四节都是混色时,B需要故意错示:
    *3.1. 当第三节的少数在第7轮时,B在第三节的第5或6轮错示,
    *3.1.1. 第5轮错示,
    按事先约定A明白了是第7轮是少数,第三节中2轮,
    按事先约定A也明白了是89轮是01, 末尾节中2轮;
    *3.1.2. 第6轮错示,
    按事先约定A明白了是第7轮是少数,第三节中2轮,
    按事先约定A也明白了是89轮是10, 末尾节中2轮;
    而第二节已中2轮!
    *3.2. 当第三节的少数在第5轮时,B在第二节的两个正确轮错示,
    *3.2.1. 若前轮错示,
    按事先约定A明白了是第5轮是少数, 第二节中1轮,
    加上A根据第二节A错轮时的B示,可第三节中3轮,
    按事先约定A也明白了89轮是01, 末尾节中2轮;
    *3.2.2. 若后轮错示,
    按事先约定A明白了是第5轮是少数, 第二节中1轮,
    加上A根据第二节A错轮时的B示,可第三节中3轮,
    按事先约定A也明白了89轮是10, 末尾节中2轮;
    *3.3. 当第三节的少数在第6轮时,B在首节错示为第二轮的少数,
    第二节能在少数轮中1轮,
    *3.3.1. B在第二节的两个多数位出示0-0,
    按事先约定A于第二节结束后明白了是第6轮是少数,
    也明白了第三节多数为0,第三节为010,末尾节为01,
    *3.3.2. B在第二节的两个多数位出示0-1,
    按事先约定A于第二节结束后明白了是第6轮是少数,
    也明白了第三节多数为0,第三节为010,末尾节为10,
    *3.3.3. B在第二节的两个多数位出示1-0,
    按事先约定A于第二节结束后明白了是第6轮是少数,
    也明白了第三节多数为1,第三节为101,末尾节为01,
    *3.3.4. B在第二节的两个多数位出示1-1,
    按事先约定A于第二节结束后明白了是第6轮是少数,
    也明白了第三节多数为1,第三节为101,末尾节为10,
    以上4种情况均做到第三节中3轮,
    末尾节中2轮。

  • lyc1102

    @evan 你没有看完巴

  • 沉睡海洋

    费脑子…
    没看完

  • matrixfan

    美垂克斯六七先生赶紧更新一篇吧,我快死了。

  • ning

    在3k+1保证2k中
    在全对的环节,B其实可以故意出错一个 来暗示下一轮?
    如果说B在第一轮故意出错 那A得到暗示 下一轮为0
    如果B在第二轮故意出错 那A得到暗示 下一轮为1
    这样行么?

  • 1

    更新,the sooner,the better.

  • hero

    更新吧!the sooner,the better.

  • Abner

    很喜欢博主的文章,刚刚用豆约翰博客备份专家备份了您的全部博文。

  • cr

    再不更新活不下去了。

  • Spectrum

    求更新!

  • tiankonguse

    好久没更新了。

  • lolo

    还是每次心情不好就来找乐子结果你没更新…… 然后我看到一个带声音的算法图示笑死了。。。orz

  • 5772156

    我认为3k+1,2k情况的描述有一处错误。
    按您的描述方式,在A猜错两次的一节,B没法给A做出暗示。下一节有可能仍然猜错两次。
    实际上,如果A第一次就猜错,而且后面两次一个0一个1,B可以直接暗示下一节,进入下一节时,A已经经历了标准答案的一次0和一次1,就知道了那次暗示。

  • sophie

    我認為其實有更簡單的方法,如將第一局為一組,第2至6為一組,7-9為一組;第一局B暗示2-6局中出現最多的數字,并在A必然錯誤的第一局中暗示7-8是01或是10,再在A必然錯誤的第二局中暗示第9局的數字,這樣就可以保證至少對6局,從而贏得勝利

回复给 manson 取消回复

8  +  1  =