1000 Lockers

Date: 11/06/97 at 23:35:30
From: Kate Thorsheim
Subject: Word problem

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? What is the formula?

I can't figure out the pattern.
Kate

Date: 11/07/97 at 13:41:12
From: Doctor Bruce
Subject: Re: Word problem

Hello Kate,

I enjoyed thinking about this problem when I first heard it some years 
ago.  

One thing we can do is to let the first 10 students go do their open/
shut thing with the lockers. The students who come after them are not 
going to touch lockers 1-10, so we can see which ones in that first 
batch are still open and try to guess the pattern.

When we do that, we find that lockers 1, 4, and 9 are open and the 
others are closed. Now, that isn't much to go on, so maybe you could 
let the next 10 students go do their thing. Then the first 20 lockers 
are through being touched, and we find that lockers 1, 4, 9, and 16 
are the only ones in the first 20 that are still open. So what is the 
pattern?

Let's take any old locker, like 48 for example. It gets its state 
altered once for every student whose number in line is an exact 
divisor of 48.  Here is a chart of what I mean:

     this Student     leaves locker 48

          1                open
          2                shut
          3                open
          4                shut
          6                open
          8                shut
         12                open
         16                shut
         24                open
         48                shut

Notice that 48 has an even number (ten) of divisors, namely
1,2,3,4,6,8,12,16,24,48. So the locker goes open-shut-open-shut ... 
and ends up shut. Any locker number that has an even number of 
divisors will end up shut.

Which numbers have an odd number of divisors?  That's the answer to 
this problem. Just to help you along, here are the locker numbers up 
to 100 that are left open:

     1,4,9,16,25,36,49,64,81,100.

See if you can describe these numbers in a different way from "having 
an odd number of divisors." Think about multiplying numbers together.  
When you understand how to describe them, you will see that 31 of the 
1000 lockers are still open (without having to work it all out!).

Good luck!

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

Date: 11/07/97 at 19:46:25
From: Anonymous
Subject: Re: Word problem

Dr. Math,

Thank you for your prompt response.
Kate