Shai Simonson         CS 201         Discrete Math for Computer Scientists


In Class Exercise

I want you to spend this class experimenting with the so-called Josephus problem.   The solution to this problem will involve a recurrence equation and some summations.  You should work in your normal groups, but feel free to share progress with others.


The Josephus Problem

Flavius Josephus was a Jewish historian during the Roman-Jewish war of  the first century. Through his writings comes the following macabre story.

The Romans had chased a group of 10 Jews into a cave and were about to attack. Rather than dying at the hands of their enemy, the
group chose to commit suicide one by one. Legend has it, though, that they decided to go around their circle of 10 individuals and eliminate
every other person until no one was left. Who was the last to die?

I want you to determine who is left assuming you start 10 people.  Then repeat the experiment starting with 1 person and going up to the number of people in class.  You should make a table including how many people were originally in the circle, and which numbered individual is saved in each case.   See if you can find any patterns.  Hint for finding pattern:  Label the individuals from 1 to n, go around the circle just once, and then think recursively.

Now do the same thing when you kill every third person left in the circle.  Can you find any patterns in this case?