Josephus

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!

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$.

Why is $j_n$ always odd?

Why is $j_n=1$ whenever $n$ is a power of 2?

Why does $j_n$ always (more or less) increase by 2 when $n$ increases by 1?

The first question is easy!

For the second question, 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. The others all change. 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$.

The last question is a bit harder, but experimenting with a few consecutive values will probably help you understand how this is.

For example, take $n=12$ and $n=13$.

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. Clearly this will work whatever two consecutive numbers we choose.

So $j_n=j_{n-1}+2$ unless $n$ is a power of $2$.

Now we are in a position to describe the function that goes from $n$ to $j_n$ perfectly well.

If $2^m$ is the highest power of 2 less than $n$ and $n=2^m+r$, what is $j_n$?

$$ j_n=2r+1 $$

If we look at the pattern of $j$ numbers again, we can see another feature: that they go up in 2s until they get to the point when $j_n$ would be greater than $n$, at which point they go back down to $1$.

So 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$.

So let's take $j_3=3$ and try the recurrence relation again, so that: <\p> $$ \begin{align*} j_3&=3\\[6pt] j_n&=j_{n-1}+2\mod n \end{align*} $$

Now we get:

$$\begin{align*} j_3&=3\\[6pt] j_4&=j_3+2\pmod 4\;=1\\[6pt] j_5&=j_4+2\pmod 5\;=3\\[6pt] j_6&=j_5+2\pmod 6\;=5\\[6pt] j_7&=j_6+2\pmod 7\;=0 \end{align*}$$

and we run into the same problem again. It's always the cases where $n=3, 7, 15, 2^m-1$ where the recurrence would give $j_n=0$ instead of $j_n=n$.

How can we adapt the recurrence relation to correct this problem?

This is not so easy, but there is a neat computer-sciencey trick for this.

$$ j_n=\left(j_{n-1}+1\mod n\right) +1 $$

Try it. It's a handy hack, if you are into that kind of thing.

We'll come back to this a bit later. In the meantime, here’s another way of looking at it.

Can you find a relationship between $j_{2n}$ and $j_n$? Can you see why it should be true?

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.

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 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*}$$

These two relationships make it easy to generate the sequence $j_n$. Try it!

$$\begin{align*} j_1&=1\\[6pt] j_2&=2j_1-1=1\\[6pt] j_3&=2j_1+1=3\\[6pt] j_4&=2j_2-1=1\\[6pt] j_5&=2j_2+1=3\\[6pt] j_6&=2j_3-1=5\\[6pt] j_7&=2j_3+1=7\\[6pt] j_8&=2j_4-1=1\\[6pt] j_9&=2j_4+1=3 \end{align*}$$

They also offer a handy way to find the winning number with a very large number of people! For example:

$$\begin{align*} j_{2000}&=2j_{1000}-1=4j_{500}-3=8j_{250}-7=16j_{125}-15=32j_{62}+1\\[4pt] &=64j_{31}-31=128j_{15}+33=256j_{7}+161=512j_{3}+417=1024j_1+929=1024\times 1+925=1953 \end{align*}$$

Try this method to find $j_n$ for some very large values of $n$.

Now we 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 }\\[8pt] &\begin{cases} j_1=1\\ j_n=(j_{n-1}+1 \mod n)+1 \end{cases}\\[8pt] &\begin{cases} j_1=1\\ j_{2n}=2j_n-1\\ j_{2n+1}=2j_n+1 \end{cases} \end{align*} $$

The first of these gives us a surprising but delightful way of finding $j_n$ for any $n$ with almost no work at all. Here's how it's done:

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}$

$\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$

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?

You may not see this right away, but 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 is 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}}$

I'm sure you can work out the equivalent recurrence relation for yourself, and why it's true. But so that you can check your solution, I'll tell you what I got:

$$ j_{n,3}=(j_{n-1,3}+2)\mod n +1 $$

In theory, there are direct ways to compute $j_{n,3}$ directly 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!

Well, that's it for my series of SUMS articles. I really hope you have enjoyed them! Keep an eye on my website mathsinsight.co.uk 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!

\(\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\)