The Josephus Problem

The story goes that the Jewish historian Flavius Josephus and his men had been in battle with Roman soldiers and they were badly losing. Eventually his forces were forced back into a cave where defeat was imminent and the Romans would come and do horrible things to them. One of the number came up with a plan for mass suicide as a way out.

The forty men were to stand around in a circle and one of them would hold a sword, let's call him number 1. He would stab the person to his left (number 2) and pass the sword to the next alive person in the circle (number 3). They would then do the same thing, killing the next person to their left (number 4) and passing the sword on. This process was to be continued until only one person remained.

However Josephus decided that he'd rather face the Romans and didnt want to die. At which position should be stand to guarantee that he is the last remaining person? Further, for n people which person remains?

This problem is somewhat of a classic of high school lessons because it demonstrates a nice pattern which can be worked out with just a little bit of experimentation and analytical reasoning. The most sensible way in is to try it with a smaller number of soldiers and try to extrapolate.

With 1 person they trivially survive and for 2 people, person 1 stabs person number 2 and wins immediately. However for the 3 person case, 1 stabs 2 then passes the sword to 3 who proceeds to stab 1.

At this point it makes sense to make a table of results:

n	Where to stand
1	1
2	1
3	3
4	1
5	3
6	5
7	7
8	1
9	3
10	5
11	7
12	9
13	11
14	13
15	15
16	1
17	3
18	5
19	7
20	9
21	11
22	13
23	15
24	17
25	19

That all of the winners are odd should be no surprise since all of the even people die out on the first circuit. The pattern is that the sequence starts at 1 and then proceeds up the odd numbers until resetting. This resetting happens whenever n is a power of 2.

So to work out where to stand, you take the largest power of 2 that you can from n and then multiply the result by 2 and add 1. For example, when n=40, the largest power of 2 that we can take away is 32. This gives us 8. 8x2+1=17.

Interesting things to explore: what happens if we kill every mth person rather than every 2nd person. It's worth a little play around with.

The applications of this come up in shuffling theory and card tricks. For example, if you start with a normal pack of cards and alternate putting the top card on the bottom and putting the top card in the discard pile you can predict which card will remain. For 52 cards this would be the 41st card, but you can work out which position will be left quickly in your head for any number of cards.