The Locker Problem

A classic problem we’ve seen hundreds of times involves students opening and closing lockers. I have often told people that, believe it or not, they could find the answer by searching the Ask Dr. Math site for the word “locker”. But I prefer to give them a reference to one of the answers in which we gave only hints, because this is a fun problem to discover the answer for yourself. You’ll soon see the connection to the topic of last week’s post on divisors.

So if you haven’t seen this problem before, be sure to read only the first answer or two below and try it yourself, before looking at the subsequent spoilers. (I have sometimes wondered why, with all the slight variations we’ve seen, they all still involve lockers, rather than, say, pulling chains on lamps, which might be easier to state.)

Tiny hints

Here is a question from 1996, which asked about two problem, the first of which is our subject:

Word Problem Hints

1)  There are 1000 lockers numbered 1 - 1000.  Suppose you open all of the lockers, then close every other locker.  Then, for every third locker, you close each opened locker and open each closed locker.  You follow the same pattern for every fourth locker, every fifth locker, and so on up to every thousandth locker.  Which locker doors will be open when the process is complete?

To illustrate,  we start with all lockers closed:

C C C C C C C C C C …

Then we open every locker:

O O O O O O O O O O …

Then we change the state of every second locker (opening those):

O C O C O C O C O C …

Then we change the state of every third (opening some, closing others):

O C C C  O O O C C C …

And so on until we’re finished.

Doctor Jodi gave only a hint:

Our office is overflowing with patients at the moment, so let me just try to put a band-aid on these problems for you... 

Thinking about the influence of FACTORS in the first problem might help.

I imagine the row of lockers as a long line of off/on switches.

So every other locker means every locker whose number has what as a factor? And how many times would a switch have to be flipped to be on at the end?

Bigger hints

Here’s a question from 2004:

A Way to Think about the Locker Problem

Imagine there is an endless string of lockers in your school.

Person 1 starts at locker 1 and opens every locker.
Person 2 starts at locker 2 and closes every 2nd locker.
Person 3 starts at locker 3 and changes every 3rd locker.
Person 4 starts at locker 4 and changes every 4th locker.
Person x starts at locker x and changes every xth locker.

I need to figure out which lockers are left open in a row of 25, 100, and a row of 500 lockers. 

I have been trying to figure this out for 4 days and my parents can not figure it out either.  I don't know what number person x is.  My parents say this has nothing to do with math.  Can you help?

Clearly this is intended to be solved by trying a small example and extending it, rather than by seeing it all at once. There were already several complete solutions in the archive, but I chose to offer some suggestions to help Michael discover a solution himself, rather than just give a link:

It has a lot to do with math!  But I'm not sure whether everyone your age can be expected to figure out the complete answer on his own.  You may be expected only to recognize a pattern, but there is a lot of very interesting math if you look deep enough.

It sounds like a lot of your confusion is over the 'x' part, so maybe the problem wasn't made fully clear.  Usually in this problem (it's a classic, by the way), the number of people is the same as the number of lockers in the hallway.  So what they mean by 'person x' is all the people from person 1 up to the last person.  In other words, if there are 10 lockers there are 10 people, and the pattern continues from person 1 up through person 10.  If there are 100 lockers, there are 100 people and each of the 100 goes through the hallway turning lockers that are multiples of their own number.  Does that help?

Michael may not yet be fully accustomed to using variables, or may think x must be a specific number to be solved for. All it means is “any number”: Whatever number you are, you “skip count” by that number.

If I were you, I would first try "playing" with the problem with a small number of lockers, like 25 so you can see what the whole thing means.  Here is one way to write it out, but I'll only show 10 lockers:
 
                  person #
            --------------------
  locker #  1 2 3 4 5 6 7 8 9 10
     1      +
     2      + -
     3      +   -
     4      + -   +
     5      +       -
     6      + - +     -
     7      +           -
     8      + -   +       -
     9      +   -           +
    10      + -     +         -

I used "+" to mean "opened" and "-" for "closed".

Do you follow what I did, and understand how the problem works?  The idea is that each person opens or closes only the lockers that are a multiple of his number: #2 changes the multiples of 2, #3 changes the multiples of 3, and so on up to person x, the last one to go through.

There are many ways you might write out your work; I chose a way that requires less writing than some, while keeping all the information visible. Each column represents what that person does. A “+” means a locker is opened, a “-” means it is closed, and the last symbol in a row shows what state that locker is in. The first person opened them all; the second closed 2, 4, 6, 8, and 10; the third opened 3, closed 6, and opened 9; and so on.

The only doors left open with 10 lockers are 1, 4, and 9.  One way to work the problem is to do this with more lockers and look for a pattern in the numbers of the lockers left open; a better way is to look for a REASON why there should be a pattern.  What is it that makes one locker end up open and another end up closed?

I always emphasize reasons over patterns, because a pattern you see may not be real, and may not continue for larger numbers. I think the first time I solved the problem I saw the pattern very quickly, but had to stop and think in order to convince myself it was real.

So now we think about what it takes to leave a locker open:

Notice that each time a locker is "touched" it changes from open to closed or vice versa.  So in order to end up open, it has to be touched an odd number of times.  Now, what might make that happen?

A key is to realize that the whole problem is about multiples and divisors.  Do you see why?  That's where the math comes in!

If you have any further questions, feel free to write back.  Good luck!

We never heard back to see whether this was enough to help Michael.

We could describe my plan to attack this problem as Play, Pattern, Prove.

A little more of a hint …

This question from 1997 will take us further:

1000 Lockers

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

Note the slightly different way of saying the same thing; using example numbers is helpful. But here we’re explicitly asked for a “formula”, so more is expected than just guessing at a pattern.

Doctor Bruce carried out parts of my plan, in effect taking Kate partway through the process:

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?

We’ve done the “play” part, and seen what numbers are left open up through #20. Do the numbers 1, 4, 9, 16 look familiar?

Now we reverse the experimentation, picking a single locker and thinking about what happens to it, in order to answer my question about what it takes for a locker to end up open:

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.

So the lockers that are open must have an odd number of divisors. We saw something about this last week …

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!

With more numbers, it should be clear: the answer is, all perfect squares. We just have to convince ourselves that this makes sense, and count how many of them there are.

A full answer

Another 1997 question was given a complete answer:

Opening and Closing 1000 Lockers

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.

Doctor Anthony started with a correction, assuming this is meant to be the usual 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.

There’s the answer we’d stopped short of in the answers so far: Perfect-square-numbered lockers will be left open. Is that easy to see? Only when you see it the right way. He uses examples to make it as easy as possible, showing some facts we’ve observed above:

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.

So, if it’s left open, it has an odd number of factors, and if it has an odd number of factors, it’s a perfect square. But why? We saw this last week, and he briefly explains it here, using prime factors:

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, .....

Now we have not only a conjecture that it will be the perfect squares, based on experiment, but we have a proof – a reason to believe it will always be true. (An actual proof would go beyond mere example, but this is sufficient for an elementary level.)

How many lockers are open? The largest perfect square less than 1000 is \(31^2 = 961\), so the answer is 31. For versions that ask for a formula for this number, it would be \(\text{floor}(\sqrt{n})\); that is, take the square root and round down.

For similar answers with different details, see:

100 Lockers, 100 Students

Locker Problem

Further questions

In 2001, Michael, already having seen that last answer, had deeper questions about it:

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.

Doctor Schwa first gave his opinion of the level:

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.

So what level the problem belongs to depends on what you expect as an answer.

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.

We saw this last time.

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 TWE added a list of five previous answers to the question (two of them I skipped over), and added:

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!

How about the question, which are touched exactly twice? Can you see the answer? How many there are is a little more work …