bell 寫到:想到一個方法
1.開會討論時指定一人, (就先稱為A先生)負責紀錄放風人次並消除另99人的共同記號.(關燈)
2.初次被抽到放風的囚犯, 必須做記號: "離去時將燈關上." 此人以後不需再做記號.
3.自此以後再被抽到初次放風的囚犯, 必須直到A先生消除此記號前, 也就是看到"燈是打開的", 才可以做關燈記號.
4.當A先生紀錄達99人次(加上自己), 便能夠表示自己已明確知道100位囚犯都被放風過了! 但這樣十分地曠日費時啊.......
5.如果能夠想出其他不同的記號方法, 如: 燈泡可以取下的話, 可將它作為關燈記號之後的第二項記號, 那麼就可以減少A先生計次的次數! (共50次, 最後一次燈會是關上而不是燈泡被取下), 如此每增加一項記號就可以更縮短計次的次數(33次, 25次....). 百位囚犯就能更早被釋放了.
J+W 寫到:
這個答案就是我預設的答案!
沒想到英雄所見略同
不過有人提出更好的方式
就是確認的人不一定要是A的方式
J+W 寫到:有100個無期徒刑囚徒,被關在100個獨立的小房間,互相無法通信。每天會有一個囚徒被隨機地抽出來放風,隨機就是說可能被抽到多次。放風的地方有1盞燈,囚徒可以打開或者關上。除囚徒外,沒有別人會去動這個燈。每個人除非出來放風,是看不到這個燈的。
一天,全體囚徒大會,國王大赦,給大家一個機會:如果某一天,某個囚徒能夠明確表示,所有的囚徒都已經被放過風了,而且的確如此,那麽所有囚徒釋放;如果仍有囚徒未被放過風,那麽所有的囚徒一起處死!
囚徒大會後給大家20分鐘時間討論,囚徒們能找到方法麽?
補充:囚犯放風時不能帶任何可以做記號的工具
好好的一個題目大家拿來腦筋急轉彎, 這裡的程度實在要加強.
****************************************************************
請注意, 本題解法是假設一開始燈是關著; 如果燈是亮的怎麼辦?
很簡單, 大家犧牲一天, 第一天去的人唯一要做的事就是把燈關掉, 然後當作自己沒去過; 一切從第二天開始算.
方案一: 一百人中間選一人當經理, 其他是員工; 經理點名, 員工舉手答有.
員工舉手答有就是將燈打開, 一個人只能舉手答有一次.
經理點收就是將燈關掉, 就算做點名一次了.
若是員工想要舉手答有時, 發現燈已經是亮的了; 代表之前已經有員工舉手答有, 而經理還未點收. 這時這員工只好下次再來.
經理點到九十九個員工時, 就知道人人來過了.
你只會方案一嗎? 網路上到處查的到; 這種耗費三十幾年的方法也能當解答?
方案二: 將工作分為前一百天與一百天以後.
在前一百天裡, 第一天去的人將燈打開; 之後的人就讓燈一直保持亮著, 直到有人第二次被叫過來時將燈關掉, 這人就被選為經理了.
經理是誰? 經理是最先被叫去兩次的人. 在他之前, 沒有人去過兩次( 不然那個人就關燈當經理了 ); 在他之後, 燈一直都是滅的, 直到一百天過去.
也就是說, 在前一百天裡, 燈從第一天開始亮; 直到第一次有人去過兩次時被關掉, 一直維持關著直到前一百天過完.
為什麼要一百天呢? 因為一百天"幾乎"可以擔保選出經理;
若是在第一百天時還選不出來, 就代表說前九十九天都是不同的人進去;
而在第一百天正巧第一百人被叫去, 他一去看到燈居然是亮著! 那要馬上跪地感謝上蒼因為大家立刻被釋放了.
若是在一百天之內選出經理了, 那所有人可以分為四類, 且自己知道自己是哪一類:
1. 經理本人
2. 那些第一次被叫去時, 看見燈仍是亮的人( 包括第一天開燈的人 ).
3. 那些第一次被叫去時, 看見燈已經是關的人.
4. 在前一百天從未被叫去的人.
假設經理本人在第三十天關燈, 也就是說前二十九天人人不同, 也就是說第二類人有二十八個( 經理本人不算 )
故, 此時經理已經點了二十八個人名字了( 加自己二十九 ), 第二類人再也不需要舉手答有了.
所以在一百天以後, 只有第三類與第四類的人要舉手答有.
方案二改進了很多, 但是真的不能再快嗎? 坐牢很無聊啊!!
方案三: 員工, 經理, 總經理:
一百人有九十個人當員工, 九個人作經理, 一個總經理.
而工作分為兩種階段, 第一階段叫"員工向經理報告", 第二階段叫"經理向總經理報告".
這兩階段的天數長度可以自行設定, 若有電腦模擬可以找出最佳解.
這兩階段是循環的, 也就是說階段一完了變成階段二, 階段二完了變回階段一.
在階段一, 由員工舉手答有, 經理與總經理點收. 請注意, 一個經理或總經理負責九個員工;
若是一個經理已經點到九個員工, 他的部門就滿編了, 不能再收人了.
一個員工只能舉手答有一次.
在階段二, 由"已經滿編"的經理舉手答有, 總經理點收. 一但總經理點到一名, 他就知道已經有十個人了( 九個員工與一個經理 ).
一個經理只能舉手答有一次, 答完之後不能再收新員工了( 部門滿編了 ).
也就是說, 當總經理點名點到另外九個經理時, 他就知道有 10 * 9 個人已經去過了;
同時, 若總經理自己的部門也點收到九名員工的話, 那一百人都去過了.
這種批量處理的速度絕對快過前兩個方案, 但是他有一個"繼承"的觀念不能忽略.
什麼是繼承呢?
回看上面的解法, 我們假設每一階段開始時燈是關的;
要是有一個員工在階段一舉手答有, 但是一直沒有合適的經理來點收, 這燈不就亮到第二階段了嗎? 這不全亂了嗎?
所以, 每個階段的最後一天, 去的人要負責將燈熄滅, 確保下一階段的乾淨.
將燈熄滅後, 這人就繼承了當初開燈舉手答有的人的工作; 因為只有你才知道他的舉手答有未完成.
所以你要在下次有機會時, 以他的身份幫他舉手答有一次.
"繼承"舉例:
現在是第二階段的最後一天, 我是一個尚未舉手答有過的員工; 照道理, 第二階段是經理與總經理的事, 員工根本不必去.
可是這是該階段的最後一天, 我必須去.
我一去看到燈是亮著, 表示有一個滿編的經理; 自以為已經向總經理報告過了, 可是很顯然總經理沒機會聽到.
所以我把燈關掉, 確保下一階段乾乾淨淨; 而後, 我不光是一個尚未舉手答有的員工了, 我還是一個部門滿編的經理.
在第一階段, 身為一個尚未舉手答有過的員工, 我要向一位經理報告.
到第二階段, 身為一個部門滿編的經理, 我要向總經理報告我的部門滿編.
有沒有方案四啊? 我相信是有的....
asmobia 寫到:好好的一個題目大家拿來腦筋急轉彎, 這裡的程度實在要加強.
****************************************************************
所以在一百天以後, 只有第三類與第四類的人要舉手答有.
方案二改進了很多, 但是真的不能再快嗎? 坐牢很無聊啊!!
skymen 寫到:而且,小弟不才,我不懂你方案二和方案T的結論。方案二提到在100天後,只有第三類和第四類要舉手答有。那,有什麼不一樣嗎?100天後會去放風的還是包含了第一類和第二類,從何得知100人全部放風過?舉例來說,經理在30天時熄燈,那之後燈是一直熄著吧?若是持續亮著下一個人會以為還沒人重複,因為沒人知道經理出現了沒,那如果第50天經理又放風了,燈熄著,他可以得到什麼結論嗎?也許第31天就是重複的人,他應該開燈嗎?他不開燈經理怎知道有人重複了?他開了燈下一個重複的人就以為自己是經理。那究竟多少人放風過從何得?我不懂的是,知道有30人放風過可以得知何時100人都放風過嗎?你的解法好難懂,大概是小弟太笨了,還望大大你多指教。
asmobia 寫到:當然, 當最初的一百天過後, 剩下的人還是必須用老法子去辦, 而那些去過的人( 第二類人 )仍然會被重複的叫出去, 浪費大家的機會( 那沒辦法 ); 所以你若是想要更快, 請用第三種批量點名的方法.