Josephus problem


Josephus problem

The Josephus problem (or sometimes Josephus permutation) is a theoretical problem occurring in computer science and mathematics.

There are n people standing in a circle waiting to be executed. After the first man is skipped, k-2 people are skipped (skipping over k-1 people set you over the "k"-th man) and the "k"-th man is executed. Then again, k-1 people are skipped and the "k"-th man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining), given n and k.

History

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As his own account goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they would draw lots to determine who would kill whom. Josephus and one other man were the last remaining. Josephus convinced the other Jew that they should both surrender to the Romans rather than kill themselves. Josephus attributed his survival to luck or to Providence, he knew not which. [The War of the Jews 3.387-391]

Solution

We explicitly solve the problem when every 2nd person will be killed, i.e. k=2. (For the more general case k eq 2, we outline a solution below.)We express the solution recursively. Let f(n) denote the position of the survivor when there are initially n people (and k=2).The first time around the circle, all of the even-numbered people die.The second time around the circle, the new 2nd person dies, then the new 4th person, etc; it's as though there were no first time around the circle. If the initial number of people was even, then the person in position x during the second time around the circle was originally in position 2x - 1 (for every choice of x). So the person in position f(2n) was originally in position 2f(n) - 1. This gives us the recurrence:

: f(2n)=2f(n)-1.,

If the initial number of people was odd, then we think of person 1 as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc.In this case, the person in position x was originally in position 2x+1. This gives us the recurrence:

:f(2n+1)=2f(n)+1.,

When we tabulate the values of n and f(n) we see a pattern:

This suggests that f(n) is an increasing odd sequence that restarts with f(n)=1 whenever the index "n" is a power of 2.Therefore, if we choose m and l so that n=2^m+l and 0leq l<2^m, then f(n)=2 cdot l+1.It is clear that values in the table satisfy this equation. But mathematics demands exact proof. Below, we give a proof by induction.

Theorem: If n=2^m+l and 0leq l<2^m, then f(n) = 2l+1.

Proof: We use strong induction on n. The base case n=1 is true.We consider separately the cases when n is even and when n is odd.

If n is even, then choose l_1 and m_1 such that n/2 = 2^{m_1}+l_1 and 0leq l_1 < 2^{m_1}. Note that l_1 = l/2. We have f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1, where the second equality follows from the induction hypothesis.

If n is odd, then choose l_1 and m_1 such that (n-1)/2 = 2^{m_1}+l_1 and 0leq l_1 < 2^{m_1}. Note that l_1 = (l-1)/2. We have f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1, where the second equality follows from the induction hypothesis. This completes the proof.

The most elegant form of the answer involves the binary representation of size n: f(n) can be obtained by a one-bit left cyclic shift of n itself. If we represent n in binary as n=b_0 b_1 b_2 b_3dots b_m, then the solution is given by f(n)=b_1 b_2 b_3 dots b_m b_0. The proof of this follows from the representation of n as 2^m+l.

The easiest way to solve this problem in the general case is to use dynamic programming. This approach gives us the recurrence:

f(n,k)=(f(n-1,k)+k) mod n, with f(1,k)=0

which is evident when considering how the survivor number changes when switching from n-1 to n. This approach has running time O(n), but for small k and large n there is another approach. The second approach also uses dynamic programming but has running time O(klog n). It is based on considering killing "k"-th, 2"k"-th, ..., 2lfloor n/k floor-th people as one step, then changing the numbering.

Variants

According to Concrete Mathematics, section 1.3, Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival).

References

Notes

Others

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.

External links

* [http://www.cut-the-knot.org/recurrence/flavius.shtml Josephus Flavius game] (Java Applet) at cut-the-knot;
*
* [http://mathdl.maa.org/mathDL/3/?pa=content&sa=viewDocument&nodeId=322 Josephus Problem at Shippensburg University] .
* [http://www.apuzzleaday.org/puzzle/puzzle.php?ID=94.html Josephus Problem at APuzzleADay] .


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Josephus-Problem — Das Josephus Problem oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik. Es werden n nummerierte Objekte im Kreis angeordnet; dann wird beginnend mit der Nummer s, jedes s te Objekt entfernt, wobei der… …   Deutsch Wikipedia

  • Josephus Problem — Das Josephus Problem oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik. Es werden n nummerierte Objekte im Kreis angeordnet; dann wird beginnend mit der Nummer s, jedes s te Objekt entfernt, wobei der… …   Deutsch Wikipedia

  • Josephus — For other uses, see Josephus (disambiguation). A Roman portrait bust said to be of Josephus[1] Titus Flavius Josephus (37 – c. A.D. 100),[2] also called Joseph ben Matityahu (Bibl …   Wikipedia

  • Josephus-Permutation — Das Josephus Problem oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik. Es werden n nummerierte Objekte im Kreis angeordnet; dann wird beginnend mit der Nummer s, jedes s te Objekt entfernt, wobei der… …   Deutsch Wikipedia

  • Josephus Permutation — Das Josephus Problem oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik. Es werden n nummerierte Objekte im Kreis angeordnet; dann wird beginnend mit der Nummer s, jedes s te Objekt entfernt, wobei der… …   Deutsch Wikipedia

  • Josephus — Büste von Flavius Josephus Flavius Josephus (* 37 oder 38 als Joseph ben Mathitjahu ha Kohen, hebräisch: יוסף בן מתתיהו , in Jerusalem, † nach 100 vermutlich in Rom) war ein jüdischer Historiker des 1. Jahrhunderts, der seine Werke, die später… …   Deutsch Wikipedia

  • Josephus Flavius — Büste von Flavius Josephus Flavius Josephus (* 37 oder 38 als Joseph ben Mathitjahu ha Kohen, hebräisch: יוסף בן מתתיהו , in Jerusalem, † nach 100 vermutlich in Rom) war ein jüdischer Historiker des 1. Jahrhunderts, der seine Werke, die später… …   Deutsch Wikipedia

  • Josephus on Jesus — This article is part of the Jesus and history series of articles.There are two extant references in Josephus on Jesus, the one directly concerning Jesus has come to be known as the Testimonium Flavianum. These passages appear in The Antiquities… …   Wikipedia

  • Flavius Josephus — Büste von Flavius Josephus Flavius Josephus (* 37 oder 38 als Joseph ben Mathitjahu ha Kohen, hebräisch: יוסף בן מתתיהו , in Jerusalem; † nach 100 vermutlich in Rom) war ein römisch jüdischer Historiker des 1. Jahrhunderts, der seine Werke auf… …   Deutsch Wikipedia

  • Contra Apionem — Büste von Flavius Josephus Flavius Josephus (* 37 oder 38 als Joseph ben Mathitjahu ha Kohen, hebräisch: יוסף בן מתתיהו , in Jerusalem, † nach 100 vermutlich in Rom) war ein jüdischer Historiker des 1. Jahrhunderts, der seine Werke, die später… …   Deutsch Wikipedia