Josephus Problem: Last Person Standing in a Circle

MediumProbability

Reported in interviews at Belvedere Trading Squarepoint Capital Walleye Capital

Problem statement

100 people stand in a circle, numbered $1$ through $100$. Person $1$ has a sword and eliminates person $2$. Person $3$ then picks up the sword and eliminates person $4$. This pattern continues around the circle (each surviving person eliminates the next surviving person) until only one person remains.

Which person is the last one standing?

Show hint

What happens if you play the game with small circles, say up to a dozen or so people, and list who survives each time?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems