[推理]100個囚犯的問題

[推理]100個囚犯的問題

J+W 於 星期五 四月 22, 2005 12:21 pm


有100個無期徒刑囚徒,被關在100個獨立的小房間,互相無法通信。每天會有一個囚徒被隨機地抽出來放風,隨機就是說可能被抽到多次。放風的地方有1盞燈,囚徒可以打開或者關上。除囚徒外,沒有別人會去動這個燈。每個人除非出來放風,是看不到這個燈的。
一天,全體囚徒大會,國王大赦,給大家一個機會:如果某一天,某個囚徒能夠明確表示,所有的囚徒都已經被放過風了,而且的確如此,那麽所有囚徒釋放;如果仍有囚徒未被放過風,那麽所有的囚徒一起處死!
囚徒大會後給大家20分鐘時間討論,囚徒們能找到方法麽?

補充:囚犯放風時不能帶任何可以做記號的工具

J+W
版 主
版 主
 
文章: 2161
註冊時間: 2003-12-30

devell 於 星期六 四月 23, 2005 11:33 pm


恩,我猜應該可以在那一盞燈上按自已的指紋吧,

這樣就可以証明誰放過風了

devell
大 師
大 師
 
文章: 303
註冊時間: 2005-03-07

車神 於 星期日 四月 24, 2005 12:26 am


好像很難@@

車神
初學者
初學者
 
文章: 34
註冊時間: 2004-08-05

bell 於 星期一 四月 25, 2005 12:54 am


請問,
囚犯放風的"一天"是指24小時嗎?

主要是想知道, 前一位和後一位囚犯是否有機會碰面?

如果沒有的話, 光靠這一盞燈的開和關....., 還是想不出來.....

 

bell
研究生
研究生
 
文章: 146
註冊時間: 2005-03-23

bell 於 星期二 四月 26, 2005 4:15 pm


想到一個方法

1.開會討論時指定一人, (就先稱為A先生)負責紀錄放風人次並消除另99人的共同記號.(關燈)

2.初次被抽到放風的囚犯, 必須做記號: "離去時將燈關上." 此人以後不需再做記號.

3.自此以後再被抽到初次放風的囚犯, 必須直到A先生消除此記號前, 也就是看到"燈是打開的", 才可以做關燈記號.

4.當A先生紀錄達99人次(加上自己), 便能夠表示自己已明確知道100位囚犯都被放風過了! 但這樣十分地曠日費時啊.......

5.如果能夠想出其他不同的記號方法, 如: 燈泡可以取下的話, 可將它作為關燈記號之後的第二項記號, 那麼就可以減少A先生計次的次數! (共50次, 最後一次燈會是關上而不是燈泡被取下), 如此每增加一項記號就可以更縮短計次的次數(33次, 25次....). 百位囚犯就能更早被釋放了.

 

bell
研究生
研究生
 
文章: 146
註冊時間: 2005-03-23

J+W 於 星期二 四月 26, 2005 11:27 pm


bell 寫到:想到一個方法

1.開會討論時指定一人, (就先稱為A先生)負責紀錄放風人次並消除另99人的共同記號.(關燈)

2.初次被抽到放風的囚犯, 必須做記號: "離去時將燈關上." 此人以後不需再做記號.

3.自此以後再被抽到初次放風的囚犯, 必須直到A先生消除此記號前, 也就是看到"燈是打開的", 才可以做關燈記號.

4.當A先生紀錄達99人次(加上自己), 便能夠表示自己已明確知道100位囚犯都被放風過了! 但這樣十分地曠日費時啊.......

5.如果能夠想出其他不同的記號方法, 如: 燈泡可以取下的話, 可將它作為關燈記號之後的第二項記號, 那麼就可以減少A先生計次的次數! (共50次, 最後一次燈會是關上而不是燈泡被取下), 如此每增加一項記號就可以更縮短計次的次數(33次, 25次....). 百位囚犯就能更早被釋放了.


這個答案就是我預設的答案!
沒想到英雄所見略同
不過有人提出更好的方式
就是確認的人不一定要是A的方式

J+W
版 主
版 主
 
文章: 2161
註冊時間: 2003-12-30

bell 於 星期三 四月 27, 2005 1:33 am


J+W 寫到:
這個答案就是我預設的答案!
沒想到英雄所見略同
不過有人提出更好的方式
就是確認的人不一定要是A的方式

耶? 真的啊? 相同的答案!!哈哈哈~~~英雄?不敢不敢...熊熊當真的變了性去~


是有想過若是由A先生以外的人來表示明確知道每個人都已放風過了的可行性. 不曉得那位提出更好方式的人, 所用的方法是什麼呢?在前面所提的這個方法為前提下, 曾這樣設想過.....

譬如, 當有兩項記號時, 那個"關燈"記號遲遲未有人再來做"取下燈泡"的記號時, 或許其他囚犯也能夠確實地表示知道了, 但又認為這樣很冒險, 因為計算人次的工作越到後頭, 時間會拉得越長.......所以, 到底是在多少人次時出現遲遲沒有人來做"取下燈泡"的記號, 這一點是很難讓除了A先生以外的人準確的知道的, 甚至於做"關燈"這個記號也是一樣, 越到後面, 燈持續地顯示在"開燈"這樣的情況的機率會越大.

另外考慮, 若有其他人看過"取下燈泡"的記號出現了49次, 而其後又注意到燈持續很長久地只出現關燈記號, 是否就能夠代表這人明確知道100人均放風過了呢?這應該是不一定, 因為他有可能在A先生尚未做"開燈"記號前, 就在這之間計算了兩或三次也不一定呢. 這都很不保險~~


請您告訴我那個更好的方式吧!! Please...Orz...
我想不出來了 

 

bell
研究生
研究生
 
文章: 146
註冊時間: 2005-03-23

J+W 於 星期三 四月 27, 2005 1:36 am


我覺得狐狸阿布的方法是目前最好的
因為它既簡單可行性又高
只不過題目特地出的"燈"這個條件
好像被他用來綁繩子了
而不是用來照明了       

http://twbbs.net.tw/412854.html

J+W
版 主
版 主
 
文章: 2161
註冊時間: 2003-12-30

bell 於 星期三 四月 27, 2005 1:48 am


原來是這樣呀!

不受題目引導地去思考也是很厲害啦~~
這樣的話, 應該會有很多種方式吧? 頭髮, 指甲, ...但這兩樣應該很容易不見就是了...

 

bell
研究生
研究生
 
文章: 146
註冊時間: 2005-03-23

devell 於 星期六 四月 30, 2005 1:55 am


看了之後 我是覺得把燈打破成100片也是很好的方法,

至少要如何打破成100片,很簡單啊,叫第一個打破燈的人數一下不就得了,他走之後只留下99片的碎片在就ok啦

devell
大 師
大 師
 
文章: 303
註冊時間: 2005-03-07

娜可兒 於 星期六 四月 30, 2005 2:46 pm


依版主的意思,這是沒有正解的,只要是沒有缺陷的方法都OK
*真正熱愛數學的人,是重質不重量的
 希望大家成為數學狂熱者,而不是積分狂熱者
 別做讓版管為了您的文而頭疼的小白!

*知識的價值 不在於你能擁有多少
 而是在於你要如何活用於生活之中
左鍵: 點擊縮放; 右鍵: 觀看原圖

娜可兒
版 主
版 主
 
文章: 765
註冊時間: 2005-03-19
來自: 侍魂-神仙之村    職業: 蝦夷族巫女        興趣: 蹓鷹

沁沁 於 星期五 三月 31, 2006 8:51 pm


可以这样吧:在进去前把灯关上,,,,,,指定一个人(称他A)计数,如果是第一次放风的就让灯亮着,二次以上的不管灯是开是关都不要动.....A只作关灯动作.A在关了100次灯以后,说明每个人都去放过风了.
呵~~~这样很费时间啊,运气不好的话,,,,,,,哈,不如死了算了

沁沁
訪客
 

JK 於 星期四 四月 13, 2006 12:08 am


你們所提出的解答好像是那100個囚犯早就知道一樣
但題目不是國王臨時宣布的嗎???

JK
訪客
 

Re: [推理]100個囚犯的問題

J+W 於 星期四 四月 13, 2006 1:08 am


J+W 寫到:有100個無期徒刑囚徒,被關在100個獨立的小房間,互相無法通信。每天會有一個囚徒被隨機地抽出來放風,隨機就是說可能被抽到多次。放風的地方有1盞燈,囚徒可以打開或者關上。除囚徒外,沒有別人會去動這個燈。每個人除非出來放風,是看不到這個燈的。
一天,全體囚徒大會,國王大赦,給大家一個機會:如果某一天,某個囚徒能夠明確表示,所有的囚徒都已經被放過風了,而且的確如此,那麽所有囚徒釋放;如果仍有囚徒未被放過風,那麽所有的囚徒一起處死!
囚徒大會後給大家20分鐘時間討論,囚徒們能找到方法麽?
補充:囚犯放風時不能帶任何可以做記號的工具


注意上面引言的紅字部份

J+W
版 主
版 主
 
文章: 2161
註冊時間: 2003-12-30

[成功] 正解 * 3

asmobia 於 星期日 二月 11, 2007 6:49 pm


好好的一個題目大家拿來腦筋急轉彎, 這裡的程度實在要加強.

 

****************************************************************

請注意, 本題解法是假設一開始燈是關著; 如果燈是亮的怎麼辦?
很簡單, 大家犧牲一天, 第一天去的人唯一要做的事就是把燈關掉, 然後當作自己沒去過; 一切從第二天開始算.



方案一: 一百人中間選一人當經理, 其他是員工; 經理點名, 員工舉手答有.

員工舉手答有就是將燈打開, 一個人只能舉手答有一次.
經理點收就是將燈關掉, 就算做點名一次了.

若是員工想要舉手答有時, 發現燈已經是亮的了; 代表之前已經有員工舉手答有, 而經理還未點收. 這時這員工只好下次再來.
經理點到九十九個員工時, 就知道人人來過了.



你只會方案一嗎? 網路上到處查的到; 這種耗費三十幾年的方法也能當解答?





方案二: 將工作分為前一百天與一百天以後.
在前一百天裡, 第一天去的人將燈打開; 之後的人就讓燈一直保持亮著, 直到有人第二次被叫過來時將燈關掉, 這人就被選為經理了.
經理是誰? 經理是最先被叫去兩次的人. 在他之前, 沒有人去過兩次( 不然那個人就關燈當經理了 ); 在他之後, 燈一直都是滅的, 直到一百天過去.

也就是說, 在前一百天裡, 燈從第一天開始亮; 直到第一次有人去過兩次時被關掉, 一直維持關著直到前一百天過完.

為什麼要一百天呢? 因為一百天"幾乎"可以擔保選出經理;
若是在第一百天時還選不出來, 就代表說前九十九天都是不同的人進去;
而在第一百天正巧第一百人被叫去, 他一去看到燈居然是亮著! 那要馬上跪地感謝上蒼因為大家立刻被釋放了.

若是在一百天之內選出經理了, 那所有人可以分為四類, 且自己知道自己是哪一類:
1. 經理本人
2. 那些第一次被叫去時, 看見燈仍是亮的人( 包括第一天開燈的人 ).
3. 那些第一次被叫去時, 看見燈已經是關的人.
4. 在前一百天從未被叫去的人.

假設經理本人在第三十天關燈, 也就是說前二十九天人人不同, 也就是說第二類人有二十八個( 經理本人不算 )
故, 此時經理已經點了二十八個人名字了( 加自己二十九 ), 第二類人再也不需要舉手答有了.

所以在一百天以後, 只有第三類與第四類的人要舉手答有.



方案二改進了很多, 但是真的不能再快嗎? 坐牢很無聊啊!!







方案三: 員工, 經理, 總經理:
一百人有九十個人當員工, 九個人作經理, 一個總經理.


而工作分為兩種階段, 第一階段叫"員工向經理報告", 第二階段叫"經理向總經理報告".
這兩階段的天數長度可以自行設定, 若有電腦模擬可以找出最佳解.
這兩階段是循環的, 也就是說階段一完了變成階段二, 階段二完了變回階段一.


在階段一, 由員工舉手答有, 經理與總經理點收. 請注意, 一個經理或總經理負責九個員工;
若是一個經理已經點到九個員工, 他的部門就滿編了, 不能再收人了.
一個員工只能舉手答有一次.


在階段二, 由"已經滿編"的經理舉手答有, 總經理點收. 一但總經理點到一名, 他就知道已經有十個人了( 九個員工與一個經理 ).
一個經理只能舉手答有一次, 答完之後不能再收新員工了( 部門滿編了 ).


也就是說, 當總經理點名點到另外九個經理時, 他就知道有 10 * 9 個人已經去過了;
同時, 若總經理自己的部門也點收到九名員工的話, 那一百人都去過了.
這種批量處理的速度絕對快過前兩個方案, 但是他有一個"繼承"的觀念不能忽略.


什麼是繼承呢?

回看上面的解法, 我們假設每一階段開始時燈是關的;
要是有一個員工在階段一舉手答有, 但是一直沒有合適的經理來點收, 這燈不就亮到第二階段了嗎? 這不全亂了嗎?

所以, 每個階段的最後一天, 去的人要負責將燈熄滅, 確保下一階段的乾淨.
將燈熄滅後, 這人就繼承了當初開燈舉手答有的人的工作; 因為只有你才知道他的舉手答有未完成.
所以你要在下次有機會時, 以他的身份幫他舉手答有一次.



"繼承"舉例:
現在是第二階段的最後一天, 我是一個尚未舉手答有過的員工; 照道理, 第二階段是經理與總經理的事, 員工根本不必去.
可是這是該階段的最後一天, 我必須去.
我一去看到燈是亮著, 表示有一個滿編的經理; 自以為已經向總經理報告過了, 可是很顯然總經理沒機會聽到.
所以我把燈關掉, 確保下一階段乾乾淨淨; 而後, 我不光是一個尚未舉手答有的員工了, 我還是一個部門滿編的經理.
在第一階段, 身為一個尚未舉手答有過的員工, 我要向一位經理報告.
到第二階段, 身為一個部門滿編的經理, 我要向總經理報告我的部門滿編.





有沒有方案四啊? 我相信是有的....


asmobia
訪客
 

[討論]還不能夠修改文章

asmobia 於 星期日 二月 11, 2007 7:21 pm


居然不能修改在訪客時留的文章?
 
好吧! 在這裡加一條.
 
 
**********************************************************
網路上有很多這題目, 都規定"囚犯們完全算不出時間, 就連三餐都不定時"
 
在這種情況下, 只有第一種笨解適用
 
 
後面的加強版都不行啦! 尤其是第三版要算時間算的很猛.
 
 
 
除此之外, 第三版不市有兩階段嗎?
合理的建議是先讓第一階段進行很長一陣子....因為沒有滿編的經理第二階段就沒有意義....
 
然後此二階段再互相輪迴. 其實, 若是機率上能算出 "未報告員工碰上未滿編經理" 與 "滿編未報告經理碰上總經理" 的機會的話, 就可以算出這兩階段時間的比例了.

asmobia
實習生
實習生
 
文章: 95
註冊時間: 2007-02-11

Re: [成功] 正解 * 3

skymen 於 星期一 二月 12, 2007 6:30 pm


asmobia 寫到:

好好的一個題目大家拿來腦筋急轉彎, 這裡的程度實在要加強.

 

****************************************************************

所以在一百天以後, 只有第三類與第四類的人要舉手答有.

方案二改進了很多, 但是真的不能再快嗎? 坐牢很無聊啊!!

說別人程度要加強,我個人覺得似乎有點太過,本來每個人的想法就會不一樣,哪種方法最好是見仁見智。
 
而且,小弟不才,我不懂你方案二和方案三的結論。
 
方案二提到在100天後,只有第三類和第四類要舉手答有。
那,有什麼不一樣嗎?100天後會去放風的還是包含了第一類和第二類,從何得知100人全部放風過?
舉例來說,經理在30天時熄燈,那之後燈是一直熄著吧?若是持續亮著下一個人會以為還沒人重複,因為沒人知道經理出現了沒,那如果第50天經理又放風了,燈熄著,他可以得到什麼結論嗎?也許第31天就是重複的人,他應該開燈嗎?他不開燈經理怎知道有人重複了?他開了燈下一個重複的人就以為自己是經理。那究竟多少人放風過從何得知?
我不懂的是,知道有30人放風過可以得知何時100人都放風過嗎?
 
你的解法好難懂,大概是小弟太笨了,還望大大你多指教。

skymen
訪客
 

Re: [成功] 正解 * 3

asmobia 於 星期二 二月 13, 2007 6:10 am


skymen 寫到:

而且,小弟不才,我不懂你方案二和方案T的結論。
 
方案二提到在100天後,只有第三類和第四類要舉手答有。
那,有什麼不一樣嗎?100天後會去放風的還是包含了第一類和第二類,從何得知100人全部放風過?
舉例來說,經理在30天時熄燈,那之後燈是一直熄著吧?若是持續亮著下一個人會以為還沒人重複,因為沒人知道經理出現了沒,那如果第50天經理又放風了,燈熄著,他可以得到什麼結論嗎?也許第31天就是重複的人,他應該開燈嗎?他不開燈經理怎知道有人重複了?他開了燈下一個重複的人就以為自己是經理。那究竟多少人放風過從何得?
我不懂的是,知道有30人放風過可以得知何時100人都放風過嗎?
 
你的解法好難懂,大概是小弟太笨了,還望大大你多指教。
 
 
 
不是我的解法難懂, 是我的表達能力太遜, 對不起...
 
現在看方案二, 現在討論一百天之後, 會有幾種人, 而她們該做什麼事:
 
 
第一類人是經理, 請問:
1:   經理知不知道自己是經理?
答: 當然知道, 經理是第一個進去房間兩遍的人, 是熄燈的人, 自己當然知道.
 
2:   有沒有別人可能誤會自己是經理?
答: 當然沒有, 經理是熄燈的人, 自己沒熄燈就不是.
 
3:   經理在一百天之後要不要報數答有?
答: 不必, 他自己就是點名的人, 報數給自己聽幹嘛?
 
 
第二類人是在最先一百天裡, 有進去過房間而且第一次去的時候燈還是亮的人:
1:   第二類人知不知道自己是第二類人?
答: 當然知道, 第二類人在最先一百天裡, 第一次去房間時, 燈還是亮的, 包括頭一天開燈的都算.
 
2:   有沒有別人可能誤會自己是第二類人?
答: 你在前一百天裡有去過房間, 也看過亮燈的人就是第二類人.
      沒去過房間( 第四類 ), 或是去的時候燈都已經暗了( 第三類 )就不是.
 
3:   第二類人在一百天之後要不要報數答有?
答: 不必. 因為經理是 "第一個" 第二次進房間的人 ( 同時也是關燈的人).
      也就是說, 在經理第二次進房間之前的每一天都有不同的人進去.
 
      所以若是有人在第四十三天的時候第二次進房間, 看見燈仍然是亮著;
      那他立刻就升官成為經理, 接著關燈,
      而且他當場就知道有另外四十一人進過房間了.
 
      為什麼是四十一呢? 因為這四十三天裡有兩天是經理本人去的( 43-2 = 41 ).
 
      這四十一人就是第二類人. 所以若你是第二類人( 你當然知道自己是不是, 不信看上面的1. 與 2. ), 你也從此不必再報數, 因為經理算過你了.
 
      
 
 
 
 
第三類人是在最先一百天裡, 有進去過房間但是去的時候燈都已經是熄掉的人:
1:   第三類人知不知道自己是第三類人?
答: 當然知道, 第三類人是在最先一百天裡, 去房間時燈都已經熄掉的人.
 
2:   有沒有別人可能誤會自己是第三類人?
答: 你在前一百天裡有去過房間, 看到燈都已經熄掉的就是第三類人.
      沒去過房間( 第四類 ), 或是曾經看到燈是亮著的( 第二類 )就不是.
 
3:   第三類人在一百天之後要不要報數答有?
答: 要. 因為經理沒算過你.
 
 
 
第四類人是在最先一百天內從來沒去過房間的人. 這個不在浪費篇幅了; 她們在一百天後肯定要報數答有的啦!
 
 
 
第二種方法比第一種好在哪裡? 你看當經理被選出來的時候, 他立刻就能知道有許多人已經進過房間了; 除此之外, 這些人( 第二類人 )也知道自己以後不必再報數答有了.
 
而你只是花去一百天, 就得到這樣的成果; 請問您若是用第一種方法, 花上一百天, 能夠點名點到幾個人?
按照機率, 一個人平均一百天被選出來一次, 也就是說在整整一百天裡,. 經理差不多只被選出來一次, 你覺得他能點名點到多少人?
 
所以第二種方法的前一百天是超級加速啊! 可以讓你完成平常要花好幾年才能做完的事.
 
用第一種方法, 在開始初期, 經理平均每一百天點名點到一人.
用第二種方法, 在經理被選出來的時候, 有百分之五十的機率是在第十三天以後, 也就是說, 有一半的機會, 經理在前一百天裡可以點名點到十一人以上.
換句話說, 有一半的機會, 第二種方法比第一種方法快一千天 "以上".
 
第二種方法可不可能慢呢? 它最壞是在前一百天一個人都點不到( 前兩天都是同一個人被選中 ); 不過基於第一種方法實在太慢了, 所以第二種方法的損失確實有限, 而好處確實很大.
 
當然, 當最初的一百天過後, 剩下的人還是必須用老法子去辦, 而那些去過的人( 第二類人 )仍然會被重複的叫出去, 浪費大家的機會( 那沒辦法 ); 所以你若是想要更快, 請用第三種批量點名的方法.
 
 
 
 
解題法不難啦! 只是我的表達能力很差; 能看懂我在胡說什麼, 還問出問題的人就令我十分佩服了!!  對於我的解法有什麼建議與問題請不要客氣.

asmobia
實習生
實習生
 
文章: 95
註冊時間: 2007-02-11

Re: [成功] 正解 * 3

SKYMEN 於 星期二 二月 13, 2007 9:53 am


asmobia 寫到:
 
 
當然, 當最初的一百天過後, 剩下的人還是必須用老法子去辦, 而那些去過的人( 第二類人 )仍然會被重複的叫出去, 浪費大家的機會( 那沒辦法 ); 所以你若是想要更快, 請用第三種批量點名的方法.
 
 
 
喔喔!這方法是為了先扣除一部分的人可以不用再算,後續還是回歸到土法煉鋼。
我誤會是要用這方法找出100人都放風過。
多謝大大的解釋。

SKYMEN
訪客
 

jessie 於 星期六 三月 31, 2007 3:04 am


利用燈光對每位囚徒造成永久性的傷害,
例如:每位囚徒持續凝視燈光,照瞎左或右眼即可知道

jessie
訪客
 




邏輯推理學院