The Josephus Problem

I recently responded to a question from a student about
a class of problems called *Josephus problems*. The question, and
my repsonse follow:

>The emperor has invited you to dinner. It is well known
that the

>emperor regularly invites a number of guests to dinner
and only one

>person leaves the dinner as a happy person. You see,
the emperor is a

>bit "touched" in the head! He invites people to dinner
then dumps

>oatmeal on top of every other person's head until only
one person

>remains! The one guest without oatmeal at the end of
the meal

>receives a million dollars! How can you determine where
to sit if you

>don't want oatmeal on your head. You won't know how
many guests have

>been invited to dinner unitl you arrive. You do know
that every

>second person will receive the oats, you do know where
the emeperor

>will begin this silly feat with the eager beaver in
seat number one!

>

>How would you find a formula for this. Is there a pattern?
Please

>help me!

>

>Thank you.

>

This type of problem is called a "Josephus problem",
after a story about a historian of the first century, Flavius Josephus,
who survived the Jewish-Roman war perhaps due to his mathematical talents. In his book __The Jewish Wars__ Flavius tells that he was one out of 41 Jewish rebels trapped by the Romans. His
companions preferred suicide to escape, so they decided to draw lots to see who would kill whom so that they could avoid both capture and the sin of suicide. The idea that they decided to form a cycle
and to kill every third person and to proceed around the circle until no
one was left is probably a myth. According to the problem Josephus wasn't excited by the idea of killing himself, so
he calculated where he has to stand to survive the vicious circle. The
general Josephus problem; involves how many people will stand around
a circle and how many shall be passed over before the next one is killed
(or in your case, have oatmeal dumped on their head).

I interject here a little about the history of the problem

Somewhile after I responded to the letter above, I sent a note to the Historia Matematica discussion list and Albrecht Heeffer gratiously answered to tell me a little more about the history of this problem. Here is his answer, interlaced with my questions:

> First, is it essentially correct that Cardan created or first wrote > the story of Josephus into the problem?Here is an excerpt from a note by David Singmaster

Yes! Probably the most extensive study on the history of the "Christians and Turks problem" is by Wilhelm Ahrens (1901). It is Ahrens who stated that Cardan was the first to use Josephus as the last man and to name the problem "ludus Josephi" (p. 287-8). No instances of the name 'Josephus game' were found prior to Cardan's "Practica Arithmeticae generalis" of 1539 (see Tropfke 1980 and Singmaster 2002). I traced and checked several sources as well.

> Is there record of alternative versions of the problem prior to > Cardan, and where, how early, and in particular, how early do we have > recorded evidence of children's counting games for elimination?

The problem was very popular during the 15th and 16th century. It appears in many arithmetics books under different variations: christians and jews (Buteo), Franciscans and Camoldensians (Calandri, c. 1500), students and rascals (Ben Ezra, c. 1150). The problem, under the same form was know to the Arabs. Singmaster quotes several Japanese sources from the 12th century and later. Singmaster also refers to a study by Gerard Murphy (1942) who found several Latin sources dealing with the problem before the 10th century. Murphy claims the problem is of Irish origin from the 9th century!

Children's counting games must have existed already much earlier.

It appears in the Japanese literature as early as 1627, with 15 children and 15 stepchildren counted by 10s, but with one child (the 15th) skipped, until only one is left. Ahrens cites some indications that it may go back to the 11C in Japan and believes that the problem arose independently in Japan. Takagi has sent me an article by Shimodaira (source and date not given) on the recreational problems in Jing_ki, but this doesn't indicate the date of the second edition which first contained these problems. Shimodaira states the Japanese name of the problem, Mamakodate, first occurs in the essay Tsurezuregusa by Kenk_ Yoshida (1283-1350), but it's not clear if the problem itself is given there. Shimodaira gives the problem in the form where the 15th stepchild protests that he is about to be eliminated and the stepmother agrees to restart from him. Ahrens says that Jing_ki has the stepmother doing this by accident and the bit about the 15th stepchild first occurs in Miyake Kenry_, 1795. Is there any Chinese material on this problem? I have recently seen an article which claims an Irish origin of the problem, c800, and which gives early medieval forms called the Ludus Sancti Petri. It is often thought to derive from the Roman practice of decimation. Murray's History of Chess mentions 10 diagrams of this in an Arabic chess MS of c1370, possibly referring to a c1350 work. Murray asserts the problem is of Arabic origin. Wakoku Chie-kurabe shows a version with 8 and 8 counted by 8s, such that either group can be the group counted out first!, depending on where one starts.

Is there a pattern? Yes, let's look. If the first
"dump" is on head number one then we know that for N guests :

N Best seat
Order of elimination

2
2
1

3
2
1,3

4
4
1,3,2

5
2
1,3,5,4

6
4
1,3,5,2,6

7
6
1,3,5,7,4,2

8
8
1,3,5,7,2,6,4

9
2
1,3,5,7,9,4,8,6

10
4
1,3,5,7,9,2,6,10,8

I hope I did all those correctly, I would think you can
continue.

If you start with every other one and dump on the second instead of the first, then the numbers of the survivors for a group of n would be

n ---2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18

S ---1---3---1---3----5--7---1---3---5----7----9---11--13--15--1---3---5

Notice that for any power of two, one is the safe place, and for a number 2^{n} + c the best place is 2c+1 (C of course, must be less than 2^{n}).

If you start counting from number one and eliminate every nth person starting with person number "n", the sequence of best places to stand can be found by using modular arithmetic (what many students learn in school as clock arithmetic).. For example, if you eliminate every third person, you can use trial and error to find out that for two poople the best place to stand is position 2. After that, the best place to stand can be found by adding three to the previous best position, with the restriction that if the new position is higher than the number of people simply reduce the position number by n.

N people Best position

2 ---------- 2

3 ---------- 2+3=5 ---- 5-3 = 2

4 ---------- 2+3=5 ---- 5-4 = 1

5 ---------- 1+3=4

6 ---------- 4+3=7 --- 7-6=1

7 ---------- 1+3 = 4

8 ---------- 4+3=7

9 ---------- 7+3=10 --- 10-9=1

10----------- 1+3=4

11 ---------- 4+3=7

12 ---------- 7+3=10

13 ---------- 10+3= 13

14 ---------- 13+3=16 --- 16-14=2

It would seem, then, that for eliminating every fifth peron the best positions would be (starting with n=2) at positions number 2, 1, 2, 2, 1, 6, 3, etc...

It may be more fun to do this on an interactive java script at Alex Bolgony's cut-the-knot web site

You can select a person to be "you" and the number of
candidates and how they eliminate to test your theory. Alex
has also provided both a recursive and a direct (but advanced) solution.
The answer, as you can see is probabilistic, but I'm thinking two shows
up the most.