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
I interject here a little about the history of the problem
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 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 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... 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.
>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).
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.
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 2n + c the best place is 2c+1 (C of course, must be less than 2n).
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 may be more fun to do this on an interactive java
script at Alex Bolgony's cut-the-knot
web site