智力吧 关注:36,876贴子:250,778
  • 9回复贴,共1

经典高难度智力题之《死囚试毒酒》

取消只看楼主收藏回复

现在有1024瓶红酒,其中两瓶有毒。毒性只对人有效,而且喝了之后要七天后才毒发,毒发者全身变金色而死 (喝一滴和喝一瓶都一样)。已知世上只有这两瓶毒酒有此效果。另外毒酒跟普通红酒外表、气味完全一样,即使在显微镜下。所以除了用活人试毒外别无他法。
现在你手上有一批用来试毒的死囚,每位参与试毒的死囚都按规定能收取安家费一万元 (不论最后是否中毒) ,你必须于七天后找出哪两瓶是毒酒。问如何设计方案使用最少成本 (即参与试毒的死囚数量) 并保证七天后找出两瓶毒酒?
初级难度:65人
中级难度:40人
高级难度:36人或更少


IP属地:澳大利亚来自Android客户端1楼2014-02-19 16:26回复


    IP属地:澳大利亚来自Android客户端2楼2014-02-19 16:27
    收起回复
      暂时还没有人提出稍为靠谱的方案或思路。。。不是乱说一个数目字就是说太难了之类。。。楼主这几天比较忙,下星期才回来看看有没有高手莅临露一下真功夫、。。


      IP属地:澳大利亚来自Android客户端13楼2014-02-20 14:32
      收起回复
        关于24楼的答案,其实原题设定是这样的(这里的40人是直接挑战中级难度了):
        有一个小国家,以生产高级葡萄酒闻名,全国的经济命脉也全依仗葡萄酒出口贸易。
        某一年,另一大国向这小国下了1024瓶最高级红酒的订单,并预付了丰厚的定金。
        假如交易成功并获得好评,类似生意将滚滚而来,会为全国人民带来很多年富足的生活。
        于是全国人民同心协力,终于耗尽那一季的所有资源制成了1026瓶质量超高的名贵红酒,其中两瓶送交国家博物馆留为纪念,余下1024瓶准备付运。
        但是,有一个对这国家极度憎恨的恐怖分子为了破坏这宗交易,不惜偷偷混入生产运输团队中,并在1024瓶酒中的其中两瓶酒内下了强力的生化毒药。
        此毒药药性强烈,只需极少份量(约0.01毫升)便可置人于死,如混酒饮下则中毒者24小时内并无异样,但24小时过后的15分钟内(可能是1秒钟后,也可能是14分59秒后)会立即七孔流血暴毙。
        在1024瓶酒要运上飞机的26小时前,恐怖分子的身份和计划都曝光了,但是因为他及时自杀了,官员们只确定了他在其中两瓶酒里下了生化毒药及其药性,但完全不知道是哪两瓶。
        这时全国陷入一片恐慌,假若不把1024瓶酒及时运送到目的地,哪怕是少了一瓶,都作违约论,国家要赔偿巨额的违约金,财政上会出现严重赤字,未来好几年的人民生计将会非常艰辛。
        但是假若把有剧毒的酒售卖出口并造成人命伤亡,将会对全国赖以为生的葡萄酒出产业造成无可挽救的声誉伤害,以后也休想做其他国家的生意了。
        就在这危急关头,监狱里有40名快将行刑的死囚站了出来,为了他们的亲人和朋友,决定自告奋勇,以身试毒,望能挽回这一笔对全国人民至关重要的生意。
        国家为了犒赏他们,不论试毒结果生死都会给与其家人一笔优厚奖金。(但是他们假若这次生还,回到监狱还是要服罪被处死的,不会被特赦。)
        时间还有25小时多一点,官员们已经聚集了全国很多熟手包装工人,花了大半小时把1024瓶红酒拆装,从每瓶酒内提取了数毫升份量作试毒用途,然后又把它们全部重新包装。
        现在距离最后时限还有24小时30分钟,40名自愿试毒的死囚和1024杯可能有毒的酒(每杯上都有标贴对照其相应的酒瓶号码)已经准备好了,现在只欠一个完善有系统的试毒程序来解决这难题。
        (提示:因为考虑到试酒程序最少需要数分钟来执行,所以时间只够让死囚们试酒一次。如果分隔15分钟让死囚们试两次酒,那么第二批中毒者可能会在时限之后才被发现暴毙。)
        附加题(暂时未有答案):为了替国家节省奖金费用,希望能有更优化方案让参与试毒的死囚人数从40减低到32甚至更少。


        IP属地:澳大利亚25楼2014-02-23 23:58
        收起回复
          关于40人的中级解法,我会于三月一日公布……


          IP属地:澳大利亚26楼2014-02-24 00:02
          回复
            一个极端的例子,假如0号组和3号组的10人全部暴毙,而1号、2号、近、远四组的30人却一个都没有死,那么毒酒是哪两瓶呢?
            很简单,就是编号0(00000)和1023(33333)的两瓶。
            以下是一个比较“正常”的例子:
            假如最后暴毙了的是:
            0号组:A0、C0、D0
            1号组:C1
            2号组:B2
            3号组:A3、B3、E3
            近组:AC1、BC1、BE1、CD1
            远组:AB2、AC2、AD2、AE2、BC2、BD2、CE2、DE2
            那么毒酒是哪两瓶呢?如果你能推算出来,就证明你真正明白了这个试毒酒的程序!


            IP属地:澳大利亚48楼2014-02-26 20:17
            回复
              目前的已知纪录是最少需要33人可以试出1037瓶酒中的其中两瓶毒酒,但这需要运用高等电脑编程技术计算出一大堆人脑不能理解的随机数据作工具:
              “数学研发论坛”的专业研究帖(包括上述33人方案的数据,见90楼):
              http://bbs.emath.ac.cn/thread-1511-9-1.html


              IP属地:澳大利亚49楼2014-02-26 20:22
              回复
                @沙城雨人 兄,搞了两个python程序,欢迎点评一下:
                65人初级解法(请用取代功能把“~”符号全部改成空格):
                from random import randrange
                def to_b2(n):
                ~~~~return [n/2**k%2 for k in range(10)]
                def fr_b2(li):
                ~~~~return sum([li[k]*2**k for k in range(10)])
                def drink(p1,p2):
                ~~~~li1,li2 = to_b2(p1),to_b2(p2)
                ~~~~g0 = [li1[k]==0 or li2[k]==0 for k in range(10)]
                ~~~~g1 = [li1[k]==1 or li2[k]==1 for k in range(10)]
                ~~~~gd = {}
                ~~~~for i in range(9):
                ~~~~~~~~for j in range(i+1,10):
                ~~~~~~~~~~~~gd[i,j] = li1[i]!=li1[j] or li2[i]!=li2[j]
                ~~~~return g0,g1,gd
                def test(g0,g1,gd):
                ~~~~diff = 10
                ~~~~t1,t2 = range(10),range(10)
                ~~~~for k in range(9,-1,-1):
                ~~~~~~~~if not g0[k]:
                ~~~~~~~~~~~~t1[k],t2[k] = 1,1
                ~~~~~~~~elif not g1[k]:
                ~~~~~~~~~~~~t1[k],t2[k] = 0,0
                ~~~~~~~~elif diff == 10:
                ~~~~~~~~~~~~diff = k
                ~~~~~~~~~~~~t1[k],t2[k] = 0,1
                ~~~~~~~~elif gd[k,diff]:
                ~~~~~~~~~~~~t1[k],t2[k] = 1,0
                ~~~~~~~~else:
                ~~~~~~~~~~~~t1[k],t2[k] = 0,1
                ~~~~return fr_b2(t1),fr_b2(t2)
                poison1 = randrange(1024)
                poison2 = (poison1 + randrange(1,1024)) % 1024
                g0,g1,gd = drink(poison1,poison2)
                target1,target2 = test(g0,g1,gd)
                print poison1,poison2
                print to_b2(poison1)
                print to_b2(poison2)
                print "0:",g0
                print "1:",g1
                print "d:",gd
                print target1,target2


                IP属地:澳大利亚50楼2014-02-26 20:43
                收起回复
                  这是40人中级解法(请用取代功能把“~”符号全部改成空格):
                  from random import randrange
                  def to_b4(n):
                  ~~~~return [n/4**k%4 for k in range(5)]
                  def fr_b4(li):
                  ~~~~return sum([li[k]*4**k for k in range(5)])
                  def drink(p1,p2):
                  ~~~~li1,li2 = to_b4(p1),to_b4(p2)
                  ~~~~g0 = [li1[k]==0 or li2[k]==0 for k in range(5)]
                  ~~~~g1 = [li1[k]==1 or li2[k]==1 for k in range(5)]
                  ~~~~g2 = [li1[k]==2 or li2[k]==2 for k in range(5)]
                  ~~~~g3 = [li1[k]==3 or li2[k]==3 for k in range(5)]
                  ~~~~gc,gf = {},{}
                  ~~~~for i in range(4):
                  ~~~~~~~~for j in range(i+1,5):
                  ~~~~~~~~~~~~diff1 = abs(li1[i]-li1[j])
                  ~~~~~~~~~~~~diff2 = abs(li2[i]-li2[j])
                  ~~~~~~~~~~~~gc[i,j] = diff1 == 1 or diff2 == 1
                  ~~~~~~~~~~~~gf[i,j] = diff1 > 1 or diff2 > 1
                  ~~~~return g0,g1,g2,g3,gc,gf
                  def check(u,v,d1,d2,c,f):
                  ~~~~a = [[0,1,2,2],[1,0,1,2],[2,1,0,1],[2,2,1,0]]
                  ~~~~a11 = a[u][d1]
                  ~~~~a22 = a[v][d2]
                  ~~~~c1 = a11 == 1 or a22 == 1
                  ~~~~f1 = a11 == 2 or a22 == 2
                  ~~~~if c == c1 and f == f1:
                  ~~~~~~~~return u,v
                  ~~~~else:
                  ~~~~~~~~return v,u
                  def test(g0,g1,g2,g3,gc,gf):
                  ~~~~diff = 5
                  ~~~~t1,t2 = range(5),range(5)
                  ~~~~for k in range(4,-1,-1):
                  ~~~~~~~~li = [g0[k],g1[k],g2[k],g3[k]]
                  ~~~~~~~~u = li.index(True)
                  ~~~~~~~~if (li.count(True) == 1):
                  ~~~~~~~~~~~~t1[k],t2[k] = u,u
                  ~~~~~~~~else:
                  ~~~~~~~~~~~~li[u] = False
                  ~~~~~~~~~~~~v = li.index(True)
                  ~~~~~~~~~~~~if diff == 5:
                  ~~~~~~~~~~~~~~~~diff = k
                  ~~~~~~~~~~~~~~~~t1[k],t2[k] = u,v
                  ~~~~~~~~~~~~else:
                  ~~~~~~~~~~~~~~~~t1[k],t2[k] = check(u,v,t1[diff],t2[diff],gc[k,diff],gf[k,diff])
                  ~~~~return fr_b4(t1),fr_b4(t2)
                  poison1 = randrange(1024)
                  poison2 = (poison1 + randrange(1,1024)) % 1024
                  g0,g1,g2,g3,gc,gf = drink(poison1,poison2)
                  target1,target2 = test(g0,g1,g2,g3,gc,gf)
                  print poison1,poison2
                  print to_b4(poison1)
                  print to_b4(poison2)
                  print "0:",g0
                  print "1:",g1
                  print "2:",g2
                  print "3:",g3
                  print "c:",gc
                  print "f:",gf
                  print target1,target2


                  IP属地:澳大利亚51楼2014-02-26 20:51
                  收起回复
                    36人解法在此帖子:http://tieba.baidu.com/p/3817681959


                    IP属地:澳大利亚151楼2015-07-13 23:58
                    收起回复