Problem 5 · AMC 8 Stretch
Core
Number Theory
pattern-recognitionlogical-reasoning
A hallway has \(100\) lockers, numbered \(1\) to \(100\), all closed. Student \(1\) opens every locker. Student \(2\) changes (opens if closed, closes if open) every \(2\)nd locker: \(2, 4, 6, \dots\). Student \(3\) changes every \(3\)rd locker: \(3, 6, 9, \dots\). This continues through student \(100\). After all \(100\) students go by, how many lockers are OPEN?
Show answer
Answer: 10 lockers (the perfect squares)
Show hints
Hint 1 of 4
Pick one locker, say number \(12\), and figure out exactly which students touch it. A student numbered \(n\) touches locker \(12\) only if \(n\) divides \(12\).
Still stuck? Show hint 2 →
Hint 2 of 4
So locker \(m\) gets touched once for each divisor of \(m\). A locker ends OPEN if it was touched an ODD number of times. So the question becomes: which numbers have an odd number of divisors?
Still stuck? Show hint 3 →
Hint 3 of 4
Divisors usually come in pairs. For \(12\): \((1, 12), (2, 6), (3, 4)\) — that is \(6\) divisors, an even number, so locker \(12\) ends closed. When does a divisor get paired with ITSELF?
Show solution
Approach: Count divisors; perfect squares have an odd number of divisors
- Focus on one locker, number \(m\). Student \(n\) touches it exactly when \(n\) divides \(m\). So locker \(m\) gets touched once for every divisor of \(m\), and it ends OPEN when the number of divisors is ODD.
- Divisors come in pairs \((d, m/d)\). For example \(12\) has the pairs \((1,12), (2,6), (3,4)\) — six divisors, an even number, so locker \(12\) ends closed.
- The only way to get an ODD count is when one divisor pairs with itself, meaning \(d = m/d\), so \(m = d^2\). For example \(9\) has divisors \(1, 3, 9\): the pair \((3,3)\) is just one number, giving the odd count \(3\).
- So the lockers that stay open are exactly the perfect squares \(1, 4, 9, 16, 25, 36, 49, 64, 81, 100\) — ten lockers.
Mark:
· log in to save