The Josephus Problem
A puzzle about circles and counting — that turns out to have a beautiful connection to binary numbers and a surprising piece of ancient history.
Work through the questions before looking at the answers!
Dr Brian Brooks
Mathematics InSight
Imagine a game. Quite a simple game. 12 people stand in a circle, and another person stands in the middle.
The one in the middle points at each standing person in turn, and every second person they point to leaves the circle.
Who is left at the end?
The first six eliminations are easy! All the even-numbered people leave the circle.
Once we have eliminated number 12, we have to skip number 1, and eliminate number 3 (as number 2 has already gone).
Now you can finish the whole thing off, but the more have been eliminated, the harder it is to see who goes next. Pay attention!
Try this with other numbers of people in the circle.
Fill in this table, where \(n\) is the number of people, and \(j_n\) is the number of the last person standing.
| \(\boldsymbol{n}\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) | \(9\) |
| \(\boldsymbol{n}\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) | \(1\) | \(1\) | \(3\) | \(1\) | \(3\) | \(5\) | \(7\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) | \(11\) | \(13\) | \(15\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) |
Looking at the pattern in the table, could you describe the rule that tells you \(j_n\) when you know \(n\)?
When \(n\) is a power of \(2\), \(j_n=1\). For the others, \(j_n\) goes up by \(2\) every time \(n\) goes up by \(1\).
| \(\boldsymbol{n}\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) | \(1\) | \(1\) | \(3\) | \(1\) | \(3\) | \(5\) | \(7\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) | \(11\) | \(13\) | \(15\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) |
Why is \(j_n\) always odd?
Person 1 is the first one skipped, so the first person to be eliminated is always even-numbered. Only odd-numbered people can survive to later rounds, so \(j_n\) is always odd.
Why is \(j_n=1\) whenever \(n\) is a power of 2?
Why is \(j_n=1\) whenever \(n\) is a power of 2?
Imagine you have 64 people. After the first round, there are 32 left. Renumber them 1 to 32. Number 1 stays at number 1. The others all change. After the next round, there are 16. Renumber them 1 to 16. Number 1 stays at number 1. And so on. Until there is only number 1 left, and that has never changed its number. So \(j_{64}=j_{32}=j_{16}=\dots=j_2=j_1=1\).
| \(\boldsymbol{n}\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) | \(1\) | \(1\) | \(3\) | \(1\) | \(3\) | \(5\) | \(7\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) | \(11\) | \(13\) | \(15\) | \(1\) | \(3\) | \(5\) | \(7\) | \(9\) |
Why does \(j_n\) always (more or less) increase by two when \(n\) increases by one? For example, why is \(j_{13}\) two more than \(j_{12}\;\)?
We already know that \(j_{12}=9\). When \(n=13\), after we have eliminated the first person, we have \(12\) people left, which we can renumber like this (in green):
The next person to be eliminated is number 2 in the new numbering, and we have 12 people, so the last one standing will be number 9 in the new numbering, which is the original number 11.
Will this always work for any pair of consecutive numbers?
Can you find a relationship between \(j_{2n}\) and \(j_n\)?
For example, take \(2n=22\). After all the evens have been eliminated, we can renumber the rest like this (in pink):
The next person to be eliminated is number 2 in the new numbering, and now it's just like \(n=11\) using the pink numbers. The last person standing is pink \(j_{11}\), which is the original \(2j_{11}-1\). This will clearly be the same whatever value of \(2n\) we choose. So
\[ j_{2n} = 2j_n - 1 \]Can you find a relationship between \(j_{2n+1}\) and \(j_n\)? Can you see why it should be true?
The argument is very similar, and I'll leave most of it with you. So now we have
\[\begin{align*} j_1&=1\\[6pt] j_{2n}&=2j_n-1\\[6pt] j_{2n+1}&=2j_n+1 \end{align*}\]If we look at the pattern of \(j\) numbers, it looks as though
\[\begin{align*} j_1&=1\\[6pt] j_n&=j_{n-1}+2\pmod n \end{align*}\]but actually this is not quite right.
Try this recurrence relation: what sequence does it generate? Why doesn't it yield exactly the sequence we want?
The recurrence generates the sequence
\[\begin{align*} j_1&=1\\[6pt] j_2&=j_1+2\pmod 2\;=1\\[6pt] j_3&=j_2+2\pmod 3\;=0 \end{align*}\]but we want \(j_3=3\). It's always the cases where \(n=3, 7, 15, 2^m-1\) where the recurrence gives \(j_n=0\) instead of \(j_n=n\).
There is a neat computer-science trick to fix this:
\[ j_n=\left(j_{n-1}+1 \bmod n\right) +1 \]Try it. It's a handy hack, if you are into that kind of thing.
In fact, we now have three different ways to figure out \(j_n\):
\[\begin{align*} &j_n=2r+1 \text{ where } n=2^m+r,\;r>0,\text{ and }m\text{ is maximal }\\[10pt] &\begin{cases} j_1=1\\ j_n=\left(j_{n-1}+1 \right)\bmod n+1 \end{cases}\\[10pt] &\begin{cases} j_1=1\\ j_{2n}=2j_n-1\\ j_{2n+1}=2j_n+1 \end{cases} \end{align*}\]The doubling relationships make it easy to generate the sequence \(j_n\):
They also offer a handy way to find the winning number with a very large number of people:
Try this method to find \(j_n\) for some very large values of \(n\).
Go back to the earlier table, but fill it out in binary.
| \(\boldsymbol{n}\) | \(1\) | \(10\) | \(11\) | \(100\) | \(101\) | \(110\) | \(111\) | \(1000\) | \(1001\) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) |
Can you see how to get from \(n\) to \(j_n\) by moving digits around in their binary representations? Can you explain why this should be so?
| \(\boldsymbol{n}\) | \(1\) | \(10\) | \(11\) | \(100\) | \(101\) | \(110\) | \(111\) | \(1000\) | \(1001\) | \(1010\) | \(1011\) | \(1100\) | \(1101\) | \(1110\) | \(1111\) | \(10000\) | \(10001\) | \(10010\) | \(10011\) | \(10100\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_n}\) | \(1\) | \(1\) | \(11\) | \(1\) | \(11\) | \(101\) | \(111\) | \(1\) | \(11\) | \(101\) | \(111\) | \(1001\) | \(1011\) | \(1101\) | \(1111\) | \(1\) | \(11\) | \(101\) | \(111\) | \(1001\) |
If you take the left-most \(1\) in \(n\) and move it to the right-most position, you will have \(j_n\).
Removing the initial digit 1 from \(n\) is equivalent to taking away the highest power of 2. So \(2^m+r\) becomes just \(r\). Now we need \(2r+1\), which is equivalent to shifting all the remaining digits to the left (multiplying by 2) and then putting a 1 on the right-hand end (adding 1).
This problem is often called the Josephus problem, after the 1st-century historian Josephus Flavius. A little research on your part will reveal why this is.
Investigate the order of elimination for any \(n\). For example, when \(n=12\), people step out of the circle in the order
2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1
And lastly, try the same problem (game), but with every third person stepping out of the circle.
That turns out to be a bit harder. In fact, only one of our various ways of finding \(j_n\) will help in this new situation — the first recurrence.
Try filling out a new table for every third person:
| \(\boldsymbol{n}\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\boldsymbol{j_{n,3}}\) |
The equivalent recurrence relation for every third person is
\[ j_{n,3}=(j_{n-1,3}+2)\bmod n +1 \]In theory, there are direct ways to compute \(j_{n,3}\) without recurrence, but it all gets a bit inscrutable and messy, so I don't recommend following this up. We've done plenty on the Josephus problem to be going on with!
We've done plenty on the Josephus problem to be going on with!
I really hope you have enjoyed this article. Keep an eye on the website for more along the same lines. Enjoy your mathematical journey. If I've only shown you one thing, I would like it to be that maths is far more interesting than your exam curriculum would have you believe!
Dr Brian Brooks
Mathematics InSight