Math puzzle: The locker problem (Sep 21)

 

A school has 1,000 students and 1,000 lockers. On the first day of school, all the lockers are open.

• Student #1 closes each locker.
• Student #2 opens each second locker.
• Student #3 changes the state of each third locker (i.e. opens them if they are closed, or closes them if they are open)
• ...and so on, until all 1,000 students have had their turn.

After all 1,000 lockers are done, which lockers are open? Which are closed? Why?

To solve this problem, the mathematical thinking I used include: identify assumption, looking for pattern, looking for connection, identify appropriate knowledge and reasoning. 

Problem solving strategies I used include: drawing graph, guessing and checking, working backward.  

Solution: 

1.    Drawing a chart is a good start.

This is my first draft. Using pencil to draw could save your papers, since it is easy to make mistakes.

In this chart, "circles" stand for opened, "crosses" stand for closed.

Then I just follow the rules to complete the chart.

 

2.    Observation.

When I was drawing, I found two things from this chart.

·        Circles and crosses in the upper triangle shows the final state of each locker. Since Nth student will only start to change the states from the Nth locker.

·        I found 1st, 4th, 9th lockers will be closed at the end. I guessed (making assumption) there is something related to perfect square numbers, but I was not sure. I needed to draw a larger chart, then try to prove it.

 

 3.  Draw second chart.

I drew a neat larger chart in order to make sure that I could start to think about this problem from perfect square numbers. I stopped drawing my second chart at 16, another perfect square number.

   4. Build connection ( This step normally take more time.)

I tried to:

 - Find patterns from the chart. Failed, since I couldn't find any pattern in these circles and crosses.

 - Try to think backwards from perfect square numbers. Failed, since I couldn't see any difference from the chart between perfect square numbers and other numbers.

 Then go back to problem, and change direction.

when the state is changed? By checking the 16th row, I found the state of this locker is changed at 2, 4, 8 , and 16. That's right, 2, 4, and 8 are factors of 16, and that makes sense that student #2, students #4, and students # 8 will change the state of the 16th locker.

The state of Nth locker will be changed by those students whose number is the factor of N.  

Since there are only two types of the state of the locker, we just need to know whether the amount of factors of N is even or odd. (Reasoning)

We know perfect square numbers have odd number of factors, and other numbers have even number of factors (factor pairs). (Identify appropriate knowledge)

Then the answer is:  The lockers with perfect square numbers are closed, the rest of the lockers are opened.