作者DreamYeh (天使)
看板puzzle
标题Re: [问题] 染血的国庆 (悬赏P币)
时间Fri Feb 25 09:17:03 2011
这一题光出题就花我蛮多时间，大约花两小时想出题目，一小时补完细节XD
很希望这个原创题能增加puzzle板生意，引起大家讨论
因此特回一篇说明一下各细节XD
※ 引述《DreamYeh (天使)》之铭言：
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 为着建国百年的国庆日晚宴，你已经筹备很久，为了这一天，你特别订做
: 了 13000瓶窖藏高梁，据说这些美酒，都是超过几十年的佳酿，这个世界
: 再也找不到第二批替代品。
这一段强调「再也找不到第二批替代品」是要避免有人回答再找一样的来补充就好XD|||
13000这个数字当然不是乱掰出来的，事实上如果方法正确，最多可以从13xxx瓶
当中找出唯一那瓶有毒的酒
但13xxx这数字本身就带着解法暗示，因此我将之取13000整数
: 只见一狡诈小人被押上来，你厉声问：「你来自哪！」「青海的草原～」
: 「你来这做了些什麽！」「一眼望不完～」
: 「更！」你大骂：「老梗了啦！不招是吧？来人～好好招待客人一下！让
: 他吃吃毒奶粉、美国牛，然後招待他看电影－刺陵跟靠岸轮流播！」
: 「别这样！我全招就是了！」小贼丧胆地说：「我是敌对酒厂，奉命来破
我在写时候，招供过程本来写得更搞笑，不过不是题目原意，这边就删掉很多了XD
: 「如果误吃了这种毒药会怎麽样？」
: 一个月後就会疯狂发情！而且药让人精神错乱，会专找如花、许Ｘ美之
: 类.....！」
这边强调一个月後才发作，就是要避开加入人体实验的可能性
: 只有一种检验剂可以验出毒药，只需要一滴酒就可以检验出有没有毒药。
: 但是检验剂需要花上一整瓶才行。更糟糕的是，将检验剂跟酒结合後，需
: 要三天（72小时）时间才能验出，而且前後还可能有<12小时随机误差！
这边叙述麻烦的「随机误差」是非加不可的
如果是很准确地出现反应结果，这类题型一直有个作弊解法就是：
「将酒编号後，每一秒顺序滴定，一定时间後开始看哪一秒有反应」
: 今天是10月4日，你必须要等到10月5日凌晨0点才能拿到头三瓶检验药剂，
: 但是10/10中午12:00就要宴客了！你只剩下五天！
这边强调时间就是要让定义更明确，大概时程表定义如下：
10/05 00:00 拿到前三瓶检验剂
10/06 00:00 拿到第四～第六瓶检验剂
10/07 00:00 拿到第七～第九瓶检验剂
10/07 12:00後~10/08 12:00前 前三瓶检验剂结果出现
10/09 12:00後~10/10 12:00前 第七～第九瓶检验剂检验结果出现
这边的巧思就是要让你「刚好」在筵席开始一瞬间确定结果
这边强调一下误差是<12小时的，你可以想像是
最多11小时59分50秒之类
因此不用担心12:00时候才出现结果
当然你混合药剂所需的时间这边是不予以考虑的
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 提示：
: 1.本题极度困难，第一个给出详解者将给予1000批币作为奖励
: 2.本题描述看似复杂，其实很多细节仅是避免简单解出现罢了
: 3.认为本题无解者，建议可从相似题目做起
这一题的原型可看这里：
http://blog.xuite.net/dreamyeh/blog/43029055
对於板上朋友来说，应该是个老梗题目（极建议没看过解答的自己先想出这题解答）
不过两题的难易度差异极大
"似乎"可以简单证明本题「无解」
最多只有九瓶检验剂能发挥作用，而九瓶检验剂只能做出2^9个结果
但13000>>2^9=512
因此本题无解!!!?????
不过我一直很喜欢益智题目一个地方在於
「看起来无解了，但事实上解答就在其中！」
因此希望大家能享受一下这一题的乐趣:pp
（悬赏部分当然没问题，你敢提我敢给XD，希望更多人来讨论）
--
— 请多指教喔!!
／＼●／＼ ))
(( ／ /▲\ ＼
\\ My Blog:
http://dreamyeh.pixnet.net/blog
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.222.246
1F：→ puzzlez:如果只有一瓶有问题 那麽9次是可以用於 2^10=1024瓶的... 02/25 09:20
2F：→ puzzlez:哦 我想太多= = 02/25 09:21
3F：推 eagleofsouth:想问一下 检验剂如果3天+误差时间内没验出毒 02/25 10:10
4F：→ eagleofsouth:就不能再用了吗? 这瓶就报销了? 不管有没有验出毒? 02/25 10:11
5F：→ DreamYeh:没验出毒 当然还可以再用罗.. 02/25 10:21
6F：→ DreamYeh:只有一种情况检验剂不能再用 就是已经验出毒.. 02/25 10:21
※ 编辑: DreamYeh 来自: 122.116.222.246 (02/25 10:28)
7F：推 arthurduh1:请问"检验出有没有毒"的反应时间之边界有没有带等号XD 02/25 10:27
8F：推 eagleofsouth:喔 我白问了 时间上也不允许前3瓶再做第2次检验 02/25 10:30
9F：→ DreamYeh:没有...XD 02/25 10:30
10F：→ DreamYeh:我补充了 你可以当最多误差11小时59分 避免灰色地带 02/25 10:31
11F：推 turing:谢谢提示，13xxx的後三位数字解出来了.. 02/25 10:47
12F：→ DreamYeh:感谢楼上 基本上知道13xxx是啥离解出也只差一步了 02/25 11:34
13F：推 x12345x:只有一瓶检验剂 跟有九瓶检验剂有什麽差别? 02/25 11:35
14F：推 x12345x:每一瓶酒加一点检验剂下去 就够了 02/25 11:39
15F：→ puzzlez:请看白色字 第五大段 02/25 11:41
16F：→ puzzlez:随机误差那里..... 02/25 11:41
17F：→ eagleofsouth:检验剂要用一整瓶 才能发挥作用 请看题目 02/25 11:43
18F：→ puzzlez:检验剂加进酒里哦？0.0 那就算没毒也不能喝了吧..... 02/25 11:44
19F：→ DreamYeh:"要一整瓶" 可以分瓶的话这题跟没出一样=3=/ 02/25 11:47
20F：推 walkwall:其实我觉得这有点像是图论中的cicular coloring 02/25 12:03
21F：推 nobrother:原PO举的例题里,若是要牺牲最少死囚,应该要找1000人来 02/25 17:36
22F：→ nobrother:喝吧,这样只会死一人 02/25 17:36
23F：→ eagleofsouth:"但国家并没有 1000 个死囚那麽多" 题目设想到了 02/25 17:48
24F：推 nobrother:可是我觉得如果要往牺牲最少人来想,会是10个吗 02/25 17:50
25F：推 kohttp:虽然没到1000,但越多死囚去试就牺牲越少,因此只派10个不对 02/25 18:26
26F：推 eagleofsouth:只派10个怎会不对呢? 你要考虑最坏状况吧 02/25 20:18
27F：→ eagleofsouth:最坏状况就是 你派n个人去 n个人都喝到那瓶毒酒 02/25 20:19
28F：→ eagleofsouth:结果n个人都挂了 02/25 20:20
29F：→ eagleofsouth:这可不是机率耶 愈多人去 喝到毒酒的机率愈少! 02/25 20:21
30F：→ DreamYeh:原题目情况是 不考虑这边说的简单解的话 只作一次试验 02/25 21:07
31F：推 nobrother:N个人去,每个人都喝不同瓶阿 02/26 02:02
32F：→ nobrother:假设只有900个囚犯,那就喝1--900瓶,剩下再用他给的解法 02/26 02:03
33F：→ nobrother:这样这样死的一定少於10人,虽然题目的方法也有可能只死 02/26 02:04
34F：→ nobrother:少於10个 02/26 02:04
35F：推 eagleofsouth:题目的两到叙述卡到你的解 02/26 07:04
36F：→ eagleofsouth:1."这毒的特性是一个月後才发作的" 02/26 07:04
37F：→ eagleofsouth:2. "国王原本打算一个月又一天後招待邻国国王时用上" 02/26 07:05
38F：→ eagleofsouth:900个囚犯喝1--900瓶 如果毒不在这900瓶里 02/26 07:07
39F：→ eagleofsouth:你根本没机会做第2次测试 02/26 07:07
40F：推 eagleofsouth:另外 题目的方法不是"有可能"只死少於10个 02/26 07:12
41F：→ eagleofsouth:而是一定少於10个 最多9个,因为1111111111=1023>1000 02/26 07:13
42F：→ ACGfans:最坏状况就是 你派n个人去 n个人都喝到那瓶毒酒 <-有问题 02/26 16:39
43F：→ ACGfans:如果有一千人 就最多只会有一个喝到毒酒 最多牺牲一人 02/26 16:40
44F：→ ACGfans:这样就比有十个人 最多牺牲九人 还要来的好 02/26 16:42
45F：→ ACGfans:所以就像kohttp说的 越多死囚 你最坏情况牺牲数就越少 02/26 16:43
46F：→ eagleofsouth:那是死囚有1000人以上的情形 文中说死囚并没有1000人 02/26 21:24
47F：→ eagleofsouth:越多死囚 你最坏情况牺牲数就越少? <--策略是什麽? 02/26 21:29
48F：→ eagleofsouth:我今天给你100个死囚好了 你能找出死少於9个死囚的 02/26 21:32
49F：→ eagleofsouth:策略吗? 不能的话 何来的死囚越多, 牺牲愈少? 02/26 21:34
50F：→ eagleofsouth:400个死囚 好了! 你觉得有何策略? 02/26 21:34
51F：推 ACGfans:也是用类似方法 只要给我56个死囚 就能最多死7个 02/26 21:51
52F：→ ACGfans:有七个死囚 最坏情况死七个人 从128瓶找出一瓶有毒的酒 02/26 21:52
53F：→ ACGfans:因此56个死囚分8组 每组7人 1024瓶酒也分成8组 每组128酒 02/26 21:54
54F：→ ACGfans:一组死囚测一组酒 因为毒酒一定在其中一组 02/26 21:54
55F：→ ACGfans:因此56个死囚 最多死七个人 就能从1024瓶酒找出毒酒 02/26 21:55
56F：→ ACGfans:阿..抱歉 上述数字128改成127 1024改成1016 02/26 22:05
57F：推 nobrother:如果有900个囚犯,编号1号到900号,酒也这样编号 02/27 18:01
58F：→ nobrother:先让1~893的犯人去喝跟其编号相符的酒 02/27 18:02
59F：→ nobrother:剩下107瓶酒,如同题目的讲解,只要7个人就可以试出了 02/27 18:03
60F：→ nobrother:最坏情况,前893人没事,之後7人全死 02/27 18:04
61F：→ nobrother:原本的最坏情况,10个人全死 02/27 18:04
62F：推 nobrother:但致这样的解法对囚犯少於490(大概的数字)就没用 02/27 18:07
63F：→ nobrother:因为前面的人照顺序喝完之後,剩下的酒还是要10个人来喝 02/27 18:08