A Hundred Doors, A Hundred Passes
The puzzle
A corridor has a hundred doors, numbered 1 to 100, all closed.
You make a hundred passes along it. On the first pass you toggle every door - open the closed ones, close the open ones. On the second pass you toggle every second door, on the third every third door, and so on until the hundredth pass, when you toggle only door 100.
Which doors are open at the end?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Door 12 is toggled on which passes? Write them down.
Hint 2
A door ends open if it was toggled an odd number of times. When does a number have an odd number of divisors?
Show the answer Hide the answer
The ten perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.
How to get there
Door n is toggled on pass k exactly when k divides n. So the number of times door n is touched is its number of divisors, and since every door starts closed, it ends open precisely when that count is odd.
Divisors normally come in pairs: if a divides n then so does n/a, and the two are different numbers. Pairing them up makes the count even - door 12 has 1 and 12, 2 and 6, 3 and 4. Six divisors, so it ends closed.
The pairing fails in exactly one case: when a equals n/a, which means n is a perfect square and its square root is its own partner. Door 36 has 1 and 36, 2 and 18, 3 and 12, 4 and 9, and then 6 alone. Nine divisors, so it ends open.
The perfect squares up to 100 are 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 - ten doors.
The technique worth keeping
The question asks about a process and the answer is a property of the numbers, which is the shape of a great many of these. Stop simulating the passes and ask what decides the final state of one door; here it is the parity of the divisor count, and that is a fact about n, not about the corridor.