Solution to 1000 Samurai (hard)

Who survives?

1000 Samurai stand in a circle. They are labeled 1 through 1000. Samurai 1 is handed a sword, which he uses to kill Samurai 2 and hands the sword to Samurai 3, who kills Samurai 4 … and so on around the circle until only one Samurai remains. What is the number of the last Samurai left?

Solution: We will solve the general case for N Samurai. It is easy to check that if there are N = 2^k Samurai for some k>1, then the Samurai left standing is the one labeled “1”. If there are N = 2^k + m Samurai, it is also easy to show that the one left standing is the one with label 2m+1. Since N = 1000 = 2⁹ + 488 = 512 + 488, the Samurai left standing is the one labeled 2x488+1 = 977.