The Josephus problem

Josephus Flavius was a famous Jewish historian of the first century AD. During his time, the Jewish-Roman war was being fought, and at some point, legend has it, he was trapped in a cave with a group of forty soldiers, surrounded by hordes of Romans on every side. The legend goes that the Jewish soldiers preferred suicide to capture, and thus hit upon a method of doing this: the Jews formed a circle and, proceeding around the circle, every third person committed suicide or was killed until no one was to be left. Now Josephus, being a sensible man, decided this wasn't the way he wanted to go out, so he quickly determined the spot in the circle where he would be the last person standing and thus stayed alive.

This is actually a problem in recurrence relations, a subfield of discrete mathematics, which itself has applications in many areas, including computer science and genetics. Josephus was able to solve the problem quickly likely using intuition, but the Josephus problem is a clear example of how a recurring event can be calculated.

Let's simplify things first, though; rather than having a circle of forty one (the forty soldiers including Josephus), let's reduce the circle size to ten (for ease in explanation). Let's also say that instead of every third soldier dying, every second soldier does instead; this is just for simplicity's sake to explain the principles used to solve the problem.

So, we start off with a circle like so:

                    1     2
                 /-----------\ 
             10 /   ^         \ 3
               /    |          \
               |               |
             9 |               | 4
               |               |
               \               /
              8 \             / 5
                 \-----------/
                    7     6

With this circle, the elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9, so 5 survives.

This is easy to do by merely counting, but we want to be able to solve this problem no matter how many people are standing in the circle. We define a function J(n), where n is the number of people around the circle; J(n) returns the number of the winner.

The first reaction would be that J(n) = n/2, which is true if n=10 and n=2. But if n=4, J(4)=1, so this idea is false. We might then observe that for every n we plug in, the result is odd; this is because the first round eliminates all the even numbers. We also might note that when n = 1, that means just Josephus is standing there, so he's not going to commit suicide, so J(1) = 1.

So, let's suppose we have 2n people originally. After the first round, we are left with:

                    1     3
                 /-----------\ 
           2n-1 /   ^         \ 5
               /    |          \
               |               |
          2n-3 |               | ...
               |               |
               \               /
                \             / 
                 \-----------/
                         

This is just like starting out with n people, except the number of people have been doubled and decreased by one:

                      1     2 = (3+1)/2
                   /-----------\ 
   (2n-1+1)/2 = n /   ^         \ 3 = (5+1)/2
                 /    |          \
                 |               |
(2n-3+1)/2 = n-1 |               | ...
                 |               |
                 \               /
                  \             / 
                   \-----------/
                         

So, we see that J(2n) = 2*J(n) - 1 for all n greater than one. But what if we have 2n + 1 people (i.e., an odd number)? Well, if we draw out the circle, we get something like this:

                    3     5
                 /-----------\ 
           2n+1 /   ^         \ 7
               /    |          \
               |               |
          2n-1 |               | ...
               |               |
               \               /
                \             / 
                 \-----------/
                         

... because 1 has just been eliminated to start the second trip around the table. We have almost the same situation except the numbers are doubled and increased by one. So, J(2n + 1) = 2*J(n) + 1 for n greater than one.

Putting these all together, we have a way of finding out which person survives if every other person is eliminated no matter how many are at the table:

J(1) = 1
J(2n) = 2*J(n) - 1 for n greater than one
J(2n+1) = 2*J(n) + 1 for n greater than one

We can use similar methods for the actual Joseph problem to get the result of the problem where every third person is eliminated: J(2^a + t) = 2t + 1 for any a and any t.

The Josephus problem is an interesting visual example of the challenges of solving recurrence relations.

Far be it from me to step into the realm of mathematics, or to mar the excellent writeup above. But the history of Josephus's death differs from the quoted legend.

Josephus himself tells us the story (in Book III of The Jewish War) of how, in 67 AD, he flees from the fallen city of Jotapata and takes refuge in a cave. Therein he finds 40 men, resigned to their fates. The Romans track Josephus to the cave and besiege it, at one point setting a fire at the entrance. Josephus goes out to parley with the troops, and arranges a surrender. The 40 men, however, will have none of it, and propose mass suicide. Josephus harangues them, speaking in a very long-winded speech about the evils of suicide. The 40 call him a coward, and at this point Josephus suggests that they draw lots, each man killing the one who drew a chit before him. Josephus then says:

He (Josephus) however (should one say by fortune or by the providence of God?), was left alone with one other; and, anxious neither to be condemned by the lot nor, should he be left to the last, to stain his hand with the blood of a fellow countryman, he persuaded this man also, under a pledge, to remain alive. --Jewish War III.391

Josephus, of course, lives to write the story, and in fact is eventually adopted into the Flavian family of the Roman generals who were once his enemies. What a guy.

But how can you, the intrepid math geek, work this out in your head? (It's a problem in Knuth, so it must be important...)

Easy! (Well, somewhat easily). Interpret tes' recurrence relations in binary (after all, they keep multiplying by 2).

What these recurrence relations are telling us to do is to take the binary representation of the number of people and reinterpret each 1 bit as "+1" and every 0 bit as "-1", keeping the same values for all positions. For example, for 9=1001₂ we have +8 and +1 for the 1's, and -4 and -2 for the 0's. Adding up, we get J(9)=3.

Can we do better? WATCH THIS SPACE! (Or add your easy-bit-operations below).