Opening and Closing 1000 Lockers

Date: 03/16/97 at 19:57:30
From: J.t.
Subject: word problem

There are 1000 closed lockers.  There are 1000 students.  The first 
student comes in and opens every locker.  The second student comes in 
and closes every other locker.  The third student comes in and opens 
every third locker.  The pattern continues until all 1000 students 
have done what they're supposed to do.  At the end, how many lockers 
are still open?

I need to know what track I have to be on at the very beginning.

Date: 03/17/97 at 12:14:47
From: Doctor Anthony
Subject: Re: word problem

I think you have made a mistake in your description of the problem.  
The first student opens every locker, the second student REVERSES 
every second locker, i.e. closes lockers that are open and opens 
lockers that are closed. The third student REVERSES every third 
locker, and so on.  In this situation it is easy to see that every 
locker whose number is a perfect square will be open at the end of the 
exercise, and all other lockers will be closed.

For example the 18th locker will be visited by those students whose 
numbers are factors of 18. i.e. by numbers 1,2,3,6,9,18.  This is 6 
students (an even number) and this means the locker will in turn be 
open/closed/open/closed/open/closed. Now all numbers with an even 
number of factors will end up closed. And all numbers EXCEPT PERFECT 
SQUARES have an even number of factors if we include 1 and the number 
itself.  For a perfect square, say 16, we have factors 1,2,4,8,16, an 
odd number, and the lockers would be open/closed/open/closed/open.

We conclude that all the lockers whose numbers are perfect squares 
will be open at the completion of the exercise.

To show that perfect squares have an odd number of factors we express 
the number in its prime factors.  If it is a perfect square the power 
of each prime factor must be even, e.g.  2^2 x 3^4 x 5^2 so that the 
square root is given by  2 x 3^2 x 5. 

Consider the number 2^2 x 3^4 x 5^2.  The number 2  could be chosen 
0,1,2 times,i.e. in 3 different ways, the number 3 could be chosen  
0,1,2,3,4 times, i.e. in 5 different ways, and similarly the number 5 
could be chosen in 3 different ways.  So total number of ways that 
factors could be made up is given by 3 x 5 x 3 = 45 which is an odd 
number.  Note that taking none of 2,3 or 5 as factors gives the 1 
which we require as a factor.  Taking all the numbers 2, 3, 5 to their 
highest power gives the number itself - again one of the factors we 
require.  Thus perfect squares always have an odd number of factors, 
and all other numbers have an even number of factors. 

Lockers that are open are 1, 4, 9, 16, 25, 36, .....

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