Problem 4 · AMC 8 Stretch
Stretch
Number Theory
Logic & Word Problems
solve-a-simpler-problempattern-recognition
People stand in a circle, numbered \(1, 2, 3, \dots, N\) clockwise. Person \(1\) says 'one' and stays. Person \(2\) says 'two' and steps OUT. Person \(3\) stays, person \(4\) steps out, and so on around and around: every other person leaves. The counting keeps going (it does NOT restart) until one person is left. Who survives when \(N = 100\)?
Show answer
Answer: Person 73
Show hints
Hint 1 of 4
One hundred is too many to act out. Solve smaller versions first! Make a table: for \(N = 1, 2, 3, 4, 5, 6, 7, 8\), who survives?
Still stuck? Show hint 2 →
Hint 2 of 4
Notice the rows where the survivor is person \(1\). They happen at \(N = 1, 2, 4, 8, 16, \dots\) — the powers of \(2\). What pattern do you see between those points?
Still stuck? Show hint 3 →
Hint 3 of 4
Write \(N\) as (a power of \(2\)) plus a leftover: \(N = 2^k + L\), where \(2^k\) is the biggest power of \(2\) that is not bigger than \(N\). The survivor turns out to be a simple formula in \(L\).
Show solution
Approach: Solve a simpler problem, find the pattern, then apply the formula
- Build a table of survivors for small \(N\):
N 1 2 3 4 5 6 7 8 survivor 1 1 3 1 3 5 7 1 - The survivor is person \(1\) exactly when \(N\) is a power of \(2\) (\(1, 2, 4, 8, 16, \dots\)). Between powers of \(2\), the survivor jumps up by \(2\) each time (\(1, 3, 5, 7, \dots\)) and then resets to \(1\).
- So write \(N = 2^k + L\), where \(2^k\) is the biggest power of \(2\) that fits inside \(N\) and \(L\) is the leftover. The survivor's number is \(2L + 1\).
- For \(N = 100\): the biggest power of \(2\) that is \(\le 100\) is \(64\), so \(L = 100 - 64 = 36\) and the survivor is \(2(36) + 1 = 73\).
Mark:
· log in to save