The School Locker Problem
The students lined up according to their locker number in ascending sequence from 1 to 1000.
The first student, Locker 1, went down the whole row of 1000 lockers and, starting at Locker 1, opened every locker door.
The second student, Locker 2, started at the second locker and closed every second locker door.
The third student, Locker 3, started at the third locker and closed the door, then proceeded to either open or close every third locker as required.
And so it continued with each student starting at their locker “N” and proceeding to the next “Nth” locker, either opening or closing the locker door as required. If the locker door was closed when they arrived, they opened it. If the locker door was open when they arrived, they closed it. But they looked at only every “Nth” locker door.
This process continued until all 1000 students had performed the task.
how many doors were open, how many were closed, and why?
4 comments:
uh who cares?
Any locker number, n, will be visited by x students over the course of the process. As each student visiting it will change it from open to closed or vice versa, whether n is open or closed at the end depends on whether x is an even (=closed) or odd (=open) number.
But the students who visit locker n are precisely those whose ordinal number is a factor of n. For instance, locker number 24 will be visited by the first, second, third, fourth, sixth, eighth, twelfth, and twenty-fourth students. In this case, the number of factors is even, so locker 24 will be closed at the end.
In fact, the only numbers that have an ODD number of factors are the perfect squares. This is because any factor of n, x1, is a factor precisely because it can be multiplied by another factor of n, x2, to produce n. So factors come in pairs, except for the special case where x1 = x2, i.e. x1 is the square root of n, i.e. n is a perfect square.
So all the lockers will be closed except for those whose number is a perfect square. And since 31 is the highest integer whose square ≤ 1,000 (31 x 31 = 961; 32 x 32 = 1,024), therefore there will be 31 open doors and 1,000 - 31 = 969 closed doors.
Q.E.D.
What's "Q.E.D."?
I wasn't sure what it stood for either. Had to look it up. "Quod erat demonstrandum" means "which was to be demonstrated." You put it at the end of proofs in math and logic, signifying that the last line is what you'd set out to prove.
Post a Comment