Problem #28 HARD
The Survivor's Position
Google Adobe Combinatorics Logic
Problem Statement
A group of n soldiers stand in a circle, numbered 1 through n clockwise. Starting with soldier 1, every second soldier is eliminated — soldier 2 is first out, then soldier 4, and so on, going around the circle as many times as needed. The last soldier standing receives a prize. For any given n, which position should you choose to guarantee survival?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Winning position = 2L + 1, where L = n minus the largest power of 2 that does not exceed n. Binary shortcut: write n in binary, rotate the leading '1' to the end, convert back to decimal.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Let n = 2^m + L where 0 ≤ L < 2^m. The winner's seat number W(n) = 2L + 1. This arises from a recurrence relation that has binary structure at its core.
Step 1: Establish base cases: n=1 → W=1. n=2 → soldier 2 is eliminated first, so W=1. n=3 → W=3. n=4 → W=1.
Step 2: Recurrence: with an even number 2k of soldiers, after one full revolution the circle halves and soldier 1 is now effectively in a new position. W(2k) = 2·W(k) − 1. For odd 2k+1: W(2k+1) = 2·W(k) + 1.
Step 3: Binary shortcut: write n in binary. Move the leftmost '1' bit to the rightmost position (cyclic left-rotation). Read the result as a decimal.
Step 4: Example n = 10: binary = 1010. Remove leading 1 → 010. Append 1 at the right → 0101 = 5. Winning position: 5.
Step 5: Example n = 6: binary = 110. Remove leading 1 → 10. Append 1 → 101 = 5. Winning position: 5.
Step 6: Verify: n=6, eliminations in order: 2, 4, 6, 3, 1 → survivor is 5. Confirmed.
Key Insight:
Powers of 2 are the 'reset points' — with exactly 2^m soldiers, soldier 1 always wins because the eliminations cycle perfectly. For any extra L soldiers beyond the nearest power of 2, the winner shifts forward by 2L positions.