魔方吧·中文魔方俱乐部

标题: 1000瓶酒2瓶毒酒的问题，目前最少41人（待验证） [打印本页]

---

作者: dextersa    时间: 2009-6-27 16:59:08     标题: 1000瓶酒2瓶毒酒的问题，目前最少41人（待验证）

应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    时间: 2009-6-27 17:02:20

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

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

---

作者: ducksun5555    时间: 2009-6-27 17:03:29

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

---

作者: 专业新手    时间: 2009-6-27 17:05:03

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

---

作者: landswimmer    时间: 2009-6-27 17:25:52     标题: 回复 4# 的帖子

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

---

作者: xhzwd    时间: 2009-6-27 17:31:23

要喝掺酒啦！
方法是用到黄金分割法，黄金分割为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    时间: 2009-6-27 18:42:09

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

---

作者: Room    时间: 2009-6-27 18:46:48

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

---

作者: 花满楼haha    时间: 2009-6-27 18:59:08

原帖由 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次天平

   问题解决

---

作者: 骰迷    时间: 2009-6-27 19:04:31

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

---

作者: shenheng    时间: 2009-6-27 20:53:50

１瓶的情况，用９个人就可以解决了，第１０个是枉死的

---

作者: dextersa    时间: 2009-6-27 21:46:43

头大了…………

---

作者: lulijie    时间: 2009-6-28 00:19:30

我的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。唯一确定。

---

作者: yilonglucky    时间: 2009-6-28 01:05:44     标题: 回复 9# 的帖子

汗……是啊……谢谢你的详细解答哦……
我的意思是说能不能利用这个道理来比较，后来发现好难，遂放弃……

---

作者: Cielo    时间: 2009-6-28 01:49:25

想了一下没想明白，只有1瓶的时候，10个人怎么试出来？
——————————————————————————————————
呃想错了，10个人肯定可以的……

19楼的答案是有一定道理的，至少给出了一个下界。
因为这是从信息量的角度来考虑的，要能试出哪两瓶有毒，那么测试的总的结果数应该≥C[sub]1000[/sub][sup]2[/sup]，
而如果有n个人，结果数差不多就是2[sup]n[/sup]（每个人有生死两种结果）。

[ 本帖最后由 Cielo 于 2009-6-29 04:52 编辑 ]

---

作者: edmond-xym    时间: 2009-6-28 07:18:53

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

你的问题不难，三个一组来分组，两次就能称出来。

---

作者: ggglgq    时间: 2009-6-28 17:23:12

　　
　　
  
  
  
    建议楼主把题目改一下，拿“死刑犯”作实验也有点儿太残忍了吧？！  如果是
  
一 杯毒酒，可以用 10 个酒杯测试！ 比如：
  
    测试.rar (40.63 KB, 下载次数: 20)

2009-6-28 17:23:12 上传

下载次数: 20

  
    其中 标 1 的为掺酒， 标 0 的为不掺酒。
　　
　　
　　
　　
　　

[ 本帖最后由 ggglgq 于 2009-6-29 02:18 编辑 ]

附件: 测试.rar (2009-6-28 17:23:12, 40.63 KB) / 下载次数 20
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTcwMjd8MzAxMDFjNDB8MTc0MDk0ODAwN3wwfDA%3D

---

作者: 06154    时间: 2009-6-29 02:43:51

原帖由 dextersa 于 2009-6-27 04:59 PM 发表
有1000瓶酒，其中只有2瓶是毒性很强的慢性毒酒（一滴就足以至人死亡，但发作的时间可能要24小时），现有足够的死刑犯供你试验，请问为了在24小时之内找出这两瓶毒酒的话至少需要多少个死刑犯？说白了就是只能测试一次就要准确结果请具体说明检验的方法。

是我理解有问题吗？怎么都觉得这个题目无解？？既然“发作的时间可能要24小时”，即使找1000个人试了这1000瓶酒，也很可能要在24小时后才有两人倒下。若是这样，就不可能“在24小时之内找出这两瓶毒酒”。不是吗？

---

作者: yq_118    时间: 2009-6-29 02:57:34

1000*999/2=499500
ln499500/ln2=18.93……
所以要19个人。

---

作者: superacid    时间: 2009-6-29 11:54:52

原帖由 yq_118 于 2009-6-29 02:57 发表
1000*999/2=499500
ln499500/ln2=18.93……
所以要19个人。

我也是这么想的，但是无法举出例子

---

作者: superacid    时间: 2009-6-29 11:59:35

是否能够这样：
把每两瓶酒组成的对子设为一瓶新的“酒”，这样就有499500瓶新“酒”，
题目变成：
有499500瓶“酒”，其中只有1“瓶”是毒“酒，现有足够的死刑犯供你试验，请问为了在24小时之内找出这两瓶毒酒的话至少需要多少个死刑犯？
这样19人就够了（仿照1000瓶10人的方法）

---

作者: dextersa    时间: 2009-6-29 20:08:49

原帖由 superacid 于 2009-6-29 11:59 发表
是否能够这样：
把每两瓶酒组成的对子设为一瓶新的“酒”，这样就有499500瓶新“酒”，
题目变成：
有499500瓶“酒”，其中只有1“瓶”是毒“酒，现有足够的死刑犯供你试验，请问为了在24小时之内找出这两瓶毒酒的 ...

注意，是剧毒，这样会使毒酒变为1999瓶，也就是说会得到1999个编号的每位逻辑或比从2个2进制的数每位逻辑或可能还要难。

举例，假设我们用二进制。

5号和6号有毒。
5：0000000101
6：0000000110
逻辑或之后0000000111
那么死掉三个人，如何将他分解开来？

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

---

作者: lulijie    时间: 2009-6-29 22:35:37

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

---

作者: lulijie    时间: 2009-6-29 22:39:54

用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)

[ 本帖最后由 lulijie 于 2009-6-29 22:48 编辑 ]

---

作者: superacid    时间: 2009-6-30 08:40:22

楼上的例子看上去挺有道理的，不过证明不太严密，有巨大漏洞没有讲清。

[ 本帖最后由 superacid 于 2009-6-30 10:10 编辑 ]

---

作者: cg372101    时间: 2009-6-30 09:33:59

19人是否够用，我不知道，但是我感觉20人应当够了。

下面以16瓶8个人为例（依样画瓢可以推广到1024瓶20人，在稍加整理即可推及到1000瓶20人）

对16瓶酒依次编号1至16，8个人一次编号为①至⑧
照下表取相应瓶编号的就勾兑，并给相应编号的人喝，比如“③：1—4，9—12”表示把编号为1、2、3、4、9、10、11、12的酒给编号为③的人喝。

①：1—8　　　　　　　　　　　　　　②：9—16
③：1—4，9—12　　　　　　　　　　 ④：5—8，13—16
⑤：1—2，5—6，9—10，13—14　　　⑥：3—4，7—8，11—12，15—16
⑦：1，3，5，7，9，11，13，15　　　⑧：2，4，6，8，10，12，14，16

比如：
若①至⑧全部完蛋了，那就只可能是1、16两瓶有毒（当然前提是有且仅有两瓶有毒）

也不知对不对，请高人批评指正。

---

作者: lulijie    时间: 2009-6-30 12:28:08

26#:：
①：1—8　　　　　　　　　　　　　　②：9—16
③：1—4，9—12　　　　　　　　　　 ④：5—8，13—16
⑤：1—2，5—6，9—10，13—14　　　⑥：3—4，7—8，11—12，15—16
⑦：1，3，5，7，9，11，13，15　　　⑧：2，4，6，8，10，12，14，16
若毒酒是14，15，那么  饮  ②  ④⑤⑥⑦⑧  的人会死。
若毒酒是13，16，那么  饮  ②  ④⑤⑥⑦⑧  的人会死。
那么这两种情况如何能区分呢？所以上述方法不行。
-------------------------------------------------------------
其实26#的方法就是我的2进制的方法。A0A1A2A3  表示0-15 （1-16号改为0-15）
① 相当于A0位为0的酒的混合  ②   相当于A0位为1的酒的混合
③ 相当于A1位为0的酒的混合   ④ 相当于A1位为1的酒的混合
⑤ 相当于A2位为0的酒的混合  ⑥ 相当于A2位为1的酒的混合
⑦ 相当于A3位为0的酒的混合 ⑧ 相当于A3位为1的酒的混合

当 ⑤⑥⑦⑧ 都死人时，相当于两瓶毒酒A2位分别是0和1，A3位分别是0和1，
    两瓶毒酒的A2A3位到底是00，11 还是01，10 无法区分。

---

作者: superacid    时间: 2009-6-30 13:40:14     标题: 回复 24# 的帖子

你仅仅说明了如果用进制方法最小可以达到50，如果不用这类方法呢？
需要严格证明。

---

作者: lulijie    时间: 2009-6-30 14:47:04

我只是举出我的一系列方案，该方案是不是最少人的方案，我也不知道。如果有谁举出少于50人的具体例子，那么50人的方案就不是最佳方案。
这一系列方案是我的一种思路。
--------------------------------------------------------------------------------------
还有一种思路是：倒推法
假设最少方案是N个人，每个人喝一杯调和成的酒，那么每个人只有死和活两种状态，N个人总共有2^N种状态。
而两瓶毒酒在1000瓶酒中的分布一共有1000*999/2=499500中情况。
要想从喝酒后的分布状态推出唯一的毒酒分布状态，
499500种毒酒分布状态与2^N 种喝酒后的分布状态必须一一对应。
不能有某两种毒酒分布状态对应同一种 喝酒后的分布状态。
这样499500<=2^N  ，得出N>=19。
关键是如何设计这种一一对应关系，即从2^N 种喝酒后的分布状态中取出499500种与毒酒分布状态一一对应，使得N尽可能的小。
比如：假设N=19可行，2^19=524288,也就是从524288种精心挑选出499500种。
        1.喝酒都不死人的状态，对应1号和2号是毒酒，那么19个人喝的酒配方中都不能混有1和2号，（当然也可以把该状态旷置不用。）
        2. 第一个人喝死，其他人不死的状态，对应1号和3号是毒酒,那么第一个人酒配方必须有3号酒，其他人配方中无3号酒。
       这样对于2号酒、3号酒是毒酒的情况就无法设置一一对应关系。
    所以如果使用喝酒都不死人的状态，那么死一个人的状态对应的两毒酒就不能和喝酒都不死人的状态对应的毒酒相同。我觉得还是把喝酒都不死人的状态旷置不用的好。
       。。。。。。
    依次类推，若将所有的毒酒分布状态都对应完毕，也没出现矛盾，那么这种方案就是可行的。

---

作者: superacid    时间: 2009-6-30 14:51:11

确实是一道好题啊！我问问我的同学，看他们有什么想法。

---

作者: lulijie    时间: 2009-6-30 20:31:42

1000瓶太多，先从少数瓶开始，容易一点。

N瓶酒中有两瓶毒酒，需试验的最少杯数为S
      N=             S=
      2                0
      3                2
      4                3
      5                4
      6                4？
      7                5？

6瓶酒中有两瓶毒酒，理论上S必须>=4，S=4的方案能不能举出例子呢？若N=6，理论上的最少值都无法取到，有理由相信对于1000这么大的数，理论上的最少值19也无法取到。

---

作者: superacid    时间: 2009-6-30 22:08:24

经过我的同学的编程验证(比较可靠)：

0:2
2:3
3:4
4:5
5:6
6:7-8
7:9-12
8:13-16
9:17-24
10:25-32
11:33-48
12:49-64
13:65-96
14:97-128
15:129-192

左边是最少需要的人数，右边是酒的总瓶数，例如：如果酒的瓶数在129~192之间的话至少要15个人

---

作者: lulijie    时间: 2009-6-30 22:30:51

楼上的结果
0:2
2:3
3:4
4:5
5:6
6:7-8
7:9-12
8:13-16
9:17-24
10:25-32
11:33-48
12:49-64
13:65-96
14:97-128
15:129-192

左边是最少需要的人数，右边是酒的总瓶数

---------------------------------------
观察上述结果，好像从6开始，最少值等于  理论的最少值+1
能否对N=8-16各举出一个例子来。
我怀疑他的程序设计有问题。

---

作者: superacid    时间: 2009-7-1 07:52:59

有问题的，他题目理解错了

---

作者: ting12377    时间: 2009-7-14 13:20:32

好难哦-.-...
数学真有趣-.-

---

作者: kf2004    时间: 2016-4-22 17:33:19

这还不简单吗?
直接摆个XYZ的三位立体坐标,
X轴上是X1,X2,X3,X4,X5,X6,X7,X8,X9,X10(每个坐标放一只老鼠)
Y轴上是Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9,Y10(每个坐标放一只老鼠)
Z轴上是Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9,Z10(每个坐标放一只老鼠).
这样一共30只老鼠
然后再在每个对应的XYZ的三位坐标上放一瓶酒,这样刚好放1000瓶酒
每只老鼠喝掉对应轴上的酒一滴,
比如X3老鼠,那么它要喝掉X3轴对应的100瓶酒每滴
比如Y6老鼠,那么它要喝掉Y6轴对应的100瓶酒每滴

毒性发作时死掉的老鼠对应的坐标位置就是毒酒的位置.

---

作者: flwb    时间: 2016-4-24 20:51:47

只需一个就行：每隔3秒喝一瓶酒中的一滴，23小时后，根据死亡时间断定是哪一瓶。

---

作者: flwb    时间: 2016-4-24 20:54:15



如果是2瓶毒酒，就需要两个，一个从1喝到1000，另一个从1000喝到1。

---

欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)

Powered by Discuz! X2