exupero's blog
RSSApps

Locker doors puzzle

An old puzzle whose answer used to baffle me is one about a row of one hundred lockers that have students pass by opening or closing every Nth locker. The first student opens every locker, the second student opens or closes every second locker, the third student every third, and so on. After all 100 students pass by, which lockers remain open?

The answer is lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100—perfect squares. Why perfect squares should appear from nowhere I couldn't figure out. To see where they come from, I had to pivot the problem from thinking about students walking down the row of lockers to thinking about each locker and what students interacted with it.

Notice that the state of the locker depends on how many factors the locker's number has. Most numbers have an even number of factors because factors come in pairs: e.g., 8 has factors 1 and 8, and 2 and 4. Perfect squares, on the other hand, also have factors that come in pairs as well, but one of the pairs is just the same number twice, creating an odd number of distinct factors: 16 has factor pairs 1×16, 2×8, and 4×4. Students 1, 2, 4, 8, and 16 will toggle locker #16's door, but even though 4×4 is a factor pair, the fourth student only toggles the door once, which creates the imbalance that leaves locker #16 to open at the end.

What's clever about this puzzle is that it stems from a simple observation about how many distinct factors different kinds of numbers have, but that observation has been pivoted and hidden inside a sequential puzzle that seems tedious and manual to work out. Someone did that deliberately, but probably a lot of life's puzzles hide similar observations accidentally, and a little pivot to how we're thinking about it can help us cut through the tedium to find something slightly magical.