There are one thousand students at the George Washington
High School. Each student is assigned a locker, numbered 1 through
1000. On the first day of school each year, the students participate
in an unusual ritual: The students enter the school through one door,
parade past the all the lockers, and then exit through another door.
While in the school, the first student reverses the door position of each
locker -- if the door is open, he closes it, and if it is closed, he opens
it. The second student reverses the door position of every other
locker, starting with locker number 2. The third student
reverses every third locker, starting with locker number 3, etc.
After all 1000 students have completed this ritual, which lockers will be
left open?
Answer:
The lockers whose numbers are perfect squares will be left open.
That's because only a perfect square has an odd number of factors, and
only numbers with an odd number of factors are perfect squares.
Why is this true?
Consider a number, n, and its prime factorization 2a 3b
5c 7d 11e 13f...
The the set of factors of n are {2i 3j 5k 7l
11m 13n..., such that i ranges from 0 to a, j
ranges from 0 to b, etc.}
Therefore, the number of elements of this set is
(a+1)(b+1)(c+1)(d+1)(e+1)(f+1)...
The only way for this number to be odd is if each of a+1, b+1, etc is
odd, or, in other words, if each of a, b, etc. is even.
If each of a, b, etc. is even, then n is a perfect square -- it is the
square of 2a/2 3b/2 5c/2 7d/2 11e/2
13f/2...
Let's take an example to illustrate the point.
144 is a perfect square, so it has an odd number of factors.
The prime factorization of 144 is 24 32.
The factors of 144 are:
20 30,
20 31,
20 32,
21 30,
21 31,
21 32,
22 30,
22 31,
22 32,
23 30,
23 31,
23 32,
24 30,
24 31, and
24 32.
Count 'em up, and you'll see there are (4+1)(2+1) = 15, an odd number
of factors.
