# complexity theory – How to prove this josephus problem variation is a np-complete or np-intermediate problem?

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 or np-intermediate 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)
``````