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

lulijie

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

lulijie

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

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)

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

lulijie

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 无法区分。

lulijie

我只是举出我的一系列方案，该方案是不是最少人的方案，我也不知道。如果有谁举出少于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号酒是毒酒的情况就无法设置一一对应关系。
    所以如果使用喝酒都不死人的状态，那么死一个人的状态对应的两毒酒就不能和喝酒都不死人的状态对应的毒酒相同。我觉得还是把喝酒都不死人的状态旷置不用的好。
       。。。。。。
    依次类推，若将所有的毒酒分布状态都对应完毕，也没出现矛盾，那么这种方案就是可行的。

lulijie

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也无法取到。

lulijie

楼上的结果
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各举出一个例子来。
我怀疑他的程序设计有问题。