AMC 10 · 2016 · #7

Grade 6 counting
Archetype Branching State Enumeration └ Sub-archetype Rule-Governed Process Simulation
pattern-recognitionmultiplesexponents pattern-recognitioneasier-related-problem ↑ Prerequisites: multiplespattern-recognition
📏 Medium solution 💡 3 insights
Problem
Every other survivor is struck out, sweep after sweep, until one remains. Find the survivor.

Pick an answer.

(A)
13
(B)
32
(C)
56
(D)
64
(E)
96
How to solve
Strategy Look for a Pattern

Simulating all 100 numbers by hand is slow and error-prone, but the survivors after each sweep form a very regular set. So run Tool #2 (Make a Systematic List) on the first two sweeps to see exactly who lives, then switch to Tool #5 (Look for a Pattern) to prove the rule that turns one sweep's survivors into the next sweep's survivors. Once that rule is nailed down, the whole problem collapses into counting how many sweeps it takes to get down to one number. Tool #9 (Solve an Easier Related Problem) gives a cheap sanity check afterwards on a shorter list.

1STEP 1

Run the first sweep

One sweep leaves only the even numbers.

after sweep 1: 2,4,6,8,…,100 (50 numbers, all multiples of 2)
2STEP 2

Run the second sweep

A second leaves only the multiples of four.

after sweep 2: 4,8,12,…,100 (25 numbers, all multiples of 4)
3STEP 3

Prove the doubling rule

The spacing provably doubles each time.

j · 2^k survives⇔ j=2m → 2m · 2^k=m · 2^k+1
4STEP 4

Count survivors sweep by sweep

Counting survivors runs down to one.

50, 25, 12, 6, 3, 1 survivors after sweeps 1,2,3,4,5,6
5STEP 5

Identify the last survivor

The last one is 64, choice (D).

2⁶=64 ≤ 100 ＜ 128=2⁷ → last survivor=64 → (D)
Answer
64
Two checks agree. First, the survivor must be a multiple of 2, then of 4, then of 8, and so on for as long as the sweeps continue, so it has to be highly even — that alone kills 13 and 56. Second, running the sweeps explicitly gives 2,4,…,100, then 4,8,…,100, then 8,16,…,96, then 16,32,48,64,80,96, then 32,64,96, then 64, matching the counts 50,25,12,6,3,1. The near-misses behave exactly as the rule predicts: 96 survives five sweeps and then falls, and 32 falls at the same moment because it is first in line. Answer 64 is confirmed.
💡Key takeaway

Each sweep keeps every second number, so the gap between survivors doubles every time, and the one number that lasts to the end is the biggest power of 2 in the list.

  • Run the first sweep
  • Run the second sweep
  • Prove the doubling rule
  • Count survivors sweep by sweep
  • Identify the last survivor

More like this

Same archetype — closest grade level first.