The Thousand Locker Problem: How Many Remain Open?

[PRodQuanta]

You have a thousand kids that go to high school. In this school, there are 1000 lockers, so each kid has a separate locker. Now, All the kids , numbered 1-1000 line up outside of the school.

The first kid comes in a opens all the lockers.

The second kid comes in a shuts all of the even number lockers.

The third kid comes in and changes (if it's open, he shuts it, and vice versa) all the lockers that are multiples of 3.

The forth kid comes in and changes all the lockers that are multiples of 4.

And so on and so forth, with the 1000th kid changing the locker that is a multiples of 1000.


The question? After the 1000th kid changes the locker, how many lockers are left open?

Make sure you prove it.

Paden Roder

P.S.-If you need any more explanation, tell me. I may have left some small details out on accident.

 

[Gokul43201]

I think you mean 'multiples' when you say 'factors'.

My guess : 31

A fairly common number theory result states than the only numbers with an odd number of factors (in/ex cluding 1 and itself) are perfect squares. This result is not hard to prove.

[tex] If ~~n=p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_r^{k_r}[/ tex]

[tex] No. ~of~divisors~\tau (n) = (k_1+1)(k_2+1)(k_3+1)...(k_r+1)[/ tex]

This can be odd only if all k's are even, implying that n is a perfect square.

PS : The LaTeX wouldn't change color, so I put in a space between / and TEX to deformat it.

 

[PRodQuanta]

Sorry, I read (and posted) the problem wrong. I meant multiples, not factors. Anybody agree? Disagree?

Paden Roder

 

[PRodQuanta]

this is what Gokul43201 meant:

$$If ~~n=p_1^{k_1}p_2^{k_2}p_3^{k_3}...p_r^{k_r}$$

$$No. ~of~divisors~\tau (n) = (k_1+1)(k_2+1)(k_3+1)...(k_r+1)$$

 

[Gokul43201]

Well, this post hasn't been up long enough. I would have given it more time...

 

[TenaliRaman]

I wonder why Gokul is calling it a guess that's a perfect impromptu approach ... ofcourse there is no point to disagree

 

[Gokul43201]

Oh, just so often, when you're absolutely positive about something and you're willing to bet your salary on it, someone will come along and show you where you wrote 2-1=3.

It's just for safety, I guess, since I did that in a bit of a hurry...and actually checked that the numbers are right only much later.

 

[BobG]

You have a thousand kids that go to high school. In this school, there are 1000 lockers, so each kid has a separate locker. Now, All the kids , numbered 1-1000 line up outside of the school.

The first kid comes in a opens all the lockers.

The second kid comes in a shuts all of the even number lockers.

The third kid comes in and changes (if it's open, he shuts it, and vice versa) all the lockers that are multiples of 3.

The forth kid comes in and changes all the lockers that are multiples of 4.

And so on and so forth, with the 1000th kid changing the locker that is a multiples of 1000.


The question? After the 1000th kid changes the locker, how many lockers are left open?

Make sure you prove it.

Paden Roder

P.S.-If you need any more explanation, tell me. I may have left some small details out on accident.

Select to see:


31 will be open (square root of 1000 is 31 point something). 31 doors had an odd number of students come along - 969 doors had an even number of students come along.

Most numbers have an even number of factors.
Example: 18 = 18 x1, 9x2, 6x3. Factors are 1, 2, 3, 6, 9, and 18.

The only exception are perfect squares. The fact that you're multiplying a number of by itself gives it an odd number of factors.

Example: 16 = 1x16, 2x8, 4x4. Factors are 1, 2, 4, 8, and 16.

Since 31 is the largest number that can be squared and still be less than 1000, there are 31 perfect squares between 1-1000 (counting 1 which only has 1 as a factor).

 

[PRodQuanta]

Good job. All perfect squares will be left open. That's 31.

Paden Roder

 

[Physics is Phun]

sorry to revive an old thread, but how did you figure that out? that is just so above me. why is it that every other locker will be closed? because only the squares will not be changed an even number of times?

 

[NateTG]

sorry to revive an old thread, but how did you figure that out? that is just so above me. why is it that every other locker will be closed? because only the squares will not be changed an even number of times?

Can you see that the number of times that a locker gets switched is equal to the number of factors that the corresponding number has?

After that, it's a matter of figuring out that the only numbers that have an odd number of factors are squares. That's pretty easy to prove, but I'm not sure how to come up with it as a hypothesis.

 

[BTruesdell07]

All the lockers would be closed except locker one because the multiples of a number are the number times one, times two, ect. numbers times one are the number so all lockers would be closed but locker number one.

 

[wave]

All the lockers would be closed except locker one because the multiples of a number are the number times one, times two, ect. numbers times one are the number so all lockers would be closed but locker number one.

That's false. Consider locker 4. The first kid will open it, the second kid will shut it, the third kid will leave it shut, the fourth kid will open it. The fifth, sixth, ..., thousandth kid will leave locker 4 open.