Tricky lockers

  • Thread starter PRodQuanta
  • Start date
  • #1
341
0
You have a thousand kids that go to highschool. 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 explaination, tell me. I may have left some small details out on accident.
 
Last edited:

Answers and Replies

  • #2
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
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.
 
Last edited:
  • #3
341
0
Sorry, I read (and posted) the problem wrong. I meant multiples, not factors. Anybody agree? Disagree?

Paden Roder
 
Last edited:
  • #4
341
0
this is what Gokul43201 meant:


[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]
 
  • #5
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
Well, this post hasn't been up long enough. I would have given it more time...
 
  • #6
644
1
I wonder why Gokul is calling it a guess that's a perfect impromptu approach .... ofcourse there is no point to disagree
 
  • #7
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
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.
 
  • #8
BobG
Science Advisor
Homework Helper
185
80
PRodQuanta said:
You have a thousand kids that go to highschool. 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 explaination, 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).
 
  • #9
341
0
Good job. All perfect squares will be left open. That's 31.

Paden Roder
 
  • #10
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?
 
  • #11
NateTG
Science Advisor
Homework Helper
2,450
6
Physics is Phun said:
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.
 
  • #12
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.
 
  • #13
97
0
BTruesdell07 said:
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.
 

Related Threads on Tricky lockers

  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
10
Views
2K
  • Poll
  • Last Post
2
Replies
32
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
2
Replies
35
Views
2K
Replies
3
Views
2K
  • Last Post
19
Replies
456
Views
326K
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
8
Views
14K
  • Last Post
Replies
11
Views
2K
Top