Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/