Solve This Deadly Puzzle! Investigating the Josephus Problem

Hello everybody! Today, I'd like to talk about an interesting problem. It does happen to have a rather gruesome context, but it's a fascinating bit of math. Just like last week, I'm trying out writing articles in more of a problem-solution format in an effort to get all of my members (including you!) thinking creatively as you read, so let me know what you think of the article!


During the Siege of Jerusalem in 70 AD, the story goes, a certain number of Jewish soldiers were captured by the Roman army. They did not want to remain in captivity and instead decided to all die for their cause before the Roman army was fully mobilized to take them in.


They come up with the following scheme to all die. All the soldiers will stand in a circle, and the first person will kill the second in the circle. Then, the next remaining living person (the third) will kill the next person (the fourth), and the next remaining living person after that (the fifth) will kill the next person (the sixth), and so on. The idea is that once the soldiers complete one path around the circle, they'll continue rotating around the circle, always with the living killing the next person in line. At the end, there will be one person remaining, who will (presumably) die at his own hand.


One of the soldiers, Josephus, does not want to die. As he prefers capture to death, he wishes to be the last person remaining in the circle and to make his own decision—to stay alive.


Here's the problem:

If Josephus is with 40 other soldiers (for a total of 41 in the circle), what position should he sit at to survive? By convention, we assume that the positions are numbered 1 to 41 clockwise, the very same direction at which the above process proceeds.

What about the general case? If Josephus is with some number of soldiers (for a total of n in the circle), how can you express the position Josephus should begin at in terms of n (or in relation to n)?


Before you continue reading this article, see if you can begin to answer these questions yourself. What ideas can you come up with?


Here are a couple problem-solving strategies to try:

See if you can begin by trying small cases. Try making a table comparing the number of soldiers to the desired position. What patterns do you see?

This puzzle seems to have something to do with factors of 2. After all, all the even numbered positions are eliminated on the first go-around. Can you harness this fact and expand it?


Don't forget to test it out before you begin reading the hint, solution and discussion below!

Thirteen soldiers. Courtesy of Numberphile

HINT: What are the possible numbers of soldiers that give Position 1 as the desired position for Josephus to sit? What property do these numbers share?

Try writing n as a sum of one of the values necessary for Position 1 and a remainder. How can you express the desired position in terms of the remainder? (You do know the desired position is odd—make sure your formula matches that fact!)

If you want to discover something more, try writing both the final position and the number of soldiers in binary.

The captured soldiers. Courtesy of Numberphile

SOLUTION AND DISCUSSION:

It's time to discuss the problem! This problem, along with the Pirate-Coconut riddle I mentioned in "10 Mathy Things to Try in Quarantine", were actually two of my favorite problems when I started out in the wonderful world of creative math investigations, so I really hope you got something out of trying this one! Even if you just skipped down here to the solution, I hope you can get some value out of the insight behind this problem.


Let's begin! Let's start by working through some cases:

Here's a chart of some of the positions you'll get from working out different numbers of soldiers:

To see a couple of these in action, here are some clips from Numberphile:

Five soldiers:


Six soldiers:

Seven soldiers:

The first thing you should notice here is that all of the positions are odd numbers, a fact that makes sense when you consider that all the even numbers are eliminated on the first trip around the circle as 1 kills 2, leaving 3 to kill 4 and so on. Moreover, these aren't just any odd numbers: they seem to be increasing by 2 each time until, at some point, they reset back to 1.


We'll circle back to the question of why the values increase by 2, but first, let's figure out why they reset at the point they do. Here are the first few values of soldiers where position 1 wins:


Notice that these are the powers of 2! This is the key to understanding the problem: If we are given a number of soldiers that is a power of 2 (let's say 2^k where k is an integer), we will first eliminate all the even numbers, and since the person at the last number, 2^k, is killed (it's even), the person at 1 survives the first round, being given the opportunity to kill the next person in line.


At this point, we will have eliminated half of the soldiers, leaving 2^k/2 = 2^(k-1) soldiers. This is still a power of 2, so the exact same reasoning can be applied, and the person at 1 survives again. (Renumbering the spots 1,3,5,7,9,11... to 1,2,3,4,5,6... makes this even clearer—we're merely eliminating the even numbers again!)


Since a power of 2 remains a power of 2 (and namely, even!) no matter how many times it is divided in 2 (until it reaches the final person), the person at 1 will continue to survive every trip around the circle, and the person at 1 will ultimately be the last man standing.


Think of it this way: the person at 1 is only eliminated if at some point on its turn, the total number of soldiers in the circle is odd, as this would imply the last person would not be killed and would instead kill the person at 1.