chaostar吧 关注:3,071贴子:343,801

挖坑不埋的数学题系列之合作坑庄家

只看楼主收藏回复

出典:IBM Ponder This。
涉及知识:情报/密码学
说Alice和Bob两人被迫参加一个邪恶的赌局,规则是这样的:
Alice猜一个数0或1并公开,然后Bob猜一个数0或1并公开,然后庄家翻开事先已经藏好写在纸上的一个数字0或1,只有这三个数都相等时,Alice和Bob才视为赢。
如果Alice和Bob两孩子特别傻,就闷头乱猜,那么一局里赢的概率显然只有25%。
如果Bob比较聪明,看Alice猜什么自己就跟着猜什么,那么一局里赢的概率立刻会上升到50%,效率高多了。
然而,如你所知,上文里的数字都是概率,即使50%概率获胜也可能屡战屡败惨死。
明天比赛就要开始了,今晚Bob得到了一个振奋人心的好消息:
明天比赛开始后,Bob有内线,可以拿到庄家藏好的纸上所有的情报!
但是比赛一旦开始,Alice和Bob就再也无法交流,只能眼睁睁的看着他们选择了0还是1。
那么,Alice和Bob开始讨论,他们有什么办法,可以确保在明天的9局比赛里,赢下至少4局呢?
哦,这个问题并不复杂,Bob大可以放弃第1357局,不管Alice猜了什么,Bob都明确给出下一局庄家藏起来的数字,然后第2468局Alice和Bob只要一起猜这个数字,就可以安定的拿下来4局,可喜可贺,可喜可贺。
多么好的策略,但还是不够。
明天的9局比赛里,Alice和Bob要至少拿下6局,才能逃出升天。
现在,商量一个办法,让两个人都能活命吧。


IP属地:上海1楼2016-06-07 18:35回复
    我学弟给我一个12局赢9局的,我做了2个晚上也没做出来……


    IP属地:陕西3楼2016-06-07 19:24
    回复
      每次猜完,能否马上知道结果?


      IP属地:江苏7楼2016-06-08 08:49
      收起回复
        如果能马上知道结果,大概有2个思路。
        第一,传递有序度,而不是具体0和1。
        第二,传递0和1的个数,而不是具体0和1.


        IP属地:江苏8楼2016-06-08 08:53
        回复
          各位可以先考虑两个相对简单的子问题:同样的条件下如何确保七局四胜,如何确保八局五胜,然后再思考最为复杂的九局六胜。


          IP属地:上海来自手机贴吧9楼2016-06-08 09:02
          回复
            没能解完,先提个思路吧
            事先定好B行动的4组序列,其前2位各不相同,等于是序列的编号。
            序列设计的目标是:对于任意一种庄家出牌可能性,至少存在一个序列,其后7位至少与其有6位相同。
            一个等效且的问题是:在一个7维的单位立方体上,选取4个特殊顶点,保证这个7维立方体的任意一个顶点至少与一个特殊顶点重合或相邻。
            更抽象的版本:在一个9-N维的单位立方体上,选取2^N个特殊顶点,保证这个9-N维立方体的任意一个顶点到最近的特设顶点的“距离”不超过3-N。(上面是N=2时的情况)
            此外还有一个可以利用的地方是序列的编号本身。
            要求A如此行动:第一次随意(默认失败),第二次跟随B第一次的行动;第三次起根据B的序列行事。
            这样在不止一个序列的后7位都只有5位于庄家序列相同时,B可能可以选择序列,使得能在传递编号的阶段胜利一次,凑够6次。
            使用这样的方案的话,使用前3位传递信息,一共8组序列似乎也不是完全不可能,但目前没找到可行的方案。
            目前的难点就是选取顶点的问题,空间想象力不太够,没找到一个好的选取方式。只解决的7局4胜的问题,更进一步的问题始终差一些。在考虑要不要写个小程序穷举算了。
            附7局4胜的4组序列:
            0000000
            0100111
            1011000
            1111111


            IP属地:北京10楼2016-06-08 12:12
            收起回复
              之前好像误导了,那个是12局8胜……


              IP属地:陕西16楼2016-06-08 15:22
              回复
                感谢各位支持:
                我整理了一下通俗易懂简洁明了的5000字答案,希望大家喜欢。
                http://weibo.com/p/1001603984059859653404


                IP属地:上海17楼2016-06-08 22:02
                回复