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.


Return to Chris Reid's home page