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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum