4
$\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$
  • 2
    $\begingroup$ You mean wiki explanation in general case is not enough? $\endgroup$ – user742 Nov 30 '12 at 17:43
4
$\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$
  • 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$ – David Richerby Jun 20 '15 at 19:52
  • $\begingroup$ thanks @DavidRicherby , i have updated my answer on this. $\endgroup$ – Sukhmeet Singh Jun 21 '15 at 8:10
0
$\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, privacy policy and cookie policy

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