一道頗有難度的邏輯題？
23個犯人被典獄長叫過來，典獄長說：有一個房間，裡面有兩盞燈，燈只有兩個狀態：開和關。我會在任意時間隨機叫一個人，讓他進入這個房間動其中一且只有一盞燈的開關，使那盞燈改變狀態。然後他會回去。我再在另一時間再隨便叫一個人。任何時候任何一個人可以對我說：每個人都被叫過一遍了。如果這時真的所有人都被叫到了，那麼你們可以獲得自由，如果其實還有人沒被叫過，那麼你們都要死。你們可以現在討論一個策略，在開始之後每個人單獨一個牢房，你們無法通過任何手段互相交流，只有燈的亮暗。注意一開始兩個燈的情況可以是任意的，你們不知道你們看到的燈的狀況是上一個人擺的還是一開始就這樣而你剛好是第一個人。我可以連續叫一個人三次，也可以很久都不叫一個人，但最終每個人都會被叫到。
犯人採用什麼策略才可以保證逃脫？
來個通俗易懂的
其實可以只用到一個燈，下面我們假設只有一個燈
假設100個犯人每人有倆蘋果，現在約定一個人為收集者，好了，現在讓他們進入
如果非收集者每次進入，發現盒子里有去蘋果，他不做任何事退出，如果沒有蘋果，他就放一個進去，（把燈開了）（前提是他還有蘋果）
收集者每次進入都收集蘋果（把燈滅了。）
好了因為初始狀態不知道是燈是亮還是滅，如果初始是滅燈，所以收集者至少要收集到199個蘋果才能宣布勝利，他最多能收集200個，如果初始是亮的，他至少要收集200個才能勝利，最多能收集201個。
那麼他一定可以收集到200個，那時必勝。
這裡有幾個詳細而直觀的理解方案，以及對原題目的拓展研究。
1. 原題目的答案及分析（是否存在一個協議，使得最終可以產生某個人，他知道所有人都進過房間）
- 100個囚犯和燈泡的那些事兒（上）
2. 題目的加強版和加加強版答案及分析（是否存在一個協議，使得最終可以產生兩個人，他們都知道所有人都進過房間）（條件為有兩個燈泡，分別由兩個開關來控制；所有人都必須遵循同一套策略。問和原問題一樣。）
- 100個囚犯和燈泡的那些事兒（下）
3. 更多其他100囚犯問題（前者是囚犯戴帽子問題，後者是囚犯選手套問題）
- 100囚犯問題、100囚犯問題加強版與選擇公理（上）
- 100囚犯問題、100囚犯問題加強版與選擇公理（下）
- UyHiP趣題：100囚犯之黑白手套
-----------------------------------------------------------------------------------------
註：以上引用均來自 Matrix67.com: Home
假定任何人都可以被叫任何次的話可以用如下方法：
我們可以把燈看做一個交易平台，有一個人是「收款」人，其餘22人每人有1塊錢他們需要通過交易平台將錢付給「收款」人。
協議如下：
if 第一次被叫到 then //初始化交易平台
if 是"收款"人 and 第一盞燈是滅的 then
改變第一盞燈
else
改變第二盞燈
end
else
if 是"收款人" then
if 總收款數 == 22 then
告訴典獄長人已全部被叫過
exit
else if 第一盞燈是滅的 then
改變第一盞燈
總收款數 + 1
else
改變第二盞燈
end
else
if 第一盞燈是亮的 and 還未付款 then
改變第一盞燈
狀態改為已付款
else
改變第二盞燈
end
end
end
更新1:
----
我之前的演算法有問題，把初始化改為只有當付款人看到第一盞燈變化後才執行else以下部分，而收款人則通過改變第一盞燈使得付款人確保平台已運作。這是可行的（即它給出有解時一定是正確的），證明如下：
1. 若收款人未經過房間，那麼第一盞燈永遠不會改變，因此付款人不會付款
2. 若付款人看到第一盞燈變化了（即與他之前看到的不同），那麼說明平台已經運轉，他將在第一盞燈亮（只有收款人才能使之變亮）的時候付款。
3. 對於收款人，他會依次執行以下步驟：
a. 將第一盞燈變亮
b. 等待n（隨機數）次直到第一盞燈滅掉
b1. 若n次過後燈未滅（說明付款人並未看到變化），將第一盞燈變滅等待m（隨機數）次後goto a
c. 若第一盞燈滅掉，則收款，goto a.
這本質上是一個蒙特卡洛演算法，如果典獄長每次採用最優策略那永遠得不到解，但一旦有解則解一定是對的。
第二盞燈只是保證他題目中說的每次必須改變一盞燈。這是一個相當困難的問題，來自於分散式計算，具體的解法出自這篇文章：
ftp://www1.idc.ac.il/Faculty/gadi/MyPapers/1996FMRT-wakeup.pdf
稱為"see-saw protocol"
0，假定每個犯人初始時有兩個虛擬籌碼，兩盞燈一盞用於指示每個犯人當前的狀態，稱為"see-saw switch" 狀態可以約定為1和－1, 另一盞用於指示犯人當前應採取的行為，稱為"pebble switch"，狀態可以約定為on和off
每個犯人可以有三種狀態 0，－1，1
1，每個犯人第一次進入房間時，扳動see-saw開關，並記住自己對應的狀態 （－1或 1，由開關指示）；
2， 此後每次進入房間：
2.1 若自身狀態為0，則不採取任何行動
2.2 若自身狀態為1或－1，則：
2.2a 若此時犯人無籌碼，且與當前see-saw開關的狀態一致，則扳動see-saw開關，並將自己標記為0
2.2b 若此時犯人有籌碼, 則：
2.2b1 若自身狀態與當前see-saw開關的狀態一致，且pebble開關為off, 則扳動pebble開關並視作給出一個籌碼
2.2b2 若自身狀態與當前see-saw開關的狀態不一致，且pebble開關為on, 則扳動pebble開關並視作獲得一個籌碼
任意時刻，某個犯人獲得了2n （設有n個犯人）個籌碼時可以宣布所有人均已訪問過房間
上述操作並不消滅或產生籌碼，並總是保證籌碼向當前人數低的一方流動，因此最終某人將獲得全部2n或2n＋1個籌碼 （取決於pebble開關的初始狀態）誰也不說：每個人都被叫過了！
這樣大家都不會死！
因為決定權在獄長手裡！
題目條件不夠強吧……應該要保證每個人都會被叫到無窮多遍，而不是每個人都會被叫到。
這個寫的很通俗易懂：100個囚犯和燈泡的那些事兒其他人放球，指定一個人收球即可。
題意不是很清楚，不知道外面的人是否能分辨出兩盞燈，以及在室內的人能否判斷每盞燈對應的開關。
先不妨假定外面的人能夠分辨的明暗程度有三種狀態：沒有燈亮，一盞燈亮，兩盞燈亮。只要囚犯約定好，比如：如果你進入房間並且第一次碰到一盞燈亮的狀態，將不亮的燈打開；如果你進入房間並且不是第一次碰到一盞燈亮的狀態，將亮的燈關掉；這樣進去過的人只要看到發生22次從一盞燈亮變成兩盞燈亮，就可以斷定所有人都進去過了。
如果外面的人可以進一步分辨出亮的是哪一盞燈，那麼更簡單，如果第一次進去，則開或者關A燈，如果不是第一次進去，則開或者關B燈，同樣進去過的人只要看到發生22次A燈的變化就可以斷定了。
如果外面的人能夠分辨的狀態少於三種，那應該是沒有辦法的。
條件：
1.兩個盞燈，每盞燈有兩個狀態，關或者開。
2.只能一次只能改變一盞燈的狀態。
3.有人可能被叫多次，所有人都要進去過才過關。
4.開始燈的狀態不確定。
我的方案：
不管開始狀態。
1.「初次」燈。
初次燈的定義：囚犯第一次次進去時，改變此燈狀態，後面的囚犯跟隨第一位囚犯的習慣。
當你第一次進去時，改變此燈的狀態。
2.「非出次」燈
非初次燈的定義：如果不是第一次進去房間，則改變此燈的狀態。
3.N初始值＝0，「初次」燈變化時N＋1；「非初次」燈變化時，N值不變。
4.當N＝23時，即代表所有人都進到房間裡面。再無法明確區分AB燈的情況下：
我們把第一個進去的犯人改變狀態的燈設為A燈，反之則為B燈
因為每個人進去都必須改變且只能改變一盞燈的狀態，我們把每一次的狀態改變記錄下來；
每個人第一次進去的時候都改變A燈的狀態，如果是第二次或更高次進去改變B燈的狀態；
最後記錄A燈的狀態變化次數，當達到23次時，即為每個人都進入了房間；
題設說得不夠完整，根據題意推測，對題目做出以下補充：
1、從房間外面能看見燈光甚至能看見兩盞燈的狀態是不太可能的；
2、每個犯人都能被叫到無窮多次應該是個必要條件；
3、題目規定每個犯人進入房間後都必須且只改變一盞燈的狀態。
解題的思路大家說得很清楚了，覺得還有幾個要點需要說明。
1、犯人討論時要明確哪個燈為A用來計數，哪個燈為B。比如說離門近的燈為A，或者再加一個附屬條件，以防兩個燈一樣近。
2、在房間里是否能夠直觀地看出哪個開關對應哪盞燈，這個很關鍵：
1）如果可以的話，由於初始狀態未知，要求每個犯人在前兩次碰到A燈為關閉時，開A燈，其他情況下則改變B燈的狀態；負責計數的犯人在進入房間時，如果A燈為開，則關閉A燈，其他情況下改變B燈的狀態，當計數的犯人關閉A燈44次後，可以確定所有犯人都來過這個房間；
2）如果不能判斷哪個開關對應哪一盞燈，則每人在最開始的時候要多一次試驗，每人進入房間後隨意改變一盞燈的狀態：
a）對於計數的那個犯人來說，隨機的第一次：如果開了A燈，則接下來第一次碰到A燈亮時，關A燈且不計數；如果關了A燈，則做法同1），計數一次；如果開或關了B燈，就當什麼也沒發生吧，哈哈
b）對於其他犯人，第一次隨機開關燈：如果開了A燈，則做法同1），之後還需要開啟A燈1次；如果關了A燈，則之後需要開啟A燈3次（原本為兩次）；如果開或關了B燈，也就當什麼也沒發生咯，之後進入還需要開啟A燈2次
同樣是在完成44次計數後，可以確定所有犯人來過這個房間。
指定一人收蘋果，其他人放蘋果。 暗暗作為開始收放蘋果的信號。
初始狀態，暗暗(00)，那很簡單直接開始收放。初始01 10則進去的人關掉燈，外面的人接到信號開始收放。初始11進去的人關掉一盞，下一個進去的人又關掉一盞，再下一個開始收放蘋果。
假設燈的狀態00 01 10 11 ，原始狀態有四種情況，假設初始為 01 除去11的狀態還有 01 10 00三種狀態，第一次進去的人改變左邊的燈，重複進去的人改變右邊的燈，看左邊的燈的開個次數就能計算出多少人是否進去過了 -------百事可樂
設置甲，乙，兩個燈
一共有四種情況。
1-1 0-0 1-0 0-1
可以構成一個環
1-1*1-0*0-0*0-1*1-1
約定不論是誰，只要進去一次，見到1-1就改成1-0，見到0-0就改成0-1，哪怕連續兩次都是自己也一樣。
通過這樣一個周期。
假如我第一次進入，見到了0-0,第二次進入，見到了1-1。那麼在兩次之間最少被修改了兩次。因為一定是連續三次被叫進去，所以中間一定最少有兩個人被叫進來了。
第三次進入，見到了1-0。那麼中間可能是我被連續叫了兩次。所以我已知最少進入的人還是3。但也有已經輪完幾個周期了。
將可能重複的人數照常計算。並往後預計4個周期左右。
等我已知最少的次數。已經足夠23了。
我就可以去向典獄長說明全部通過。
燈一或二可以自己選嗎？如果可以且犯人能看見燈亮那麼
不妨設開始時燈1和2的狀態為0-0
當叫到某犯人，如果他是第一次進去，則動第一盞燈（1-0）；如果不是第一次進去，則動第二盞燈（0-1）
當第一盞燈發生第23次變化時，則所有人都進去過
當然，外面的犯人可以通過光的強弱或者燈光位置的分布判斷進去的人動的是燈一還是二
如果是同一個人就開關同一盞燈，不同的人就開關不同的燈，直到所有人都出去過
可能出現的情況有4種，光暗，暗暗，暗光，光光分別記為1234，犯人講好順序12341為一個循環，如果犯人連叫三次即可將燈的狀況調為第一次改的燈的狀況，犯人記住每次開燈的狀況，依此算出進來過的人，穩妥起見，宗旨是寧多勿少。另外，這個題沒說清。
說實話我連題都沒有看懂，關於邏輯和計算等問題更是不會了。不過我想到一個，就是從一人或多人身上取與人數相等的毛髮，每人持一根，放到房間里，待到房間里毛髮與人數相等時便可知每人都被叫過。知識淺薄，各位勿噴
推薦閱讀：