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.