主題
Search

約瑟夫問題


JosephusDecimation

給定一組 n 人,他們圍成一個圓圈,並頒佈法令,每數到第 m 個人將被處決,沿著圓圈進行,直到只剩下一個人為止。找到為了成為最後的倖存者,你應該站在哪個位置 L(n,m) (Ball and Coxeter 1987)。給出第一個、第二個等人的處決順序的列表可以用下式表示Josephus[n, m] 在 Wolfram Language 包中Combinatorica`. 例如,考慮 n=4 個人,編號為 1 到 4,每數到第二個人 (m=2) 就迭代地處死,如上圖所示。可以看出,第一個人是第 4 個被處死的,第二個人是第 1 個,第三個人是第 3 個,第四個人是第 2 個,所以Josephus[4, 2] 返回 {4, 1, 3, 2}

要獲得連續被處死的人的有序列表,InversePermutation可以應用於以下輸出Josephus所以,在上面的例子中,4, 2]]返回 {2, 4, 3, 1},因為第 2 個人是第一個被處死的,第 4 個人是第二個被處死的,第 3 個人是第三個被處死的,第 1 個人是第四個被處死的。

Josephus41-3

最初的約瑟夫問題是由 41 個人圍成一個圓圈,每數到第三個人就被殺死 (n=41, m=3),如上圖所示,外面的數字表示給定的人被殺死的順序。為了讓最後兩個人的生命得以倖免,他們必須被安排在位置 31 (最後) 和 16 (倒數第二)。完整的處決順序列表是 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16, 31。

Josephus30-9

該問題的另一個版本考慮由兩組(例如,“A” 和 “B”)各 15 人組成的圓圈(總共 30 人),每數到第九個人就被扔下船,如上圖所示。為了拯救 “A” 組的所有成員,這些人必須被安排在位置 1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29。明確寫出,順序是

 AAAABBBBBAABAAABABBAABBBABBAAB.
(1)

這個字母序列可以用助記符 “From numbers' aid and art, never will fame depart.” 來記住。只考慮母音,賦值 a=1, e=2, i=3, o=4, u=5,並交替新增與母音值對應的字母數量,例如 4A (o), 5B (u), 2A (e) 等 (Mott-Smith 1954, §149, pp. 94 和 209-210; Ball and Coxeter 1987)。

Josephus30-10

如果改為每個人被扔下船,則 “A” 組的人員必須安排在位置 1, 2, 4, 5, 6, 12, 13, 16, 17, 18, 19, 21, 25, 28, 29。明確寫出,

 AABAAABBBBBAABBAAAABABBBABBAAB
(2)

這可以使用拉丁助記符 “Rex paphi cum gente bona dat signa serena” 來構建 (Ball and Coxeter 1987)。

下表給出了從 n=1, 2, ..., 人組中最後倖存者的原始位置,如果每數到第 m 個人被殺死,其中 m=1, 2, ..., n

 1         ; 2 1        ; 3 3 2       ; 4 1 1 2      ; 5 3 4 1 2     ; 6 5 1 5 1 4    ; 7 7 4 2 6 3 5   ; 8 1 7 6 3 1 4 4  ; 9 3 1 1 8 7 2 3 8 ; 10 5 4 5 3 3 9 1 7 8
(3)

(OEIS A032434)。對於 m=2 的倖存者可以用解析式給出

 L(n,2)=1+2n-2^(1+|_lgn_|),
(4)

其中 |_n_|向下取整函式lg 是以 2 為底的對數。因此,前幾個解是 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, ... (OEIS A006257)。

下表給出了 n=2, 3, ... 組中倒數第二個倖存者的原始位置。

 1 2        ; 2 1 1       ; 3 3 4 3      ; 4 5 2 2 4     ; 5 1 5 6 3 5    ; 6 3 1 3 1 4 4   ; 7 5 4 7 6 2 3 7  ; 8 7 7 2 2 8 1 6 7 ; 9 9 10 6 7 4 8 4 6 4
(5)

(OEIS A032435)。

下表給出了 n=3, 4, ... 組中倒數第三個倖存者的原始位置。

 1 2 3       ; 2 4 2 1      ; 3 1 5 5 3     ; 4 3 2 3 2 2    ; 5 5 5 7 7 1 2   ; 6 7 8 3 4 7 1 2  ; 7 9 2 7 9 4 8 1 2 ; 8 1 5 1 4 10 5 9 1 7
(6)

(OEIS A032436)。

Mott-Smith (1954, §153, pp. 96 和 212) 討論了一種名為 “Out and Under” 的紙牌遊戲,其中一副牌頂部的牌交替地被丟棄並放在底部。這是一個引數為 m=2 的約瑟夫問題,Mott-Smith 暗示了上面的閉式解。


另請參閱

柯克曼女學生問題, 項鍊

使用 探索

參考文獻

Bachet, C. G. Problem 23 in Problèmes plaisans et délectables, 2nd ed. p. 174, 1624.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 32-36, 1987.Ballew, P. "The Josephus Problem." http://www.pballew.net/josephus.html.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Kraitchik, M. "Josephus' Problem." §3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.Mott-Smith, G. "Decimation Puzzles." Ch. 9, §149-154 in Mathematical Puzzles for Beginners and Enthusiasts, 2nd rev. ed. New York: Dover, pp. 94-97 and 209-214, 1954.Odlyzko, A. M. and Wilf, H. S. "Functional Iteration and the Josephus Problem." Glasgow Math. J. 33, 235-240, 1991.Skiena, S. "Josephus' Problem." §1.4.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 34-35, 1990.Sloane, N. J. A. Sequences A006257/M2216, A032434, A032435, and A032436 in "The On-Line Encyclopedia of Integer Sequences."Update a linkSmith, H. J. "Josephus Permutation Problems." http://www.geocities.com/hjsmithh/Josephus.html

在 中引用

約瑟夫問題

請引用為

Weisstein, Eric W. "約瑟夫問題。" 來自 Web 資源。 https://mathworld.tw/JosephusProblem.html

主題分類