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

64. 100 people stand in a circle in order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next living person (i.e. No. 3). All people do the same until only 1 survives. Which number survives to the end?

The answer to this puzzle is difficult to work out, though it's not that hard to follow. Since working out the answer I've discovered it's an example of quite a famous puzzle called the Josephus Problem...

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

Note: no information is sent to me, the calculation is done entirely locally, on your computer.

Delay between people =ms

people

1✓
2✓
3✓
4✓
5✓
6✓
7✓
8✓
9✓
10✓
11✓
12✓
13✓
14✓
15✓
16✓
17✓
18✓
19✓
20✓
21✓
22✓
23✓
24✓
25✓
26✓
27✓
28✓
29✓
30✓
31✓
32✓
33✓
34✓
35✓
36✓
37✓
38✓
39✓
40✓
41✓
42✓
43✓
44✓
45✓
46✓
47✓
48✓
49✓
50✓
51✓
52✓
53✓
54✓
55✓
56✓
57✓
58✓
59✓
60✓
61✓
62✓
63✓
64✓
65✓
66✓
67✓
68✓
69✓
70✓
71✓
72✓
73✓
74✓
75✓
76✓
77✓
78✓
79✓
80✓
81✓
82✓
83✓
84✓
85✓
86✓
87✓
88✓
89✓
90✓
91✓
92✓
93✓
94✓
95✓
96✓
97✓
98✓
99✓
100✓
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

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

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 Y

The winning player is 2 * (X - Y) + 1

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

^{n}like 16, 32 etc.Note: no information is sent to me, the calculation is done entirely locally, on your computer.

Delay between people =ms

people

^{n}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

^{n}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 Y

The winning player is 2 * (X - Y) + 1

© Nigel Coldwell 2004 - – The

**questions**on this site may be reproduced without further permission, I do not claim copyright over them. The

**answers**are mine and may not be reproduced without my expressed prior consent. Please inquire using the link at the top of the page. Secure version of this page.

__PayPal__

I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel