你是一个监狱长,掌管着1000个犯人,有一天你要举行一个宴会,要用1000瓶葡萄酒,但是有1瓶被下了毒,这个毒在吃了之后的10至12小时后就会发作,你至少用几个犯人来试酒在24小时之内能找出哪瓶有毒?.

10个？.

请说明理由呢。.

1000个，一人一瓶，毒死拉到，没有毒死的算运气。.

.

引用:

原帖由 老猫 于 2008-10-17 16:30 发表
1000个，一人一瓶，毒死拉到，没有毒死的算运气。

爽气！.

在可排序的请况下，是17个人吧？先每个人喝90瓶（有一个人喝70瓶），其中60瓶中各30瓶由另两个不同的人喝。可能会最多毒死两个人，剩下15人对付30瓶（或仁慈一点，对付29瓶），一个人喝三瓶，其中两瓶由另两个不同的人喝。.

不过感觉上这不是正确答案。
一般地，将1000瓶分成m堆，每堆n瓶。
先由a个人喝，每堆有不同的人喝，共有西格玛Cai 种喝法，其中i=1到a。这个西格玛>=(m-1)。
最坏的情况是a个人全死了，第二轮有b个人对付n瓶，西格玛Cbj >= n-1, j=1到b。
求a+b的最小值。
不做了。.

什么是最好的做法？
必须有个标准。

4楼的做法符合一个标准：死的人最少。
只死掉一个。

其他做法，至少死的比我的做法要多。
：）.

如果要求是最快。
应该是十个人，然后用二进制。
但是可能要死掉十个人。.

再换个思路呢。。。。
采用10*10*10三维的方法试试，后面还有奥妙哦，呵呵。。。。比你17人要少的。.

问的是“你至少用几个犯人来试酒？”
答的却是...
脑筋急转弯呀.

二进制应该是最少人的方法，但需要的时间过长啊。因为要等10-12小时，而且只给你24个小时。.

9个？.

9个？.

理由说说看呢.

如果答对了，可以谈谈，否则不好意思现丑了.

引用:

原帖由 ITmeansit 于 2008-10-18 00:07 发表
二进制应该是最少人的方法，但需要的时间过长啊。因为要等10-12小时，而且只给你24个小时。

12小时就够了。

将每瓶酒的编号转化成为二进制，由于只有1000瓶酒，所以最多只有十位数。比如35号就是0000100011。那么这瓶酒就让6号，2号和1号犯人去尝。
12小时以后，看看毒死了哪几个。把他们的编号写成二进制数，然后就知道哪瓶酒是有问题的。.

引用:

原帖由 二尔 于 2008-10-18 00:50 发表
如果答对了，可以谈谈，否则不好意思现丑了

错误的解答中，往往也包含着许多可以让大家学习的东西。

另外这个问题应该是没有标准答案的，就是看看谁做的更好。要是要严格证明是最少的，估计很麻烦。.

引用:

原帖由 老猫 于 2008-10-18 06:23 发表


12小时就够了。

将每瓶酒的编号转化成为二进制，由于只有1000瓶酒，所以最多只有十位数。比如35号就是0000100011。那么这瓶酒就让6号，2号和1号犯人去尝。
12小时以后，看看毒死了哪几个。把他们的编号写成二 ...

额

俺只要12小时内，时间少用了。

换言之可以让参与的犯人更少了。
拉出六个出来，编号1-6。喝酒！
12小时以后，死了一些。
然后没死的继续喝，再补一些人，补满五个。编号7-11。喝酒！
12小时后，又死掉几个。
写成二进制，搞定。.

编号1-6只能测试2^6=64人哦。这样分法有点问题。.

至少需要7个犯人。不过从人道主义讲，应该用4楼的方法，只用999人就可以了。.

从解决实际问题的效果看，4#的方法最好：1. 死的人最少，最多死一个，碰巧了一个不死（用999人试）。  2. 方法最简单，  3. 测试时间最短，12小时肯定见分晓.

它没说尝一口会4
还是一整瓶喝了会4.

引用:

原帖由 老猫 于 2008-10-18 06:23 发表


12小时就够了。

将每瓶酒的编号转化成为二进制，由于只有1000瓶酒，所以最多只有十位数。比如35号就是0000100011。那么这瓶酒就让6号，2号和1号犯人去尝。
12小时以后，看看毒死了哪几个。把他们的编号写成二 ...

这样的话要10个人,如果只允许试一轮,就是它了.但允许试两轮的话....

引用:

原帖由 ITmeansit 于 2008-10-17 22:01 发表
再换个思路呢。。。。
采用10*10*10三维的方法试试，后面还有奥妙哦，呵呵。。。。比你17人要少的。

这个10*10*10三维空间搞的俺头痛欲裂...
找到一个更优解,8个人,每人(或仁慈一点,先7个人喝)先喝128瓶(只喝一半!),可能一个死了,剩下7个对付128瓶.
但如老猫老师所说,似乎很难证明这是最优解?或者哪种思路可一定达到最优解?.

二进制解法应该是最优答案。（可能中毒的人最多，题目没说中毒的人一定S啊， ）.

分5轮或4轮,200瓶/250,间隔大于2小吋小于3小时(5轮),12小时内喝完,
用8人,毎批1-200/250用8位二进制编号

[ 本帖最后由 ellajl 于 2008-10-18 22:48 编辑 ].

狡猾狡猾滴! 这样的话5个人应该够了?.

我的想法和二进制有异曲同工之处，我考虑： 喝了酒有死或不死两种可能，2的10次方可以有1024种可能，所以说是10个人，但没有考虑到你给的时间可以做两次实验，所以是不是5个人就够了呢？.

晕啊~~~S 与 不S 不关俺事儿,俺路过走过.

引用:

原帖由 wushixiancn 于 2008-10-20 08:33 发表
我的想法和二进制有异曲同工之处，我考虑： 喝了酒有死或不死两种可能，2的10次方可以有1024种可能，所以说是10个人，但没有考虑到你给的时间可以做两次实验，所以是不是5个人就够了呢？

不是，五个人还是不够。
要是第一批的五个人统统挂掉，还是要补满人的。.

26楼和28楼的想法很有趣。.

谢谢!.

一次实验二进制，二次实验三进制，三次实验四进制，依次类推。
此题是3^7=2187>1000 3^6=729<1000,所以需要7个人。
通过构造一个一一映射，就可以证明充分必要性。

[ 本帖最后由 xyq2100 于 2008-10-22 12:04 编辑 ].

好像三进制不行吧。二进制是0/1表示喝和不喝，那0/1/2如何表示呢？.

是啊，俺也没看明白。.

引用:

原帖由 greenjyz 于 2008-10-18 11:53 发表

这个10*10*10三维空间搞的俺头痛欲裂...
找到一个更优解,8个人,每人(或仁慈一点,先7个人喝)先喝128瓶(只喝一半!),可能一个死了,剩下7个对付128瓶.
但如老猫老师所说,似乎很难证明这是最优解?或者哪种思路可一定达 ...

不会是三聚氰胺害的吧！.

I GOT IT，你启发了我！第一次用这5个人做500瓶实验，如果又人挂了，就已经可以按他的编号知道哪瓶有毒，如果没人死，再用这5人做剩下的500瓶的实验！所以，5  人是可以的！.

还好还好，俺不习惯喝牛奶和吃奶制品，所以幸免于害，不过现在吃东西可真是神经过敏、提心吊胆。。。
实在是您的题目太难，连方向都没有，晕乎中您再来个三维空间。。。.

我举一个9瓶葡萄酒的例子,这时候两次实验需要2个犯人
第一次实验 分为               2^2=4 (1,2,3,4)                   2^1=2 (5,6)          2^1= (7,8)                     1(9)
                                             都不喝                                 1号犯人喝           2号犯人喝                2个犯人同时2个喝
第二次实验 (1) 2个犯人都不中毒           (1,2,3,4) 中有一瓶有毒   用2个犯人可以检验出那一瓶有毒
(2) 1号犯人中毒           5,6号 中有一瓶有毒   用2号犯人可以检验出那一瓶有毒
(2) 2号犯人中毒           7,8号 中有一瓶有毒   用1号犯人可以检验出那一瓶有毒
(4) 2个犯人同时中毒           9号 瓶 有毒.

没看懂。。。500瓶的两进制数是个九位数，5个人哪够涅？
感觉上用5个人的话是这样滴。。。
先将1000瓶分成32堆，用5个人喝。
按27#的提示，不管这5个人有几个会东倒西歪，总之再逼着他们继续对付那堆让他们东倒西歪的32瓶。这样5个人够了。
但按32#的提示，最坏的情况是5个人都挂了，只能再找5个人对付32瓶，这样就要十个DM蛋了。。。.

引用:

原帖由 greenjyz 于 2008-10-22 11:48 发表
还好还好，俺不习惯喝牛奶和吃奶制品，所以幸免于害，不过现在吃东西可真是神经过敏、提心吊胆。。。
实在是您的题目太难，连方向都没有，晕乎中您再来个三维空间。。。

这题好像还可以进一步条件，一个人可以喝几瓶？一次最多是多少？否则好像是有点头晕乎乎.

这个看明白了，不过题目可是1000瓶喔？放大了111.111111.....倍哎？
反正俺的理解能力有限，头大了头大了头大了。。。。。。。.

这奥数题好深奥.

天哪！您还嫌ITmeansit折腾俺们不够啊 。。。去赶飞机了，回来再向各位大师请教。.

对不起，5人做500瓶的实验是不够的，要9人，所以，是不是9人呀.

引用:

原帖由 xyq2100 于 2008-10-22 12:04 发表
我举一个9瓶葡萄酒的例子,这时候两次实验需要2个犯人
第一次实验 分为               2^2=4 (1,2,3,4)                   2^1=2 (5,6)          2^1= (7,8)                     1(9)
                            ...

时间不够.

15人，对吧

1000=2^10
24/12=2
10/2=5
5-1=4
1+2+4+8=15

[ 本帖最后由 何球球 于 2008-10-22 19:18 编辑 ].

以IT和猫老师为首的一群谋杀嫌疑人 至少也可以判个虐囚罪.