Re: Apology
Response To:
Apology ()

Larry Barrett
No apology necessary at all. My 'solution' was terribly cumbersome and not at all obvious why it happened to lead to the correct solution. I would say that my solution was a 'forest and trees' solution, but in my case I was lost in the forest and could not see the important trees. The important trees, thanks to your hint, being the open lockers after the first 25 students had followed the principals directions, namely lockers 1,4,9,16,25. So the aha moment is that all lockers of the form N^2, where N^2 is less than 1000 will be open; 31^2=961, 32^2=1024 so the answer is 31.
But why are only the N^2 lockers open? The answer to that is something I think I was getting at a couple of posts above, where I suggested that the prime numbered lockers would clearly be closed, and that considering the factors of the remaining numbers might lead to the correct solution.
All prime numbers, by definition, are of the form 1xP since they have no other factors other than 1 and P. Non-prime numbers can be represented as 1xN and then additional pairs of factors; for instance 12 can be represented as 1x12, 2x6, 3x4; 15 can be represented as 1x15, 3x5; 16 can be represented as 1x16, 2x8, 4x4. Observe that 16 is different than 12 and 15 in that one of its representations is a number (4 in this case) times itself.

If we now think of students opening and closing lockers, and those students representing factors of locker N we can start to see what is happening.
Student 1 opens all lockers, and for prime numbered lockers the only other student to reach those lockers is the 'prime numbered' student, who will close it. So for the first 25 lockers, the prime numbered lockers, namely 2,3,5,7,11,13,17,19,23 will all be closed once those students reach those lockers.
What about locker 4? Student 1 will open it, student 2 will close it, student 3 skips it, and student 4 will open it. And 1, 2, and 4 are the factors of 4.
What about locker 6? Student 1 opens it, 2 closes it, 3 opens it, 4 and 5 skip it, and 6 closes it.
What about locker 8? Student 1 opens it, 2 closes it, 3 skips it, 4 opens it, 5,6 and 7 skip it, and 8 closes it.
What about 9? Student 1 opens it, 2 skips it, 3 closes it, 4,5,6,7 and 8 skip it, and 9 opens it.
You can start to see the pattern. For lockers that have multiple pairs of factors beginning with 1xN but which do not include a pair of the form nxn, student 1 opens it, the in-between factor pairs will close then open, and then student N will close it.
Because lockers of the form N^2 have one factor pair that is nxn, when student n reaches locker N he will reset the sequence and the next-to-last student to reach that locker before N will close it; then N will open it.

© 1998 - 2017 by Ellis Walentine. All rights reserved.
No parts of this web site may be reproduced in any form or by
any means without the written permission of the publisher.