Re: [討論] 毒酒問題
※ 引述《andan (我從你的眼睛看出來樓~)》之銘言：
: ※ 引述《kimjay (kim)》之銘言：
: : 題目怎樣我有點忘了
: : 內容大概如下
: : 有一位皇帝要十天後要宴客
: : 有1000瓶酒
: : 其中一瓶酒是有毒的
: : 喝下去後十天後會毒發身亡
: : 請問要如何利用十位罪犯來找出這一瓶有毒的酒
: 這類問題還有好幾種變型
: 例如:
: 1. 12瓶酒其中2瓶有毒
: 2. 12瓶酒其中1瓶有毒,1瓶是解藥
: 3. 12瓶酒其中1瓶有毒,
: 罪犯裡面有一個人是郭靖喬裝(百毒不侵)
: 請問10個罪犯夠嗎?
: 有辦法同時找到毒酒,解藥,跟郭靖嗎?
要講變型題目之前 我先從原始題目開始會比較好了解
原始題目(縮小版)是這樣子的
有一位皇帝十天後要宴客，酒窖裡面有12瓶酒，
其中1瓶是毒酒，喝了之後十天會毒發身亡。
請問要利用幾名罪犯才能找出毒酒?
解答: 四名罪犯就足夠了
010101010101 --->表示第一名罪犯喝下編號 2,4,6,8,10,12的酒
001100110011 我們會一直用0-1矩陣來表示罪犯跟酒的關係
000011110000
000000001111
仔細觀察就可以知道，上面不管哪瓶酒有毒，死掉的罪犯都不會相同!
這表示我們可以從十天後死掉的罪犯，來得知哪瓶酒有毒!
例如:死的人就只有二號罪犯的話，那我們知道第3瓶酒有毒。
以下我們來看其他變型題目
變型1:
１２瓶酒之中，有２瓶毒酒。
解答：可以！
１１１１００００００００ 左邊矩陣可以觀察出
１０００００１１０１００ 1) 任意一瓶酒都有三個罪犯喝
１００００１００００１１ 2) 任意兩瓶酒最多只會同時給一個罪犯喝
００１０１１０１００００ 由此可知 如果x不是毒酒的話
０１０００００１１０１０ 至少會有一名罪犯喝了x這瓶酒
０００１０１１０１０００ 而且他又沒喝到這兩瓶毒酒
００１０００００１１０１
０１００１０１００００１ 所以，只要看沒死的人喝了哪些酒，
０００１１００００１１０ 就知道哪些酒是沒有毒的！
變型2：
１２瓶酒之中，有１瓶毒酒；１０大罪犯中，有１個是郭靖(百毒不侵)。
解答；沒辦法保證能同時找到！！
解法同上個矩陣！
如果x不是毒酒的話，至少會有兩名罪犯喝了x這瓶酒但沒死。
而如果x是毒酒的話，最多只會有一名罪犯喝了它卻沒事！
哪瓶酒喝了之後，只有一個人存活，那麼這瓶酒就是毒酒，
而這個人就是郭靖！
但是！如果那瓶酒喝了之後沒有人存活呢？！
我們就沒辦法找出郭靖了！
只能再花十天！
變型3：
１２瓶酒之中，有１瓶毒酒，１瓶解藥。
解答：沒辦法同時找出毒酒跟解藥！（罪犯夠多就可以！)
以下提供十天內單只找出解藥的辦法！
解法同上個矩陣！
（但０１代表的意思互換，也就是０代表要喝，１代表不喝）
注意變型1解答中的這段話
由此可知 如果x不是毒酒的話
至少會有一名罪犯喝了x這瓶酒
而且他又沒喝到這兩瓶毒酒
經過０１意思互換之後，可以想成如下
任意兩瓶非解藥的酒，必定有一名罪犯會
喝下這兩瓶酒，卻沒有喝到解藥。
意思就是說，即使是沒有毒的酒，也一定會有人同時
喝了它跟毒酒，卻沒有喝到解藥。
哪瓶酒喝了沒死人，就表示它是解藥！
那罪犯要多少人才可以同時找出毒酒跟解藥呢？
一個簡單的辦法就是任兩瓶酒給一名罪犯喝
沒有毒的酒恰好只會造成一名罪犯死亡！
此法需要 １２取２＝６６人
ＰＳ：目前最好的方法可以在２４人解決。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.22.206
推
05/09 05:25, , 1F
05/09 05:25, 1F
推
05/10 23:43, , 2F
05/10 23:43, 2F
推
05/26 22:17, , 3F
05/26 22:17, 3F
討論串 (同標題文章)