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

superacid

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

dextersa

原帖由 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

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 编辑 ]

superacid

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

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

cg372101

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

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

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

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

superacid

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