Numberphile

This maths problem will make your brain hurt - but it could save your life

Algebra meets a suicide squad.

DAVID NIELD
4 NOV 2016
 

The most rewarding maths problems look simple at first, get really tricky when you try and figure them out, and then resolve themselves in clever ways in the end. And the infamous Josephus problem ticks all three boxes, as shown in the video above by Numberphile.

 

The problem gets its name from Titus Flavius Josephus, a first-century Jewish scholar.

The story goes that he was with 40 other soldiers when they were surrounded by conquering Romans - imagine that scene in Games of Throneswhere Ramsay Bolton's men trap Jon Snow's army in a tight circle and start moving in.

Rather than give themselves up, the soldiers decided to commit suicide en mass, but by killing each other rather than themselves, to avoid any last-minute changes of heart. Sitting in a circle, the first soldier would kill the man to the left of him, the next living soldier would kill the man to his left, and so on around the circle.

When the circle of slaughter got back to the start, the process would repeat with the smaller group of people. Finally, the last man alive would fall on his sword.

Josephus' problem was that he was much keener on living than dying - but he didn't want to let his fellow soldiers in on that secret. So, where should he position himself in the circle to be the last man standing?

The answer: 19th place. But how you arrive at that number, and how you figure it out for any different number of soldiers, is actually pretty interesting, as Daniel Erman from the University of Wisconsin-Madison shows in the video above.

 

On the first swing around the circle, it's pretty obvious that everyone standing in an even-numbered position is going to meet a grisly end, so if you want to survive, the first thing is getting yourself an odd-numbered position.

But the circle then resets as it reaches the beginning again: suddenly a new set of people have a fatal even number assigned to them.

The next pattern to note is if the number of soldiers is a power of 2 (so 1, 2, 4, 8, 16, 32, 64, and so on). Then the place to sit is in first place, spot 1, to start off the killing.

Think about it. With two people, 1 kills 2. With four people, 1 kills 2, 3 kills 4, and then 1 kills 3. It doesn't matter how high you go with these powers of 2, because soldier 1 always starts the loop off again.

After each go around the circle, you're back with another power of 2, and soldier 1 is safe again until he's the only one left. The group is halving itself exactly each time.

That power of 2 calculation is key to the whole problem, as you can see in the video. Work out how many extra men there are compared to the closest power of 2, and you can work out how to save your skin.

That extra number is labelled as "l" in the final formula, and the place to be is (2 x l) + 1.

To put it another way, you're making sure you're in first place when the circle dwindles to a power of 2, like 16 or 32, no matter how many people there are to begin with. You have to double "l", because every other soldier is getting killed.

So Josephus needs to sit in 19th place - 32 is our closest lower power of 2, there are 9 extra people, and (2 x 9) + 1 is 19. Josephus is the crucial number 1 as soon as the circle gets to a nice neat power of 2, in this case 32, and so he will stay as number 1 until everyone else is dead, based on the patterns we already know about.

The video above explains it much better than we can, and adds a clever binary trick for good measure. Just try and remember the rules next time you're in a mass execution situation.

More From ScienceAlert

Will Earth still exist in 5 billion years?

Lessons from a twin solar system.

1 day ago