Locker Problem

Essay #3

EMAT 6690

by Chris Reid

There are 1000 lockers numbered 1 to 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 this 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?

Consider lockers numbered 1 to 25 to begin. All doors are opened. Then every other door is closed.

 Locker # Status: 1 2 1 open 2 open closed 3 open 4 open closed 5 open 6 open closed 7 open 8 open closed 9 open 10 open closed 11 open 12 open closed 13 open 14 open closed 15 open 16 open closed 17 open 18 open closed 19 open 20 open closed 21 open 22 open closed 23 open 24 open closed 25 open

That is, every multiple of 1 is opened and every multiple of 2 is then closed.

Next, every third locker changes from open to closed or closed to open. That is, every locker numbered as a multiple of three, changes its status.

 Locker # Status: 1 2 3 1 open 2 open closed 3 open closed 4 open closed 5 open 6 open closed open 7 open 8 open closed 9 open closed 10 open closed 11 open 12 open closed open 13 open 14 open closed 15 open closed 16 open closed 17 open 18 open closed open 19 open 20 open closed 21 open closed 22 open closed 23 open 24 open closed open 25 open

Then, every fourth locker changes from open to closed or closed to open. Or, another way to look at the situation is that every locker numbered as a multiple of four changes its status.

 Locker # Status: 1 2 3 4 1 open 2 open closed 3 open closed 4 open closed open 5 open 6 open closed open 7 open 8 open closed open 9 open closed 10 open closed 11 open 12 open closed open closed 13 open 14 open closed 15 open closed 16 open closed open 17 open 18 open closed open 19 open 20 open closed open 21 open closed 22 open closed 23 open 24 open closed open closed 25 open

On the fifth pass, lockers numbered as multiples of five are changed from open to closed or closed to open.

 Locker # Status: 1 2 3 4 5 1 open 2 open closed 3 open closed 4 open closed open 5 open closed 6 open closed open 7 open 8 open closed open 9 open closed 10 open closed open 11 open 12 open closed open closed 13 open 14 open closed 15 open closed open 16 open closed open 17 open 18 open closed open 19 open 20 open closed open closed 21 open closed 22 open closed 23 open 24 open closed open closed 25 open closed

Notice that the locker changes status when every nth locker is open or closed. That is, the locker door will change from open or closed when "n" is a factor of the locker number.

Also notice that since the doors were opened first, that the doors opened and closed an odd number of times remain open when the number of factors of the locker number is odd. That is, the lockers numbered with perfect squares are left open at the end of the process. Perfect squares have an odd number of distinct factors and remain open.

 Locker # Status: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 open 2 open closed 3 open closed 4 open closed open 5 open closed 6 open closed open closed 7 open closed 8 open closed open closed 9 open closed open 10 open closed open closed 11 open closed 12 open closed open closed open closed 13 open closed 14 open closed open closed 15 open closed open closed 16 open closed open closed open 17 open closed 18 open closed open closed open closed 19 open closed 20 open closed open closed open closed 21 open closed open closed 22 open closed open closed 23 open closed 24 open closed open closed open closed open closed 25 open closed open

Look at the factors of a few numbers and the results of each pass.

36: 1 open; 2 closed; 3 open; 4 closed; 6 open; 9 closed; 12 open; 18 closed; 36 open

49: 1 open; 7 closed; 49 open

55: 1 open; 5 closed; 11 open; 55 closed

64: 1 open; 2 closed; 4 open; 8 closed; 16 open; 32 closed; 64 open

81: 1 open; 3 closed; 9 open; 27 closed; 81 open

100: 1 open; 2 closed; 4 open; 5 closed; 10 open; 20 closed; 25 open; 50 closed; 100 open

125: 1 open; 5 closed; 25 open; 125 closed

275: 1 open; 5 closed; 11 open; 25 closed; 55 open; 275 closed

324: 1 open; 2 closed; 3 open; 4 closed; 6 open; 9 closed; 12 open; 18 closed; 27 open; 36 closed; 54 open; 81 closed; 108 open; 162 closed; 324 open

The doors of lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 will remain open on the first 100 passes through the lockers. Lockers numbered 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, and 961 will also remain open since these numbers are the squares of numbers 11 to 31.