The Locker Problem: Perfect Squares & Divisors
What This Problem Teaches
- Divisor analysis: Understanding how the number of divisors determines the final state
- Perfect square recognition: Identifying why only perfect squares have odd numbers of divisors
- Parity reasoning: Using even/odd properties to determine outcomes
- Pattern abstraction: Moving from specific cases to general mathematical principles
- Logical deduction: Working systematically through complex multi-step processes
Solution: Method 1 — The Divisor Count Approach
The key insight is recognizing when each locker gets toggled. Let's trace the pattern systematically.
Step 1 — Identify the toggle pattern
Locker number n gets toggled on day d if and only if d divides n evenly. For example:
- Locker 12 gets toggled on days: 1, 2, 3, 4, 6, and 12 (the divisors of 12)
- Locker 16 gets toggled on days: 1, 2, 4, 8, and 16 (the divisors of 16)
Step 2 — Count the total toggles
Since all lockers start open on day 1, a locker's final state depends on how many times it gets toggled:
Odd number of toggles → Locker ends OPEN
The number of toggles equals the number of divisors of that locker number.
Step 3 — Analyze divisor patterns
Let's examine some specific cases:
| Locker | Divisors | Count | Final State |
|---|---|---|---|
| 6 | 1, 2, 3, 6 | 4 (even) | Closed |
| 8 | 1, 2, 4, 8 | 4 (even) | Closed |
| 9 | 1, 3, 9 | 3 (odd) | Open |
| 12 | 1, 2, 3, 4, 6, 12 | 6 (even) | Closed |
| 16 | 1, 2, 4, 8, 16 | 5 (odd) | Open |
Step 4 — Discover the perfect square pattern
Notice that 9 and 16 are both perfect squares and both stay open. This isn't a coincidence! For most numbers, divisors come in pairs: if d divides n, then n/d also divides n.
For example, with 12: (1,12), (2,6), (3,4) — three pairs, so 6 total divisors.
But for perfect squares, one "pair" is actually the same number twice. For 16: (1,16), (2,8), (4,4) — the last pair is really just 4, so we count 5 divisors total.
Step 5 — List all perfect squares from 1 to 100
The perfect squares from 1 to 100 are:
6² = 36, 7² = 49, 8² = 64, 9² = 81, 10² = 100
Solution: Method 2 — The Pairing Argument
Here's a more elegant way to see why only perfect squares survive, using the divisor pairing principle directly.
Step 1 — Understand divisor pairing
For any positive integer n, divisors naturally pair up: if a divides n, then n/a also divides n. These form pairs (a, n/a).
Step 2 — Count pairs vs. individuals
Most numbers have all their divisors in distinct pairs, giving an even count. But when a = n/a, we have a² = n — meaning n is a perfect square and a pairs with itself.
Step 3 — Apply the odd/even principle
Step 4 — Visualize the final state
Since all lockers start open and get toggled once for each divisor, only numbers with odd divisor counts (perfect squares) end up open.
Verification
Let's verify our answer by checking a few specific cases:
Locker 25: Divisors are 1, 5, 25. That's 3 toggles (odd), so it stays open. ✓
Locker 24: Divisors are 1, 2, 3, 4, 6, 8, 12, 24. That's 8 toggles (even), so it ends closed. ✓
Locker 49: Divisors are 1, 7, 49. That's 3 toggles (odd), so it stays open. ✓
Count check: There are exactly 10 perfect squares from 1 to 100, and we found 10 open lockers. ✓
Watch Out For These
The Pattern Behind This
This problem illustrates a fundamental principle about divisors:
Why this works: Divisors pair up as (d, n/d). The only time a divisor pairs with itself is when d = n/d, which means d² = n. That unpaired middle divisor is what gives perfect squares their odd count.
General application: This principle appears in many contexts beyond locker problems — anywhere you need to count factors, find divisors, or analyze toggle patterns.
Beyond the Textbook
Computer science: Toggle patterns appear in bit manipulation algorithms, where flipping bits follows similar divisor-based rules.
Number theory: This connects to the study of divisor functions — mathematical tools that count or sum divisors systematically.
Combinatorics: The pairing argument used here is a fundamental technique for proving that certain sets have even or odd cardinality.
A Brief History
The locker problem is a modern variation of ancient divisor puzzles that appeared in early number theory. Greek mathematicians knew that perfect squares had special divisor properties, though they expressed it in geometric terms — perfect squares could be arranged as actual squares of dots.
The "toggle" format became popular in 20th-century recreational mathematics as a way to make divisor theory more concrete and visual. It's now a standard problem in discrete mathematics courses because it connects abstract number theory to a process students can visualize and simulate.
Try These Variations
All lockers start closed instead of open. The janitor follows the same pattern: Day 1 toggles every locker, Day 2 toggles every 2nd locker, etc. Which lockers are open after 100 days?
The pattern is identical — each locker gets toggled once for each of its divisors. The only difference is the starting state.
Starting closed: odd toggles → open, even toggles → closed. This is exactly the same rule as before!
Perfect squares still have odd numbers of divisors, so they still end up open.
Starting state doesn't matter — only the parity of toggles matters. The answer is still the perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
The janitor works for 200 days total. Days 1-100 follow the original pattern, then Days 101-200 repeat the exact same pattern (Day 101 = Day 1, Day 102 = Day 2, etc.). Which lockers are open after all 200 days?
Each locker gets toggled exactly twice as many times — once for each divisor in the first 100 days, then again for each divisor in the second 100 days.
If a locker had d divisors originally, it now gets 2d toggles total. Since 2d is always even, every locker ends up closed.
Locker 16 originally had 5 toggles (odd) and stayed open. Now it has 10 toggles (even) and ends closed.
After 200 days, all lockers are closed. Doubling an odd number gives an even number, so perfect squares lose their special status.
The janitor only works on prime-numbered days: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. On each prime day p, every locker whose number is divisible by p gets toggled. Which lockers are open?
Locker n gets toggled on prime day p only if p divides n. So locker n gets toggled once for each prime divisor it has.
Examples: Locker 30 = 2×3×5 has prime divisors {2,3,5}, so 3 toggles. Locker 32 = 2⁵ has only prime divisor {2}, so 1 toggle.
Numbers with an odd number of distinct prime factors stay open. This includes all primes (1 prime factor) and products of odd numbers of distinct primes.
Open lockers: All prime numbers 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, plus products like 6=2×3, 10=2×5, 14=2×7, 15=3×5, etc.
Same as the original problem (start open, 100 lockers), but the janitor skips any day that is a perfect square. So Days 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 are skipped entirely. The janitor works on days 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, etc. Which lockers are open now?
The janitor works on all days from 1-100 except {1,4,9,16,25,36,49,64,81,100}. So working days are all non-perfect-square numbers in this range.
Locker n gets toggled once for each of its divisors that is NOT a perfect square. For example, locker 12 has divisors {1,2,3,4,6,12}, but Day 1 and Day 4 are skipped, so it gets toggled on Days {2,3,6,12} — 4 times total.
Perfect squares lose their "unpaired" divisor (their square root) since that day is skipped. For example, locker 36 has divisors {1,2,3,4,6,9,12,18,36}, but Days {1,4,9,36} are skipped. Remaining: {2,3,6,12,18} — 5 toggles, which is odd!
Counterintuitively, perfect squares still end up open! Skipping perfect square days removes an even number of toggles (the perfect square divisors), preserving the odd parity.
Frequently Asked Questions
2026-07-04