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 that are closed, closes lockers that are 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?
One hint that will be familiar to you if you were ever a student of ours: the question is very abstract and hopelessly large in scale, so try to make it more “tangible” or “concrete” and perhaps even consider a “simple parallel example” so that you can gain a better understanding of what’s really happening in the problem.
Answer:
One thing we can do is to let the first 10 students 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 is a divisor of 48. Here is a chart of what happens:
- Student 1 opens it
- Student 2 shuts it
- Student 3 opens it
- Student 4 shuts it
- Student 6 opens it
- Student 8 shuts it
- Student 12 opens it
- Student 16 shuts it
- Student 24 opens it
- Student 48 shuts it
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? Only perfect squares will have an odd number of divisors, so you need to figure out how many perfect squares are less than 1000. 30 x 30 equals 900, so at least 30. If you try 31 x 31 you will see that that is less than 1000 but 32 squared is not. So there will be 31 lockers that are open.