Josephus Problem

Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 40 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive. How did he did all that?

This problem or its variants are studied for a long time and i have found some formulations from the great book “Concrete Mathematics”, so like to share it with u people.

Lets look that how people get executed if n increases.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Have a look, Voila………. got the pattern. Its a sequence of odd numbers and starts from the start at every power of 2!

Just waiting to formalize it into a mathematical equation.

Advertisements

One comment

  1. Here the direct formula for calculation of position of the person which will survive. If we kill every second person than for N people the position of the surviver p = (N-(2^floor(lg(N))))*2 +1

    Check this out here at this applet!
    http://www.cut-the-knot.org/recurrence/flavius.shtml

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: