Problem 5 · AMC 8 Stretch
Stretch
Number Theory
Counting & Probability
reduce-and-expandpattern-recognitionorganizing-datadivisor-counting
A hallway has 100 lockers, all closed, and 100 students. Student 1 walks by and opens every locker. Student 2 toggles every 2nd locker (2, 4, 6, ...), closing each one. Student 3 toggles every 3rd locker (3, 6, 9, ...) — opening it if closed, closing it if open. In general, Student \(k\) toggles every \(k\)-th locker. After all 100 students have gone by, how many lockers are still open?
Show answer
Answer: 10 lockers (the perfect squares)
Show hints
Hint 1 of 4
One hundred lockers is too many to track in your head. Reduce! Just do the first 10 or 12 lockers by hand. Mark each locker O (open) or C (closed) after each student passes. Which ones end up open?
Still stuck? Show hint 2 →
Hint 2 of 4
Focus on one locker, say locker 12. Which students touch it? Only the ones whose number divides 12 evenly: students 1, 2, 3, 4, 6, 12. So a locker gets toggled once for each of its divisors (factors).
Still stuck? Show hint 3 →
Hint 3 of 4
A locker starts closed. Each toggle flips it. So it ends OPEN only if it was toggled an ODD number of times — that is, only if its locker number has an ODD number of divisors.
Show solution
Approach: Reduce and expand — a locker ends open iff it has an odd number of divisors (perfect squares)
- Reduce the problem — trace just the first 12 lockers by hand, marking open (O) or closed (C). The lockers left open are 1, 4, 9: the perfect squares.
- Who touches a locker? Student \(k\) toggles locker \(n\) exactly when \(k\) divides \(n\). So locker \(n\) is toggled once for each of its divisors. Locker 12 has divisors 1, 2, 3, 4, 6, 12 — six toggles.
- Every locker starts closed and each toggle flips it, so a locker ends OPEN only if it is flipped an ODD number of times — its number must have an ODD number of divisors.
- Divisors normally come in pairs \((d, n/d)\), giving an even count. The count is odd only when one divisor pairs with itself, \(d \times d = n\) — exactly when \(n\) is a perfect square (e.g. 16 has divisors 1, 2, 4, 8, 16, an odd 5, because \(4 \times 4 = 16\)).
- The open lockers are the perfect squares up to 100: \(1, 4, 9, 16, 25, 36, 49, 64, 81, 100\) — that is \(1^2\) through \(10^2\), a total of \(10\) open lockers. (In the original 1000-locker version the answer is the perfect squares up to \(31^2 = 961\), so 31 open lockers.)
Mark:
· log in to save