The Josephus problem

Alvin Choy

6 December 2023

• Click to share on Twitter (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)

A group of children stand around in a circle. Each one puts a foot into the centre. One of the children starts tapping the feet around the circle in a clockwise direction and reciting one word per foot:

Ip dip dip,
My little ship,
Sailing on the water,
Like a cup and saucer,
But you are not in…
it!

The child whose foot is tapped on the final it is eliminated, then the rhyme starts again. Eventually, there is only one child left: the winner. The winner might get some chocolate, or might get to be it in the next game of tag. Imagine there are 13 children to start with. They begin by standing in a circle:

In the first round, they count round starting from 1 until number 8 is eliminated:

They then continue from the next number 9,until eventually number 4 is eliminated:In the next few rounds, 2, 3, 7, 13, 12, 6, 9, 10 and 5 are eliminated (in that order), leaving just 1 and 11. The next ‘ip’ starts on 11; 1 is dip’; 11 is the second ‘dip’… this continues until finally 11 is ‘it’. The winner is 1. If you were one of the children, you might want to save a lot of time and work out who was in the winning position before the eliminations started. This is often called ‘the Josephus problem’.

Generalisation

In the example above, we worked out who would win if we started with 13 people and counted out the whole ‘ip dip dip’ rhyme. But we’d like to be able to work out the winner if we start with any number of people. To make it a little easier, we’re going to use a shorter rhyme with just two words (‘Ip it!’). We can start by doing some examples and looking for a pattern. We can choose some values for the number of children, $n$, and by following the rules of the Josephus problem find the location of the winner, $w$. Here is the table for the winner depending on the number of children:

From the table, we can notice a couple of patterns: the winner is always odd; if we start with $2^k$ players, the winner is always 1. We can prove that both of these patterns will also hold true for larger numbers. To show that the winner is always odd, we simply need to notice that all the even positions lose during the first set of rounds. We can show that the winner is always 1 when we start with $2^k$ players by induction: in this case, the $2^{k-1}$ even numbers are eliminated first, leaving $2^{k-1}$ numbers. We can then renumber the remaining players, and in the subsequent round of eliminations, the even numbers are eliminated again. The number 1 is never removed in these rounds of eliminations, so remains as the winner.

Modular arithmetic

Thinking about everyone standing in a circle suggests that modular arithmetic might be the light of our problem. But what is modular arithmetic? Modular arithmetic uses the modulo function—a function that generates the remainder when dividing by a number $k$. For example, when 7 is divided by 2, the remainder is 1, and when 8 is divided by 2, the remainder is 0. We can write these facts as
\begin{align*} 7\text{ mod }{2}&= 1,\\ 8\text{ mod }{2}&=0. \end{align*}
Notice that when we divide by 2, the remainder is either 0 or 1. We can write \[ a\text{ mod }{2}=b, \] where $b$ is 0 or 1. In general, the remainder of $a\div k$ can be from 0 as a minimum to $k-1$ as a maximum. Modular arithmetic is often called clock arithmetic, as a 12-hour clock counts in mod 12. This way of thinking about counting around a circle like on a clock suggests that it might be useful for our problem. Let’s see if it can help us work out what happens if we start with a number of players that isn’t a power of 2.

Finding a solution

We start by guessing that the solution for $n=2^k+r$ (with $r<2^k$) might be \[w = c + a(n\text{ mod }{2^k}),\] where $c$ and $a$ are positive constants. When $n=2^k$, we know from earlier that $w$ is equal to 1. We can deduce that \begin{align*} 1 &= c + a(2^k\text{ mod }{2^k})\\ &=c, \end{align*} and so if our guess was right, the solution is \[w = 1 + a(n \text{ mod} {2^k}).\] We can now try this formula using some values of $n \not={2^k}$. For example, when $n=11$ we know from the table that $w=7$. The nearest power of 2 less than 11 is 8, which is $2^3$. So $k=3$ and our solution formula becomes \begin{align*} 7 &= 1 + a(11\text{ mod }{2^3})\\ &= 1 + a(11\text{ mod }{8})\\ &= 1 + 3a. \end{align*} Our formula works if $a=2$, and so our solution is \[ w=1+2(n\text{ mod }{2^k}). \] If you try this formula out on the other numbers in the table, you’ll see that it always gives the right answer. But checking all of these examples isn’t enough to know that this formula will work for all values of $n$. For that, we need a proof. Luckily finding a proof isn’t too hard. First, we know from earlier that if we start with $2^k$ players then player 1 will win. From this we also know that if we’re in the middle of a game and have reached a point where there are $2^k$ players left, then the player who we are starting with next will win. So if we start with $n=2^k+r$ players, we can find the winner by working out who we’ll be pointing to once the extra $r$ players are eliminated. Noticing that $r\equiv n\mod 2^k$, and that we count out two people for each elimination tells us that in eliminating these $r$ players, we’ll have counted on $2(n\text{ mod }2^k)$ places from the 1 we started at. We have a general formula connecting the number of players, $n$, the winning position, $w$, and we’re not certain this it’s right. But maybe you’re wondering if there’s a nice observation we could use to save ourselves time? For that, we’re going to need binary numbers.

Binary numbers

In our usual decimal numbers, each digit represents the next power of 10. If instead, we use each digit to represent a power of 2, we have binary numbers. There are 2 digits in this number system: 0 and 1. For example, $1101_2$ is a binary number (we include the $_2$ to make it obvious that we’re using binary): it is equal to the decimal number 13 as it has ones in the 1, 4, and 8 positions. Every decimal number can be represented as a unique binary number: this is the key to our trick. Let’s try writing some values of $n$ and $w$ from the table in binary. First up, let’s try $n=10$ and $w=5$: \begin{align*} n &= 1010_2 & w_1 &= 0101_2. \end{align*} Another example: $n=14$ and $w=13$ becomes \begin{align*} n &= 1110_2 & w_1 &= 1101_2. \end{align*} Notice that if we take the 1 at the front of the binary number $n$, then move it to the end, we get $w$. This works for the other numbers too, for example for $n=8$:

This gives the correct value for $w$! You can prove that this version of the solution works for every value of $n$ using our formula from the previous section. I’ll leave you to think about how to do this. We’ve found two ways to work out who the winner is if we eliminate the second person. While I go away and enjoy all the chocolate I’ve won, you can try to work out the solution when we use a longer rhyme…

Alvin Choy

Alvin is a HK college student in Ruislip High School who enjoys maths as a subject and career. He thinks that although maths can be complex in some ways, it is always entertaining and beautiful.

All articles by Alvin