Results 1 to 11 of 11

Math Help - Which lightbulbs are on?

  1. #1
    Junior Member Ruichan's Avatar
    Joined
    Oct 2006
    Posts
    56

    Which lightbulbs are on?

    There are 100 people and 100 lightbulbs. All the lightbulbs are off.
    The first person flips the switch and turn all the lightbulbs on.
    The 2nd person flips the switch of every 2nd lightbulb.
    The 3rd person flips the switch of every 3rd lightbulb.
    The 4th person flips the switch of every 4th lightbulb and so on till the 100th person.
    How many lightbulbs are on after the 100th person flips the switch?

    Do not use Excel to solve the question.

    EDIT: Actually, please feel free to use any methods to solve the puzzle. :P Heheheh....I actually was looking to see if there's any other way apart from using Excel, which I did. :P

    Sorry, it's the 4th person flips the switch of every 4th lightbulb.
    Last edited by Ruichan; October 26th 2006 at 11:26 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Ruichan View Post
    There are 100 people and 100 lightbulbs. All the lightbulbs are off.
    The first person flips the switch and turn all the lightbulbs on.
    The 2nd person flips the switch of every 2nd lightbulb.
    The 3rd person flips the switch of every 3rd lightbulb.
    The 4th person flips the switch of every 5th lightbulb and so on till the 100th person.
    How many lightbulbs are on after the 100th person flips the switch?
    I was just about to do it when I read:
    Do not use Excel to solve the question.
    There's always a catch

    Anyway, is it every prime number? Or what...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Ruichan's Avatar
    Joined
    Oct 2006
    Posts
    56

    Talking

    Quote Originally Posted by Quick View Post
    I was just about to do it when I read:

    There's always a catch

    Anyway, is it every prime number? Or what...
    Actually, please feel free to use any methods to solve the puzzle. :P Heheheh....I actually was looking to see if there's any other way apart from using Excel, which I did. :P

    I need to check my answer too. My usage and knowledge of Excel is really not the best.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by Ruichan View Post
    Actually, please feel free to use any methods to solve the puzzle. :P Heheheh....I actually was looking to see if there's any other way apart from using Excel, which I did. :P

    I need to check my answer too. My usage and knowledge of Excel is really not the best.
    There is usually a way to do things mathematically, but back to my question, you say that the 4th person turns off every 5th light bulb, did you mean to say 4th lightbulb or is it that each person turns off the next primeth light bulb?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I came up with an elegant way to solve this problem

    This approach uses Number Theory.
    Specifically something called number-theortic functions.
    The function that I will use is \tau (n) it is the number of divisors of n\geq 1. For example,
    \tau (6)=4 because 1,2,3,6 are divisors.

    Now, returning back to the problem.

    I will work backwards because it is easier to follow.

    The number 100 is activated (either on or off) by 1,2,4,5,10,20,25,50,100
    That means it is turned on and off \tau (100) times.

    The number 99 is activated (either on or off) by 1,3,9,11,33,99. That means it is turned on and off \tau (99) times.

    That means 98 is activated (either on or off) by \tau (98).

    And so on....

    ~~~~~~ Take a pause

    Okay now we get to the fun part.

    The numbers that are remained lit are those numbers that have an odd number of divisors. Because: on, off, on, off, on, off.... So if the number is odd then it remains lit.

    What I am about to state I will not prove....
    It can be shown in number theory that  \tau (n) is odd if and only if n is a square.

    That means, all the square in between 1 and 100 are lit.
    That means,
    1,4,9,16,25,36,49,64,81,100
    Which is 10.
    ~~~
    Given n\geq 1 lightbulbs.
    The number of ones that remain lit is,
    [\sqrt{n}]
    Where [ \, ] is the greatest integer function.

    As a result I can up with my own riddle.
    What is the ratio of the lightbulbs lit to lightbulbs dead, tending to?
    Last edited by ThePerfectHacker; October 26th 2006 at 06:59 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member Ruichan's Avatar
    Joined
    Oct 2006
    Posts
    56
    Quote Originally Posted by Quick View Post
    There is usually a way to do things mathematically, but back to my question, you say that the 4th person turns off every 5th light bulb, did you mean to say 4th lightbulb or is it that each person turns off the next primeth light bulb?
    Oops, sorry, didn't check what I typed. yup it's every 4th lightbulb.

    Gee... I didn't know about number theory. Havn't taken number theory at all.

    I only came up with the squares with Excel, 10 bulbs on.
    Since my excel sucks, I was intending to check the answer with the old fashion way, drawing 100 lightbulbs then striking them off. Yeah...I'm that slow when it comes to using my brain for Math.
    Last edited by Ruichan; October 27th 2006 at 08:20 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    Hello, Ruichan!

    This is a classic (old) problem.


    There are 100 people and 100 lightbulbs. . All the lightbulbs are off.
    The first person flips the switch and turn all the lightbulbs on.
    The 2nd person flips the switch of every 2nd lightbulb.
    The 3rd person flips the switch of every 3rd lightbulb.
    The 4th person flips the switch of every 4th lightbulb and so on till the 100th person.
    How many lightbulbs are on after the 100th person flips the switch?

    With a little exploring you could have discovered the secret.

    Consider the 12th bulb. .It will be:
    . . turned on by the 1st person,
    . . turned off by the 2nd person,
    . . turned on by the 3rd person,
    . . turned off by the 4th person,
    . . ignored the 5th person,
    . . turned on by the 6th person,
    . . ignored by the 7th, 8th, 9th, 10th, and 11th persons,
    , , turned off by the 12th person.

    The state of the bulb is changed by people with numbers that divide 12.
    Since 12 has six divisors: 1, 2, 3, 4, 6, 12 . . . an even number of divisors,
    . . bulb #12 will be off and the end of the problem.

    In general, if a bulb has a number with an even number of divisors, it will be off.

    The only bulbs left on have numbers with an odd number of divisors.
    Very well, which ones are they?


    Most number have an even number of divisors because they "come in pairs".
    For example: . 24\:=\:1 \times 24 \:=\:2 \times 12 \:=\:3 \times 8 \:=\:4 \times 6 (8 divisors).

    We find that 16 has five divisors: 1, 2, 4, 8, 16
    . . and that 25 has three divisors: 1, 5, 25
    . . and that 36 has seven divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36

    Get it? . . . Only the squares have an odd number of divisors!


    The bulbs that are left on are: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member Ruichan's Avatar
    Joined
    Oct 2006
    Posts
    56
    Quote Originally Posted by Soroban View Post
    Hello, Ruichan!

    This is a classic (old) problem.



    [/size]
    My prof did mention that it's a classic. However, all Math puzzles to me, are new and I have to spend time looking at it if I don't know how to use Excel to solve it. Yup, I'm kind of slow at Math. I'm going to study what all of you guys wrote.

    Thank you very much. At least if the prof asked how did I get the answer, I could give him an answer that make sense. Thank you very much again!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Soroban View Post

    The bulbs that are left on are: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

    I was doing the similar Locker Problem and was directed to this thread, where Student 1 opens all lockers, 2 changes 2,3,4 etc... There are 1000 lockers and 1000 students.

    How would we solve:

    i) How many lockers are closed immediately after the third student has walked along the corridor? Explain your reasoning.

    (ii) How many lockers are closed immediately after the fourth student has walked along the corridor? Explain your reasoning.

    My answer was:

    ) student 3 opens all even multiples of 3, closes odd multiples. He changes 333 lockers, and 333/3 = odd, so last thing he does is close a locker, which isnt cancelled by a further opening.

    so 1 more closed at the end. ==> 501 closed

    ii) All multiples of 3 and 4 will be closed, and multiples of 4 not multiples of 3 opened

    all numbers of the form 12a are multiples of 3 and 4

    1000 div by 4 250 times, so 250 lockers changed

    1000 is div by 12, 83 times, so 83 closed

    250 - 83 = 167 opened

    so the total is: 167 - 83 = 83 lockers opened which not cancelled by another closing

    so 501 - 84 = 417 lockers closed at the end

    Is this correct? Does anyone have a more elegant solution?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Soroban View Post

    Get it? . . . Only the squares have an odd number of divisors!

    The bulbs that are left on are: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

    Also:

    (iv) After the hundredth student has walked along the corridor, what is the state of locker 1000? Explain your reasoning.

    1000 is not a square number, but it is left open since it has 11 divisors from 0-100. Is there any other method to do this, without counting up its divisors in that range?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by Quick View Post
    I was just about to do it when I read:

    There's always a catch

    Anyway, is it every prime number? Or what...
    How would you use Excel? I want to check my answers
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Probability 2 - Lightbulbs
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 28th 2009, 04:01 PM
  2. Calculus - Lightbulbs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 9th 2007, 04:40 AM

Search Tags


/mathhelpforum @mathhelpforum