Josephus Solution

Time for the solution to the Josephus problem from last time. As is common for problems that are basically induction puzzles, its easiest to see what is going on by looking at a few cases.

First of all, you can just work through who wins in the cases N=1,2,3,4,5,6,7,8 and so on, you will see that the winners are 1,1,3,1,3,5,7,1. A bit of an interesting note is that all the winners are odd numbers, of course this note is instantly less interesting when you realize that all the even numbered individuals are killed on the first pass. Actually, if N is even, that brings up a good point, specifically that for N=2K you immediately reduce to the problem with K people, with #1 going first and a bit of a renumbering that person 2m-1 is now person m. But if this new K also happens to be even, then you can half it again. From here you can see that if the initial N is some power of 2, then person #1 will be the last one standing.

At this point, we can realize that whoevers turn it is when the total number of people is a power of two is the person who is going to win. Naturally, if the total is an even number, then that is person #1, but if N is equal to 2^k+M, for some M less than 2^k (or we would just use k+1 in the power instead), then once M people die, the next person on turn will live. Clearly since M is less than half of N, those first M people will die on the first pass around the table, so when M people have died it is the turn of person #2M+1.

This gives us the general solution for an arbitrary N. Let 2^k be the largest power of 2 less than or equal to N, and let M=N-2^k. The final person standing will be person #2M+1.