Re: [問題] 染血的國慶 (懸賞P幣)

看板puzzle作者 (天使)時間13年前 (2011/02/25 09:17), 編輯推噓17(17推 0噓 46→)
留言63則, 10人參與, 最新討論串2/5 (看更多)
這一題光出題就花我蠻多時間，大約花兩小時想出題目，一小時補完細節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
→
02/25 09:20, , 1F
如果只有一瓶有問題 那麼9次是可以用於 2^10=1024瓶的...
02/25 09:20, 1F
→
02/25 09:21, , 2F
哦 我想太多= =
02/25 09:21, 2F
推
02/25 10:10, , 3F
想問一下 檢驗劑如果3天+誤差時間內沒驗出毒
02/25 10:10, 3F
→
02/25 10:11, , 4F
就不能再用了嗎? 這瓶就報銷了? 不管有沒有驗出毒?
02/25 10:11, 4F
→
02/25 10:21, , 5F
沒驗出毒 當然還可以再用囉..
02/25 10:21, 5F
→
02/25 10:21, , 6F
只有一種情況檢驗劑不能再用 就是已經驗出毒..
02/25 10:21, 6F
※ 編輯: DreamYeh 來自: 122.116.222.246 (02/25 10:28)
推
02/25 10:27, , 7F
請問"檢驗出有沒有毒"的反應時間之邊界有沒有帶等號XD
02/25 10:27, 7F
推
02/25 10:30, , 8F
喔 我白問了 時間上也不允許前3瓶再做第2次檢驗
02/25 10:30, 8F
→
02/25 10:30, , 9F
沒有...XD
02/25 10:30, 9F
→
02/25 10:31, , 10F
我補充了　你可以當最多誤差11小時59分　避免灰色地帶
02/25 10:31, 10F
推
02/25 10:47, , 11F
謝謝提示，13xxx的後三位數字解出來了..
02/25 10:47, 11F
→
02/25 11:34, , 12F
感謝樓上 基本上知道13xxx是啥離解出也只差一步了
02/25 11:34, 12F
推
02/25 11:35, , 13F
只有一瓶檢驗劑 跟有九瓶檢驗劑有什麼差別?
02/25 11:35, 13F
推
02/25 11:39, , 14F
每一瓶酒加一點檢驗劑下去 就夠了
02/25 11:39, 14F
→
02/25 11:41, , 15F
請看白色字 第五大段
02/25 11:41, 15F
→
02/25 11:41, , 16F
隨機誤差那裡.....
02/25 11:41, 16F
→
02/25 11:43, , 17F
檢驗劑要用一整瓶 才能發揮作用 請看題目
02/25 11:43, 17F
→
02/25 11:44, , 18F
檢驗劑加進酒裡哦？0.0 那就算沒毒也不能喝了吧.....
02/25 11:44, 18F
→
02/25 11:47, , 19F
"要一整瓶" 可以分瓶的話這題跟沒出一樣=3=/
02/25 11:47, 19F
推
02/25 12:03, , 20F
其實我覺得這有點像是圖論中的cicular coloring
02/25 12:03, 20F
推
02/25 17:36, , 21F
原PO舉的例題裡,若是要犧牲最少死囚,應該要找1000人來
02/25 17:36, 21F
→
02/25 17:36, , 22F
喝吧,這樣只會死一人
02/25 17:36, 22F
→
02/25 17:48, , 23F
"但國家並沒有 1000 個死囚那麼多" 題目設想到了
02/25 17:48, 23F
推
02/25 17:50, , 24F
可是我覺得如果要往犧牲最少人來想,會是10個嗎
02/25 17:50, 24F
推
02/25 18:26, , 25F
雖然沒到1000,但越多死囚去試就犧牲越少,因此只派10個不對
02/25 18:26, 25F
推
02/25 20:18, , 26F
只派10個怎會不對呢? 你要考慮最壞狀況吧
02/25 20:18, 26F
→
02/25 20:19, , 27F
最壞狀況就是 你派n個人去 n個人都喝到那瓶毒酒
02/25 20:19, 27F
→
02/25 20:20, , 28F
結果n個人都掛了
02/25 20:20, 28F
→
02/25 20:21, , 29F
這可不是機率耶 愈多人去 喝到毒酒的機率愈少!
02/25 20:21, 29F
→
02/25 21:07, , 30F
原題目情況是 不考慮這邊說的簡單解的話 只作一次試驗
02/25 21:07, 30F
推
02/26 02:02, , 31F
N個人去,每個人都喝不同瓶阿
02/26 02:02, 31F
→
02/26 02:03, , 32F
假設只有900個囚犯,那就喝1--900瓶,剩下再用他給的解法
02/26 02:03, 32F
→
02/26 02:04, , 33F
這樣這樣死的一定少於10人,雖然題目的方法也有可能只死
02/26 02:04, 33F
→
02/26 02:04, , 34F
少於10個
02/26 02:04, 34F
推
02/26 07:04, , 35F
題目的兩到敘述卡到你的解
02/26 07:04, 35F
→
02/26 07:04, , 36F
1."這毒的特性是一個月後才發作的"
02/26 07:04, 36F
→
02/26 07:05, , 37F
2. "國王原本打算一個月又一天後招待鄰國國王時用上"
02/26 07:05, 37F
→
02/26 07:07, , 38F
900個囚犯喝1--900瓶 如果毒不在這900瓶裡
02/26 07:07, 38F
→
02/26 07:07, , 39F
你根本沒機會做第2次測試
02/26 07:07, 39F
推
02/26 07:12, , 40F
另外 題目的方法不是"有可能"只死少於10個
02/26 07:12, 40F
→
02/26 07:13, , 41F
而是一定少於10個 最多9個,因為1111111111=1023>1000
02/26 07:13, 41F
→
02/26 16:39, , 42F
最壞狀況就是 你派n個人去 n個人都喝到那瓶毒酒 <-有問題
02/26 16:39, 42F
→
02/26 16:40, , 43F
如果有一千人 就最多只會有一個喝到毒酒 最多犧牲一人
02/26 16:40, 43F
→
02/26 16:42, , 44F
這樣就比有十個人 最多犧牲九人 還要來的好
02/26 16:42, 44F
→
02/26 16:43, , 45F
所以就像kohttp說的 越多死囚 你最壞情況犧牲數就越少
02/26 16:43, 45F
→
02/26 21:24, , 46F
那是死囚有1000人以上的情形 文中說死囚並沒有1000人
02/26 21:24, 46F
→
02/26 21:29, , 47F
越多死囚 你最壞情況犧牲數就越少? <--策略是什麼?
02/26 21:29, 47F
→
02/26 21:32, , 48F
我今天給你100個死囚好了 你能找出死少於9個死囚的
02/26 21:32, 48F
→
02/26 21:34, , 49F
策略嗎? 不能的話 何來的死囚越多, 犧牲愈少?
02/26 21:34, 49F
→
02/26 21:34, , 50F
400個死囚 好了! 你覺得有何策略?
02/26 21:34, 50F
推
02/26 21:51, , 51F
也是用類似方法 只要給我56個死囚 就能最多死7個
02/26 21:51, 51F
→
02/26 21:52, , 52F
有七個死囚 最壞情況死七個人 從128瓶找出一瓶有毒的酒
02/26 21:52, 52F
→
02/26 21:54, , 53F
因此56個死囚分8組 每組7人 1024瓶酒也分成8組 每組128酒
02/26 21:54, 53F
→
02/26 21:54, , 54F
一組死囚測一組酒 因為毒酒一定在其中一組
02/26 21:54, 54F
→
02/26 21:55, , 55F
因此56個死囚 最多死七個人 就能從1024瓶酒找出毒酒
02/26 21:55, 55F
→
02/26 22:05, , 56F
阿..抱歉 上述數字128改成127 1024改成1016
02/26 22:05, 56F
推
02/27 18:01, , 57F
如果有900個囚犯,編號1號到900號,酒也這樣編號
02/27 18:01, 57F
→
02/27 18:02, , 58F
先讓1~893的犯人去喝跟其編號相符的酒
02/27 18:02, 58F
→
02/27 18:03, , 59F
剩下107瓶酒,如同題目的講解,只要7個人就可以試出了
02/27 18:03, 59F
→
02/27 18:04, , 60F
最壞情況,前893人沒事,之後7人全死
02/27 18:04, 60F
→
02/27 18:04, , 61F
原本的最壞情況,10個人全死
02/27 18:04, 61F
推
02/27 18:07, , 62F
但致這樣的解法對囚犯少於490(大概的數字)就沒用
02/27 18:07, 62F
→
02/27 18:08, , 63F
因為前面的人照順序喝完之後,剩下的酒還是要10個人來喝
02/27 18:08, 63F
‣ 更多 DreamYeh 的文章
文章代碼(AID): #1DPmCJjK (puzzle)
‣ 更多 DreamYeh 的文章
文章代碼(AID): #1DPmCJjK (puzzle)