Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tricky lockers

  1. Aug 30, 2004 #1
    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: Aug 30, 2004
  2. jcsd
  3. Aug 30, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Aug 30, 2004
  4. Aug 30, 2004 #3
    Sorry, I read (and posted) the problem wrong. I meant multiples, not factors. Anybody agree? Disagree?

    Paden Roder
     
    Last edited: Aug 30, 2004
  5. Aug 30, 2004 #4
    this is what Gokul43201 meant:


     
  6. Aug 30, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, this post hasn't been up long enough. I would have given it more time...
     
  7. Aug 31, 2004 #6
    I wonder why Gokul is calling it a guess that's a perfect impromptu approach .... ofcourse there is no point to disagree
     
  8. Aug 31, 2004 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  9. Aug 31, 2004 #8

    BobG

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  10. Aug 31, 2004 #9
    Good job. All perfect squares will be left open. That's 31.

    Paden Roder
     
  11. Oct 12, 2004 #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?
     
  12. Oct 12, 2004 #11

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  13. Oct 14, 2004 #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.
     
  14. Oct 14, 2004 #13
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Tricky lockers
  1. Tricky tricky (Replies: 10)

Loading...