Pirates in Circle

1000 pirates stand in a circle, numbered 1 to 1000. Pirate 1 kills pirate 2 and passes the dagger to pirate 3, who kills pirate 4 and passes to pirate 5, and so on. This continues until only one pirate remains. Who is the last pirate standing?

Answer

Initially let’s check small $$n$$ : for $$n=2,3,4$$ ... for $$n=4$$ we have Pirate 1 kills 2, Pirate 3 kills 4, then Pirate 1 kills 3. This gives the first insight: in each round exactly half the pirates die, and if you start first you survive when $$n$$ is a power of 2. For $$n=1000$$ , the largest power of 2 below 1000 is $$512$$ . To reduce from 1000 to 512 pirates we must kill $$1000-512=488$$ pirates. Each kill shifts the “first-in-line” position by two, so $488\times2=976$ . Hence the survivor is pirate number

976 + 1 \;=\; 977.

Notes and comments

Comment 1: For $$n=100$$ , the nearest lower power of 2 is 64, so $(100-64)\times2+1=73$ .