100 Doors Puzzle: Parity, Perfect Squares, Divisor Counts

The 100 Doors Puzzle: Parity, Perfect Squares, and Why Divisor Counts Matter

The 100 doors puzzle is a beautiful number-theory interview question. The setup: 100 doors, all initially closed. 100 people walk past. Person k toggles every kth door. After all 100 people have walked past, which doors are open? The answer involves divisor counts and reveals a deep connection to perfect squares. This guide covers the puzzle, the elegant solution, and the variations interviewers ask.

Problem Statement

Doors 1 through 100, all initially closed.

• Person 1 toggles every door (every 1st door): doors 1, 2, 3, …, 100.
• Person 2 toggles every 2nd door: doors 2, 4, 6, …, 100.
• Person 3 toggles every 3rd door: doors 3, 6, 9, …, 99.
• …
• Person 100 toggles every 100th door: door 100.

“Toggle” means flip the state — closed becomes open, open becomes closed. After all 100 people have walked past, which doors are open?

The Naive Approach

Simulate. For each door d, count how many people toggle it; if odd, it ends open; if even, it ends closed.

def doors_after_toggling(n: int) -> list[bool]:
    """Simulate the puzzle. Returns list of door states; True = open."""
    doors = [False] * (n + 1)  # 1-indexed
    for person in range(1, n + 1):
        for door in range(person, n + 1, person):
            doors[door] = not doors[door]
    return doors[1:]


# Test
result = doors_after_toggling(100)
open_doors = [i + 1 for i, state in enumerate(result) if state]
print(open_doors)  # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

The output is the perfect squares from 1 to 100. There are 10 of them.

Complexity: O(n × n) for the simulation. Acceptable for n = 100; impractical for very large n. Strong candidates derive the result analytically.

The Elegant Answer: Doors at Perfect Squares Are Open

Door d is toggled by person k if and only if k divides d. So door d is toggled exactly τ(d) times, where τ(d) is the number of divisors of d.

Door d ends open iff τ(d) is odd.

For most numbers, divisors come in pairs: if k divides d, then d/k also divides d. So τ(d) is typically even. The exception: when k = d/k, i.e., k² = d, i.e., d is a perfect square. In that case, k is paired with itself, contributing only one to the divisor count instead of two.

Therefore, τ(d) is odd if and only if d is a perfect square.

For n = 100, the perfect squares are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. Ten doors end open.

def perfect_square_doors(n: int) -> list[int]:
    """Return doors that end open (perfect squares ≤ n)."""
    result = []
    k = 1
    while k * k <= n:
        result.append(k * k)
        k += 1
    return result


print(perfect_square_doors(100))
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Complexity: O(√n) time, O(√n) space (for the result). Massively faster than the simulation.

Why Perfect Squares Have Odd Divisor Counts

For any integer d, the divisors come in pairs (k, d/k). Each divisor k corresponds to its complement d/k. The pair contributes 2 to τ(d).

The exception is when k = d/k, which requires k² = d. This means d is a perfect square; the divisor k = √d pairs with itself, contributing 1 instead of 2.

For non-square d: all divisor pairs are distinct → τ(d) is even.

For square d: one divisor pairs with itself; rest pair distinctly → τ(d) is odd.

Verification:

• d = 6: divisors {1, 2, 3, 6}. τ(6) = 4. Even. Door 6 ends closed.
• d = 9 = 3²: divisors {1, 3, 9}. τ(9) = 3. Odd. Door 9 ends open.
• d = 16 = 4²: divisors {1, 2, 4, 8, 16}. τ(16) = 5. Odd. Door 16 ends open.

Common Variations

K people instead of N

Only k people walk past (k < n). Door d is toggled τ(d, k) times, where τ(d, k) is the number of divisors of d that are at most k. Doors open iff this count is odd. The “perfect square” answer no longer applies cleanly — now it depends on which divisors fall within k.

Doors initially open instead of closed

Same toggling logic, just inverted. Doors initially open end closed iff toggled an odd number of times → perfect squares end closed; non-squares end open.

Bidirectional walks

Each person walks past twice (or N times). The toggle count multiplies, but parity changes only when the multiplier is odd. Most “k passes” variants reduce to a single equivalent puzzle.

Mod-3 or mod-K state instead of toggle

“Each visit increments the door’s counter; door is open iff counter ≥ K.” Different problem; the divisor-count insight no longer applies directly.

What Interviewers Test

• Recognize that the simulation’s answer (perfect squares) suggests a deeper structure
• Connect “door d toggled if person k divides d” to divisor counts
• Realize divisors pair except for perfect squares
• Conclude: doors at perfect squares end open

Strong candidates derive the answer without simulation, then verify on small cases. Weaker candidates simulate and stop without seeing the structure.

Frequently Asked Questions

See also: Bridge Crossing Puzzle • Fruit Jar Labeling Puzzle • Power of Two Check