Legend has it that Josephus wouldn’t have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. What happened next?

What happened

Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle so that they could live to see the next day! It’s not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. This is one example of a ‘recursive problem’, i.e, problems whose solutions all use the idea of recurrence, in which the solution to each problem depends on the solutions to smaller instances of the same problem! This way of solving problems is especially useful because it is easier to look at small cases first and then build towards our solution for the bigger cases rather than directly jumping on the problem and trying to ‘brute-force’ our way to the solution. Hence, one thing all such problems require, is a base case, or a boundary condition. At first glance, the problem seems fairly non-trivial. However, when you arrive at the solution to this problem, you would see how painfully clear the answer would’ve been had you just changed your ‘point of view’!

This Numberphile video explains this problem in a very entertaining way For the formal proof and generalisations of the problem, click here For an in-depth introduction to a similar class of problems based on recurrence, you can read the first chapter of Concrete Mathematics by Graham, Knuth and Patashnik. Cheers!

comments powered by Disqus