智力吧 关注:36,876贴子:250,778

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

只看楼主收藏回复

楼主我不知道,,感觉好难,肿么办,我觉得我好笨


来自Android客户端35楼2014-02-25 20:43
回复
    1024=4^5=4*4*4*4*4
    所以1024可用五位数【0,1,2,3】【0,1,2,3】【0,1,2,3】【0,1,2,3】【0,1,2,3】来表示
    需要20个人(4*5=20)每人代表某一位上某个数字。如A0代表第一位0,A1代表第一位1,A2代表第一位2,A3代表第一位3,B0代表第二位0,B1代表第二位1。。。。。。
    再来10人(C(5,2)=10)代表每两位之间数字相同,记为H(m,n)(1<=m<n<=5,)
    再来10人(C(5,2)=10)代表每两位之间数字之差值为1:差值=高位减低位,如为负数则再加4,即1-0=1,2-1=1,3-2=1,0-3=1。记为J(m,n)(1<=m<n<=5,)
    这样一共需要40人
    如何判断两瓶酒的数字:
    每一位4个数字最多出现2个数字中毒,只有1个中毒说明两瓶酒在这位数字相同
    如果出现多个位子2个数字中毒,从最小那个位子开始,根据后面20人的中毒表现推断
    如:m、n(m<n)位都出现两个数字,记为m1,m2,n1,n2
    首先看H(m,n)这个人是否中毒,如中毒,则m1或m2与n1,n2中有相等的立即匹对
    如H(m,n)不中毒,则看J(m,n)是否中毒,如中毒,则m1或m2与n1-1,n2-1(负值再加4)中有相等的立即匹对
    易证如果m、n位都出现2个数字中毒,则H(m,n)、J(m,n)中至少有一个中毒
    下面简单举例示范:
    五位数字出现中毒为【0,2】【0,2】【1】【3】【1,3】
    则先看H(1,2)为中毒,则两瓶酒为【0013,2213】【1,3】
    再看H(1,5)为不中毒(或者H(2,5)),再看J(1,5)为中毒(或者J(2,5)),
    则两瓶酒为【00131】、【22133】,转换为十进制过程略去


    IP属地:江苏36楼2014-02-26 11:09
    收起回复
      最少10个。用集合的知识,10个元素的集合共有1024个子集。


      来自Android客户端37楼2014-02-26 11:46
      回复
        每瓶红酒对应一个子集里的人,无论多少瓶毒酒用这10个人都能找出来~


        来自Android客户端38楼2014-02-26 11:53
        回复
          不对,想错了


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


            IP属地:云南来自Android客户端40楼2014-02-26 13:11
            收起回复
              40人:
              1024=4^5=4*4*4*4*4
              所以1024可用五位数【0,1,2,3】【0,1,2,3】【0,1,2,3】【0,1,2,3】【0,1,2,3】来表示
              需要20个人(4*5=20)每人代表某一位上某个数字。如A0代表第一位0。。。。。。
              再来10人(C(5,2)=10)代表每两位之间数字相同,记为H(m,n)(1<=m<n<=5,)
              再来10人(C(5,2)=10)代表每两位之间数字之差值为1:差值=高位减低位,如为负数则再加4,即1-0=1,2-1=1,3-2=1,0-3=1。记为J(m,n)(1<=m<n<=5,)
              这样一共需要40人
              如何判断两瓶酒的数字:
              每一位4个数字最多出现2个数字中毒,只有1个中毒说明两瓶酒在这位数字相同
              如果出现多个位子2个数字中毒,从最小那个位子开始,根据后面20人的中毒表现推断
              如:m、n(m<n)位都出现两个数字,记为m1,m2,n1,n2
              ——————————————————————————
              首先看H(m,n)这个人是否中毒,如中毒,则m1或m2与n1,n2中有相等的立即匹对
              如H(m,n)不中毒,则m1或m2与n1,n2中有相等的立即与另一个匹对
              再看J(m,n)是否中毒,如中毒,则m1或m2与n1-1,n2-1(负值再加4)中有相等的立即匹对
              如J(m,n)不中毒,则m1或m2与n1-1,n2-1(负值再加4)中有相等的立即与另一个匹对
              ——————————————————————————
              易证如果m、n位都出现2个数字中毒,则根据H(m,n)、J(m,n)一定可以确定对应序列


              IP属地:江苏41楼2014-02-26 13:39
              收起回复
                设置比较难啦,不过理论上要找出最少的人还是很简单的,就结果上来说C(0,n)+C(1,n)+。。。+C(n,n)>=1024.找到最小的n即可。


                42楼2014-02-26 13:58
                回复
                  拿4瓶开始啊,两个人。
                  甲喝1,2
                  乙喝1,3,那么出现4种情况能辨别。
                  8瓶,三个人
                  甲喝1,2,3,7
                  乙喝1,2,4,6
                  丙喝1,3,4,5
                  以此类推。后面你真要我写出来没劲


                  43楼2014-02-26 14:07
                  收起回复
                    反正10个人就够了,每人512滴很简单的,要答案我做个Excel给你就好了


                    44楼2014-02-26 14:14
                    收起回复
                      看到了觉得我对的话,发个邮件告知一下,648317200@qq.com,谢谢!古天乐我看好你哟!


                      45楼2014-02-26 14:17
                      收起回复
                        一个极端的例子,假如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
                            收起回复