New School Lockers

Date: 01/28/2001 at 13:35:55
From: Michael Lopez
Subject: New School Lockers

A new school is being opened. The school has exactly 1000 lockers and 
1000 students. On the first day of school, the students meet outside 
the building and agree on the following plan: the first student will 
enter the school and will open all of the lockers. The second student 
will enter and close every locker with an even number. The third 
student will then "reverse" every third locker; that is, if the locker 
is closed, he will open it; if it is open, he will close it. The 
fourth student will then "reverse" every fourth locker, and so on 
until all 1000 students in turn have entered the building and 
"reversed" the proper lockers. Which lockers will finally remain open?

1. For a particular locker, how many times was it touched?
2. How many lockers, and which ones, were touched exactly twice?
3. Which locker was touched the most?

A picture must be drawn of a table and or graph.

By doing a search of your Web site, we were able to find the answer to 
the problem:

  Opening and Closing 1000 Lockers
  http://mathforum.org/dr.math/problems/atsang.3.16.97.html   

I was curious to know what level of math this type of question is - is 
it middle school, high school, or college?

The one question that remained unanswered was which locker was touched 
the most. If you or your team has time to return that answer, that 
would be greatly appreciated.  

Thank you for your time.

Date: 01/29/2001 at 12:12:32
From: Doctor Schwa
Subject: Re: New School Lockers

Your question about the math level of this problem is a good one.
In middle school, I'd expect people to be able to *get* the answers 
after an hour or two of work looking for patterns. By high school,
I'd expect people to be able to *prove* the answers after getting 
them. In college, I'd expect a math major to already *know* the 
answer, or at most have to work on it for a few minutes to figure out 
the pattern and then prove it.

Which locker is touched the most? Each locker is touched once for each 
factor the number has. For instance, locker number 10 is touched four 
times: by persons numbers 1, 2, 5, and 10.

So, what we need to figure out is what number from 1 to 1000 has the
most factors.

One clever shortcut for counting the number of factors of a number 
is to look at its prime factorization. For instance, since 
1000 = 2^3 * 5^3, any factor of 1000 has to have 2^0, 2^1, 2^2, or 2^3 
in it (4 choices), and 5^0, 5^1, 5^2, or 5^3 in it (4 choices), and 
therefore it has 4*4 = 16 factors.

There is, unfortunately, no nice way to find the best number with a
simple formula, but now at least you can quickly find how many factors 
a number has.

If a number is made up of just one factor, 2^9 has 10 factors, and 
that's the most.

If a number is made up of two factors, 2^a * 3^b, well, 2^5 * 3^3 has 
(5+1) * (3+1) = 24 factors, and I think that's the most.

If a number is made of three factors, 2^a * 3^b * 5^c, well, 
2^4 * 3^2 * 5 might be pretty promising (30 factors?), or maybe 
2^2 * 3^2 * 5^2 (27 factors, not as good)... maybe a little more 
experimenting will convince you of whether or not 30 is the best.

And what about four factors? 2^3 * 3 * 5 * 7 would be one 
possibility... it has a lot of factors (32 factors?)

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 01/29/2001 at 12:33:30
From: Doctor Twe
Subject: Re: New School Lockers

Hi Michael - thanks for writing.

I see that Dr. Schwa has already responded to your questions, but I'll 
add a little bit to his response.

We have five "lockers" problems in our Ask Dr. Math archives, and all 
of them are categorized as high school level (either in discrete math, 
number theory, and/or puzzles), and one is also categorized in middle 
school puzzles. The URLs for these archives are:

   Word Problem Hints (discrete math - high)
   http://mathforum.org/dr.math/problems/reichel3.12.96.html   

   Opening and Closing 1000 Lockers (discrete math, puzzles - high)
   http://mathforum.org/dr.math/problems/atsang.3.16.97.html   

   Locker Problem (discrete math, puzzles - high)
   http://mathforum.org/dr.math/problems/boyer11.21.97.html   

   100 Lockers, 100 Students (puzzles - high)
   http://mathforum.org/dr.math/problems/5591121.8.16.96.html   

   1000 Lockers (number theory, puzzles - high, puzzles - middle)
   http://mathforum.org/dr.math/problems/thorsheim11.6.97.html   

As to which locker was touched the most, as Dr. Schwa explained, the 
number of times a locker is touched is equal to the number of factors 
of the number. I ran a quick program I had previously written, and 
found that 840 (= 2^3 * 3 * 5 * 7) has 32 factors, the most of any 
number between 1 and 1000 inclusive - good work, Dr. Schwa!

I hope this helps. If you have any more questions or comments, write 
back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/