作者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