# The 100 chair survivor challenge

I came across the following challenge. Here is my implementation in Python 3.7

A room has 100 chairs numbered from 1-100. On the first round of the game the FIRST individual is eliminated. On the second round, the THIRD individual is eliminated. On every successive round the number of people skipped increases by one (0, 1, 2, 3, 4...). So after the third person, the next person asked to leave is the sixth (skip 2 people - i.e: 4 and 5).

This game continues until only 1 person remains.

Which chair is left by the end?

I actually don't know what the true answer is, but my code outputs 31.

I think this is the fastest solution and at worst has an O(N^2) time complexity

n = 100
skip = 0
players = [x for x in range (1, n+1)]
pointer = 0
while len(players) > 1:
pointer += skip
while pointer >= len(players):
pointer = pointer - len(players)
players.pop(pointer)
skip += 1
print(players)


• The loop

while pointer >= len(players):
pointer = pointer - len(players)


is a long way to say pointer %= len(players).

• You'd be in a better position factoring the computations into a function,

def survivor(n):
skip = 0
players = [x for x in range (1, n+1)]
pointer = 0
while len(players) > 1:
pointer += skip
while pointer >= len(players):
pointer = pointer - len(players)
players.pop(pointer)
skip += 1
return players


and adding an if __name__ == '__main__' clause. This way it is easy to generate first few results.

TL;DR

I did so, generated first 20 numbers,

    1 2 2 2 4 5 4 8 8 7 11 8 13 4 11 12 8 12 2


and search this sequence in OEIS.

Surprisingly there was a match. A closer inspection demonstrated that the problem is a Josephus problem with eliminating every n-th person. Try to prove, or at least convince yourself, that it is indeed the case.

Further reading revealed that there is a linear solution.