Tuesday, August 18, 2009

Math from the past

The kids were all great at math. I tried to assist Andrew only once. Here is the one problem. I think he was in Jr High at the time, grade 7 or 8.

The School Locker Problem

Once there was a school that had exactly 1000 students. The student population had been exactly 1000 for many years, never varying, so the school had built exactly 1000 lockers – one each for the 1000 students. Each of the students was assigned a locker each year. The lockers were numbered from 1 to 1000. At the start of the year, the students performed a ritual, “Preparing the Locker Doors”. This is the story of that ritual.

To start, all the locker doors, all 1000 of them, were closed.

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.

At the end of the process,

how many doors were open, how many were closed, and why?

4 comments:

Anonymous said...

uh who cares?

Andrew said...

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.

St. Louis Family said...

What's "Q.E.D."?

Andrew said...

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.