Answer to Riddle #64: 100 People in a Circle With a Sword, Last one to Survive

Before reading the answer can I interest you in a clue?

We will be working towards a generalised answer, not simply a numerical answer to this version with 100 people. A sensible method, certainly what works for me, is to workout who survives for different numbers of players and see if I can spot a pattern. To that end I have built the simulator below.

I suggest you have a play, pay particular attention to games where the number of contestants is of the form 2ⁿ like 16, 32 etc.

Note: no information is sent to me, the calculation is done entirely locally, on your computer.
Go!  StopReset Delay between people =ms
people
So obviously we can see the 'winner' is player 73. But we need to know why. I suggested that you examine what happens when the number of 'players' is a 2ⁿ number, as in 2, 4, 8, 16 etc. You will notice that in this case the person who starts, player 1, is also the last person to survive. But why?

Consider the game with 16 people. Every time we go around we kill every other surviving person, we halve the number of survivors like so.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

The significance of the powers of 2 is that these can halve without a remainder. Hence if the number of players is a power of 2 the survivor will be the person who starts the game.

Now consider: when we have a game with something other than a power of 2 players as we kill people, the number of players will necessarily reduce to be a power of two. At that point the survivor will be the person holding the sword. Effectively the first player in a game with 2ⁿ players.

In our example starting with 100 players - we need to kill 36 of them to get down to a power of 2 (64). Since we kill every other person starting at player 2 the last person we need to die is player 72, they will be killed by player 71 and the first person in the effective power of 2 game, who will win is player 73.

(It's worth noting that this process of reducing to a power of 2 will always be completed in the first round regardless of the number of players, but why?)

Consider X players, let Y be the highest power of 2 that is less than or equal to X
The winning player is 2 * (X - Y) + 1



I prefer Google's Bard AI's answer to this problem...

If you're curious what Bard made of this puzzle...

Show/Hide Google's Bard AI's Answer

If you're curious what ChatGPT made of this puzzle...

Show/Hide ChatGPT's Answer