旺旺网 - Powered by Discuz! Board

标题: [数学] 巧妙的题目 [打印本页]

作者: ITmeansit 时间: 2008-10-17 11:07 标题: 巧妙的题目

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

作者: wushixiancn 时间: 2008-10-17 14:59

10个？.

作者: ITmeansit 时间: 2008-10-17 15:46 标题: 回复 2#wushixiancn 的帖子

请说明理由呢。.

作者: 老猫 时间: 2008-10-17 16:30

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

作者: ITmeansit 时间: 2008-10-17 17:21 标题: 回复 4#老猫的帖子

作者: greenjyz 时间: 2008-10-17 17:49

引用:

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

爽气！.

作者: greenjyz 时间: 2008-10-17 18:30 标题: 回复 1#ITmeansit 的帖子

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

作者: greenjyz 时间: 2008-10-17 18:40

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

作者: 老猫 时间: 2008-10-17 21:44

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

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

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

作者: 老猫 时间: 2008-10-17 21:45

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

作者: ITmeansit 时间: 2008-10-17 22:01 标题: 回复 8#greenjyz 的帖子

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

作者: echooooo 时间: 2008-10-17 23:32

问的是“你至少用几个犯人来试酒？”
答的却是...

脑筋急转弯呀

作者: ITmeansit 时间: 2008-10-18 00:07 标题: 回复 10#老猫的帖子

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

作者: 二尔 时间: 2008-10-18 00:43 标题: 回复 13#ITmeansit 的帖子

9个？.

作者: 二尔 时间: 2008-10-18 00:44 标题: 回复 13#ITmeansit 的帖子

9个？.

作者: ITmeansit 时间: 2008-10-18 00:46 标题: 回复 15#二尔的帖子

理由说说看呢.

作者: 二尔 时间: 2008-10-18 00:50

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

作者: 老猫 时间: 2008-10-18 06:23

引用:

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

12小时就够了。

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

作者: 老猫 时间: 2008-10-18 06:26

引用:

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

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

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

作者: 老猫 时间: 2008-10-18 06:29

引用:

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

12小时就够了。

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

额

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

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

作者: ITmeansit 时间: 2008-10-18 08:43 标题: 回复 20#老猫的帖子

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

作者: xyq2100 时间: 2008-10-18 08:56

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

作者: 水淼淼 时间: 2008-10-18 10:17

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

作者: 小猫妹妹 时间: 2008-10-18 10:37 标题: 题目还是有缺陷

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

作者: greenjyz 时间: 2008-10-18 11:26

引用:

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

12小时就够了。

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

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

作者: greenjyz 时间: 2008-10-18 11:53

引用:

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

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

作者: ITmeansit 时间: 2008-10-18 17:25 标题: 回复 26#greenjyz 的帖子

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

）.

作者: ellajl 时间: 2008-10-18 17:30

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

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

作者: greenjyz 时间: 2008-10-18 17:37

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

作者: wushixiancn 时间: 2008-10-20 08:33

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

作者: wusola 时间: 2008-10-21 20:29

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

作者: 老猫 时间: 2008-10-21 22:48

引用:

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

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

作者: 老猫 时间: 2008-10-21 22:52

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

作者: greenjyz 时间: 2008-10-21 23:16 标题: 回复 33#老猫的帖子

谢谢!.

作者: xyq2100 时间: 2008-10-22 11:05

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

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

作者: ITmeansit 时间: 2008-10-22 11:15 标题: 回复 35#xyq2100 的帖子

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

作者: greenjyz 时间: 2008-10-22 11:29 标题: 回复 36#ITmeansit 的帖子

是啊，俺也没看明白。.

作者: GerryBB 时间: 2008-10-22 11:33

引用:

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

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

不会是三聚氰胺害的吧！

作者: wushixiancn 时间: 2008-10-22 11:46 标题: 回复 32#老猫的帖子

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

作者: greenjyz 时间: 2008-10-22 11:48 标题: 回复 38#GerryBB 的帖子

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

作者: 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)
                                          都不喝                               1号犯人喝          2号犯人喝             2个犯人同时2个喝
第二次实验 (1) 2个犯人都不中毒          (1,2,3,4) 中有一瓶有毒用2个犯人可以检验出那一瓶有毒
(2) 1号犯人中毒          5,6号中有一瓶有毒用2号犯人可以检验出那一瓶有毒
(2) 2号犯人中毒          7,8号中有一瓶有毒用1号犯人可以检验出那一瓶有毒
(4) 2个犯人同时中毒          9号瓶有毒.

作者: greenjyz 时间: 2008-10-22 12:11 标题: 回复 39#wushixiancn 的帖子

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

作者: GerryBB 时间: 2008-10-22 12:13

引用:

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

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

作者: greenjyz 时间: 2008-10-22 12:18 标题: 回复 41#xyq2100 的帖子

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

作者: 未来奶爸 时间: 2008-10-22 12:19

这奥数题好深奥

作者: greenjyz 时间: 2008-10-22 12:24 标题: 回复 43#GerryBB 的帖子

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

作者: wushixiancn 时间: 2008-10-22 13:12

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

作者: 猴子称大王 时间: 2008-10-22 13:44

引用:

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

时间不够.

作者: 何球球 时间: 2008-10-22 16:37

15人，对吧

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

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

作者: shumi1 时间: 2008-10-23 08:40 标题: 楼上各位

以IT和猫老师为首的一群谋杀嫌疑人

至少也可以判个虐囚罪

作者: 猴子称大王 时间: 2008-10-23 09:03

说句公道话。

it虐囚。老猫设法死人尽量的少。.

作者: wushixiancn 时间: 2008-10-23 09:16

我还有一个发现，犯人是可以重复利用的，因为他说10-12个小时发作，又给了你24小时，所以还可以考虑他是什么时候死的，让我再想想
不管怎么样，我们都会折磨死这些犯人的！！！.

作者: wushixiancn 时间: 2008-10-23 09:21

不对，请问LZ如果我让他重复喝毒酒，药效会不会叠加而影响我的判断？.

作者: ITmeansit 时间: 2008-10-23 09:27

引用:

原帖由 shumi1 于 2008-10-23 08:40 发表 $\"\"$
以IT和猫老师为首的一群谋杀嫌疑人至少也可以判个虐囚罪

呵呵，前面说过了，题目没说中毒的人一定S啊！！何来谋杀？.

作者: ITmeansit 时间: 2008-10-23 09:29 标题: 回复 53#wushixiancn 的帖子

12小时发作了，接着试就试不出是中毒还是不中毒了啊！.

作者: shumi1 时间: 2008-10-23 09:39 标题: 回复 4#老猫的帖子

1人1瓶全喝完了，拿什么开宴会？

猫老师有酒窖，难道想垄断酒的生意？

作者: shumi1 时间: 2008-10-23 09:41 标题: 回复 54#ITmeansit 的帖子

一级谋杀罪不成立，二级谋杀罪估计逃不了

作者: xyq2100 时间: 2008-10-23 10:58 标题: 回复 36#ITmeansit 的帖子

0表示不喝，1表示第一次试验喝，2表示第二次试验喝，
例如3瓶葡萄酒编号 0，1，2 有1个犯人
第一次试验犯人喝1号葡萄酒
如果中毒  1号葡萄酒有毒
如果不中毒  进行第二次试验犯人喝2号葡萄酒
如果中毒  2号葡萄酒有毒
如果不中毒 0号葡萄酒有毒

例如9瓶葡萄酒编号 00，01，02 ,10，11，12,20，21，22    有2个犯人 1,2分别对应三进制编号首位，第二位
第一次试验 1号犯人喝10,11,12号葡萄酒  2号犯人喝01,11,21号葡萄酒
如果2个犯人同时中毒  11号葡萄酒有毒
如果只有1号犯人中毒 10 12号葡萄酒有毒，再用1号犯人试验可验出有毒葡萄酒
如果只有2号犯人中毒 01 21号葡萄酒有毒，再用2号犯人试验可验出有毒葡萄酒
如果都不中毒  00 02 20 22号葡萄酒有毒用2个犯人进行第二次试验可验出有毒葡萄酒

以下依次类推，41楼的方法是一样的，只不过排了序，更容易理解
基本原理3^n=(2+1)^n=2^n+n*2^(n-1)+......+n*2+1.

作者: wushixiancn 时间: 2008-10-23 12:44

引用:

原帖由 ITmeansit 于 2008-10-23 09:29 发表 $\"\"$
12小时发作了，接着试就试不出是中毒还是不中毒了啊！

不是这个意思，我是想：用7个人先试128瓶，过2个小时再让同样的人试128瓶，以次类推可以分6批试验128瓶，过了12个小时后看哪几个人是在哪个时间段发作的，可以知道是第几批的。所以，用7个人就可以了。.

作者: ITmeansit 时间: 2008-10-23 12:53 标题: 回复 59#wushixiancn 的帖子

还是需要8人。
知道哪个128中有毒，就要少一人。六人如何试128瓶呢？.

作者: wushixiancn 时间: 2008-10-23 13:03 标题: 回复 60#ITmeansit 的帖子

不用呀，我不是说了吗，用7个人测试128瓶，然后根据他们是什么时候发作的来决定是第几批的128瓶。
也许我没表达清楚：用7个人分别在第0、2、4、6、8、10小时喝，这样比如他们在第13小时发作了，那就是第二批里的，再根据他们分别哪几个发作了，确定是这第二批128瓶里的第几瓶有问题！

[ 本帖最后由 wushixiancn 于 2008-10-23 13:04 编辑 ].

作者: ITmeansit 时间: 2008-10-23 13:09 标题: 回复 61#wushixiancn 的帖子

题目是10-12小时发作，如果在第12小时整发作，算是0小时喝还是第2小时喝的呢？且7*128=896<1000啊。.

作者: wushixiancn 时间: 2008-10-23 13:19

好，输给你，我投降，需要8个人分4批测试，每批256瓶，4*256，这样时间就有宽余了，我可以在第0、3、6、9小时测试，就没有骑墙的情况了，亲爱的LZ，告诉我这下对了吧

作者: ITmeansit 时间: 2008-10-23 13:32 标题: 回复 63#wushixiancn 的帖子

作者: wushixiancn 时间: 2008-10-23 13:45

作者: yezima 时间: 2008-10-23 14:07 标题: 回复 4#老猫的帖子

那宴会还开不开啦？

作者: lichunyan 时间: 2008-10-24 08:11

我作出的答案是92人对吗?.

作者: yuhemama 时间: 2008-10-24 13:29

10个。
就是前面说的二进制原理， 1000转化为二进制为：1000=1 1 1 1 1 0 1 0 0 0共10位，那就是10个人，把酒按照0000000001－1 1 1 1 1 0 1 0 0 0的顺序排列，来喝。
刚才没看清楚跟帖，看了题目就做，呵呵，同意老猫的思路，

[ 本帖最后由 yuhemama 于 2008-10-24 13:45 编辑 ].

作者: qunfengfu 时间: 2008-10-24 16:27

按现在的处理方法是这1000瓶酒全部销毁，另外再拿1000瓶.

作者: greenjyz 时间: 2008-10-24 19:06 标题: 回复 57#shumi1 的帖子

咋地？转了一圈回来数学沙龙变谋杀现场啦？！.

作者: greenjyz 时间: 2008-10-24 19:07 标题: 回复 63#wushixiancn 的帖子

这个做法有意思喔！.

作者: yhm 时间: 2008-10-24 20:29 标题: 32人，应该对吧

第一次，每人尝31瓶，共尝了992瓶，万一所有的人没反应，那就用其中的8人尝剩下的酒，肯定一个不行，如果原来尝完时那些人有某个出问题，则找其余的31人分别品尝这人喝过的那组酒，题目就解了，希望正确哦.

作者: ITmeansit 时间: 2008-10-24 21:19

引用:

原帖由 greenjyz 于 2008-10-22 12:24 发表 $\"\"$
天哪！您还嫌ITmeansit折腾俺们不够啊。。。去赶飞机了，回来再向各位大师请教。

呵呵，刚刚解了二道难题。以后不敢发题目了。.

作者: greenjyz 时间: 2008-10-24 22:35 标题: 回复 73#ITmeansit 的帖子

别别别！您可别撂挑子！.

作者: greenjyz 时间: 2008-10-24 22:37 标题: 回复 73#ITmeansit 的帖子

别别别！您可不能撂挑子！.

欢迎光临旺旺网 (http://321ww.org/)