毒酒问题(加强版)

bolizhou

1000转化为二进制“11 1110 1000”，给1000坛酒用二进制编号，假如有20人，前10人中，第1人只喝二进制中编号第一位为1的那坛，第2个人只喝二进制中编号第二位为1的那坛......后10人中，第1人只喝二进制中编号第一位为0的那坛，第2个人只喝二进制中编号第二位为0的那坛......然后是否可以确定这两坛有毒的酒呢？

bolizhou

哦，这种方法不行，确定1坛有毒还可以，10人就够，确定2坛不行。

tannis_jin

http://bbs.emath.ac.cn/viewthrea ... amp;page=7#pid19609里的方法可以，不过不是我说的方案。
设正方形变长为a
对角线需要：
若a=2k，则需k人。
若a=2k+1，则需k人。（k>1）
举个例子：
a=7
0123321
1012332
2101233
3210123
3321012
2332101
1233210
在这个方案的基础上，继续优化。

mathe

如果按照上面的方案,那么使用32*32的正方形.
利用计算机搜索出12个人识别33坛酒的方案(其中有一坛酒没有任何人喝)
也就是12人可以识别32坛包含1到2坛毒酒的情况
        0C4
        10A
        110
        181
        231
        254
        28A
        2C1
        30C
        322
        428
        485
        4C2
        521
        540
        600
        000
        003
        00D
        016
        024
        038
        048
        062
        098
        819
        852
        882
        920
        941
        A10
        C04
        C0A
于是两组边共24人可以了.而对角线tannis_jin分成了16种情况,而这个可以用9个人识别(余下4个人总可以找到两个人分在不同组),也就是这个方案也可以达到33人了.

tannis_jin

将之前的平面方案推广到立体：
列成10×10×10的方阵。
行，列，高各派8人（应该能更少）
10人确定对角线。（也应该能再少点）

这样，至多需要34人。
维数再高点的话，效果好像不明显。

数学星空

对于n=6,可以识别8坛酒
     00
        03
        0C
        15
        1A
        26
        29
        30
按照mathe的解释:设第N坛酒用A(N)表示,第M个人喝用B(M)表示
即第一坛酒A(1):  无人喝
          A(2): B(5),B(6)
               A(3):B(3),B(4)
               A(4): B(2),B(4),B(6)
               A(5): B(2),B(3),B(4)
               A(6): B(1),B(3),B(4)
               A(7): B(1),B(3),B(6)
               A(8): B(1),B(2)
        若设A(2),A(3)有毒,则第3,4,5,6个囚犯被毒死
      但:  A(3):B(3),B(4)
               A(4): B(2),B(4),B(6)
               A(5): B(2),B(3),B(4)
               A(6): B(1),B(3),B(4)  
        并不能唯一确定是A(2),A(3)有毒啊,A(4),A(5)也可以有毒哟

mathe

如果是A(4),A(5)有毒,那么死亡组合应该是{2,3,4,6}而不是{3,4,5,6}
其实从第2个囚犯没有死就可以淘汰A(4),A(5)

数学星空

懂了,呵呵,多谢解答....

本因坊算帐

非常好的题目啊~~  看上去似乎很简单，但如果要彻底解决却很困难

我思考了一下，有一些思路和猜想，不过都还没严格的论证过（应该很繁琐），写出来和大家讨论一下。也是不知道是否有人已经有类似结论了，怕前面七八页看下来，万一漏看了啥的

题目稍稍改变一下：设N桶酒，毒酒不超过两桶。至少需要f（N）个罪犯试喝，可以保证甄别出至少 N-2桶的好酒。其它条件不变

我的猜想是：

记 g（N） = 2*根号2 * （log2（N） - 1 ）

猜想1： 对于充分大的N，f（N） 不小于 g（N）

猜想2： 当N趋于无穷的时候， f（N）和g（N）之比趋于1

如果猜想1和猜想2都成立的话，那么某种意义上说，g（N）是f（N）的一个比较好的估计。当然，要对每个具体的N，给出f（N）的精确值，估计就很难有统一的公式了，得靠计算机验证一些边缘情形

先简单说一下我的思路吧，如果有空，争取最近几天把论证补上来。我的思路是，对于 M桶酒，N个罪犯，每人喝其中的 M*根号2/2 桶。把M桶酒看做概率空间，N个罪犯看做N个事件，某桶酒被某罪犯喝了，就表示这桶酒属于该罪犯对应的事件。令N个事件（罪犯）尽量不相关，（由于M有限，要想彻底不相关是不可能的，但利用一些有关正交系的结果，可以做到准不相关），这样，从概率上看，对任一桶酒，它不属于的所有事件的并，将包含至少 M-2 个元素。
以上只是个粗浅的思路，写出来抛砖引玉罢了~~  当然，也可能是错的……

本因坊算帐

7# 给出了一个递推式： f(3a^2+3a+1) 不超过 6a+3

稍微改进一下，有： f(3a^2+3a+1)不超过 3f(2a+1)

我想了一下，把这个式子又改进了一下，成为：  f( (2a+1)^2 ) 不超过 3f(2a+1)

思路是，用坐标(i,j)来表示 (2a+1)^2 桶酒，其中i,j=0，1，……，2a

给出所有(i,j)的三种不同的划分方式，每个方式都将所有的(i,j)等分为 2a+1 份
方式1） 按i划分
方式2） 按j划分
方式3） 按 i+j 对2a+1取模划分
分别用 f(2a+1) 个囚徒，可以验证出毒酒按照每种方式属于哪个或哪两个划分类。
假设用了 3f(2a+1) 个囚徒试验之后，确定的毒酒范围为：

i = a 或 b
j = c 或 d
i+j = e 或 f  (mod 2a+1)

容易看出，如果此时毒酒范围尚大于2桶，必有：
毒酒为 (a,c) (b,d) 或者 (a,d) (b,c)

另外，显然 a+c 和 a+d 关于 2a+1 不同余，所以有
a+c = e mod 2a+1   a+d = f mod 2a+1
或者 a+c = e mod 2a+1   a+d = f mod 2a+1
同理，对于b+c 和 b+d 也有类似结论
但 a+c 和 b+c 关于 2a+1 也不可能同余，故必有：

a+c = b+d mod 2a+1
a+d = b+c mod 2a+1
相加得  2a = 2b mod 2a+1， 推出 a=b mod 2a+1，矛盾
证毕

不过这个递推式，也不是精确的……  我猜想精确的递推式应该是 f(n^2) = 2f(n) + o(n)