2015.04‎ > ‎ 用數學逃出密室 posted 12 hours ago by 陳宏賓

2015.04‎ > ‎

用數學逃出密室

posted 12 hours ago by 陳宏賓   [ updated 12 hours ago ]

最近實境密室逃脫遊戲越來越盛行，這兩三年來，台灣大大小小的逃脫少說也有辦過兩百場，而且梗一直不斷的推陳出新，新工作室也持續地成立。就連柯P競選市長時，也曾帶著團隊挑戰過密室逃脫。 在密室裡，常常需要「翻找線索  -> 解出謎題  -> 打開寶箱或門」。寶箱上的鎖，若是鑰匙鎖，多半是利用現場工具來取得鑰匙；此外，最常見的，就是密碼鎖了，因為密碼鎖可以跟謎題配合，計算出密碼來解出。 提到密碼鎖，筆者小時候受馬蓋先的影響，對解鎖非常感興趣，每次看到朋友的腳踏車有下面的這種鎖時： 就會很興奮的跟他說：「我可以很快的把你的密碼找出來」。在我真的說出他們的密碼後，他們就開始追問我怎麼解的。我告訴他們：「就一組一組慢慢試就可以了」。他當然不會相信。那筆者到底怎麼猜出密碼的呢？ 就一組一組慢慢試就可以了！ 其實方法很簡單，就從 1234, 1235, 1236, 1237, 1238, 1239, 1230, 1245, 1246, …一組一組試即可，而且每次大約三四分鐘就可以試出結果。筆者當時只有國中，並沒有學過排列組合，所以對於每次都這麼快可以試出來，也是非常訝異。 當時的我，想說「第一碼有 10 種選擇，當試第二碼的時候剩 9 種選擇，第三碼剩 8 種選擇，最後一碼剩 7 種，所以總共 10 x 9 x 8 x 7 = 5040 組號碼」，若試一組要花 2 秒鐘，假設平均試到一半會試出來，也要 2520 x 2 = 5040 秒，差不多要 1 個多小時，怎麼會每次只要三~四分鐘呢？ 難道，我是賭神再世，運氣超好嗎？! 密碼鎖的對稱性 後來我 觀察 到，當這個密碼鎖「正面按下四個鈕」時，其實相當於「背面按下六個鈕」，所以四位密碼，跟六位密碼的數量應該要一樣多才對，但如果根據之前我的算法，六位密碼卻要 10 x 9 x 8 x 7 x 6 x 5 = 151200 組，而且最不合理的是若十位密碼竟然要 3628800 組。因此，可以 歸納 出 我的算法一定有錯！ 後來才想到，密碼 1234 跟 4321、1342、…這些都是一樣的，並沒有順序的差別，所以要把重覆的扣掉，成為(10 x 9 x 8 x 7)/(4!) = 210。這也驗證了四位數密碼跟六位數密碼的數量 (10 x 9 x 8 x 7 x 6 x 5)/(6!) = 210 是一樣的。這其實是高中數學中排列組合的一個重要定理： 如果看數學式子讓你頭昏，那麼請你從另一角度，看看這式子的數學意義: n 個物品拿出其中 m 個的方法數 = n 個物品拿出其中 n-m 個的方法數 是不是比較可愛了呢! 什麼！！這個鎖竟然只有 210 組不同的密碼，一組一組試的話，試 105 組就有 50 % 的機率可以試出來，若試一組耗時 2 秒，差不多 3 分鐘多一點就可以解開; 最糟最糟 210 組全試也不過 7 分鐘以內。 上面是舊式十選四的密碼鎖，只是單純的卡榫型式，按一陣子，按鈕容易鬆動，所以已經停產，目前市面上比較常見，也是實境逃脫密室最常用的鎖是下面這種： 它是從 1~8 中選四位出來當密碼。事實上它只有 70 組不同的密碼而已，平均試一分鐘左右就可以試出來了。因此，在密室中，遇到了這種鎖的候時，一般來說，「翻找」加上「解謎」的時間，大概也要六、七分鐘；何況有時，密室創作者會做線性安排，要先解出 A，才能解 B，然後才能得到此鎖的線索，這時解開此鎖，就不是十幾、二十分鐘可以完成的了。此時當然是二話不說，立刻暴力解才是最省時的做法。若是像右邊這種「十選五」的鎖，其實也只有 252 組，五分鐘應該沒問題。 另外還有一類的密碼鎖：   由左至右分別是 1000 組、10000 組、100000 組，這類的鎖若完全靠暴力試的話，投資報酬率就非常低了。但也不是完全沒辦法，以四位數的鎖來說，若玩家只從線索推得了密碼的四個數字是 2、3、7、9，但卻一直推不出順序的話，其實也只有 4! = 24 種選擇，用試的其實也很快。若是像 2、3、3、7 這種有重複的話，就更少組了。另外，有時玩家只推測出前三位數，第四位一直找不出來時，也是可以用試的。 故事只到這裡嗎？其實這只是個開始！ 格雷碼 Gray Code 當我們在嘗試解出「十選四」的密碼鎖時，1234 -> 1235，只需改變鎖頭上，4 與 5 兩個按鈕狀態即可，但是當試到 1890 時，下一組是 2345，卻要改變到 8 個按鈕。因此，其實試每一組密碼花的時間並非是一樣的，有的可能要花比較久的時間才行。 那怎麼樣才會最省時呢？ 數學家、密碼學家早已解決了這個問題。舉一個比較小的例子來說明，「五選二」的密碼鎖，共有十組密碼。 12->13->14->15->23->24->25->34->35->45 讀者可以數一下，這樣總共要改變 22 次按鈕才能試完所有的情況。若改成下面的順序： 12->13->23->24->34->35->45->14->15->25 只要按 18 次按鈕，即可試完所有的情況。 而且這已是最少的次數了，因為每換一組密碼至少要 2 次按鈕。從上面可以看出，字典序(lexicographic order)的方式，雖然可以試完所有的密碼，但並非最快。最快就是每試一組密碼只需要按 2 次按鈕，在密碼學上，這種順序稱作「等權重格雷碼 (Constant Weight Gray Code)」。 另外，若知道某個密碼鎖的密碼是由「1、2、3」組成，但不知道順序的時候，也有同樣的問題。一般我們也是會用字典序的方式來嘗試所有組合： 123->132->213->231->312->321 上面的流程中，132->231 時三個位數都要調整，231->312 時也是，其餘的都是改變兩個位數，但這樣六組密碼試下來，總共改變了 12 個位數。但如果換下面的順序： 312->132->123->321->231->213 這樣，每次只要調整兩個位數(達到最小值)，就可以試完全部的密碼。 我們再仔細觀察，上面這個例子，在 123->321 時，是交換第一位與第三位，如果有辦法每次都只交換「相鄰」兩位數，就可以試完所有排列的話，不就更省時了嗎？下面這個例子就是： 123->213->231->321->312->132 這是著名的「強森托特演算法(Johnson-Trotter algorithm)」，它與格雷碼，或是排列圖上的漢彌爾頓圈也有關係。 格雷碼的應用非常廣，除了解決電子訊號傳遞的問題外，在「九連環」、「河內塔」等數學遊戲上也都與格雷碼有關。我想，這部份就此打住，否則大家心中可能就不只籠罩著<格雷的五十道陰影>了...XD 若讀者沒有時間去嘗試實境密室逃脫的話，其實手機、平板上也有非常多的逃脫遊戲可以玩。當然，在平板上玩，與親身參與實境的 feel 有很大的不同，但在解謎方面，是大同小異的。而且因為是電腦程式，所以會有更多的數學梗出現：解多元一次聯立方程、一筆畫問題、漢彌爾頓路徑、最優分割問題、開關燈問題、完美配對、……等等。筆者推薦兩個個人覺得還不錯的給大家： Doors & Rooms: Apple, Android  Open Puzzle Box: Apple, Android  當我們面臨問題時，其實常常都是正面去迎擊，但往往都會落入謎題設計者的圈套中，此時若能夠利用所學，做個合理的評估，繞道閃過陷阱，反而會更快到達目的地。例如，在密室逃脫時，需要解開某個文學題，才能解開密碼鎖，此時若發現自己應該想不出來，就可以找文學造詣高的隊友來幫忙，或是使用暴力解，或是直接用掉唯一的提示機會。一切都要在短時間做出正確的評估，才能在此分秒必爭的遊戲中，獲得最高的效益。 文末我們來做個小測試，測驗讀者能否跳脫慣性思考。請用四個連續直線段，一筆畫將下圖的九個點連起來。(註：線是沒有寬度的。) 作者簡介 郭君逸 － 國立台灣師範大學數學系助理教授、魔術方塊收藏家 主要研究興趣為組合、圖論、演算法。近年來致力於科普的推廣，喜愛玩各種數學遊戲、益智玩具以及各類型魔術方塊。目前為世界魔方聯盟(WCA)台灣地區認證員。曾開設整個學期的魔術方塊通識課程，跑遍全台進行魔術方塊系列演講。