Locker Problem

From ProofWiki
Jump to: navigation, search

Problem

There is a school with $100$ students, and correspondingly $100$ lockers, all of which start off closed.

The first student opens every locker. The second student closes every other locker, starting with the second.

The third student changes the state of every third locker, starting with the third. That is, if the locker is open, she closes it, and if it is closed, she opens it.

This continues similarly until all $100$ students have passed along the lockers.

After the $100$th student is done, which lockers are open and which are closed?


Solution

The square numbered lockers ($1$, $4$, $9$ ...) are open, and all others are closed.


Proof

Lockers switch state when a student whose number is a factor of the locker's number makes a pass.

Because they start closed, only those lockers whose state has been switched an odd number of times will finish open.

By definition, any factor of a number has another (not necessarily distinct) matching factor such that the product of the two is the multiple.

In most cases, these factor pairs have distinct elements; however, if the number in question is a square, then one of its pairs of factors is identical - namely, both parts of the pair are the number's square root.

Thus, square numbers will have their state switched an odd number of times, and will be left open, while all other numbers will have their state switched an even number of times, and will be left closed.

$\blacksquare$


Quicker Proof

Alternatively, we can take a less elementary, more rigorous, and far shorter approach:

The result follows trivially from Tau Function Odd Iff Argument is Square.

$\blacksquare$