**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?

http://www.stonehill.edu/compsci/shai.htm