Every Third Man in the Circle
The puzzle
Forty-one people stand in a circle. Starting the count at position 1, every third person is removed from the ring, and the counting continues from the next person still standing.
Which position is the last one left? Simulating it works but takes a page; there is a way to compute it in forty lines of arithmetic.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Solve it for a circle of one. Then two. Then three. Look at how the answer moves.
Hint 2
If you know the survivor for n-1 people, the survivor for n is that position shifted round by k.
Show the answer Hide the answer
Position 31. (With every SECOND person removed instead, the survivor is position 19.)
How to get there
Number the positions from 0 for the arithmetic. With one person, the survivor is 0. Now add a person: after the first removal the circle is the same as the smaller problem, but rotated. That gives the recurrence J(n) = (J(n-1) + k) mod n, with J(1) = 0.
Running it for k = 3 from n = 1 up to n = 41 takes forty steps of add-three-and-take-the-remainder, and lands on 30. Adding one to convert back to positions numbered from 1 gives 31.
The k = 2 case has a closed form worth knowing: write n as 2^m + L, and the survivor is 2L + 1. For 41 = 32 + 9 that gives 19, which is where you would stand if every second person were removed. No such tidy formula exists for k = 3, which is why the recurrence is the method.
The technique worth keeping
When a process shortens the problem by one each round, look for a recurrence relating the answer for n to the answer for n-1. Solving the smallest cases first and watching how the answer moves is how you find it.