Results 1 to 19 of 19

Thread: How to solve this math problem?

  1. #1
    Senior Member CC's Avatar
    Join Date
    Apr 2003
    Posts
    5,173

    Default How to solve this math problem?

    Whats the formula or trick to use?

    ******

    Can anyone solve it ? ( I canít ÖÖ )



    To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

    The lights are originally switched off

    The first student went up to all the lights that are multiples of 1 and switched them on

    The next student then went to switch off all the lights that are multiples of 2

    The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

    This process continued until the 2009th student, who then switched on or off the last light

    The teacher then asked another student to count the number of lights they remain switched on

    Q : How many lights did he count ?
    Its BIxie Jianfa Gawdammit you guys!!!!

  2. #2
    Senior Member yittz's Avatar
    Join Date
    Jul 2005
    Posts
    3,943

    Default

    Spoilers below
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    click to show/hide spoilers

    How many square numbers are there below 2009?

    Only square numbers have an odd number of factorials (is that what they are called?). All other numbers have even number of factorials (say 24 is 1, 24, 2, 12, 3, 8, 4, 6; whereas 25 is 1, 25, 5).

    Odd number of factorials result in lights being switched on. Even number of factorials result in lights being switched off.

  3. #3
    Senior Member remember_Cedric's Avatar
    Join Date
    Oct 2007
    Location
    right here, right now
    Posts
    3,541

    Default

    Interesting math problem. I prefer reverse engineering to the problem. I think Yittzie's solution seems logical to the insolvent.
    What can I say? I'm still standing! No weapon against me shall prosper! I am more than a conqueror!!!

    I don't care to sit by the window on an airplane. If I can't control it, why look?

  4. #4
    Senior Member
    Join Date
    Aug 2007
    Posts
    516

    Default

    Quote Originally Posted by yittz View Post
    Spoilers below
    click to show/hide spoilers

    How many square numbers are there below 2009?

    Only square numbers have an odd number of factorials (is that what they are called?).
    No, they are called factors. Hehe. Factorial is this, for example, factorial of 4: 1x2x3x4=24.

  5. #5
    Senior Member jiang bao's Avatar
    Join Date
    Sep 2008
    Posts
    1,489

    Default

    sounds like a job for a computer program LOL.

    In terms of math, I guess the key may be common multiples.

    I think after the 2nd guy, there may be 1005 on and 1004, then after 3rd guy, there may be 1005 off and 1004 on.

    don't have the time or interest to go further.
    What are you fighting for? Just mix them into pissing beef balls, stupid.
    SOD Pt. 7 updated Jan. 6, '08

    Jiang Bao's Karaoke Corner

  6. #6
    Senior Member
    Join Date
    Sep 2005
    Posts
    2,822

    Default

    Quote Originally Posted by CC View Post
    To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

    The lights are originally switched off

    The first student went up to all the lights that are multiples of 1 and switched them on

    The next student then went to switch off all the lights that are multiples of 2

    The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

    This process continued until the 2009th student, who then switched on or off the last light

    The teacher then asked another student to count the number of lights they remain switched on

    Q : How many lights did he count ?
    click to show/hide spoilers

    44 lights it looks like. Based on yittz "tactic". 1936 is the largest square below 2009. And 44 is the square root of 1936.

  7. #7
    Senior Member jiang bao's Avatar
    Join Date
    Sep 2008
    Posts
    1,489

    Default

    I do agree that the solution probably has to do with the number of factors a certain number have. For example, after the 1st student goes, the 6th light will be flipped on or off thrice more, because itís also a multiple of 2, 3 and 6, so it should be off at the end. Similarly the 11th light would be flipped just one more time so it should be off.

    I donít know how to put it in formula. I havenít studied math since HS, but in words, the rules should be as follows;

    If N is an odd number and N has an odd number of factors excluding 1 (e.g. 11), then that light should be off at the end.

    If N is an odd number but has an even number of factors excluding 1 (eg: 9ó3 and 9), then that light should be on at the end.

    Apply same reasoning to even number N. Itís not necessary to exclude 1 as a factor I think, but itís just easier for me.

    The answer is definitely not 44. Itís probably closer to the mid-point of 1004/1005.
    What are you fighting for? Just mix them into pissing beef balls, stupid.
    SOD Pt. 7 updated Jan. 6, '08

    Jiang Bao's Karaoke Corner

  8. #8
    Senior Member yittz's Avatar
    Join Date
    Jul 2005
    Posts
    3,943

    Default

    What's wrong with if N has even number of factors it's going to be off, and N has odd number of factors it's going to be on. N with odd numbers of factors must be a square number and all square numbers have odd number of factors, hence must be on. The number of square numbers under 2009 is 44. 44 lights will be on.

    1 - 1 *
    2 - 1, 2
    3 - 1, 3
    4 - 1, 2, 4 *
    5 - 1, 5
    6 - 1, 2, 3, 6
    7 - 1, 7
    8 - 1, 2, 4, 8
    9 - 1, 3, 9 *

  9. #9
    Senior Member seventhfairy's Avatar
    Join Date
    Nov 2008
    Location
    california
    Posts
    223

    Default

    Quote Originally Posted by CC View Post
    Whats the formula or trick to use?

    ******

    Can anyone solve it ? ( I canít ÖÖ )



    To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

    The lights are originally switched off

    The first student went up to all the lights that are multiples of 1 and switched them on

    The next student then went to switch off all the lights that are multiples of 2

    The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

    This process continued until the 2009th student, who then switched on or off the last light

    The teacher then asked another student to count the number of lights they remain switched on

    Q : How many lights did he count ?
    I have seen these kind of problems before and I can't solve it either! Sorry

  10. #10
    Senior Member
    Join Date
    Oct 2005
    Posts
    1,097

    Default

    Quote Originally Posted by jiang bao View Post

    The answer is definitely not 44. Itís probably closer to the mid-point of 1004/1005.
    Actually 44 seems close to the actual answer, but I don't think the logic behind is square numbers.

    I'm thinking the answer is around 41, probably less. It's definitely not 1003/1004, the median. That's because it's a continuous process of switching on and off.

    If you try to work out a large enough number, say 50 or 100 on paper (try the process?), you'll probably find a pattern in the left-over number of lights on. As the multiples move on, most numbers (notably the number itself) will be switched off, with only a few numbers smaller than that multiple 'on'. Beyond 1005th student, most lights will eventually be off right, assuming those lights are turned on/untouched. Factors bigger than 1005 will all be off. Hence the answer will not be as big a number as we'd expect it to be, right?

    Maybe, someone should work this out, heh like ancient Greeks? It's better than counting Avogadro's number or the decimals of pi, IMO.

  11. #11
    Member Lifeburner's Avatar
    Join Date
    Apr 2008
    Location
    Indonesia, where people will trap you in a Big Dipper formation if you steal a chicken...
    Posts
    148

    Default

    I agree that any number above 1005 would be left untouched. But can you explain why you're so sure that they'd be off?
    It was often said, "Among horses, Chi Tu (Red Hare). Among retards, Lu Bu."

    Vice-President of Wuji Haters Club!

    Originator of "Wuv Kuddly Hamsty" activity.

  12. #12
    Senior Member
    Join Date
    Oct 2005
    Posts
    1,097

    Default

    Quote Originally Posted by Lifeburner View Post
    I agree that any number above 1005 would be left untouched. But can you explain why you're so sure that they'd be off?
    No, I don't mean ANY number above 1005 would be left untouched.

    I mean by the time we progressed to beyond say 1004th student, some lights beyond this point will have been switched off and then on at least once, most will experienced this just once, and factors beyond this point will be on. My guess is that the off lights at this point will be a lot less than the on lights. So, keeping this in mind, as the multiples keep progressing, the majority of the lights which are previously on will in the end be off.

    For example, say from 1010 to 1020, if 1011, 1013, 1014, 1015, 1017, 1019, 1020 are still on by then, they will all be off eventually as the 1010th to 1020th students will switch them off. Conversely, 1012, 1016 and 1018 will be turned on. So, we can see, the proportion of 'off' lights are much more than 'on' lights. The answer can't be 1005, but I'm not sure how many. But I guess it'd be reasonable to say, the answer would be between 30 and 150?

    Also, all factors (2,3,5,7 .....) will eventually be off. The first light will always be on.

  13. #13
    Senior Member yittz's Avatar
    Join Date
    Jul 2005
    Posts
    3,943

    Default

    Quote Originally Posted by Nefertari View Post
    No, I don't mean ANY number above 1005 would be left untouched.

    I mean by the time we progressed to beyond say 1004th student, some lights beyond this point will have been switched off and then on at least once, most will experienced this just once, and factors beyond this point will be on. My guess is that the off lights at this point will be a lot less than the on lights. So, keeping this in mind, as the multiples keep progressing, the majority of the lights which are previously on will in the end be off.

    For example, say from 1010 to 1020, if 1011, 1013, 1014, 1015, 1017, 1019, 1020 are still on by then, they will all be off eventually as the 1010th to 1020th students will switch them off. Conversely, 1012, 1016 and 1018 will be turned on. So, we can see, the proportion of 'off' lights are much more than 'on' lights. The answer can't be 1005, but I'm not sure how many. But I guess it'd be reasonable to say, the answer would be between 30 and 150?

    Also, all factors (2,3,5,7 .....) will eventually be off. The first light will always be on.
    So what's wrong with square numbers? I thought the explanation was clear enough on its own, let alone me listing the first 3 open lights in numbers less than 10. Pick my answer apart, before questioning it. The answer doesn't feel right is insufficient.

    Why are there only a few lights from 1005 and beyond? Because there are only a few square numbers in between - 13 lights on between 2009 and 1005, but 31 below 1005.
    Member of HYS fanclub -> click here to join group.

    Member of TC fanclub.

  14. #14
    Senior Member
    Join Date
    Oct 2005
    Posts
    1,097

    Default

    Quote Originally Posted by yittz View Post
    So what's wrong with square numbers? I thought the explanation was clear enough on its own, let alone me listing the first 3 open lights in numbers less than 10. Pick my answer apart, before questioning it. The answer doesn't feel right is insufficient.

    Why are there only a few lights from 1005 and beyond? Because there are only a few square numbers in between - 13 lights on between 2009 and 1005, but 31 below 1005.
    There's nothing wrong with square numbers. You're right on the answer.
    It's just that I didn't quite understand what you wrote at first, because you started your sentence with 'What's wrong with.....' I don't understand what you mean. I read your logic the other way round.

    I was thinking along the lines of factors at that time, like 2 and 3 would definitely be off, since they're factors.

    I see that you're listing lights on and counting 1 as a factor and I didn't quite get it, since I didn't see 1 as a factor of anything. So, I can't see the odd number of factors. I saw it the other way round.

    Sorry about that. I know the answer would be around 40. You're definitely right with the answer being 44.

  15. #15
    Senior Member
    Join Date
    Oct 2005
    Posts
    1,097

    Default

    Minor correction to the answer guys.

    Answer is 45. We forgot to count 1 in previously. 44 + 1 = 45 lights should be on.

  16. #16
    Senior Member yittz's Avatar
    Join Date
    Jul 2005
    Posts
    3,943

    Default

    Why would you add one to the answer. 44 lights includes 1 already. 45 squared is 2025, there are only 44 square numbers under 2009 and that includes 1.
    Member of HYS fanclub -> click here to join group.

    Member of TC fanclub.

  17. #17
    Senior Member
    Join Date
    Oct 2005
    Posts
    1,097

    Default

    Quote Originally Posted by yittz View Post
    Why would you add one to the answer. 44 lights includes 1 already. 45 squared is 2025, there are only 44 square numbers under 2009 and that includes 1.
    Thanks!

    I keep forgetting that 1 is also a square number itself. I always start with 4 and then 9, coz 1 is simply too simple. Thanks for reminding yittz.

  18. #18
    Senior Member IcyFox's Avatar
    Join Date
    Nov 2005
    Location
    Unknown
    Posts
    4,556

    Default

    OK this problem is difficult - mainly because there isn't a simple algebraic form of the series, meaning that it's very hard to solve it with algebra. (Or that I don't know of any efficient method of doing it.)

    The big issue here is that each person must turn on/off the lights in multiples of his/her assigned number. Here are the 1st few cases:


    X ~ On ; O ~ Off

    1. XXX ... (2009)
    2. OOO ... (2008, X)
    3. XXX ... O X (2007, O, X)
    4. OOO ... XXX O X (2004, 3X, O, X)
    5. XXX ... OOOO XXX O X (2000, 4O, 3X, O, X)

    ETC ETC ETC...


    If the lights are NOT multiples of the person's number, they CANNOT be touched.

    It's pretty obvious that the number of lights still ON at the end of this whole meaningless exercise is kinda difficult to count by hand. So, I think the best way to solve it is of course by computer. (Unless you have lots of spare time and waste paper...)

  19. #19
    Senior Member IcyFox's Avatar
    Join Date
    Nov 2005
    Location
    Unknown
    Posts
    4,556

    Default

    As mentioned previously, I solved the problem using a computer with a program written in C++. (The final answer actually converged in less than 100 iterations.)


    LIGHTS ON : 1019


    Attached are both the C++ source code and the output text file.

    An assumption I made in order to simplify the computation was that the remaining lights were grouped in numbers less than multiples of the person's assigned number.

    Actually this is quite obvious and requires no proof to see why it is so. If you spot any flaw in my method, please explain mathematically or work it out for yourself on paper to convince yourself.



    Attached Files Attached Files

Similar Threads

  1. Math Help
    By creamcheese007 in forum Academia
    Replies: 4
    Last Post: 04-23-09, 05:18 AM
  2. Internet Problem
    By SkyKing in forum Tech Squad
    Replies: 5
    Last Post: 09-02-07, 11:09 PM
  3. The problem with abbreviation
    By sandy32 in forum Wuxia Fiction
    Replies: 3
    Last Post: 12-08-06, 01:42 AM
  4. Problem
    By misao ohgami in forum Technical Issues
    Replies: 3
    Last Post: 11-11-04, 11:41 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •