Question 945717: There are 500 students and 500 lockers, numbered 1 through 500. Suppose the first student opens each locker. Then the second student closes every second locker. The third student changes the state of every third locker (if it is open, she closes it; if it's closed, she opens it). The fourth student changes the state of every fourth locker. This process continues until the 500th student changes the state of the 500th locker. Which lockers are open after all 500 students have passed through?
Answer by Edwin McCravy(20063)   (Show Source):
You can put this solution on YOUR website!
Each locker will be changed as many times as its number has factors.
For example locker number 30 has 8 factors 1,2,3,5,6,10,15,30.
It will be opened by student #1, closed by the student #2, opened
by student 3, closed by student , etc. and it will finally be closed by
student #30 and will remain closed thereafter.
If a locker's number has an even number of factors it will end up closed.
If a locker's number has an odd number of factors, it will end up open.
The trick is to realize which numbers have an even number of factors and
which ones have an odd number of factors.
Looking at our example of 30, the square root of 30 is about 5.477. Why does
30 have an even number of factors? It is because for every factor below 5.477
there is a corresponding factor above 5.477 formed by dividing that number into
30. So that has to be an even number of factors.
Now which numbers have an odd number of factors? Answer: the ones whose
square roots are integers -- the perfect squares. Their square root gives
them an extra factor in addition to the even number above and below the
square root. So the lockers whose numbers are perfect squares will be
left opened, and the others closed.
Edwin
|
|
|
