這非常難的數學問題可以拯救你的生命

    加入我們永遠收到最新的消息

josephusproblem

最有價值的數學問題剛開始看起來非常簡單,當你試過並理解它們,然後用熟練的方法解答它們時會變得非常棘手,但是最著名的約瑟夫問題(Josephus problem)點出了這三種情形,就像在Numberphile下面的影片所示。

這個問題的名字來自第一世紀猶太人學者Titus Flavius Josephus

故事說,他和其他40名猶太軍人一起被入侵的羅馬軍人包圍,想像在權力遊戲中的場景,當拉姆斯波顿用圍成一個圓圈設下陷阱,將瓊恩雪諾的軍隊包圍,並開始進攻。

josephus620

比起放棄投降,這些軍人寧願集體自殺,但是是透過互殺而不是自殺,以避免有人在最後一刻改變心意,他們圍成一圈坐著,第一個軍人會殺死他左邊的人,下一個活著的軍人也可以殺他左邊的人,依此類推。

當屠殺的循環再次回到原點,下個過程中只剩下少數的人重複循環,最終,活下來的軍人將被自己的劍刺穿。

約瑟夫的問題是,他渴望生甚於死,但他不想讓其他的軍人知道這個秘密,所以他要把他自己放在圓圈的哪裡才能是最後存活的人呢?

答案是:第19個位置,但是你要如何得到這個數字,而且你要如何計算出不同數量的軍人,這確實是相當有趣的問題,就像威斯康辛大學麥迪遜分校的Daniel Eramn所拍攝的影片中說明的

josephusproblem-1

第一次輪的循環時,很明顯地,每個人站在偶數號碼位置的人都會得到可怕的結局,所以假如你想要生存下來,第一件事就是得到奇數號碼的位置。

但是當圓圈回歸原點時,會有新的一組人又獲得了致命的雙數號碼。

下一個要注意的是假如軍人選的數字是2的倍數(如1,2,4,8,16,32,64等等)。然後坐的位置是第一個位置,開始殺戮的起點1。

想想看,如果是兩個人,1殺2,如果是4個人,1殺2,3殺4,然後1殺3,不管是2的多少倍,因為1號永遠重覆這個循環。

josephusproblem2

當每執行完一輪之後,你又重新回到另一個2的倍數,而1號軍人又再一次安全,直到他是唯一存活的人,這個循環每次執行都會將人數減半。

計算2的倍數是整個問題的關鍵,如你在影片中所看到的,計算出多少額外的人需要和最接近2的倍數的數字相比較,然後算出可以救命的方法。

在最後的公式中,這個額外的數字被標記為「I」,而且所在的位置是(2xI)+1。

換句話說,無論開始的時候有多少人,你都要確保你在第1個位置,當圓圈縮小到2的倍數時,像16或32,你要將I重複,因為其他的軍人都被殺了。

Image result for Josephus Problem (2xI)+1

所以約瑟夫需要坐在第19個位置,32是我們最接近最低的2的倍數,這裡有9個額外的人,而(2×9)+1是19,約瑟夫是這個關鍵的數字1,當圓圈開始轉換為2的倍數時,在這裡是32,所以說他會一直是1號,直到其他人都被殺了,這是依據我們所知的情況所計算出來的。

下面的影片比我們解釋得更清楚,而且增加了一個聰明的2進位的花招去計算,試著去記住這些規則,當下次你面臨一個集體自殺的情形,也許可以救你一命。

來源:Ancient-code