100-gunmen brain-teaser

Problem — Suppose 100 gunmen stand in a big circle arranged by height, clockwise from #1 (lowest) to #100 (highest). In first shooting round, #1 starts off by shooting clockwise, so #2 gone. Then #3 shoots clockwise at #4, and so on. First round ends, and the lowest among the remaining gunmen continues to shoot clockwise. How many rounds will there be and who will be the last standing?
Assume each gunmen stays in his spot, and his spot has his name.
Analysis —
Let me first clarify the terminology.
* Each round has a “starter” shooter. The round ends immediately before he shoots again or immediately before he gets shot.
* Each round has a InitialCount being the number of gunmen immediately before that round.
Solution —
Round 1: starter is #1. InitialCount=100. This is an even round, so the starter remains.
Round 2: starter is #1. InitialCount=50. This is an even round, so the starter remains.
End of Round 2 the remaining shooters are #1 #5 #9… #97. They are 4 (i.e. 2^2) stops apart.
Round 3: starter is #1. InitialCount = 25. This is an odd round, so starter will shift anticlockwise by 2^2 to #97. Why am I so sure? Since InitialCount is odd, the highest (among the 25) gunmen will NOT die and will become the next round’s starter.
End of Round 3 the remaining gunmen are 8 (i.e. 2^3) stops apart. Therefore, highest two are #89 #97.
Round 4: starter is #97. InitialCount = 13. This is an odd round, so starter will shift anticlockwise by 2^3 to #89.
End of Round 4, the starter (#97) is a “sitting duck” to be shot soon.
Round 5: starter is #89. InitialCount = 7. This is an odd round, so starter will shift anticlockwise by 2^4 to #73.
End of Round 5, #89 is a “sitting duck” to be shot soon.
Round 6: starter is #73. InitialCount = 4, which is a power of 2, so #73 will remain the starter for all subsequent rounds and therefore the last standing.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s