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

Question

I have a problem that is a Josephus problem variation. It is described below:

There are m cards with number from 1 to m，and each of them has a unique number. The cards are dispatched to n person who sit in a circle. Note that m >= n.

Then we choose the person "A" who sits at the position "p" to out of the circle, just like the Josephus problem does. Next step we skip "k" person at the right of p while k is the number of the card toked by the person "A", and we do the same thing until only one person left in the circle.

Question is given n person and m cards, can we choose n cards and allocate them to the n person, to make that whether start at which position(exclude the first position), the person survival at the end is always the first person in the circle.

For example, m = n = 5, the only solution is (4, 1, 5, 3, 2).

I think this problem is a np-complete problem, but I can't prove it. Anybody has a good idea to find a polynomial time solution or prove it's np-hard?

--- example solutions ---

 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]

--- possibly helpful for a mathematical solution --- I noticed that starting with length 9, at least one solution for every length has a longish sequence of integers that decrement by 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]

@kaya3 I can't find a polynomial time solution, but I'm not sure, it's just a guess. — Xudong Chen, Jul 12 '21 at 10:28
@kaya3 Unlike the traditional Josephus problem, I can't divide it to sub problems, because the step is dynamic and the start position is uncertainly. I can only use permutation to list all situation and check all of them, it has about n! complexity. — Xudong Chen, Jul 12 '21 at 10:44
It's certainly in NP, but by Mahaney's theorem it's unlikely to be complete. — David Eisenstat, Jul 12 '21 at 10:55
@DavidEisenstat Yes. I find it is difficult to reduce from other np-complete problems, but also hard to solve it. — Xudong Chen, Jul 12 '21 at 11:02
How does the dispatching of cards work when m is less than n? What happens if somebody is shot who doesn't hold a card? Or is it a requirement that m >= n, or is the answer just "no, we can't allocate cards" in that case? I'm not seeing why this should be in NP at all. — kaya3, Jul 12 '21 at 11:06
@kaya3 oh, I forgot a point that m >= n, so everyone holds a card. — Xudong Chen, Jul 12 '21 at 11:09
OK, and the cards are numbered from 1 to m, so if there is a solution for some m then the same solution works for all m' > m, right? So if a solution can be found for m = n then there is no need to consider m at all. — kaya3, Jul 12 '21 at 11:10
OK, well there are a *lot* of permutations of 1 to n, and you only need to find one which works, so I suggest start by trying to solve it for the case m = n. — kaya3, Jul 12 '21 at 11:20
@kaya3 Do you have some fast solutions? let m = n, list all the permutations and check them has about n! complexity. — Xudong Chen, Jul 12 '21 at 11:27
Do you mean that the goal is to find a configuration such that for *any* start position 2..N the remaining person is always at position 1? — n. m. could be an AI, Jul 12 '21 at 11:54
@n.1.8e9-where's-my-sharem. Yes, in my question, the person is the first person. — Xudong Chen, Jul 12 '21 at 11:56
It may be that the number of solutions is high enough that backtracking search works in much better than O(n!) time. But instead of thinking about algorithms to search for a solution, you should think about how to construct a solution. Treat it like a pen and paper problem, how would you do it by hand? — kaya3, Jul 12 '21 at 12:33
To be NP.-complete you should be able to check your solution in a "quick"(NP?) way, can you that? — Surt, Jul 13 '21 at 13:33
@Surt Yes, checking a solution is quick, this problem is certainly in NP. — Xudong Chen, Jul 13 '21 at 16:57
I don't know if this will help, but I noticed that for every length starting with 9, one of the solutions has a run of decrementing values that is surprisingly long, and the length grows as the inputs grow. E.g., 14: [3, 5, 13, 14, 1, 12, 11, 10, 9, 8, 7, 6, 4, 2] contains 12, 11, 10, 9, 8, 7, 6 — Dave, Jul 16 '21 at 14:27
By searching for long descending runs, we can find answers that would naively take a long time. E.g., for a length of 25, the longest run in any solution is length 17: [25, 3, 2, 1, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 5, 24, 4, 6]. This doesn't help with the efficiency (O-notation) unless we have a guarantee about the length of the run growing sufficiently quickly with n. — Dave, Jul 16 '21 at 19:48
n=30, run_len = 23: [30, 5, 2, 1, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 29, 3, 4] — Dave, Jul 16 '21 at 19:50
n=35, run_len = 27: [5, 35, 3, 33, 34, 1, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 4, 2] — Dave, Jul 16 '21 at 19:51
@DavidEisenstat It looks like this may be O(1) where every value of n mod 60 has a solution expressable in constant time & space (with a long run of decrementing integers). I'm putting these at the bottom of my answer. — Dave, Jul 17 '21 at 06:27
Cross-posted: https://stackoverflow.com/q/68345550/781723, https://cs.stackexchange.com/q/142411/755, https://cstheory.stackexchange.com/q/49277/5038. Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). — D.W., Jul 19 '21 at 05:19

Dave · Accepted Answer · 2021-07-22T12:33:46.760

I noticed that for every length I tested except the very small, at least one solution contains a relatively long run of descending numbers. So far this answer only considers m = n. Here are a few examples; note that excess is 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]

20 is missing from the above table because the run length is at most 10, and is taking a long time to compute. No larger value that I've tested has such a small max run length relative to n.

I found these by checking run lengths from n-1 descending, with all possible starting values and permutations of the run & surrounding elements. This reduces the search space immensely.

For a given n, if the max run in any solution to n is length n-k, then this will find it in O(k! * n). While this looks grim, if k has a constant upper bound (e.g. k <= some threshold for all sufficiently large n) then this is effectively O(n). 'Excess' is what I'm calling k in the examples above. I haven't found any greater than 10, but I don't have a solution yet to n = 20. If it has a solution then its excess will exceed 10.

UPDATE: There are a lot of patterns here.

If n mod 6 is 3 and n >= 9, then [3, n, 2, [n-2, n-3, ..., 6], 1, 5, 4, n-1] is valid.

If n mod 12 is 5 and n >= 17 then [2, 5, n, n-2, n-3, 1, [n-4, n-5, ..., 6], 4, 3, n-1] is valid.

If n mod 20 is 10, then [n, 5, 2, 1, [n-2, n-3, ..., 6], n-1, 3, 4] is valid.

If n mod 60 is 7, 11, 31, or 47, then [5, n, 3, [n-2, n-3, ..., 6], 1, n-1, 4, 2] is valid.

If n mod 60 is 6 or 18 and n >= 18 then [6, 3, n-1, n, 1, [n-2, n-3, ..., 7], 5, 4, 2] is valid.

If n mod 60 is 1, 22, 25 or 52 and n >= 22 then [n, 3, 2, 1], [n-2, n-3, ..., 7], 5, n-1, 4, 6] is valid.

If n mod 60 is 23 then [7, 1, n, 3, [n-2, n-3, ..., 8], 6, 5, n-1, 4, 2] is valid.

If n mod 60 is 14 or 34 then [3, 5, n-1, n, 1, [n-2, n-3, ..., 6], 4, 2] is valid.

If n mod 60 is 24 then [6, 5, n, 2, [n-2, n-1, ..., 7], 3, 1, n-1, 4] is valid

If n mod 60 is 2, 6, 26, 42 and n >= 26 then [n, 3, n-1, 2, 1, [n-3, n-4, ..., 7], 5, n-2, 4, 6] is valid.

If n mod 60 is 16 or 28 then [n, 1, n-1, 2, 3, [n-3, n-4, ..., 8], 6, 5, 7, 4, n-2] is valid.

If n mod 60 is 32 then [7, n, n-1, 2, 1, [n-2, n-3, ..., 8], 5, 4, 3, 6] is valid.

If n mod 60 is 35 or 47 then [5, n, 3, n-2, n-1, 1, [n-3, n-4, ..., 6], 4, 2] is valid.

If n mod 60 is 37 then [6, 5, 2, 1, [n-2, n-1, ..., 7], n-1, n, 3, 4]

If n mod 60 is 38 then [3, 7, n-1, n, 1] + [n-2, n-3, ..., 8] + [6, 4, 5, 2]

If n mod 60 is 40 then [5, 2, 1, [n-2, n-3, ..., 8], 3, 7, n, 4, 6, n-1] is valid

If n mod 60 is 0 and n >= 60 then [3, 5, n, 2, [n-2, n-3, ..., 7], 1, 6, n-1, 4] is valid

If n mod 60 is 7, 19, or 31 and n >= 19 then [4, n, 3, n-2, n-1, 1, [n-3, n-4, ..., 7], 5, 6, 2] is valid

If n mod 60 is 23, 38, or 43 then [7, 3, n, 1, [n-2, n-3, ..., 8], 6, 5, n-1, 4, 2] is a valid solution

If n mod 60 is 14 or 44 and n >= 74 then [3, 5, n-1, n, 1, [n-3, n-4, ..., 6], n-2, 4, 2] is valid.

If n mod 60 is 1 or 49 and n >= 49 then [3, 5, n, 1, [n-2, n-3, ..., 7], 2, n-1, 4, 6] is valid.

If n mod 60 is 6, 18, 30, 42, or 54 and n >= 18 then [n, 3, n-1, 2, 1, [n-3, n-4, ..., 7], 5, 4, n-2, 6] is valid.

If n mod 60 is 10, 18, 38 or 58 and n >= 18 then [n-1, 7, 5, n, 1, [n-2, n-3, ..., 8], 2, 6, 4, 3] is valid.

Currently solved for n mod 60 is any of the following values:

 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

Also,

If n mod 42 is 31 then [n, 3, 2, 1, [n-2, n-3, ..., 8], n-1, 5, 4, 7, 6] is valid.

If n mod 420 is 36 or 396 then [n-1, 7, 3, 1, n, 2, [n-2, n-3, ..., 9], 6, 5, 4, 8] is valid.

--- Example for n=21, using the first pattern listed above, and all starting indices.

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]

You can observe the same relationship between elements from the decrementing run and other elements for all values of n that the pattern applies to. This isn't a proof, but you can turn this into a proof, though I think the work would need to be done for each pattern separately and it's beyond the scope of what I'm going to spend time on for an S/O question.

--- We can fill in the blanks by using m > n. ---

The pattern [n-1, n, 1, [n-2, n-3, ..., 3], n+5] is valid for n mod 4 is 1 and n >= 9.

The pattern [n, 2, 1, [n-2, n-3, ..., 3], n+4] is valid for n mod 2 is 0 and n >= 6.

With these two, plus what we already found, we get nearly everything. I found these by checking a single replacement value in a limited range.

 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

If n mod 30 is 29, then [3, n, 2, [n-2, n-3, ..., 4], n-1, n+15) is valid, giving us n mod 60 is 59. We're left with just one unknown: n mod 60 is 55.

...And finally! If n mod 12 is 7 (i.e. n mod 60 is 7, 19, 31, 43, or 55) then [n-1, n, 1, [n-2, n-3, ..., 6], 2, 5, 3, n+4] is valid for all n >= 19.

We now have solutions for all n mod 60, using m=n in most cases, and m=n+15 in the worst case.

@XudongChen I found them by checking for values of n <= 1000. If you need to ensure they work for arbitrarily large n then you'll need a math proof. If n is capped then you can exhaustively check for all valid n. If none of those are possible, you can check for each specific n when a request comes in. — Dave, Jul 18 '21 at 12:02
The way these work is that once you enter the decrementing segment, you stay in it until it's used up. I'll add an example. — Dave, Jul 18 '21 at 13:41
The patterns are useful to prove the existence of solution, but may have trouble when has no solution. For example, when n = 20, we don't find solutions match the patterns, but we can't say it has no solution. — Xudong Chen, Jul 19 '21 at 00:56
@XudongChen You can use the added flexibility you have to let m > n, and for the n where we have no solution, search for the least m that would allow for a solution. If you limit this to replacements that allow for a long decrementing run, the search space isn't intractably large. — Dave, Jul 19 '21 at 12:23
@XudongChen We're good for 59 out of every 60 possible inputs. I've found some solutions for 55, but nothing that repeats nicely. We might need to swap out more than one element to find something stable. — Dave, Jul 19 '21 at 19:47
@XudongChen By using m > n, I was able to solve for everything. — Dave, Jul 19 '21 at 21:11

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

1 Answers1