0
$\begingroup$

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

People are standing in a circle waiting to be executed. Counting begins at the first point in the circle and proceeds around the circle in a clockwise direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. For example if n=10 then the order of elimination is 2, 4, 6, 8, 10, 3, 7, 1, 9 and 5


 The problem is, without simulation of the above game, try to find out
 the order of elimination through means of mathematical formula or a
 mathematical pattern.

Initially we are given n i.e the number of people in the circle at the start. Give the order of elimination keeping in mind the above conditions and constraints.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

Consider the following 2 cases:

1.There was an even number of people numbered $1,2,3,..,2n$.Now you go around ina circle eliminating people. You are left with $1,3,5,...,2n-1$ which is almost the same as that of n people numbered $1,2,3,...,n$ except that the elements of the former numbering is 2 times that of the later minus 1.

$$f(2n)=2f(n)-1$$

2.If there was an odd number of people numbered $1,2,3,...,2n+1$. Going in a circle again starting from $2$ while eliminating gives us the remaining $3,5,\cdots,2n+1$. Observe that $1$ is eliminated after $2n$ since our starting point was $2$ and $1$ is the last element before we reach $2$. Proceeding in a manner similar to 1 gives us :

$$f(2n+1)=2f(n)+1$$

Now I leave it for you to prove that :

$$f(n)=2(n-2^m)+1$$

where $m=\lfloor {log_2 n}\rfloor$

$\endgroup$
2
  • $\begingroup$ I have tried to use the above relations to program it in C. The problem is, you can't use any data structures like arrays and linked list. If you are able to apply the same logic and code it in C without using data structures, please share the link on ideone. $\endgroup$ Commented Feb 2, 2016 at 18:35
  • $\begingroup$ This seems to be assuming that we skip one person and then execute one person. The OP stated only that we skip "a specified number of people". $\endgroup$
    – Teepeemm
    Commented Jan 30, 2021 at 16:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .