7
$\begingroup$

The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".

The following recursive formula is given: $$\begin{align} f(1,k)&=1, \\ f(n,k)&=((f(n-1,k)+k-1) \bmod n )+1. \end{align}$$

But this is not enough explanation, so I don't get where does it come from.

Can anyone help?

$\endgroup$
1
  • 2
    $\begingroup$ You mean wiki explanation in general case is not enough? $\endgroup$
    – user742
    Commented Nov 30, 2012 at 17:43

2 Answers 2

6
$\begingroup$

Let me explain the idea. Assume that indices start from 0. Take N = 6 and K = 3 So initial arrangement looks something like

0->1->2->3->4->5->0.... like a circle.

After round 1 , '2' is eliminated .

0->1->2->3->4->5->0->1...

....(k)->0->1->2->3->

here (k) denotes the person is killed

Since we ought to start from the last position we killed, so lets look at the updated indices.

Old Index | New Index

3 | 0

4 | 1

5 | 2

and so on.... looking closely we can easily see after each round

OldPosition = (newPosition+k)mod N

Where N is the number of people left before the round started.

Also OldPosition signifies f(N,K)

and New Position signifies f(N-1,K) as one person has already been killed.

So putting it back to OldPostion = (newPostion+k) mod N we get

f(N,K) = ( f(N-1,K)+ K ) mod N

But this is done only if u have indices starting from 0. If u want to rearrange for indices starting from 1, you can rearrange it to get the above result.

I found a beautiful paper on this

http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf

Hope this helps :)

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to Computer Science! We aim to be a source of information, rather than just a link farm so it would be great if you could at least summarize the contents of the paper and explain how it answers the question. $\endgroup$ Commented Jun 20, 2015 at 19:52
  • $\begingroup$ thanks @DavidRicherby , i have updated my answer on this. $\endgroup$ Commented Jun 21, 2015 at 8:10
  • $\begingroup$ For the rearrange part, could put it this way: If index start from 1, then just add 1 to the result when index start from 0. Similarly, if index start from t, just add t to the result when index start from 0. $\endgroup$
    – Eric
    Commented Aug 17, 2020 at 9:32
1
$\begingroup$

Knuth goes through this in the first chapter of his classic math textbook, Concrete Mathematics. His treatment is very understandable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.