Locker Problem

Date: 11/21/97 at 19:52:10
From: Jim Boyer
Subject: Locker Problem

Here is the problem:  A new high school has just been completed.  
There are 1,000 lockers in the school and they have been numbered from 
1 through 1,000. During recess (remember this is a fictional problem), 
the students decide to try an experiment. When recess is over each 
student will walk into the school one at a time. The first student 
will open all of the locker doors. The second student will close all 
of the locker doors with even numbers. The third student will change 
all of the locker doors that are multiples of 3 (change means closing 
lockers that are open, and opening lockers that are closed.) The 
fourth student will change the position of all locker doors numbered 
with multiples of four and so on. After 1,000 students have entered 
the school, which locker doors will be open, and why?

WHAT I HAVE:  I have figuered out which locker doors are open, but I 
can't figure out why!  I have tried vigorously, but I still can't 
figure out why!  Will you please explain it to me?

Date: 11/22/97 at 04:50:00
From: Doctor Anthony
Subject: Re: Locker Problem

If a number is a perfect square it will have an odd number of factors, 
e.g 4 has factors 1, 2, 4, whereas all other numbers have an even 
number of factors.  If a particular locker is visited an odd number of 
times it will be open at the end of the procedure you describe; 
otherwise it will be closed. So the open lockers are numbered:

 1, 4, 9, 16, 25, 36, ..... 900, 961

The last number is 31^2  so 31 is the number of lockers left open.

To show that square numbers always have an odd number of factors, 
consider a square like 36. This can be put into prime factors as  
2^2 x 3^2. Note that all its prime factors will be raised to EVEN 
powers since it is a perfect square.

Now the factor 2 can be chosen in 3 ways, i.e. not at all, once, 
twice. And factor 3 can also be chosen in 3 ways, i.e. not at all, 
once, or twice.

(If neither is chosen we get the factor 2^0 x 3^0 = 1).

Altogether there will be 3 x 3 = 9 factors of 36.  These are:

  1, 2, 3, 4, 6, 9, 12, 18, 36

Now the important point was made earlier that the prime factors of a 
perfect square are always raised to some even power, so we could have 
 
  a^2 x b^4 x c^2  where a, b, c are primes.

In this example a could be chosen in 3 ways  0 times, once or twice.
                b could be chosen in 5 ways  0 times, 1, 2, 3, 4 times
                c could be chosen in 3 ways  0 times, 1, 2, times

So altogether the complete number will have  3 x 5 x 3 = 45 factors.

For any number that is not a perfect square there will ALWAYS be an 
even number of factors

 e.g.   a^3 x b^2 x c  will have   4 x 3 x 2 factors = 24 factors

If it is not a perfect square at least one of its prime factors will 
be raised to an ODD power, and that means the factor can be chosen in 
an EVEN number of ways, ensuring that overall there will be an even 
number of factors.

The general rule for the number of factors is to increase the powers 
of the factors by 1 and multiply these together.

So  a^n x b^m x c^p  will have (n+1)(m+1)(p+1) factors.

 2^3 x 5^4 x 7^2  will have  4 x 5 x 3 = 60 factors   

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/