Friday Puzzler -- 1,000 lockers

Re: Friday Puzzler -- 1,000 lockers

Larry Barrett

When I see problems like this, I always start with smaller, simpler problems to see if a pattern emerges. Often it does. This time I am not sure, but this is what I have done so far. Start with one student and one locker; then two and two, and so on. Let a 0=open locker, and 1=closed locker.

So for one student and one locker the result is 0.

For two students and two lockers, after the first student the result is 00, and after the second student the result is 01.

For three and three, 000 010 011.

For four and four, 0000 0101 0111 0110.

For five and five, 00000 01010 01110 01100 01101

Six and six, 000000 010101 011100 011000 011010 011011

If you look at the end results for this series of 1 to 6 you see this sequence:

0, 01, 011, 0110, 01101, 011011. What you can see is that the nth student does not alter the first n-1 lockers, only the nth locker. The problem is to see what the n-1 students did to that nth locker before the nth student gets there. I did this up to nine and nine. It gets tricky and easy to make mistakes, but I did not see a pattern.

I tried looking at the end positions as binary numbers, hoping to see a pattern.

This is what I see: 0, 1, 3, 6, 13, 28. So far, no dice.

Good process

But

Alex Y

I don't believe your last step, viewing the string of 0s and 1s as a binary number, is helpful. I can't definitively rule it out as an approach, but I don't see it leading to the answer.

Re: But

Larry Barrett

I agree that looking at the sequence as a binary number doesn't seem to lead anywhere.

I think you can say that for each student that represents a prime number, those lockers will be closed at the end, since they will be the only students to reach those lockers. For the non-prime number lockers, it seems to me that it is necessary to consider the factors of those non-prime numbers to determine how many students will have reached each one. I don't see a simple way to look at this, so far.

Re: But

Alex Y

You're making better progress than I did on this one.

I think you can say that for each student that represents a prime number, those lockers will be closed at the end, since they will be the only students to reach those lockers.

Don't confuse locker numbers with student numbers. A better way to say this is that locker number p, where p is prime, will have its state changed only by students 1 and p, thus ending in the closed state.

Re: But

Larry Barrett

Using a spreadsheet, I pushed the simpler test cases from 1 student and 1 locker to 25 students and 25 lockers. Here is what I observe (assuming no mistakes):

For the cases 1-1, 2-2, 3-3 the end result is 1 locker open (3 cases)

For the cases 4-4 to 8-8, the end result is 2 lockers open (5 cases)

For the cases 9-9 to 15-15, the end result is 3 lockers open (7 cases)

For the cases 16-16 to 24-24, the end result is 4 lockers open (9 cases).

It looks like it is possible to extend this and I would expect to see, for instance, for the next 11 cases (25-25 to 35-35) the end result would be 5 lockers open, etc.

If this works out, I would try to find a formula to extend this to the 1000th case.

Weather is finally warming up here in MD so time to get outside and do some work.

Re: But

Larry Barrett

It seems to work out for the next 11 cases, so although it is not obvious why, if I extrapolate this up to the case in question (1000 lockers, 1000 students), I find that 31 lockers will be open (actually for all cases from 960-960 on up to 1018-1018).

Correct answer

Alex Y

But unnecessarily cumbersome calculation.

What you refer to as a simplification of looking at, e.g 10-10 and 11-11 is really just looking at the first 10 or 11 lockers in the bigger problem (since none of the rest of the students will touch those lockers).

Looking at the first 25 lockers, which ones were left open? That will give you a hypothesis for the lockers that will be left open, and the fact that it gives you the answer of 31 is confirmation. But without the confirmation of getting the right answer, can you say why it works?

Apology

Alex Y

Rereading my last note, calling your solution unnecessarily cumbersome sounds critical, and is not warranted, particularly from one who was unable to solve it. Sorry.

Re: 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.

That's it!

Alex Y

Every student will "touch" the lockers where the student's number, k, is a divisor of the locker number, n. ("Touch" is shorthand for "open if closed and close if open".)

k is a divisor of n if and only if n/k is also a divisor of n. So for the most part, divisors come in pairs. The only exception is when k=n/k, so n is a perfect square.

Where n is not a perfect square, there will be an even number of touches returning the locker to its initial closed state. Where n is a perfect square, there will be an odd number of touches leaving the locker open.

Who wudda thunk that squares had anything to do with it!