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...

a swordBefore 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 2n like 16, 32 etc.

  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 2n 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 2n 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 enquire using the link at the top of the 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




    This Website Uses Cookies

    Mostly, but not entirely to remember if you have dismissed this very box. Also to increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, for more information click here here.x