n² · The Hundred Doors
The Hundred Doors
A hallway has 100 closed doors. Person 1 toggles every door, person 2 toggles every 2nd door, person 3 every 3rd… After person 100 passes, which doors are open?
After 100 people have passed, how many doors are still open?
Think about it first
Make a prediction first. Change one input at a time and compare what happens with what you expected.
All 100 doors start closed. Press the button to send people through, one at a time.
Read the solution when you are ready
A door's fate is decided by how many times it was touched.
Why does this question matter?
The hundred doors — also known as the locker problem — is a classic of mathematical puzzles. The only rule is multiples, which a ten-year-old knows, yet almost nobody guesses the outcome right away.
The problem's true face is not toggling but counting. The people who touch door n are exactly the people whose numbers divide n. So a door's fate translates into the parity of its divisor count.
What stays with you is the translation, not the answer. The moment a 'problem about motion' becomes a 'problem about counting', the answer falls out by itself. Compressing a long process into one structure is the heart of mathematical thinking.
Read the idea from another angle
Forget the doors — count the people who touch them.
The people who stop at door n are those whose numbers divide n: the divisors of n. A complicated march of 100 people compresses into a static structure, the divisor count.
Even counts undo themselves; only odd counts leave a trace.
Open then close, and nothing happened. If a door is touched an even number of times it ends as it began. Only doors touched an odd number of times — doors with an odd number of divisors — stay open. Those are the perfect squares.
Now read the definitions with their conditions
Let's translate what you saw into the language of symbols. The one key is the translation: 'the people who touch door n = the divisors of n'.
Formula anatomy — a toggling problem becomes a divisor-counting problem
⇢
The translation (count the touchers)
Person k touches door n exactly when n is a multiple of k — that is, when k divides n. Motion becomes counting.
Divisors pair up
Find a divisor d and n÷d is a divisor too. Divisors come two by two, so their count is usually even.
The unpaired one
In a perfect square, √n partners with itself (4×4 = 16). That single unpaired divisor makes the count odd — and leaves the door open.
Make one more distinction
The doors touched by the most people should end up open.
How many times a door is touched doesn't matter — only whether that count is odd or even. An even number of touches puts a closed door right back; only an odd count leaves it open.
Divisors always come in pairs.
Almost always. The divisors of 12 pair up as 1×12, 2×6, 3×4. But for 16, the pair 4×4 makes 4 its own partner. Only perfect squares have such an unpaired divisor, which makes their divisor count odd.
Where else can this idea help?
A classic of interviews and algorithm courses
Under the name 'locker problem' it appears constantly in coding interviews and algorithm classes — built to tell apart people who simulate from people who answer by structure.
Parity bits — odd/even catches errors
Computer communication appends a single parity-check bit to detect transmission errors. 'Forget the count, keep the parity' — today's exact way of thinking, at work.
The divisor-count formula
Factor n into primes and the divisor count becomes a product: 12 = 2²×3 gives (2+1)×(1+1) = 6 divisors. Counting by structure, not door by door.
Light-switch puzzles
Puzzles where many people flip switches in turn almost always fall to a single parity argument. However long the process, only the parity survives.
Explain it in your own words
Check the idea with practice problems (4)
Questions completed 0 / 4
1. The number of people who touch door n equals…
2. After all 100 people pass, door 49 is…
3. With 1,000 doors and 1,000 people, how many doors end up open?
4. Why do only perfect squares have an odd number of divisors?
What question comes next?
Previous concept
The Tower of Hanoi
The last problem was about splitting; this one is about translating — the second weapon of problem solving.
← The Tower of Hanoi labLeads to next
Divisors & Multiples
Meet the divisors that decided the doors' fate head-on — the rhythm of divisibility continues.
Go to the Divisors & Multiples lab →Related lab
Prime Numbers
Prime factorization builds the divisor-count formula — counting without counting doors.
Go to the Prime Numbers lab →Related lab
Square Roots
The identity of the unpaired divisor √n — the bond between squares and square roots lives here.
Go to the Square Roots lab →