This past week, I flew out to New York. Unfortunately, I forgot my phone charger and used the majority of my laptop’s battery life while working at the gate (doh!). Thus, after completing the Sudoku in the airline magazine and getting my fill of the SkyMall catalog, I began to look around. After a while, I felt like David Puddy from Seinfeld (see video for reference)!
Then, for whatever reason, my eye caught those overhead cabinets and I began to think of a brainteaser. I share it with you today.
For arguments sake, let’s imagine a very large plane where there are 100 overhead cabinets on one side of the aisle. Suppose I start from the back of the plane and open every single one of them, one at a time, until I open the last one in first class. Then, suppose I go to the back of the plane again and proceed to close every other cabinet starting with the second one. Now suppose on this third round, I go to every third cabinet and close it if it’s open, or open it if it’s closed.
Define: An n-round to be the round of walking from the back to the front of the plane opening (or closing if appropriate) every nth cabinet.
The Question: For n from 1 to 100, suppose I perform an n-round. After the 100th n-round, where I either open or close the 100th cabinet, how many cabinets are left open?
Give yourself some time to think about it before scrolling down to the answer!
The Answer: After the 100-round, there are 10 cabinets left open. Specifically, they are the cabinets 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. Notice that these are the perfect squares in the interval from 1 to 100—this is no coincidence. Let’s think about what’s really going on in this problem.
Whenever I reach a cabinet, it’s because I am either starting at that cabinet, or that cabinet is a non-trivial multiple of the n in that given n-round. Either way, I perform a close or an opening at the mth cabinet if and only if the given n in that n-round is a factor of m. So, since we perform enough n-rounds to exhaust all of the factors of every single cabinet, whether a cabinet is open or closed at the end of our 100 n-rounds depends solely on the number of factors that cabinet has. If it has an even number of factors, it will be closed at the end. If it has an odd number of factors, it will be open.
It turns out that a natural number, n has an odd number of factors if and only if it is a perfect square!
Proof: Let n be given. Suppose a number d is a factor of n. Then, n=dk for some integer k. Notice that k is also a factor of n; thus, when d and k are distinct from one another, we can think of them as a factor pair. If d and k are not distinct, that is, if , then without loss of generality, .So, if n has an odd number of factors, then aside from its factor pairs, there must exist one factor without a distinct partner, which means that n is a perfect square. If n is a perfect square, then its factors consist of some number of factor pairs, plus ; thus, n has an odd number of factors.
Back to the cabinets: There is nothing special about the number of cabinets being 100. Given the scenario described above, it follows that we can extend this to n cabinets performing n n-rounds. Then, the open cabinets will be those perfect squares from 1 to n inclusive.
Notice that if we perform less than n n-rounds, this result is not necessarily true. Can you see why? If so, feel free to comment!