Locker ProblemDate: 11/21/97 at 19:52:10 From: Jim Boyer Subject: Locker Problem Here is the problem: A new high school has just been completed. There are 1,000 lockers in the school and they have been numbered from 1 through 1,000. During recess (remember this is a fictional problem), the students decide to try an experiment. When recess is over each student will walk into the school one at a time. The first student will open all of the locker doors. The second student will close all of the locker doors with even numbers. The third student will change all of the locker doors that are multiples of 3 (change means closing lockers that are open, and opening lockers that are closed.) The fourth student will change the position of all locker doors numbered with multiples of four and so on. After 1,000 students have entered the school, which locker doors will be open, and why? WHAT I HAVE: I have figuered out which locker doors are open, but I can't figure out why! I have tried vigorously, but I still can't figure out why! Will you please explain it to me? Date: 11/22/97 at 04:50:00 From: Doctor Anthony Subject: Re: Locker Problem If a number is a perfect square it will have an odd number of factors, e.g 4 has factors 1, 2, 4, whereas all other numbers have an even number of factors. If a particular locker is visited an odd number of times it will be open at the end of the procedure you describe; otherwise it will be closed. So the open lockers are numbered: 1, 4, 9, 16, 25, 36, ..... 900, 961 The last number is 31^2 so 31 is the number of lockers left open. To show that square numbers always have an odd number of factors, consider a square like 36. This can be put into prime factors as 2^2 x 3^2. Note that all its prime factors will be raised to EVEN powers since it is a perfect square. Now the factor 2 can be chosen in 3 ways, i.e. not at all, once, twice. And factor 3 can also be chosen in 3 ways, i.e. not at all, once, or twice. (If neither is chosen we get the factor 2^0 x 3^0 = 1). Altogether there will be 3 x 3 = 9 factors of 36. These are: 1, 2, 3, 4, 6, 9, 12, 18, 36 Now the important point was made earlier that the prime factors of a perfect square are always raised to some even power, so we could have a^2 x b^4 x c^2 where a, b, c are primes. In this example a could be chosen in 3 ways 0 times, once or twice. b could be chosen in 5 ways 0 times, 1, 2, 3, 4 times c could be chosen in 3 ways 0 times, 1, 2, times So altogether the complete number will have 3 x 5 x 3 = 45 factors. For any number that is not a perfect square there will ALWAYS be an even number of factors e.g. a^3 x b^2 x c will have 4 x 3 x 2 factors = 24 factors If it is not a perfect square at least one of its prime factors will be raised to an ODD power, and that means the factor can be chosen in an EVEN number of ways, ensuring that overall there will be an even number of factors. The general rule for the number of factors is to increase the powers of the factors by 1 and multiply these together. So a^n x b^m x c^p will have (n+1)(m+1)(p+1) factors. 2^3 x 5^4 x 7^2 will have 4 x 5 x 3 = 60 factors -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/