Associated Topics || Dr. Math Home || Search Dr. Math

### Opening and Closing 1000 Lockers

```
Date: 03/16/97 at 19:57:30
From: J.t.
Subject: word problem

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

```
Date: 03/17/97 at 12:14:47
From: Doctor Anthony
Subject: Re: word 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.

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.

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

-Doctor Anthony,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search