Credit for this problem goes to dyland xue. Thanks!

Odd man out

As usual, you’re a derainged jailer who is going to play an awful game with your prisoners.

You have 600 prisoners and you line them up in a row. Each prisoner has a position in the line, starting with 1. Here’s where the “fun” starts.

You pick a prisoner, at random, who is in an odd position, they’re out (you know what that means). Everyone behind them in line, shifts down. So, for example, if the prisoner is position 3 was picked, then the prisoner in position 4 will shift down into position 3, 5 -> 4, 6 -> 5, and so on.

You continue doing this until there is only 1 prisoner left. The last remaining prisoner gets to go free.

Here’s the question: which starting position is best? As in, if you wanted to maximize your chance of winning this game, what position would you like to start in when there are still 600 prisoners?

Solution