The Siege of Yodfat that occurred in Israel in the mid-1st century was a long one — almost fifty days. When it finally ended, an interesting problem came out from it and it took a millennium to figure it out.
During the siege, there were 41 Jewish soldiers surrounded by Roman soldiers ready to capture them. They decided to commit suicide rather than surrender. The soldiers stood in a circle, killing the man to their right until there were no survivors. There's historical evidence that this actually happened.
Jewish historian Flavius Josephus, along with one other soldier, survived the suicide pact. According to history, both men decided not to commit suicide and surrendered to the Romans instead. The mystery, known as the Josephus Problem, is to figure out where you need to be standing in the circle in order to survive the suicide like they did.
Mathematician Daniel Erman from the University of Wisconsin-Madison explains the problem, which he first encountered way back in high school. In a YouTube video he made for Numberphile, he said this was an intriguing problem because you don't have a lot of information from the beginning.
According to Erman, you can start small, say seven soldiers, and see how it works. So one kills two, three kills four and so on until the person at position seven is left standing. When you have 41 soldiers however, it gets complicated.
The best way to start, Erman says in the video, is to gather data. You keep running through larger and larger suicide circles, writing down the position that survives. You'll start noticing a pattern: The winner is always in an odd-numbered position. So you realize that standing in an odd spot gives you a better chance of survival, given the data you're getting.
Let's say it's a circle of ten. If we're starting at soldier one, you already know soldiers two and four are dead. If you keep going, then all soldiers on even-numbered spots are killed. From there the elimination depends on where you start, and in this case, it will leave the survivor at soldier five.
The pattern then shows that soldier one survives a lot. Why is that? Well, Erman says that If you look closely, soldier one normally wins if he's in a circle that's the power of two (for example, there's eight, or two to the third power, soldiers).
The next step is to split up the number of soldiers. It needs to be split by 2a (The highest power of 2 from the number of soldiers) + what’s left of the soldiers (let’s call it “l"). According to Erman, the end theorem for the winning spot is: 2l + l if l<2a.
So if there are 41 soldiers, you take out 32, the largest power of 2, first. You’re left with 9 soldiers, which you then put it in the equation – 2(9) + 1. The answer? The soldier in position 19 survived the suicide pact!
There's also an interesting way to solve it using binary. You break down 41 by powers of two and break it down to zeroes and ones (101001 in this case). Move the first one over to the back, switch the ones back to the original powers and then add them up. Boom! You get 19.