Locker problem (due tomorrow!)?

Question

I'm in some desperate need for help on this problem I can't seem to fully wrap my head around...(the answer is perfect squares due to odd # of factors, but I must explain it clearly!! How?)

There are 1000 open lockers at a school, one locker for each of 1000 students. The first student comes in and closes all the lockers. The second student comes ina nd changes the condition of each second locker (so if a locker is closed, it is opened, and if a locker is open, it is closed). In other words, the second student opens lockers #2, 4, 6, 8, ...., 1000. Then the third student comes in and changes the condition of each third locker, i.e. opens locker #3, closes locker #6, opens locker #9, etc. The fourth student changes the condition of each fourth locker, the fifth student does so for each fifth locker, and so on, until eventually the 1000th student comes in and changes the condition of the 1000th locker. Which lockers are now closed??

...ok I'm not sure if you guys have answered this from what I've read (like I said it's hard for me to wrap my mind around this one), but this is one of the earlier questions I need to answer:

Why are the locker #'s that remain closed determined by the 'current' student (I.D.) number's factors?? (so why does 4 remain closed by the time you hit the 5th student or something...rrg)

Answer 1

Locker number N is switched for each person D where D is a divisor N (including D=1 and D=N.)

So a locker is closed at the end if the number of distinct divisors of N is odd.

Now, if D is a divisor of N, then N/D is also a divisor of N.
So we can pair up all the divisors with another divisor, except when N=D^2, then D=N/D.

So if N is not a square, there are an even number of divisors.

If N is a square, then N has an odd number of factors - pairs {K,N/K} and the remaining factor, sqrt(N).

So the lockers closed are exactly the locker numbers which are perfect squares.

Not sure what your second question means.

Locker #N will only be opened or closed by a student whose number is a divisor of N.

Student #D opens or closes Locker #N precisely when D is a divisor of N.

That means the number of times Locker #N is 'toggled' is equal to the number of divisors of N.

Now, if, starting with an open locker, I alternately close then open the locker K times, the final state of the locker is determined by whether K is odd or even - if K is odd, then the locker ends up closed, if K is even, the locker end up open.

So in the original problem, K=t(N)=the number of divisors of N (including 1 and N.) So locker #N ends up open when t(N) is even, and closed when t(N) is odd.

But we've shown that t(N) is odd exactly when t(N) is a perfect square.

Answer 2

You are right about the answers. At the end the lockers that are closed are those numbered by perfect squares.

Think of it this way. For any number n there are factors:

1, n - always
close then open

Any other factors of n come in pairs, a and b, such that
a*b = n
a, b
close then open

Only if c = √n is an integral factor of n do you have an unpaired number
c
close

So only those lockers numbered as perfect squares end up closed.

Answer 3

I bear in mind THIS! verify for the duration of the LOCKERS that are CLOSED(possibly ITS OPEN), all the NUMBERS ARE sq. NUMBERS(NUMBERS WITH A sq. ROOT). i desire I HELPED. SORRY IF IM incorrect.