一百個囚犯和一盞燈

一、問題的初始版本

監獄裡有100個囚犯，關在100個單獨密閉的牢房裡，互相不能見面和以任何方式交流。囚犯平時都一直呆在牢房內，一日定時三餐，按時起卧。每天晚飯後，典獄長會隨機選出一個囚犯在監獄庭院內單獨放風十分鐘。每天每個囚犯都有百分之一的可能被選到做那個放風的人，和他以前的放風經歷無關。

庭院里有一盞燈和控制它明滅的開關。除了囚犯，沒有人會去動開關。燈很牢靠，不會壞，不會沒電。庭院內（包括其中的燈）的任何動靜都無法被關在牢房中的囚犯得知。

有一天典獄長發善心，把這100個囚犯聚到一起，宣布：如果某天有個囚犯報告說，所有囚犯都至少放過一次風（從宣布規定後的次日算起），而且的確如此，那麼所有囚犯都將被立即釋放；但如果其實並非如此，所有囚犯會被立即處決。

現在眾囚犯可以在一起商量一個對策，然後就又會恢復到以前不能見面和交流的狀態。

假設所有囚犯都渴望被釋放，但都不想冒哪怕是一絲被處決的風險（也即如果有人報吿說所有囚犯都已放過風，那麼他必定能以嚴謹的邏輯證明他的結論正確，而不是基於某種概率上的考慮）。我們可以假設囚犯們是永生的（典獄長也如此），這也解釋了為什麼他們不想冒一絲被處決的風險。囚犯能夠改變的唯一的庭院狀態就是燈的明滅（不許做任何其他記號）。

是否有在足夠長時間後囚犯必被釋放的方案？

二、初始版本問題的簡單解法

題目里沒有說明燈最初是開著的還是關著的。但這並不要緊，可以規定第一天無論是誰放風，都將燈關掉，而約定的方案從第二天開始執行。所以我們可以假定最初燈就是關著的。

事先選定一個囚犯做計數人，他負責記住一個數，這個數最開始是0。輪到他放風時，如果燈是關的，那麼就什麼也不做；如果燈是開的，那麼關掉燈，並將記住的數字加1。當這個數字達到99時，就向典獄長報告所有人都已放過風。

其他囚犯在輪到放風時，如果燈是開的則什麼都不做；如果燈是關的，而且以前他從來沒有開過燈，那麼就開燈；否則就什麼也不做。

容易看出在這個方案下，只要經過足夠多的時間，每個不是計數人的囚犯都會開且僅開一次燈，而這次開燈必會被計數人發現並關燈。所以這是一個足夠長時間後囚犯們必被釋放的方案。

三、進階版問題

如果典獄長提出的要求不是某個囚犯宣布所有人都放過風，而是要說出更複雜的信息呢？我們把題目改一下。

在囚犯聚集開會時，典獄長宣布的是如下規則：

等一下回牢房裡，每人都會發現牢房牆上寫有一個大於0小於100的自然數（每人牢房內的數字並不一定是獨一無二的）。

如果某天有個囚犯說出所有這100個牢房內的數字之和，那麼所有囚犯都將被立即釋放；但如果數字錯誤，所有囚犯會被立即處決。

其他情況同原題。

四、求和問題的解法

觀察原問題條件我們可以發現，囚犯通過每日的日程（一日三餐和睡覺），能夠計算日子的流逝。這是除了開關燈外的第二個傳送信息的渠道。

我們仍可假設最初的燈是關著的。

我們把日子分割成每1000000日為一個循環，就像我們日常的星期是每七天一個循環。和「星期一」、「星期二」……這些名字類似，按照日子在循環里的位置，我們將它們分別命名為「循環日1」、「循環日2」……「循環日1000000」，循環日1000000以後的那天就是新的循環日1。規定聚會的次日也即第一天是循環日1。

每個囚犯要注意計算每天是循環日幾（只要把前一天的數字加1即可，而且記得循環日1000000以後的那天是循環日1）。他還要記住一個數字，這個數字最初是他牢房裡寫的數字加上10000（比如他牢房裡的數字是12，就記住10012）。放風時的任務如下：

如果燈是開著的，那麼關掉燈。把記住的數字和當日名字里的數字相加再減1，變成新的要記住的數字（比如記住的數字是10012，當天是循環日661234，那麼就關掉燈，記住10012+661234-1也即671245）。當記住的數字超過1000000，就向典獄長報告記住的數字的最後四位（比如記住的是1007890，就報告所有數字和為7890）。

如果燈是關著的，而且放風那天的名字恰好和他記住的數字一致（比如他記住的是661234，而放風的那天恰好是循環日661234），那麼打開燈，把記住的數字變成0。

否則什麼也不做，也不改變記住的數字。

直觀地看，這是利用日子名字來不斷地合併囚犯牢房中的數字信息：如果一個囚犯記住的數是453333，這意味著他的數字已經合併了45個囚犯牢房中的數，它們的和是3333。當最終有囚犯得到100abcd這樣的數時，他就知道自己已經合併了所有100個囚犯的信息，其和為abcd。

下面嚴格證明這個方案可行。

首先容易看出，如果一個囚犯放風時發現燈是亮的，那麼一定是前一天放風的囚犯開的。

我們把囚犯和燈合稱為「賦值物」，並按如下方式給它們賦值：令每個囚犯的「值」為他記住的數。而庭院里的燈的「值」，如果是關的話為0，如果是當天被某囚犯開的，其值為當天名字里的數字，如果是前一天被開的，為當天名字里的數字減1。在最開始，所有賦值物的值的和（也就是所有囚犯的值的和，因為最初燈是關的，值為0），是一個形如100abcd的數字，其中最後四位數abcd即所求的所有牢房裡數字之和。任何99個囚犯的最初值加起來都不會大於1000000，因為每人的初值都小於10100。

首先，我們注意到，上述方案中囚犯任務的三種情況和日子的流逝，都不會改變這個和值：

如果燈是開著的，關掉燈會讓燈值清零，也即少掉了當日名字中的數字減1，但是馬上這個少掉的數字就被加到關燈囚犯記住的數里。

如果燈是關著的，而且放風那天的名字恰好和放風囚犯記住的數字一致，囚犯會打開燈，於是燈值會增加放風囚犯記住的數字，而囚犯值也即他記住的數會清零。

如果燈是關著的而囚犯什麼也沒做，和值當然不變。

如果當天不是循環日1000000，而且此日囚犯打開了燈，過一夜後日子數字加1，但是燈值不變。

循環日1000000放完風后的燈一定是滅的，不會有囚犯在循環日1000000那天打開燈，因為沒人會需要記住1000000這個數（這意味著100個牢房內的數字加起來等於0），所以從循環日1000000轉到循環日1的那天晚上不會改變和值。

其次，值非0的賦值物數目只會減少，不會增加。

上述方案的放風過程三種情況下，燈的值變非0時囚犯的值必變0，囚犯的值變非0時燈的值必變0。所以值非0的賦值物數目不會增加。

如果至少有兩個囚犯P和Q記住的數非0，那麼總存在這種可能性（儘管很小），囚犯P恰好在和他記住的數字一致的那天放風，那天的燈是關的，而囚犯Q恰好在次日放風。於是此後囚犯P記住的數字為0，而囚犯Q則記住了原來兩人值之和。這就讓值非0的賦值物數目少了1。

總而言之，足夠長的時間以後，會出現只有一個賦值物有非0值的情況，這個賦值物是一個囚犯，他發現他的值也即他記住的數字是100abcd。此時他會向典獄長報告abcd，使得所有囚犯獲釋。

####五、交換更多的信息

上面這個方案里，囚犯們不斷地用和的形式來合併各自的信息。檢查一下方案和其證明就能發現，用類似的方案，同樣可以將信息以積的形式來合併。但是積（以及整數的唯一因子分解）的計算比較複雜，我們在此假設囚犯的數學和邏輯能力超群，並且有無窮的計算和儲存能力：任意大的具體整數之間的加減乘除都能在瞬間完成，而且可以在瞬間完成有限的任意次的上述加減乘除；所有的計算結果都能保存下來。

假如囚犯們知道每個牢房裡的數字都是素數，而且都小於某具體的自然數N。那麼他們就知道所有數字的乘積小於N^100 。只要把日子改為N^100日一循環，我們就能制定出以積的形式來合併信息的方案。在這個方案中，不需要和形式方案中萬位以上用來表示已合併的數字個數的「加上10000」的部分。因為所有最初的數都是素數，所以只要把手上的自然數唯一因子分解一下，看其中有幾個素因子，就知道有多少條數字信息被合併了。

具體方案如下：

每個囚犯要注意計算每天是循環日幾。他還要記住一個數字，這個數字最初是他牢房裡寫的素數。放風時的任務如下：

如果燈是開著的，那麼關掉燈。令當日名字里的數字為A，把記住的數字乘以(A-1)，變成新的要記住的數字。當記住的自然數的唯一因子分解中的素因子個數等於100，這些素因子就是100個牢房裡的那些素數。

如果燈是關著的，而且放風那天的名字恰好和他記住的數字一致，那麼打開燈，把記住的數字變成1（注意這裡是1而不是0，因為我們使用乘法而不是加法）。

否則什麼也不做，也不改變記住的數字。

證明同和形式方案類似。

五、素數可以表示任意數

上面積形式方案的優點在於，通過自然數的唯一因子分解，最終知道的是每一個囚犯牢房中的數字也即具體的原始信息，而不是象和形式方案中得知的是所有數字的和這樣已經被整合過的信息。

也許有人會說，積形式方案增加了每個數必須是素數的要求。如果每個囚犯手裡的數並非素數，豈不是不能用這個方案了？

並非如此。把所有素數從小到大排成（無窮的）一列：

2, 3, 5, 7, 11, 13, 17, 19, ……

如果囚犯手裡的數是A，他就選取第A個素數來表示A。比如手裡的數是2，那麼就選取3，如果手裡數是5，就選取11……知道原來數字的上限，就能知道被選取的這些素數的上限，然後就能使用積形式方案交換並得到所有100個素數。通過這些素數，反過來也就能知道原來的數字是多少了。

而在如今的數字化世界中，所有信息都可以被一個自然數所表達：一張照片，一首歌，一部電影，都是一個二進位文件，也就是一個（也許很大的）自然數。所以，就算典獄長給每個囚犯一部保存在藍光碟上的電影，要求最後有個囚犯能給出所有囚犯的電影，囚犯們也能在足夠多的時間裡，僅通過一盞燈，做到這一點。

六、初始版本問題的小變動

上面討論的積形式方案無疑是強大的。但是它基於一個重要的條件：每個囚犯在放風時能夠知道那天是什麼日子，或更一般地，知道自己某次放風時，已經進行過的放風次數。如果沒有這個條件（比如說如果牢房裡的生活並不是非常有規律，以至於無法判斷兩次放風之間過去了幾天，或是典獄長並不是固定每天放風一人，而是有可能一天放風好幾人，或是好幾天都不放風一人），那麼他們就無法通過日子名字中的數字來互相交換信息，於是也就不可能實行此方案。

但是第二節中初始版本問題的簡單解法並不基於日子來交換信息，所以即使在無法判斷放風那天是什麼日子的情況下，也還是可以進行。唯一的難點在於，如果不知道最初的燈是開還是關，計數人在關掉99次燈時會遇到一個疑惑：如果最初的燈是開著的，那麼這99次關燈中，其實他關過一次並不是由某囚犯打開的燈，也就是有一個囚犯還沒有打開過燈，此人也許從來沒有放過風。

這個難點可以很容易地解決。只要規定，除了計數人以外的其他囚犯都要開兩次燈，而計數人在計數到198時才報告所有人都已放過風。

-THE END-

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！