主题
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 暗示了上面的闭式解。


另请参阅

柯克曼女学生问题, 项链

使用 Wolfram|Alpha 探索

参考文献

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

在 Wolfram|Alpha 中引用

约瑟夫问题

请引用为

Weisstein, Eric W. "约瑟夫问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/JosephusProblem.html

主题分类