The locker problem - why squares?
There are 1000 lockers in a high school with 1000 students. The problem begins with the first student opening all 1000 lockers; next the second student closes lockers 2,4,6,8,10 and so on to locker 1000; the third student changes the state (opens lockers closed, closes lockers open) on lockers 3,6,9,12,15 and so on; the fourth student changes the state of lockers 4,8,12,16 and so on. This goes on until every student has had a turn.
How many lockers will be open at the end?
I worked out this problem by doing it for 10 lockers. The pattern was obvious (1,4,9 remained open).It's easy to then say that 31 lockers remain open at the end. I don't quite understand why only square numbers remain open at the end. Is there some deeper reason?
$\endgroup$ 14 Answers
$\begingroup$Squares are the only integers which have an odd number of divisors.
All other (non-square) integers have an even number of divisors.
A deeper insight:
Given an integer $n$, for every integer $d$ which divides $n$, the integer $n/d$ also divides $n$.
If $n$ is non-square, then for every integer $d$ which divides $n$, the integer $n/d \neq d$.
So we can split the divisors of $n$ into pairs, hence $n$ has an even number of divisors.
If $n$ is square, then for every integer $d\neq\sqrt{n}$ which divides $n$, the integer $n/d \neq d$.
So we can split the divisors of $n$ except $\sqrt{n}$ into pairs, hence $n$ has an odd number of divisors.
$\endgroup$ 4 $\begingroup$If a locker number has an even number of factors, it will be alternatively opened and closed and even number of times, ending in the same configuration it started.
Square numbers have a odd number of factors.
$\endgroup$ $\begingroup$The idea here is that it is easy to identify pairs of students who will open and close a locker (well, as easy as any interesting math problem ever is!). If any given student will open or close a locker, it means their number is a divisor of the locker's number.
Consider locker X. Let's assume there is a student Y who toggles the locker. This means we know X/Y is an integer. This also means that student X/Y will also toggle the locker.
Take locker 12, with factors 1, 2, 3, 4, 6, and 12. If I rearrange them into pairs, (1, 12) (2, 6) (3, 4) we can see that for every student who opens a locker, there will be one that closes the locker.
Now, Let's look at a square. Let's take 16, with factors 1, 2, 4, 8, 16. If I rearrange them into pairs I get (1, 16) (2, 8) (4, 4)... but wait... I just had to use 4 twice. I had to do that because it was a square. However, student 4 is only going to toggle locker 16 once. Thus, the locker will be left open at the end of the day!
$\endgroup$ $\begingroup$Locker number $n$ is toggled once for each divisor of $n$. If $n$ is not a square, then the map $d \to n/d$ is a bijective map on the set of divisors $S_n$ of $n$. Thus $S_n$ has an even number of elements; it is the disjoint union of the sets of the form $\{d, n/d\}$, each of which contains $2$ elements. If $n$ is a square, then $S_n$ is the union of sets $\{d, n/d\}$ for $d^2\not = n$ and a singleton set $\{\sqrt{n}, \sqrt{n}\}$. Hence the size of $S_n$ is odd. Toggling a closed locked $n$ times leaves it closed if $n$ is even and open if $n$ is odd.
$\endgroup$
