One of the best explanations


The first thing to notice here is that if n (no. of people) is a power of 2 (2,4,8,16,32…) then the final survivor is the one who starts with the sword in the first place.

So, we wait for the current population to become a power of 2. At that moment whoever is holding the sword will be the winner.

Also, notice the first round. All the even positions are dead (2,4,6,8,10…). Thus for n=100, 50 people were killed in the first round. A power of 2 just smaller than 100 is 64. For that population to be reached, 36 people need to be killed.

36 people would have been killed in the first round itself. Also, the 36th person to die would have been at 72 as odd numbers are killing even numbers in the first round. And the sword would then be passed on to 73. So, 73 will be the final survivor.