Why do some doors end up open in the 100-doors toggle puzzle?

I’m working through the classic 100-doors puzzle and I’m so close but still stuck on the exact reasoning. Setup: there are 100 doors, all closed. On pass 1 I toggle every door, on pass 2 I toggle every 2nd door, on pass 3 every 3rd door, and so on up to pass 100. Which door numbers end up open at the end, and why?

Here’s my attempt: I noticed door n gets toggled once for every divisor of n. So the total number of toggles for door n seems to be the number of its positive divisors. If that count is even, the door goes back to closed (since it started closed); if it’s odd, it ends open. That made me think: maybe the special case is when a factor doesn’t have a distinct partner, like with squares? For example, 12 has pairs (1,12), (2,6), (3,4), which is an even count, but 9 has divisors 1, 3, 9 where 3 feels like it’s “paired with itself,” which is where my brain goes fuzzy. Am I double-counting or under-counting something subtle there?

Analogy that might be nonsense: I’m picturing the divisors as dancers lining up in pairs so everybody toggles twice, except occasionally one dancer has to dance with their mirror image and only dances once, making the total odd. Is that a valid way to think about it, or am I forcing the metaphor too hard?

My confusion: I get the high-level idea that the parity of the number of divisors decides each door’s fate, but I can’t nail down a clean, rigorous reason for exactly which n have an odd number of divisors. Also, when I list small examples, I see a pattern in which door numbers behave differently, but I can’t justify it without handwaving.

Could someone explain, step by step, how to identify precisely which doors finish open using solid reasoning (not just pattern spotting)? And if there’s a quick invariant-style argument that makes it feel obvious, I’d love to hear that too!

One Response

  1. You’re on the right track. Door n is toggled once for each positive divisor of n, so its final state depends on whether n has an odd or even number of divisors. Divisors come in pairs: if d divides n, then so does n/d, and usually d ≠ n/d, so they contribute two toggles together. The only time a divisor fails to pair with a distinct partner is when d = n/d, i.e., when d^2 = n. That means exactly the perfect squares have one unpaired divisor (their square root), giving an odd count of divisors and ending open. All non-squares have their divisors in distinct pairs and end closed.

    A more algebraic way to see the same thing: if n = p1^a1 · p2^a2 · … · pk^ak, then the number of divisors is (a1+1)(a2+1)…(ak+1). This product is odd exactly when every ai is even, i.e., when n is a perfect square. So, unless I’m overlooking an edge case, the open doors are precisely the squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

Leave a Reply

Your email address will not be published. Required fields are marked *

Join Our Community

Ready to make maths more enjoyable, accessible, and fun? Join a friendly community where you can explore puzzles, ask questions, track your progress, and learn at your own pace.

By becoming a member, you unlock:

  • Access to all community puzzles
  • The Forum for asking and answering questions
  • Your personal dashboard with points & achievements
  • A supportive space built for every level of learner
  • New features and updates as the Hub grows