MGH, that's Marvelous! Why/how does it work?

Not sure I can tell you exactly why it works but I can tell you how I came up with it. I started by looking for a pattern. First off, you find out real quick that the even people get waxed on the first round. I then checked the outcome for 1 to 20 people (it took a while). I noticed that when n (the total number of people) equals a power of 2 (i.e, 2, 4, 8, 16), then the first person is always the last man standing. Here is a list of the survivor for 1 to 20 people:

n survivor1 1

2 1

3 3

4 1

5 3

6 5

7 7

8 1

9 3

10 5

11 7

12 9

13 11

14 13

15 15

16 1

17 3

18 5

19 7

20 9

Once I saw this I was able to craft the "formula" to spit out the survivor based on any number of people. I wish I could say I used some clever method to get the formula, but I pretty much just kept looking till I found a way for it to work out.

If you look at it you do see that the formula does make sense. Take the case where n is a power of 2, say 16. On the first round of killings, all the even people are killed. You end up with a spacing of 2 in between all the survivors (i.e. 1,3,5,7,9...). Then after the second round, you end up with a spacing of 4 (1,5,9,13). Then after the third round you get a spacing of 8 (1,9). If we had used a very large power of 2 for n, then you would see that the spacings keep incrementing each round by a power of 2 (2,4,8,16,32,...). Also, if the total number of people is not a power of 2, then the spacings are still there, except there is an offset. I just used these patterns to come up with something that worked. I'm sure someone better at math could explain it better.

Mike