本文發表於《大眾科學》的前部落格網路，反映了作者的觀點，不一定反映《大眾科學》的觀點
上週三晚上，我參加了在紐約市即將開幕的數學博物館共同贊助的“數學相遇”專案。 2008年，數學家和前對沖基金經理格倫·惠特尼得知長島一家致力於數學的小型博物館即將關閉時感到沮喪。 他決定自己創辦一家數學博物館。 僅僅幾年時間，他就籌集了所需的資金，這家博物館是北美唯一一家致力於數學的機構，將於 2012 年 12 月開業。
根據惠特尼的說法，每次“數學相遇”（星期三是“第n次”）都是由數學家主導的公共專案。 昨晚，達特茅斯數學家和兩本數學謎題書的作者彼得·溫克勒在巴魯克學院發表了題為“直覺失靈：拉伸你思維的謎題”的演講。 我想深入研究他提出的一個謎題。 我之前就見過它，但它總是讓我感到驚訝。
這種情況，像許多數學謎題的假設一樣，有點牽強：一所監獄裡有 100 名囚犯，虐待狂典獄長決定今晚所有囚犯要麼被釋放，要麼死亡。 為了戲弄他們，典獄長決定讓他們自己決定命運。 在一個單獨的房間裡，他會寫下每個囚犯的名字，並隨機放入一個盒子裡。 囚犯們將一個接一個地進入房間，每人開啟 50 個盒子。 如果每個囚犯都打開了裝有自己名字的盒子，所有囚犯都將活下來。 如果任何囚犯未能找到自己的名字，所有囚犯都將死亡。 囚犯們可以事先決定策略，但一旦第一個囚犯開始開啟盒子，他們就不能商量。 囚犯應該採取什麼策略才能最大限度地提高他們看到下一個黎明的機會？
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞事業 訂閱。 透過購買訂閱，您正在幫助確保關於塑造我們當今世界的發現和思想的具有影響力的故事的未來。
顯然，每個囚犯的隨機選擇不會帶來很高的成功率。 每個囚犯有 50% 的機會找到自己的名字，但兩個囚犯成功的機會只有 1⁄2×1⁄2=1⁄4，即 25%。 三個囚犯成功的機會只有 1⁄2×1⁄2×1⁄2=1⁄8，即 12.5%。 當我們達到 100 個囚犯時，機率僅為 (½)100=7.9×10-31=0.000000000000000000000000000079%。 （是的，我數了所有的零。） 為了理解這是多麼不可能，請考慮一下，如果自宇宙大爆炸以來每納秒都發生這種情況，囚犯仍然只有不到十萬分之一的機會倖存下來。 我們可以將機率提高到百萬分之一嗎？ 千分之一？ 信不信由你，我們可以做得更好：有一種策略可以在 30% 以上的時間裡拯救囚犯。
當我第一次遇到這個謎題時，囚犯們在開始時都被分配了一個號碼——他們在盒子裡找到的是號碼，而不是名字，我認為這讓我更快地找到了解決方案的想法。 因此，從現在開始，我們假設囚犯們按照字母順序排列自己，並根據該順序分配號碼，儘管任何編號都可以。 （這與最初的問題略有不同，因為它給了典獄長額外的知識，他可以選擇一種策略來確保囚犯的厄運。 假設他隨機將號碼分配到盒子裡可以解決這個難題。）
想出一個不是隨機的開箱策略並不容易。 但正如我經常在輔導數學時告訴我的學生那樣，如果你不知道該做什麼，那就做一些事情。 做你能想到的唯一的事情——這勝過無所事事。 所以這就是我所做的。 囚犯決定開啟哪個盒子的一種方法是從隨機開始，然後使用盒子的內容來決定接下來開啟哪個盒子。 例如，如果囚犯 1 開啟盒子 5，而盒子 5 包含數字 7，則囚犯將接下來開啟盒子 7，然後開啟數字在盒子 7 中的盒子。
事實證明，這其中蘊含著正確策略的種子。 唯一缺少的是如何選擇要開啟的第一個盒子，事實證明，每個囚犯都應該從自己的號碼開始。 完全披露：我沒有自己想出答案，但我與我的數學研究生同學討論這個問題時非常有趣，最終其中一位同學告訴我們如何解決這個問題。
為了瞭解這種策略是如何運作的，我將遵循溫克勒的引導，並使用一個只有 10 個數字的“嬰兒”示例，就像他在上週三的演示中所做的那樣。 我們需要將數字分配到盒子的方式視為排列，這是一種對從 1 到 10 的數字集進行排序的方式。 假設與盒子對應的排列是：*
頂行上的數字代表盒子編號，底行上的數字是盒子中的數字。 我們也可以用所謂的迴圈表示法來寫排列：（1 7 3 4）（2 5）（6 10 8 9）。 第一個迴圈（1 7 3 4）表示盒子 1 中的數字是 7，盒子 7 中的數字是 3，盒子 3 中的數字是 4，盒子 4 中的數字是 1。 第二個迴圈（2 5）表示盒子 2 包含數字 5，盒子 5 包含數字 2，第三個迴圈（6 10 8 9）表示盒子 6 包含數字 10，盒子 10 包含數字 8，盒子 8 包含數字 9，盒子 9 包含數字 6。 兩行表示法和迴圈表示法是書寫相同排列的等效方式。
如果 10 名囚犯每人可以選擇 5 個盒子，並且每個囚犯都從自己的號碼開始，我們看到囚犯 1 將按順序開啟盒子 1、7、3 和 4。 在盒子 4 中，他找到了自己的號碼 1。 囚犯 2 只需開啟盒子 2 和 5 即可找到自己的號碼。 每個囚犯依次找到自己的號碼，因此他們都獲得了自由。 您可以透過從排列頂行的任何數字開始，並檢查返回該數字需要多少步來自行檢查這一點。
如果我為盒子選擇了不同的排列會怎樣？ 讓我們試試這個：*
用迴圈表示法寫成，這個排列是（1 3 5 6 2 9）（4 8 10）（7）。 囚犯 1 按順序開啟盒子 1、3、5、6 和 2。 在盒子 2 中，他找到的是數字 9 而不是 1。 太晚了——這是他的第五個選擇。 他沒盒子了。 在這個遊戲中，他的第六個選擇包含他的號碼這一事實並沒有任何憐憫。 事實上，號碼在第一個迴圈中的人都沒有找到自己的號碼。 當他們開啟第五個盒子時，他們都只差一步。 號碼在其他迴圈中的囚犯確實找到了自己的號碼：囚犯 7 立即在自己的盒子裡找到了，囚犯 4、8 和 10 在第三次嘗試時找到了。 唉，這個群體註定要失敗，因為囚犯 1、2、3、5、6、2 和 9 都未能找到自己的號碼。
我選擇的第一個排列的關鍵是其中沒有長度大於 5 的迴圈。 包含您的號碼的迴圈的長度與您必須開啟才能使用此策略找到您自己的號碼的盒子數量完全相同。 如果有一個迴圈，比如有 6 個數字，那麼任何號碼在該迴圈中的人都會找不到自己的號碼，囚犯肯定會輸。 但是，如果排列的所有迴圈都小於 6 個元素長，那麼每個人都會找到自己的號碼。
同樣的原理也適用於我們有 100 名囚犯的謎題，他們每人可以開啟 50 個盒子。 如果將名字隨機放入盒子中定義的排列具有長度超過 50 個數字的迴圈，則囚犯會死亡，因為每個號碼在該迴圈中的人都將無法及時找到自己的號碼。
為了計算成功的機率，我們需要弄清楚在 100 個元素的排列中，有多少比例的排列具有長度大於 50 的迴圈。 好處是，如果一個排列有一個長度為 51 或更長的迴圈，它就不能有另一個迴圈； 最多還剩下 49 個元素。 奇蹟般地，事實證明，隨機排列具有長度為 51 的迴圈的機率是 1⁄51，長度為 52 的迴圈的機率是 1⁄52，依此類推。 如果你想知道為什麼，請繼續閱讀。 如果不想知道，請跳過下一段。
為了找到一個長度為 51 的迴圈，我們有 100 個第一個元素的選擇，99 個第二個元素的選擇，98 個第三個元素的選擇，依此類推，直到第 51 個元素有 50 個選擇。 因此，我們可以用 100×99×…×50 種不同的方式編寫一個 51 迴圈。 但是其中一些迴圈是等效的。 為了使用一個小的、易於管理的例子，迴圈（1 2 3 4）等效於迴圈（2 3 4 1）。 它們只是以不同的順序寫下來，但都對應於排列
迴圈（3 4 1 2）和（4 1 2 3）也是等效的。 我們可以透過除以迴圈的長度來糾正此錯誤； 我們可以從任何數字開始寫下相同的迴圈，這就是我們過度計數的程度。 在我們的例子中，這意味著除以 51。 因此，我們排列的 51 個元素已被分配。 我們還剩下 49 個元素，它們的任何排列都是可以接受的。 49 個元素的排列數是 49×48×47×…×2×1，也稱為 49！（階乘）。 將所有內容放在一起，我們得到
具有長度為 51 的迴圈的排列。 由於 100 個元素的總排列數為 100！（這是分數中的頂部數字），因此具有長度為 51 的迴圈的排列的分數正好是 1⁄51。 相同的推理適用於任何長度超過 50 的迴圈。
我們現在需要將所有殺死囚犯的排列加起來，這意味著所有具有長度超過 50 的迴圈的排列。 就機率而言，這是 1⁄51+1⁄52+…1⁄99+1⁄100≈0.688。 因此，剩餘的比例 1-0.688，即 0.312，是找到沒有致命迴圈的排列的機率。 這種策略帶來了高達 31.2% 的成功率，比隨機策略好無數倍（技術術語）。 好耶！ 只是不要考慮他們仍然可能全部死亡的事實。
這個解決方案因其穩健性而有趣。 如果您增加囚犯的數量（並將囚犯與猜測的比例保持在 2:1），您可能會認為您的成功機會會下降。 確實如此，但幾乎沒有。 對於任何這種情況，成功率約為 1-ln2。 （請記住，ln 是以 e 為底的對數；ln(x)=y 意味著 e^y=x。） 如果您將囚犯人數增加到 1,000，猜測次數增加到 500，或者將囚犯人數增加到 10 億，猜測次數增加到 5 億，則成功率就是這個值。 原因在於，對於較大的 n，失敗的機率非常接近函式 1⁄x 從 n 到 2n 的積分。 由於對數的性質，這等於 ln2 ≈0.693，因此成功的機會約為 1-ln2≈0.307，即 30.7%。
我覺得獲勝策略有點詩意。 囚犯們不可能接近勝利，只有一兩個人未能找到自己的號碼。 如果他們沒有全部成功，那麼每個號碼在長鏈上的人都無法找到自己的號碼。 那超過一半的人！ 該策略的性質意味著您從鏈條上離您的號碼最遠的點開始開啟盒子。 但沒有更好的策略； 從您自己的盒子開始是確保您甚至在正確的鏈條上查詢的唯一方法。 它感覺像一種“團結就是力量”的態度。
彼得·溫克勒的演講描述了這個謎題和其他幾個令人費解的謎題，儘管他沒有時間像我在這裡那樣詳細地介紹。 觀眾很喜歡嘗試解決出現的謎題。 數學博物館在 12 月開幕之前，正在共同贊助更多關於各種不同數學主題的數學相遇活動。 他們的下一位特邀演講嘉賓是數學家和計算機科學家卡洛·塞金，他設計了受數學啟發的藝術作品。
*更正（2012/7/19）：這些示例在原始帖子中放置不當。 它們現在處於正確的位置。