如何证明这个 josephus 问题变体是一个 np 完全问题?

How to prove this josephus problem variation is a np-complete problem?

我有一个 Josephus 问题变体问题。说明如下:

有m张卡片,编号从1到m,每张卡片都有一个唯一的编号。卡片被分发给围成一圈坐着的 n 个人。注意 m >= n.

然后我们选择坐在位置“p”的人“A”出圈,就像约瑟夫斯问题一样。下一步我们跳过p右边的k个人,k是A个人拿的牌数,重复同样的事情,直到圈子里只剩下一个人。

题目给了n个人和m张牌,是否可以选n张牌分配给n个人,使得无论从哪个位置开始(不包括第一个位置),最后存活的人总是圈内第一人

例如m = n = 5,唯一的解就是(4, 1, 5, 3, 2)。

我认为这个问题是一个np完全问题,但是我无法证明。有人有找到多项式时间解或证明它是 np-hard 的好主意吗?

--- 示例解决方案 ---

 2: [ 1,  2]
 2: [ 2,  1]
 3: [ 1,  3,  2]
 3: [ 3,  1,  2]
 4: [ 4,  1,  3,  2]
 5: [ 4,  1,  5,  3,  2]
 7: [ 5,  7,  3,  1,  6,  4,  2]
 9: [ 2,  7,  3,  9,  1,  6,  8,  5,  4]
 9: [ 3,  1,  2,  7,  6,  5,  9,  4,  8]
 9: [ 3,  5,  1,  8,  9,  6,  7,  4,  2]
 9: [ 3,  9,  2,  7,  6,  1,  5,  4,  8]
 9: [ 6,  1,  8,  3,  7,  9,  4,  5,  2]
10: [ 3,  5,  6, 10,  1,  9,  8,  7,  4,  2]
10: [ 4,  5,  2,  8,  7, 10,  6,  1,  9,  3]
10: [ 5,  1,  9,  2, 10,  3,  7,  6,  8,  4]
10: [ 6,  3,  1, 10,  9,  8,  7,  4,  5,  2]
10: [ 8,  5,  9, 10,  1,  7,  2,  6,  4,  3]
10: [10,  5,  2,  1,  8,  7,  6,  9,  3,  4]
11: [ 2,  1, 10, 11,  9,  3,  7,  5,  6,  8,  4]
11: [ 3,  7, 11, 10,  9,  8,  1,  6,  5,  4,  2]
11: [ 3, 11, 10,  9,  8,  1,  7,  2,  4,  5,  6]
11: [ 4,  1, 10,  2,  9,  8,  7,  5, 11,  3,  6]
11: [ 4,  2,  7, 11,  5,  1, 10,  9,  6,  3,  8]
11: [ 4,  7,  2,  3,  1, 10,  9,  6, 11,  5,  8]
11: [ 4,  7,  3,  9, 11, 10,  1,  8,  6,  5,  2]
11: [ 4, 11,  7,  2,  1, 10,  9,  6,  5,  3,  8]
11: [ 5, 11,  3,  9,  8,  7,  6,  1, 10,  4,  2]
11: [ 6,  1, 10,  2,  9,  8,  7,  5, 11,  3,  4]
11: [ 6,  2,  7, 11,  5,  1, 10,  9,  4,  3,  8]
11: [ 6, 11,  1,  3, 10,  2,  7,  5,  4,  9,  8]
11: [ 9,  5,  3,  1, 10,  2,  8,  7, 11,  6,  4]
12: [ 1,  7, 11, 10,  4,  9,  2, 12,  6,  5,  8,  3]
12: [ 3,  7, 12,  2, 11, 10,  9,  1,  6,  5,  4,  8]
12: [ 3,  8, 11,  2, 12,  9,  1,  7,  5, 10,  4,  6]
12: [ 4,  2,  5,  1, 11, 10,  9,  8, 12,  7,  3,  6]
12: [ 4,  3,  7,  6,  1, 11, 10,  9,  8, 12,  5,  2]
12: [ 5,  1,  6, 11,  9,  2, 10,  7, 12,  8,  3,  4]
12: [ 5,  2,  3, 12,  9, 10,  7,  6,  1, 11,  4,  8]
12: [ 5,  7, 12,  2, 10,  9,  8, 11,  1,  4,  6,  3]
12: [ 7,  1,  2,  3,  5,  9, 10,  8, 11,  6, 12,  4]
12: [ 8,  7,  1, 11,  9,  3,  5, 10,  6,  4, 12,  2]
12: [ 8,  7, 11, 10, 12,  3,  1,  9,  6,  5,  4,  2]
12: [12,  3, 11,  5,  1, 10,  8,  7,  6,  4,  9,  2]
12: [12,  7, 11,  1,  9,  3,  2, 10,  6,  5,  4,  8]
13: [ 2,  1,  4,  7, 11,  6,  3, 10, 13,  5,  8, 12,  9]
13: [ 2,  5, 13, 12,  4, 11,  3,  1,  9,  7,  8,  6, 10]
13: [ 2, 13, 12, 11,  3,  1,  9,  4,  8,  7, 10,  5,  6]
13: [ 3,  5,  2,  1, 12,  9, 11, 10,  7,  6, 13,  4,  8]
13: [ 3,  5, 13,  1, 11,  2,  9,  8,  7, 12,  6,  4, 10]
13: [ 4, 13,  3,  1, 12, 11, 10,  9,  7,  2,  5,  6,  8]
13: [ 6,  4,  3,  1, 10, 11, 13,  5,  9, 12,  7,  8,  2]
13: [ 6,  4, 13,  7,  5,  1, 12, 11, 10,  9,  8,  3,  2]
13: [ 6,  7,  3, 13, 12, 11, 10,  2,  1,  9,  5,  4,  8]
13: [ 6,  7, 13, 11,  2, 10,  9,  1,  8, 12,  5,  3,  4]
13: [ 6, 11,  7, 13,  1, 10,  2, 12,  9,  8,  5,  4,  3]
13: [ 7,  3,  2,  1, 11, 10,  9,  8, 13,  5, 12,  4,  6]
13: [ 7,  5, 13,  3, 10, 11,  2,  9,  1,  6,  8,  4, 12]
13: [ 7,  5, 13,  3, 11,  2,  9,  8,  1,  6, 12,  4, 10]
13: [ 7,  5, 13,  3, 11, 12,  2,  1,  9,  8,  6,  4, 10]
13: [ 7,  9,  1, 11,  3, 13,  2, 10, 12,  6,  5,  4,  8]
13: [ 8,  3,  5, 11, 13,  9, 10,  7,  1,  6,  4, 12,  2]
13: [ 8,  3, 13,  1,  5, 11, 10,  9, 12,  7,  6,  4,  2]
13: [ 9,  3, 13,  2, 10,  4,  1,  7,  6,  5, 12, 11,  8]
13: [ 9,  4,  7,  5,  1, 11, 13, 10, 12,  8,  6,  3,  2]
13: [ 9,  5,  4, 13,  2, 11,  8, 10,  1,  7, 12,  3,  6]
13: [ 9,  5, 13,  4, 11,  1,  8,  3,  7, 12,  6, 10,  2]
13: [10,  4,  3,  5, 13,  1,  9, 11,  7,  6,  8, 12,  2]
13: [11,  2,  7,  3, 12,  1, 10,  9,  6,  5, 13,  4,  8]
13: [11, 13,  5,  2, 10,  9,  8,  7,  1,  6,  4,  3, 12]
13: [11, 13,  7,  1, 12,  9,  2,  3, 10,  5,  4,  6,  8]
13: [12,  1,  3,  5, 11, 13,  4, 10,  9,  8,  7,  6,  2]
13: [12,  7, 13,  3, 11,  1,  9,  8,  6,  5, 10,  4,  2]
13: [12, 13,  7, 11,  2,  5,  1,  9, 10,  6,  4,  3,  8]
13: [13,  3,  1, 12, 11,  2,  9, 10,  7,  6,  4,  5,  8]
13: [13,  3,  7,  1,  5, 12,  4, 10,  9,  8, 11,  6,  2]
14: [ 3,  5, 13, 14,  1, 12, 11, 10,  9,  8,  7,  6,  4,  2]
14: [ 3,  9,  1, 13, 11, 10,  2,  4,  7, 14,  6,  8,  5, 12]
14: [ 3, 14,  4, 12, 11,  1,  9,  8,  2, 13,  7,  5, 10,  6]
14: [ 4, 11,  1, 13,  7, 10, 12,  2, 14,  9,  8,  5,  6,  3]
14: [ 4, 14,  2,  5, 13,  1, 12, 11,  7,  6, 10,  9,  3,  8]
14: [ 5,  7,  1, 13, 12, 11, 10,  2,  9,  8, 14,  6,  4,  3]
14: [ 6,  3, 14,  5, 11, 13,  2, 12,  9,  1,  7,  4,  8, 10]
14: [ 6, 14,  1, 12,  5, 13,  2, 11,  9,  7,  8,  4,  3, 10]
14: [ 7,  5, 13, 12,  1, 11,  4, 10,  2, 14,  9,  8,  6,  3]
14: [ 7, 11,  5, 13,  1,  3,  2,  4, 10,  9, 14,  6,  8, 12]
14: [ 7, 14,  1, 13,  2,  5, 11, 12, 10,  9,  8,  4,  3,  6]
14: [ 8,  7,  5, 13,  2, 11,  3,  9, 10, 12,  1, 14,  4,  6]
14: [11,  2, 10,  5,  8,  7,  9,  1, 13, 14, 12,  4,  3,  6]
14: [11,  3, 14,  2, 13,  1, 10,  8,  9,  7,  5, 12,  4,  6]
14: [11,  5,  3, 14,  2,  1, 13, 10,  8,  7,  6, 12,  4,  9]
14: [11, 14,  5,  3, 13,  1, 10,  2,  9,  4,  7,  8, 12,  6]
14: [12,  1, 14,  3, 13,  4, 10,  9,  2,  7,  6,  5, 11,  8]
14: [12, 11,  7,  5, 13,  3,  2, 14,  1,  9,  8,  4,  6, 10]
14: [12, 14,  7, 13,  6,  5, 11,  1, 10,  9,  8,  4,  3,  2]
14: [13,  1,  7,  2, 11,  3,  9, 14,  8,  6,  5, 10,  4, 12]
14: [13, 11,  3,  1,  4,  2,  7, 10,  9,  6, 14, 12,  5,  8]
14: [14,  1, 13,  3, 11,  5, 10,  9,  2,  6,  8,  7,  4, 12]
14: [14, 5, 1, 13, 12, 2, 11, 3, 7, 9, 6, 8, 4, 10]

--- 可能对数学解决方案有帮助 --- 我注意到从长度 9 开始,每个长度至少有一个解决方案有一个较长的整数序列,该序列递减 1。

 9: [3,  1,  2,                               7, 6, 5,    9, 4, 8]  
10: [6,  3,  1,                     10, 9, 8, 7,          4, 5, 2] 
11: [3,  7,                     11, 10, 9, 8,             1, 6, 5, 4, 2]
11: [3,                         11, 10, 9, 8,             1, 7, 2, 4, 5, 6]
11: [5, 11,  3,                         9, 8, 7, 6,       1, 10, 4, 2]
12: [4,  2,  5,  1,             11, 10, 9, 8,            12, 7, 3, 6] 
12: [4,  3,  7,  6, 1,          11, 10, 9, 8,            12, 5, 2] 
13: [6,  4, 13,  7, 5, 1,   12, 11, 10, 9, 8,             3, 2]
14: [3,  5, 13, 14, 1,      12, 11, 10, 9, 8, 7, 6,       4, 2] 

我注意到对于我测试的每个长度,除了非常小的长度,至少有一个解决方案包含相对较长的 运行 降序 数字。到目前为止,这个答案只考虑了 m = n。这里有一些例子;请注意,多余的是 n - run_len:

n = 3, run_len = 2, excess = 1: [1] + [3-2] + []
n = 4, run_len = 2, excess = 2: [4, 1] + [3-2] + []
n = 5, run_len = 2, excess = 3: [4, 1, 5] + [3-2] + []
n = 6, no solution
n = 7, run_len = 1, excess = 6: [5] + [7-7] + [3, 1, 6, 4, 2]
n = 8, no solution
n = 9, run_len = 3, excess = 6: [3, 1, 2] + [7-5] + [9, 4, 8]
n = 10, run_len = 4, excess = 6: [6, 3, 1] + [10-7] + [4, 5, 2]
n = 11, run_len = 4, excess = 7: [3, 7] + [11-8] + [1, 6, 5, 4, 2]
n = 12, run_len = 4, excess = 8: [4, 2, 5, 1] + [11-8] + [12, 7, 3, 6]
n = 13, run_len = 5, excess = 8: [6, 4, 13, 7, 5, 1] + [12-8] + [3, 2]
n = 14, run_len = 7, excess = 7: [3, 5, 13, 14, 1] + [12-6] + [4, 2]
n = 15, run_len = 8, excess = 7: [3, 15, 2] + [13-6] + [1, 5, 4, 14]
n = 16, run_len = 6, excess = 10: [6, 3, 1, 10] + [16-11] + [2, 9, 7, 4, 5, 8]
n = 17, run_len = 8, excess = 9: [2, 5, 17, 15, 14, 1] + [13-6] + [4, 3, 16]
n = 18, run_len = 10, excess = 8: [6, 3, 17, 18, 1] + [16-7] + [5, 4, 2]
n = 19, run_len = 10, excess = 9: [4, 19, 3, 17, 18, 1] + [16-7] + [5, 6, 2]
n = 20, no solution found with run_length >= 10
n = 21, run_len = 14, excess = 7: [3, 21, 2] + [19-6] + [1, 5, 4, 20]
n = 22, run_len = 14, excess = 8: [22, 3, 2, 1] + [20-7] + [5, 21, 4, 6]
n = 23, run_len = 14, excess = 9: [7, 1, 23, 3] + [21-8] + [6, 5, 22, 4, 2]
n = 24, run_len = 16, excess = 8: [6, 5, 24, 2] + [22-7] + [3, 1, 23, 4]
n = 25, run_len = 17, excess = 8: [25, 3, 2, 1] + [23-7] + [5, 24, 4, 6]
n = 26, run_len = 17, excess = 9: [26, 3, 25, 2, 1] + [23-7] + [5, 24, 4, 6]
n = 27, run_len = 20, excess = 7: [3, 27, 2] + [25-6] + [1, 5, 4, 26]
n = 28, run_len = 18, excess = 10: [28, 1, 27, 2, 3] + [25-8] + [6, 5, 7, 4, 26]
n = 29, run_len = 20, excess = 9: [2, 5, 29, 27, 26, 1] + [25-6] + [4, 3, 28]
n = 30, run_len = 23, excess = 7: [30, 5, 2, 1] + [28-6] + [29, 3, 4]
n = 31, run_len = 24, excess = 7: [5, 31, 3] + [29-6] + [1, 30, 4, 2]
n = 32, run_len = 23, excess = 9: [7, 32, 31, 2, 1] + [30-8] + [5, 4, 3, 6]
n = 33, run_len = 26, excess = 7: [3, 33, 2] + [31-6] + [1, 5, 4, 32]
n = 34, run_len = 27, excess = 7: [3, 5, 33, 34, 1] + [32-6] + [4, 2]
n = 35, run_len = 27, excess = 8: [5, 35, 3, 33, 34, 1] + [32-6] + [4, 2]
n = 36, run_len = 26, excess = 10: [35, 7, 3, 1, 36, 2] + [34-9] + [6, 5, 4, 8]
n = 37, run_len = 29, excess = 8: [6, 5, 2, 1] + [35-7] + [36, 37, 3, 4]
n = 38, run_len = 29, excess = 9: [3, 7, 37, 38, 1] + [36-8] + [6, 4, 5, 2]
n = 39, run_len = 32, excess = 7: [3, 39, 2] + [37-6] + [1, 5, 4, 38]
n = 40, run_len = 31, excess = 9: [5, 2, 1] + [38-8] + [3, 7, 40, 4, 6, 39]
n = 41, run_len = 33, excess = 8: [3, 5, 1, 40, 2] + [38-6] + [41, 39, 4]
n = 42, run_len = 33, excess = 9: [42, 3, 41, 2, 1] + [39-7] + [5, 4, 40, 6]
n = 43, run_len = 34, excess = 9: [6, 5, 7, 43, 1] + [41-8] + [42, 4, 3, 2]
n = 44, run_len = 35, excess = 9: [5, 3, 2, 1] + [42-8] + [43, 7, 4, 44, 6]
n = 45, run_len = 38, excess = 7: [3, 45, 2] + [43-6] + [1, 5, 4, 44]
n = 50, run_len = 43, excess = 7: [50, 5, 2, 1] + [48-6] + [49, 3, 4]
n = 100, run_len = 91, excess = 9: [5, 2, 1] + [98-8] + [3, 7, 100, 4, 6, 99]
n = 201, run_len = 194, excess = 7: [3, 201, 2] + [199-6] + [1, 5, 4, 200]
上面的 table 中缺少

20,因为 运行 长度最多为 10,并且需要很长时间来计算。我测试过的更大的值都没有这么小的最大 运行 长度相对于 n.

我通过检查 运行 从 n-1 降序的长度找到这些,以及 运行 和周围元素的所有可能的起始值和排列。这极大地减少了搜索 space。

对于给定的 n,如果 n 的任何解中的最大值 运行 的长度为 n-k,那么这将在 O(k! * n) 中找到它。虽然这看起来很严峻,但如果 k 有一个恒定的上限(例如,对于所有足够大的 n,k <= 某个阈值)那么这实际上是 O(n)。 'Excess' 就是我在上面的例子中所说的 k 。我还没有找到任何大于10的,但我还没有n = 20的解决方案。如果有解决方案,那么它的多余部分将超过10。

更新:这里有很多模式。

如果 n mod6 为 3 且 n >= 9,则 [3, n, 2, [n-2, n-3, ..., 6], 1, 5, 4 , n-1]有效.

如果 n mod 12 是 5 并且 n >= 17 那么 [2, 5, n, n-2, n-3, 1, [n-4, n-5, ... , 6], 4, 3, n-1] 有效。

若nmod20为10,则[n,5,2,1,[n-2,n-3,...,6],n-1,3,4]有效。

如果nmod60为7、11、31或47,则[5,n,3,[n-2,n-3,...,6],1,n -1, 4, 2] 有效。

如果 n mod 60 是 6 或 18 并且 n >= 18 那么 [6, 3, n-1, n, 1, [n-2, n-3, ..., 7 ], 5, 4, 2] 有效。

如果 n mod 60 是 1、22、25 或 52 并且 n >= 22 那么 [n, 3, 2, 1], [n-2, n-3, ..., 7], 5, n-1, 4, 6] 有效。

如果 n mod 60 是 23 那么 [7, 1, n, 3, [n-2, n-3, ..., 8], 6, 5, n-1, 4 , 2]有效。

如果 n mod60 是 14 或 34 那么 [3, 5, n-1, n, 1, [n-2, n-3, ..., 6], 4, 2 ] 有效。

如果 n mod60 是 24 那么 [6, 5, n, 2, [n-2, n-1, ..., 7], 3, 1, n-1, 4 ]有效

如果 n mod 60 是 2, 6, 26, 42 并且 n >= 26 那么 [n, 3, n-1, 2, 1, [n-3, n-4, . .., 7], 5, n-2, 4, 6] 有效。

如果 n mod60 是 16 或 28 那么 [n, 1, n-1, 2, 3, [n-3, n-4, ..., 8], 6, 5 , 7, 4, n-2] 有效。

如果 n mod 60 是 32 那么 [7, n, n-1, 2, 1, [n-2, n-3, ..., 8], 5, 4, 3 , 6] 有效.

如果 n mod 60 是 35 或 47 那么 [5, n, 3, n-2, n-1, 1, [n-3, n-4, ..., 6] , 4, 2] 有效。

如果 n mod 60 是 37 那么 [6, 5, 2, 1, [n-2, n-1, ..., 7], n-1, n, 3, 4 ]

如果 n mod 60 是 38 那么 [3, 7, n-1, n, 1] + [n-2, n-3, ..., 8] + [6, 4 , 5, 2]

如果 n mod 60 是 40 那么 [5, 2, 1, [n-2, n-3, ..., 8], 3, 7, n, 4, 6, n -1] 有效

如果 n mod 60 为 0 且 n >= 60,则 [3, 5, n, 2, [n-2, n-3, ..., 7], 1, 6, n-1, 4] 有效

如果 n mod 60 是 7、19 或 31 且 n >= 19,则 [4, n, 3, n-2, n-1, 1, [n-3, n- 4, ..., 7], 5, 6, 2] 有效

如果 n mod60 是 23、38 或 43,则 [7、3、n、1、[n-2、n-3、...、8]、6、5、 n-1, 4, 2] 是一个有效的解决方案

如果 n mod 60 是 14 或 44 并且 n >= 74 那么 [3, 5, n-1, n, 1, [n-3, n-4, ..., 6 ], n-2, 4, 2] 有效。

如果 n mod 60 是 1 或 49 并且 n >= 49 那么 [3, 5, n, 1, [n-2, n-3, ..., 7], 2, n-1, 4, 6] 有效。

如果 n mod 60 为 6、18、30、42 或 54 且 n >= 18,则 [n, 3, n-1, 2, 1, [n-3, n- 4, ..., 7], 5, 4, n-2, 6] 有效。

如果 n mod 60 为 10、18、38 或 58 且 n >= 18,则 [n-1, 7, 5, n, 1, [n-2, n-3, . .., 8], 2, 6, 4, 3] 有效。

当前求解的 n mod 60 是以下任何值:

 0,  1,  2,  3,      5,  6,  7,      9, 
10, 11,         14, 15, 16, 17, 18, 19,
    21, 22, 23, 24, 25, 26, 27, 28, 29, 
30, 31, 32, 33, 34, 35,     37, 38, 39, 
40, 41, 42, 43, 44, 45,     47,     49,
50, 51, 52, 53, 54,         57, 58

此外,

如果 n mod42 是 31 那么 [n, 3, 2, 1, [n-2, n-3, ..., 8], n-1, 5, 4, 7 , 6] 有效.

如果 n mod 420 是 36 或 396 那么 [n-1, 7, 3, 1, n, 2, [n-2, n-3, ..., 9], 6 , 5, 4, 8] 有效。

--- n=21 的示例,使用上面列出的第一个模式和所有起始索引。

1:  [21,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
2:  [ 2, 18, 21, 16, 19, 14, 17, 12, 15, 10, 13,  8, 11, 6, 9, 5, 1,  4, 20,  7]
3:  [19, 21, 18,  2, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
4:  [18, 21, 19, 17,  2, 15, 16, 13, 14, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
5:  [17, 21, 19, 18, 16,  2, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
6:  [16, 21, 19, 18, 17, 15,  2, 13, 14, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
7:  [15, 21, 19, 18, 17, 16, 14,  2, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
8:  [14, 21, 19, 18, 17, 16, 15, 13,  2, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
9:  [13, 21, 19, 18, 17, 16, 15, 14, 12,  2, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
10: [12, 21, 19, 18, 17, 16, 15, 14, 13, 11,  2,  9, 10, 7, 8, 1, 5,  4, 20,  6]
11: [11, 21, 19, 18, 17, 16, 15, 14, 13, 12, 10,  2,  8, 9, 6, 7, 5,  4, 20,  1]
12: [10, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11,  9,  2, 7, 8, 1, 5,  4, 20,  6]
13: [ 9, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  8, 2, 6, 7, 5,  4, 20,  1]
14: [ 8, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 7, 2, 1, 5,  4, 20,  6]
15: [ 7, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 6, 2, 5,  4, 20,  1]
16: [ 6, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 1, 5,  4, 20,  2]
17: [ 1,  5,  2, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 6, 4, 19, 20, 21]
18: [ 5,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 4,  1, 20, 21]
19: [ 4,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5, 20, 21,  1]
20: [20,  4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 6, 1,  5, 21,  2]

对于模式适用的所有 n 值,您可以观察到递减 运行 中的元素与其他元素之间的相同关系。这不是一个证明,但你可以把它变成一个证明,尽管我认为这项工作需要分别为每个模式完成,而且它超出了我要花时间讨论 S/O问题。

--- 我们可以使用 m > n 来填空。 ---

模式 [n-1, n, 1, [n-2, n-3, ..., 3], n+5] 对 n 有效 mod 4 是 1 和 n >= 9.

模式 [n, 2, 1, [n-2, n-3, ..., 3], n+4] 对 n 有效 mod 2 为 0 且 n >= 6.

有了这两个,加上我们已经找到的东西,我们几乎得到了一切。我通过检查有限范围内的单个替换值找到了这些。

 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54,     56, 57, 58

如果nmod30为29,则[3,n,2,[n-2,n-3,...,4],n-1,n+15)有效,给我们 n mod 60 是 59。我们只剩下一个未知数:n mod 60 是 55.

...终于!如果 n mod 12 为 7(即 n mod 60 为 7、19、31、43 或 55),则 [n-1, n, 1, [n-2, n-3, ..., 6], 2, 5, 3, n+4] 对所有 n >= 19.

有效

我们现在有所有 n mod 60 的解决方案,在大多数情况下使用 m=n,在最坏的情况下使用 m=n+15。