i**i
发帖数: 1500 | 1 【 以下文字转载自 Joke 讨论区 】
发信人: pee (or no pee, it's a dilemma.), 信区: Joke
标 题: 给你们出道中学数学题
发信站: BBS 未名空间站 (Mon Jun 9 20:57:13 2014, 美东)
有10瓶酒，里面有两瓶有毒，中者必死，不中不死。
最少用几只老鼠一定可以找到毒酒？
只能用老鼠，不能用猫，不能用老毛子 etc.；
毒药慢性，所以一个老鼠只能用一次；
不能看到了一些实验结果再继续做实验。 |
i**i
发帖数: 1500 | 2 要求用6只老鼠．
前面帖子里的minsat能用上吗？ |
i**i
发帖数: 1500 | 3 brute force空间太大，不好弄．
试试看？ |
l*********s
发帖数: 5409 | |
i**i
发帖数: 1500 | 5 how?
【在 l*********s 的大作中提到】
: 3 mice
|
l******t
发帖数: 55733 | |
i**i
发帖数: 1500 | |
z*y
发帖数: 1311 | 8 6个肯定可以
把9瓶药拼成一个3X3的矩阵，然后混成六瓶药
一瓶毒药可以害死两个老鼠
如果有四只（或三只）老鼠死了，毒药在9瓶当中
否则，另一瓶毒药是第10瓶 |
i**i
发帖数: 1500 | 9 来给个详细的方案？
第一只吃： ［?, ?, ..., ?]
...
第六只吃： ［?, ?, ..., ?]
? = 1 .. 10 其中两个有毒．
【在 z*y 的大作中提到】
: 6个肯定可以
: 把9瓶药拼成一个3X3的矩阵，然后混成六瓶药
: 一瓶毒药可以害死两个老鼠
: 如果有四只（或三只）老鼠死了，毒药在9瓶当中
: 否则，另一瓶毒药是第10瓶
|
l******t
发帖数: 55733 | 10 如果是立方体加中间点，5根线就够了？
【在 z*y 的大作中提到】
: 6个肯定可以
: 把9瓶药拼成一个3X3的矩阵，然后混成六瓶药
: 一瓶毒药可以害死两个老鼠
: 如果有四只（或三只）老鼠死了，毒药在9瓶当中
: 否则，另一瓶毒药是第10瓶
|
|
|
t*********h
发帖数: 941 | 11 二进制 老题了
【在 l******t 的大作中提到】
: 思路应该是交叉混合，容我想想
|
l******t
发帖数: 55733 | |
i**i
发帖数: 1500 | 13 上答案． pls.
【在 t*********h 的大作中提到】
: 二进制 老题了
|
z*y
发帖数: 1311 | 14 5个应该也可以
平面上5条直线最多有10个交点
每个交点上放一瓶药
一只老鼠对应一条直线
两只死鼠确定交点上的毒药 |
l******t
发帖数: 55733 | 15 6个最少了。10x9/2=45种可能，需要2^6来cover。是这样？
【在 z*y 的大作中提到】
: 5个应该也可以
: 平面上5条直线最多有10个交点
: 每个交点上放一瓶药
: 一只老鼠对应一条直线
: 两只死鼠确定交点上的毒药
|
i**i
发帖数: 1500 | 16 对．
【在 l******t 的大作中提到】
: 6个最少了。10x9/2=45种可能，需要2^6来cover。是这样？
|
l******t
发帖数: 55733 | 17 是5个
【在 z*y 的大作中提到】
: 5个应该也可以
: 平面上5条直线最多有10个交点
: 每个交点上放一瓶药
: 一只老鼠对应一条直线
: 两只死鼠确定交点上的毒药
|
l******t
发帖数: 55733 | 18 5个可以，5线10点死3只
【在 i**i 的大作中提到】
: 对．
|
l******t
发帖数: 55733 | 19 5线10点不行，3个老鼠有3亇交点。还是6组按2进制每位竖排编。
【在 l******t 的大作中提到】
: 5个可以，5线10点死3只
|
t**d
发帖数: 6474 | 20 这个题出的不科学。没中毒的老鼠为什么不能再用了？ |
|
|
p**********m
发帖数: 143 | 21 某金融公司面试题。
答案把每个老鼠生死当作一个二元数。N个老鼠可测2^n瓶酒
【 以下文字转载自 Joke 讨论区 】发信人: pee (or no pee, it's a dilemma.), 信
区: Joke标
【在 i**i 的大作中提到】
: 【 以下文字转载自 Joke 讨论区 】
: 发信人: pee (or no pee, it's a dilemma.), 信区: Joke
: 标 题: 给你们出道中学数学题
: 发信站: BBS 未名空间站 (Mon Jun 9 20:57:13 2014, 美东)
: 有10瓶酒，里面有两瓶有毒，中者必死，不中不死。
: 最少用几只老鼠一定可以找到毒酒？
: 只能用老鼠，不能用猫，不能用老毛子 etc.；
: 毒药慢性，所以一个老鼠只能用一次；
: 不能看到了一些实验结果再继续做实验。
|
R***s
发帖数: 302 | 22 This has been discussed in length inside the Joke board with
no conclusion that it can be done with 6 mice.
If you think {10 bottles,2 poisonous} problem is difficult,
why not try {6 bottles,2 poisonous} problem first?
Based on the theory of "6 choose 2", there are 15 cases. So
it seems 4 mice are enough. Please try this in a brute force
fashion.
I still believe 5 mice are needed for the {6,2} problem and
9 mice are needed for the original {10, 2} problem. And the
"n choose k" method can not be used here.
Please math/programming experts, I'd like to see a conclusion
to this "middle school" problem :-)
【在 i**i 的大作中提到】
: brute force空间太大，不好弄．
: 试试看？
|
p**********m
发帖数: 143 | 23 4只老鼠的方案：
h表示喝，-表示不喝
1：hhhh
2：----
3：hhh-
4：hh-h
5：h-hh
6：-hhh
7：hh--
8：--hh
9：-h-h
10：h-h-
不管哪个瓶子有毒老鼠的死法都不一样。可以精确的知道所有瓶子的状态
hhh-
hh-h
hh--
h---- |
l******t
发帖数: 55733 | 24 45种可能编号转2进制，相同位是1的凑一组
【在 R***s 的大作中提到】
: This has been discussed in length inside the Joke board with
: no conclusion that it can be done with 6 mice.
: If you think {10 bottles,2 poisonous} problem is difficult,
: why not try {6 bottles,2 poisonous} problem first?
: Based on the theory of "6 choose 2", there are 15 cases. So
: it seems 4 mice are enough. Please try this in a brute force
: fashion.
: I still believe 5 mice are needed for the {6,2} problem and
: 9 mice are needed for the original {10, 2} problem. And the
: "n choose k" method can not be used here.
|
p**********m
发帖数: 143 | 25 SB了写错了，(10C2) = 45, 2^6 =64,所以要6个。 |
i**i
发帖数: 1500 | 26 开了个好头。继续。
【在 p**********m 的大作中提到】
: SB了写错了，(10C2) = 45, 2^6 =64,所以要6个。
|
m********5
发帖数: 17667 | 27 假设N瓶酒，其中m瓶有毒，k瓶无毒，k+m=N 找出有毒酒，需要多少老鼠？
可能组合为C(N,k)
则需要log2(C(N,k))只老鼠
序列化方式：
对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
对所有标号分析bit位，每个bit表示一只老鼠，对非零bit的老鼠给食该标号组合的酒
。直到所有C(N,k)个标号操作完毕。
结果分析：
老鼠生死作为一个bit，生为1,死为0,组合得到一个标号，该标号包含的所有酒均无毒.
则剩下的酒均有毒。
【在 i**i 的大作中提到】
: 开了个好头。继续。
|
w***g
发帖数: 5958 | 28 赞！
【在 m********5 的大作中提到】
: 假设N瓶酒，其中m瓶有毒，k瓶无毒，k+m=N 找出有毒酒，需要多少老鼠？
: 可能组合为C(N,k)
: 则需要log2(C(N,k))只老鼠
: 序列化方式：
: 对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
: 对所有标号分析bit位，每个bit表示一只老鼠，对非零bit的老鼠给食该标号组合的酒
: 。直到所有C(N,k)个标号操作完毕。
: 结果分析：
: 老鼠生死作为一个bit，生为1,死为0,组合得到一个标号，该标号包含的所有酒均无毒.
: 则剩下的酒均有毒。
|
i**i
发帖数: 1500 | 29 这么说不算。给个具体结果吧。
第i只老鼠喝[?,?,...,?]瓶酒。
【在 m********5 的大作中提到】
: 假设N瓶酒，其中m瓶有毒，k瓶无毒，k+m=N 找出有毒酒，需要多少老鼠？
: 可能组合为C(N,k)
: 则需要log2(C(N,k))只老鼠
: 序列化方式：
: 对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
: 对所有标号分析bit位，每个bit表示一只老鼠，对非零bit的老鼠给食该标号组合的酒
: 。直到所有C(N,k)个标号操作完毕。
: 结果分析：
: 老鼠生死作为一个bit，生为1,死为0,组合得到一个标号，该标号包含的所有酒均无毒.
: 则剩下的酒均有毒。
|
R***s
发帖数: 302 | 30 4只老鼠都死了，哪瓶有毒？
【在 p**********m 的大作中提到】
: 4只老鼠的方案：
: h表示喝，-表示不喝
: 1：hhhh
: 2：----
: 3：hhh-
: 4：hh-h
: 5：h-hh
: 6：-hhh
: 7：hh--
: 8：--hh
|
|
|
x******r
发帖数: 249 | 31 这个方法只适合有一瓶毒酒的情况，或者说有两瓶毒酒，但两瓶毒酒必须一起喝才能死
的情况。如果两瓶毒酒喝任何一瓶都是死就不对了。因为你没法把那10瓶酒通过互相勾
兑变成必定44种无毒，一种有毒的酒。
【在 m********5 的大作中提到】
: 假设N瓶酒，其中m瓶有毒，k瓶无毒，k+m=N 找出有毒酒，需要多少老鼠？
: 可能组合为C(N,k)
: 则需要log2(C(N,k))只老鼠
: 序列化方式：
: 对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
: 对所有标号分析bit位，每个bit表示一只老鼠，对非零bit的老鼠给食该标号组合的酒
: 。直到所有C(N,k)个标号操作完毕。
: 结果分析：
: 老鼠生死作为一个bit，生为1,死为0,组合得到一个标号，该标号包含的所有酒均无毒.
: 则剩下的酒均有毒。
|
m********5
发帖数: 17667 | 32 毒药有剂量就可以
但算剂量确实很麻烦
因此只要把组合条件改为k种酒无毒，找组合中没有任何一种酒有毒就对了
N=10,k=8,m=2
log2(C(10,8))=5.4
共需要6只
由于C(N,k)=C(N,m)所以结论是一样的，只是具体序列化步骤不同，多谢提醒。
【在 x******r 的大作中提到】
: 这个方法只适合有一瓶毒酒的情况，或者说有两瓶毒酒，但两瓶毒酒必须一起喝才能死
: 的情况。如果两瓶毒酒喝任何一瓶都是死就不对了。因为你没法把那10瓶酒通过互相勾
: 兑变成必定44种无毒，一种有毒的酒。
|
t****t
发帖数: 6806 | 33 还是不对. 关键是酒有毒是一个or的操作. 当然有一个唯一的8瓶酒组合是无毒的, 但是
从45个组合里你怎么才能找到这个组合(试6次)?
【在 m********5 的大作中提到】
: 毒药有剂量就可以
: 但算剂量确实很麻烦
: 因此只要把组合条件改为k种酒无毒，找组合中没有任何一种酒有毒就对了
: N=10,k=8,m=2
: log2(C(10,8))=5.4
: 共需要6只
: 由于C(N,k)=C(N,m)所以结论是一样的，只是具体序列化步骤不同，多谢提醒。
|
m********5
发帖数: 17667 | 34 请看我最上面的序列化操作
看不懂的话，我周末写个程序出来你就明白了
但是
【在 t****t 的大作中提到】
: 还是不对. 关键是酒有毒是一个or的操作. 当然有一个唯一的8瓶酒组合是无毒的, 但是
: 从45个组合里你怎么才能找到这个组合(试6次)?
|
t****t
发帖数: 6806 | 35 楼上有人问{6,2}的解, 你写个试试就知道了. 好好想想.
事实上找工版上有人已经贴了解析解, 不过我还没看懂.
【在 m********5 的大作中提到】
: 请看我最上面的序列化操作
: 看不懂的话，我周末写个程序出来你就明白了
:
: 但是
|
m********5
发帖数: 17667 | 36 不行啊，假设3和4瓶有毒
你得到是4只老鼠全挂了
假设1瓶和任何其他一瓶有毒，你还是4只老鼠都挂了
【在 p**********m 的大作中提到】
: 4只老鼠的方案：
: h表示喝，-表示不喝
: 1：hhhh
: 2：----
: 3：hhh-
: 4：hh-h
: 5：h-hh
: 6：-hhh
: 7：hh--
: 8：--hh
|
m********5
发帖数: 17667 | 37 你说得对，看来这东西没我一眼望去那么简单，值得想一想，虽然唯一组合无毒，但是
一混合喂，全挂了。
但是
【在 t****t 的大作中提到】
: 还是不对. 关键是酒有毒是一个or的操作. 当然有一个唯一的8瓶酒组合是无毒的, 但是
: 从45个组合里你怎么才能找到这个组合(试6次)?
|
m********5
发帖数: 17667 | 38 这个解只是上下界，而且上下差比较远，对于太小的N, N<24没有指导意义。
【在 t****t 的大作中提到】
: 楼上有人问{6,2}的解, 你写个试试就知道了. 好好想想.
: 事实上找工版上有人已经贴了解析解, 不过我还没看懂.
|
l******t
发帖数: 55733 | 39 最后一步错了。这个标号要回到那45组合，那个组合的每一个都是8个0，2个1
毒.
【在 m********5 的大作中提到】
: 假设N瓶酒，其中m瓶有毒，k瓶无毒，k+m=N 找出有毒酒，需要多少老鼠？
: 可能组合为C(N,k)
: 则需要log2(C(N,k))只老鼠
: 序列化方式：
: 对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
: 对所有标号分析bit位，每个bit表示一只老鼠，对非零bit的老鼠给食该标号组合的酒
: 。直到所有C(N,k)个标号操作完毕。
: 结果分析：
: 老鼠生死作为一个bit，生为1,死为0,组合得到一个标号，该标号包含的所有酒均无毒.
: 则剩下的酒均有毒。
|
l******8
发帖数: 1691 | 40 45种组合，用6个bit就可以表示了吧，这样应该得用6只鼠。用6只应该很简单吧。
【在 i**i 的大作中提到】
: 这么说不算。给个具体结果吧。
: 第i只老鼠喝[?,?,...,?]瓶酒。
|
|
|
l******8
发帖数: 1691 | 41 这个题应该让每天杀老鼠的生物琐男来做，必有奇招！
【在 i**i 的大作中提到】
: 这么说不算。给个具体结果吧。
: 第i只老鼠喝[?,?,...,?]瓶酒。
|
i**i
发帖数: 1500 | |
w***w
发帖数: 84 | 43 六个不行 也没有太好的解释 就是分情况讨论 七个应该可以吧 |
l*********s
发帖数: 5409 | 44 you are right. 6 is the minimal.
【在 l******8 的大作中提到】
: 45种组合，用6个bit就可以表示了吧，这样应该得用6只鼠。用6只应该很简单吧。
|
t****t
发帖数: 6806 | 45 请考古...
【在 l*********s 的大作中提到】
: you are right. 6 is the minimal.
|
i**i
发帖数: 1500 | 46 七个已经在学术版有解了。
[0,1,2],
[3,5,7],
[4,5,6],
[6,7,8],
[0,3,6],
[1,4,7],
[2,5,8],
可以换个角度理解，老鼠生死的每个组合都要有对应解释，不能出现很多不能达到的情
况。比如，
方案：
第一只喝 0 1 2
第二只喝 3 4 5
第三只喝 6 7 8 9
第四只喝 0 3 6
第五只喝 1 4 7
第六只喝 2 5 8
前几只决定在哪个组（012，345，6789）
后几只就是挨着喝。
前三只肯定至少有一只死。这样就浪费了8中可能。 就搞不定
【在 w***w 的大作中提到】
: 六个不行 也没有太好的解释 就是分情况讨论 七个应该可以吧
|
w***w
发帖数: 84 | 47 好吧 那就说明六个不行吧 如果行的话 每瓶酒最多喂两个老鼠 因为剩下的需要分辨九
种情况 至少还需要四只 情形― 每瓶酒都有老鼠喝 这样毒死的老鼠数是二 三 四，
那二四各至少是十种 唯一可能是各正好是十 (喂一鼠二鼠各五瓶) 但合起来共是40 不
到45. 情形二 有瓶酒没喂鼠 这样喂一鼠的酒 和喂二鼠的酒必须喂不同的鼠 否则无法
分辨没喝的或是只给一鼠喝的 若有k 瓶酒只喂ㄧ只鼠 则要用6-k 鼠判別 9-k 瓶 并且
每瓶酒喂两只鼠 死鼠是三或四这样pattern 数不够 比如k=0时 有 35个pattern 但有
九选二=36 种可能
太繁琐了
【在 i**i 的大作中提到】
: 七个已经在学术版有解了。
: [0,1,2],
: [3,5,7],
: [4,5,6],
: [6,7,8],
: [0,3,6],
: [1,4,7],
: [2,5,8],
: 可以换个角度理解，老鼠生死的每个组合都要有对应解释，不能出现很多不能达到的情
: 况。比如，
|
i**i
发帖数: 1500 | 48 这个也行。
第一只喝 0 1 2
第二只喝 3 4 5
第三只喝 6 7 8
第四只喝 0 3 6
第五只喝 1 4 7
第六只喝 2 5 8
第七只喝 0 4 8 (这是对角线上的三个数) |
i**i
发帖数: 1500 | 49 第七只最好玩：所有横，竖没有其他值条件的组合全可以。 |
i**i
发帖数: 1500 | 50 应该是有瓶酒没喂任何老鼠。
我没看完全明白你情形二的分析，但是觉得你的分析过于简化了。
【在 w***w 的大作中提到】
: 好吧 那就说明六个不行吧 如果行的话 每瓶酒最多喂两个老鼠 因为剩下的需要分辨九
: 种情况 至少还需要四只 情形― 每瓶酒都有老鼠喝 这样毒死的老鼠数是二 三 四，
: 那二四各至少是十种 唯一可能是各正好是十 (喂一鼠二鼠各五瓶) 但合起来共是40 不
: 到45. 情形二 有瓶酒没喂鼠 这样喂一鼠的酒 和喂二鼠的酒必须喂不同的鼠 否则无法
: 分辨没喝的或是只给一鼠喝的 若有k 瓶酒只喂ㄧ只鼠 则要用6-k 鼠判別 9-k 瓶 并且
: 每瓶酒喂两只鼠 死鼠是三或四这样pattern 数不够 比如k=0时 有 35个pattern 但有
: 九选二=36 种可能
: 太繁琐了
|
|
|
w***w
发帖数: 84 | 51 假设有k瓶酒只给一只鼠喝 则这些老鼠必须各不相同 并且它们不能再喝別的酒 否则无
法分辩没鼠喝的那瓶与相应的那瓶 所以归结为 6-k 只老鼠分辩 9-k瓶酒的问题 并且
这里每瓶给两只鼠喝 不对吗?
【在 i**i 的大作中提到】
: 应该是有瓶酒没喂任何老鼠。
: 我没看完全明白你情形二的分析，但是觉得你的分析过于简化了。
|
o**o
发帖数: 3964 | 52 5个应该够了。choose(5, 2) = choose(5, 3) = 10.
实际上5个老鼠能验出三瓶毒药，只验两瓶浪费了。 |
Y**G
发帖数: 1089 | 53 正交实验。
假定把药瓶编号，用三进制表示
老鼠A0: 吃三进制各位为零的药瓶: [0, 3, 6, 9]
老鼠A1: 吃三进制各位为1的药瓶: [1, 4, 7]
老鼠A2: 吃三进制各位为2的药瓶: [2, 5, 8]
老鼠B0: 吃三进制十位为零的药瓶: [0, 1, 2, 9]
老鼠B1: 吃三进制十位为1的药瓶: [3, 4, 5]
老鼠B2: 吃三进制十位为2的药瓶: [6, 7, 8]
* A组老鼠至少死一个
* B组老鼠至少死一个
* 任何一个A组老鼠的药瓶集合和B组的任何一个老鼠的药瓶集合相交，共同元素最多两个
* 假定A组死的是A[n], B组死的是B[m], 则A[n]和B[m]相交的集合就是有毒的药瓶。
【在 i**i 的大作中提到】
: 应该是有瓶酒没喂任何老鼠。
: 我没看完全明白你情形二的分析，但是觉得你的分析过于简化了。
|
t****t
发帖数: 6806 | 54 你怎么区别0+4和1+3?
【在 Y**G 的大作中提到】
: 正交实验。
: 假定把药瓶编号，用三进制表示
: 老鼠A0: 吃三进制各位为零的药瓶: [0, 3, 6, 9]
: 老鼠A1: 吃三进制各位为1的药瓶: [1, 4, 7]
: 老鼠A2: 吃三进制各位为2的药瓶: [2, 5, 8]
: 老鼠B0: 吃三进制十位为零的药瓶: [0, 1, 2, 9]
: 老鼠B1: 吃三进制十位为1的药瓶: [3, 4, 5]
: 老鼠B2: 吃三进制十位为2的药瓶: [6, 7, 8]
: * A组老鼠至少死一个
: * B组老鼠至少死一个
|
Y**G
发帖数: 1089 | 55 笔误，该正一下。
【在 t****t 的大作中提到】
: 你怎么区别0+4和1+3?
|
Y**G
发帖数: 1089 | 56 如果A组和B组都只死一个老鼠，就很容易证明交集就是有毒的。
如果A组只死一个老鼠，而B组死两个老鼠。
那么A组中没死的老鼠对应6个或者7个瓶子(3+3 or 3 + 4)，这样B组中每个集合可以拿
掉两个元素，而B组中肯定有个死老鼠只对应三个瓶子，拿掉两个后剩下的那个肯定有
毒。
反之，如果B组只死一个老鼠而A组死两个老鼠，也是一样的道理。
如果A组和B组都死两个老鼠比较麻烦。
假定把药瓶编号，用三进制表示
老鼠A0: 吃三进制各位为零的药瓶: [0, 3, 6, 9]
老鼠A1: 吃三进制各位为1的药瓶: [1, 4, 7]
老鼠A2: 吃三进制各位为2的药瓶: [2, 5, 8]
老鼠B0: 吃三进制十位为零的药瓶: [0, 1, 2, 9]
老鼠B1: 吃三进制十位为1的药瓶: [3, 4, 5]
老鼠B2: 吃三进制十位为2的药瓶: [6, 7, 8]
【在 Y**G 的大作中提到】
: 笔误，该正一下。
|
Y**G
发帖数: 1089 | 57 的确没法区分。看来要动用第七个老鼠。
【在 t****t 的大作中提到】
: 你怎么区别0+4和1+3?
|
k********0
发帖数: 585 | |
i**i
发帖数: 1500 | 59 你解释了一种设计，结论是不灵。你如果想得到结论，你得说所有设计都不灵。
或者说，如果这个题有解，母猪都会上树，也行。
我是班门弄斧，随便瞎说。大家继续。
【在 w***w 的大作中提到】
: 假设有k瓶酒只给一只鼠喝 则这些老鼠必须各不相同 并且它们不能再喝別的酒 否则无
: 法分辩没鼠喝的那瓶与相应的那瓶 所以归结为 6-k 只老鼠分辩 9-k瓶酒的问题 并且
: 这里每瓶给两只鼠喝 不对吗?
|
w***w
发帖数: 84 | 60 我觉着写得够淸楚了 你不懂我也沒辙 move on 吧 |
|
|
i**i
发帖数: 1500 | 61 你拿七只老鼠的情况跑跑看，看看你的证明是不是扯淡？
你这种证明照样可以证明，七只老鼠也无解。
不过我已经没兴趣了。 你也move on吧。
【在 w***w 的大作中提到】
: 我觉着写得够淸楚了 你不懂我也沒辙 move on 吧
|
