1000瓶酒2瓶毒酒的问题，目前最少41人（待验证）

dextersa

应18，19楼的要求对题目做了一定修改。

有1000瓶酒，其中只有2瓶是毒性很强的慢性毒酒（一滴就足以至人死亡，但发作的时间要23小时），现有足够的死刑犯(用小白鼠也可以，假设小白肯定会喝掉你给它的全部酒)供你试验，请问为了在24小时之内找出这两瓶毒酒的话至少需要多少个死刑犯(小白鼠)？说白了就是只能测试一次就要准确结果
请具体说明检验的方法。


注：原来这个题目是1瓶，但是我现在想要求解两瓶。1瓶用二进制10个人可以搞定。

最近几天比较忙，可能对贴的更新，以及各算法的验证，比较少。见谅。


大家有空看看

lulijie说：13楼我的41人的方法有错误，当两瓶毒酒D数位上的数字相同时，就无法唯一确定两瓶毒酒的编号。
非常对不起大家，考虑不够周密，请楼主改正。

我觉得稍加修改即可
比如添加：   (B-C)0，(B-C)1，(B-C)2，(B-C)3，(B-C)4，(B-C)5
即可。
出现一41人的办法，在13#
13楼：

原帖由 lulijie 于 2009-6-28 00:19 发表

我的41个人的方法：
将1000瓶酒从0编号到999，（6进制表示法）那么编号从0000到4343（6进制）
     ABCD（6进制）    B、C、D位的数字为0-5，A位的数字为0-4
用Xn表示X位上数字为n的所有酒混在一起形成的一杯酒，
用(X-Y)n表示X位上数字减去Y位上的数字等于n或n-6的所有酒混在一起形成的一杯酒，
    比如  C2 表示C位上为2的所有酒混在一起形成的一杯酒
            (A-D)2表示A位上数字减去D位上的数字等于2或-4的所有酒混在一起形成的一杯酒
那么我们调和成以下各酒
   A0，A1，A2，A3，A4，
   B0，B1，B2，B3，B4，B5
   C0，C1，C2，C3，C4，C5
   D0，D1，D2，D3，D4，D5
   (A-D)0，(A-D)1，(A-D)2，(A-D)3，(A-D)4，(A-D)5
   (B-D)0，(B-D)1，(B-D)2，(B-D)3，(B-D)4，(B-D)5
   (C-D)0，(C-D)1，(C-D)2，(C-D)3，(C-D)4，(C-D)5
  一共有41杯酒。
每杯酒试验一个人，就可找出那两杯毒酒来。
------------------------------------
比如两杯毒酒的编号分别为1234和2435
那么喝A1，A2，B2，B4，C3，D4，D5，(A-D)3，(B-D)4，(B-D)5，(C-D)4，(C-D)5酒的人会死，喝其他酒的人不死。
根据A1，A2、D4，D5，得出两杯毒酒编号的A位为1和2，D位为4和5，再根据(A-D)3，即A-D 都等于3或-3，得出两杯毒酒AD位为14和25
根据C3，得出两杯毒酒的C位都是3
再根据B2，B4，(B-D)4，(B-D)5，得出两杯毒酒的编号为1234和2435。唯一确定。

24楼：

原帖由 lulijie  发表

用m进制表示1000以内的数，用N表示需要的位数，用S表示最高位少用的数字数(比如6进制，最高位只需要使用5个数字，少使用1个数字，S＝1)，那么
    m=2，N=10，S＝0
    m=3，N=7，S＝1
    m=4，N=5，S＝0
    m=6，N=4，S＝1
    m=10，N=3，S=0
    m=32，N=2，S＝0
－－－－－－－－－－－－－－－－－－－－－－－－
一瓶毒酒的情况：
    用10位二进制的数 A0A1A2A3A4A5A6A7A8A9 来标记1000瓶酒
    标号从0000000000到1111100111。
    要确定毒酒的标号，必须确定每一位的数字是0还是1.
    用(Ai=0)表示Ai位为0的所有酒各取一些混成一杯酒，
    调和成以下10杯酒：
       (A0=0)，(A1=0)，(A2=0)，(A3=0)，(A4=0)，(A5=0)，(A6=0)，(A7=0)，(A8=0)，(A9=0)
    用f(i)表示饮用(Ai=0)酒后的死亡情况，
       f(i)＝0 表示饮用(Ai=0)酒后死亡，
       f(i)＝1 表示饮用(Ai=0)酒后没有死亡，
    那么毒酒的标号就是 f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)f(8)f(9)

   用其他进制标记各酒，找出毒酒所需调和的总酒杯数＝(m-1)*N-S,结果都大于10杯。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
两瓶毒酒的情况：
    用N位m进制数 A0A1......AN-1 标记1000瓶酒,
    要确定毒酒的标号，必须确定毒酒每一数位上的数字.
    将每个数位上的数字相同的所有酒混合在一起成1杯酒，那么每个数位上可混合成m杯酒（高位为m-S杯酒），一共配成m*N-S杯酒。
    每个数位上的m杯酒，被喝了，死亡人数为1人或2人。
        若为1人，那么两瓶毒酒该数位上的数字相同，两瓶毒酒该数位上的数字就可被确定。
        若为2人，那么两瓶毒酒该数位上的数字不相同，到底哪个数字是哪瓶毒酒该数位上的数字不能确定。
    若所有数位上只有一个数位不能确定，那么没关系，随便定就可。
    若有两个以上的数位不能确定，那么，毒酒就不能被唯一确定，例如两瓶毒酒A1位数字为a，b，A3位数字为c，d，那么毒酒到底是ac、bd，还是ad、bc就不能确定。只能增加调和的酒杯数，必须联合A1A3，至少配成m-1杯酒，比如按照A3-A1的值除以m的余数来配酒。
    这N个数位每两个数位之间都必须联合配酒才可。这样总共增加了(m-1)*N*(N-1)/2杯酒.
所以为了确定两杯毒酒，总共需要调和的总酒杯数为m*N-S+(m-1)*N*(N-1)/2。
计算结果，发现m＝4时，总共需要调和的总酒杯数最少，为50杯。
     总酒杯数     一杯毒酒   两杯毒酒
            2进制： 10           65
            3进制： 13           62
            4进制： 15           50
            5进制： 17           62
            6进制： 19           53
            7进制： 20           60
            8进制： 22           68
            9进制： 25           77
            10进制：27           57
            32进制：62           95
－－－－－－－－－－－－－－－－－－－－－－－－－－
即采用5位4进制数 A0A1A2A3A4 标记1000瓶酒,
    调和成以下50杯酒,每杯酒试验一个人。
                  (A0-A4 mod 4=0) 表示A0位的数字减去A4位的数字除以4的余数等于0的所有酒调和成一杯酒。
    (A0=0),(A0=1),(A0=2),(A0=3)
    (A1=0),(A1=1),(A1=2),(A1=3)
    (A2=0),(A2=1),(A2=2),(A2=3)
    (A3=0),(A3=1),(A3=2),(A3=3)
    (A4=0),(A4=1),(A4=2),(A4=3)
    (A0-A4 mod 4=0),(A0-A4 mod 4=1),(A0-A4 mod 4=2)   
    (A1-A4 mod 4=0),(A1-A4 mod 4=1),(A1-A4 mod 4=2)
    (A2-A4 mod 4=0),(A2-A4 mod 4=1),(A2-A4 mod 4=2)
    (A3-A4 mod 4=0),(A3-A4 mod 4=1),(A3-A4 mod 4=2)
    (A0-A3 mod 4=0),(A0-A3 mod 4=1),(A0-A3 mod 4=2)
    (A1-A3 mod 4=0),(A1-A3 mod 4=1),(A1-A3 mod 4=2)
    (A2-A3 mod 4=0),(A2-A3 mod 4=1),(A2-A3 mod 4=2)
    (A0-A2 mod 4=0),(A0-A2 mod 4=1),(A0-A2 mod 4=2)
    (A1-A2 mod 4=0),(A1-A2 mod 4=1),(A1-A2 mod 4=2)
    (A0-A1 mod 4=0),(A0-A1 mod 4=1),(A0-A1 mod 4=2)

[ 本帖最后由 dextersa 于 2009-6-30 13:20 编辑 ]

yilonglucky

答案肯定小于1000，占楼……
正在解答……
=============================
突然想到另外一道题：9枚硬币中有一枚重量较重的假币，只有一个天平，只需要比较两次就能找出假币。
继续求解……
=============================
汗……都是强人啊……我弃权了……呵呵

[ 本帖最后由 yilonglucky 于 2009-6-28 01:04 编辑 ]

ducksun5555

这问题过分了，用人做实验，还得喝掺酒....

专业新手

如果找一瓶998
如果两瓶全找999

landswimmer

呵呵，跟我想得一样哦
哦，不对，仔细用笔算了算，应该是要五百个人吧

xhzwd

要喝掺酒啦！
方法是用到黄金分割法，黄金分割为0.618，为了好理解我们用0.5。
就是说呢：第一位囚犯喝的酒为500瓶掺的酒，第二位囚犯喝的酒为另外500瓶掺的酒。
1                      1X1                 1X2                1X3               1X4---------
500/1000       250/500        125/500         75/125         38/75
                         1X11              1X12              1X13            1X14---------
                         250/500        125/500         75/125         38/75
                                                 1X121           1X123          1X124---------
                                                 125/500         75/125         38/75
                                                     ------              ------               ------
2                      2X1                 2X2                2X3               2X4---------
500/1000       250/500        125/500         75/125         38/75
嗨费时间不计算了。

CodS

LZ，你上面说2瓶毒酒，下面又说“找出这瓶毒酒”，到底是让我们求出1瓶还是2瓶？

Room

那就找1000个囚人，反正都是死两个人，结果一样的，不伤脑筋，呵呵

花满楼haha

原帖由 yilonglucky 于 2009-6-27 17:02 发表
突然想到另外一道题：9枚硬币中有一枚重量较重的假币，只有一个天平，只需要比较两次就能找出假币。
继续求解……

这个比较简单，把9枚硬币分成3份，每份3个。先比较其中两份，
    情况1：如果这两份中有一份比较重，那么重的硬币在重的一份里，
    情况1.1  接着用上面的方法比较这三个硬币，先比较其中2个，
     哪个重哪个就是重硬币。
    情况1.2  如果这两个硬币一样重，那么重硬币就是剩下的那个
    情况1共用2次天平

   情况2：如果这两份硬币一样重，那么重硬币在第三份里，方法见情况1.1和1.2
   情况2共用2次天平

   问题解决

骰迷

這個。。摻酒是很好的想法，支持