Josephus Problem

Ok, time for a new puzzle, I learned this one some time ago, it is a well known problem with a somewhat cool solution. This problem is well enough known as the "Josephus problem" that you can certainly just look it up along with its solution yourself if you hate my style of writing. The original problem involved N people who, having been captured by the enemy, are performing some sort of suicide pact, where they all kill eachother and there is one person standing at the end. There is a bunch of thematic bubble wrap to go with the puzzle, but I'm going to omit it just for the math. Anyway, here is the problem:
N individuals are in a circle, numbered 1 through N starting somewhere with 1 and increasing with each person to the left. Starting with person number 1, that person will kill the person to their left, and then the next person to the left will take a turn. This will continue until one person remains, which person is it?

Since that explanation is hard to do without an example, lets do one. Suppose N=5, then we start with 1 killing 2, 3 goes next, killing 4. 5 is next to take a turn, and 1 is to their left, so 1 dies and we only have 3 and 5 remaining. 3 goes next, killing 5 and the solution to the puzzle is 3.

So, in general, for an arbitrary N, who is the last person standing?

No comments: