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

Brain Teaser #94

  1. Apr 28, 2004 #1
    Brain Thumper #8

    The Pacific Proprietary Production Plant has the capacity to manufacture straight sections of miniature railroad track on two machines, each of which produces a specific length of track. For instance, suppose that the company had initially configured the machines to make straight track that is 3 cm and 5 cm long.

    A hobbyist who buys this track would be able to use different combinations thereof. For instance, she could combine one 3 cm section and one 5 cm section to fill an 8 cm gap in her modeling project. Three 3 cm sections make 9 cm, two 5 cm sections make 10 cm, and so forth. However, there are some shorter integer lengths that cannot be achieved. In this case it is impossible to get straight track in 1, 2, 4, or 7 cm segments.

    As it turns out, given the way that the two machines were configured, there are exactly eight different positive integer lengths that cannot be constructed. Find at least one possibility for the plant's machine specifications. Note, however, that requirements in the way tracks couple prohibit the manufacture of a section that is 2 cm or shorter.
     
    Last edited: Apr 28, 2004
  2. jcsd
  3. Apr 28, 2004 #2
    2.5 cm, 4.5 cm; can't make 1,2,3,4,6,8,11,13 cm sections

    Now, back to particles in boxes...
     
  4. Apr 29, 2004 #3
    gnome with the point!

    I thought people would get frustrated with this one because there aren't any solutions where the two lengths are integers. It just goes to show that you can't fool everyone.

    For the theoretical types, here is another problem. I should warn you that there is only one solution.


    Tack-on Teaser:

    Same as above except that there are 2048 positive integer lengths of track that cannot be constructed, with the added restriction that only integer lengths of track can be constructed. As before, the specs for each of the two machines must be greater than 2 cm.
     
    Last edited: Apr 29, 2004
  5. May 14, 2004 #4

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The number of unachievable lengths for any pair (L, L+1) is L(L-1)/2. Since 2048 is not of this form, the numbers can not be consecutive.

    If the pair has 2 evens then there are an infinite number of unachievables - all odd lengths.

    Need to look at odd pairs and odd,even pairs to find patterns - assuming they exist. Vague ideas are forming in my head about the convergence of sections of consecutive unachievables. Let's explore.
     
  6. May 14, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Plz ignore my naivete, if the above is obvious. This is my first time here.
     
  7. May 24, 2004 #6
    Nice formula. How did you come across it?


    True. You could also make that into a stronger statement fairly easily.
     
  8. May 24, 2004 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try it out with any such pair : say 14,15. Here's what you get for the lengths you CAN make :
    14,15,
    28,29,30,
    42,43,44,45,
    56,57,58,59,60, etc.

    That sould make it obvious !

    Eventually, I did come across a stronger form (can't remember it now) but it didn't lead me to a solution.

    Will we see that sometime ?
     
  9. May 29, 2004 #8
    I don't think anyone's going to crank this one out by brute force.
     
  10. May 30, 2004 #9

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How about a hint ??
     
  11. May 30, 2004 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Is that a challenge? :biggrin:
     
  12. May 30, 2004 #11
    Never mind, I'll take the bus; that is unless there is another one of these things to deal with for the bus as well. If there is, I will stay at home until the trains are running again.
     
  13. Jun 2, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hope you don't say that 2048 is not a solution for any integer pair - cause we all use large chunks of "brute force" to help locate patterns, and that takes time and effort. So far, it does not seem impossible to find solutions of the form 2n, but I haven't been able to find enough to see a pattern. For non-consecutive numbers, there does not appear to be a polynomial pattern. Perhaps a combinatoric approach is what you need...can't find one !

    And if you're wondering...I have NOT spent the last month trying to solve this puzzle.
     
  14. Jun 2, 2004 #13

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Did you mean "the numbers need to be relatively prime (or co-prime) to have a finite number of unmakeables" ?
     
    Last edited: Jun 3, 2004
  15. Jun 5, 2004 #14
    There should be a pattern. The more interesting is the constructive proof of the formula.


    That's it.
     
  16. Jun 5, 2004 #15

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So you refuse to throw in a hint ?
     
  17. Jun 5, 2004 #16

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    WAIT...I'm getting somewhere...don't say anything yet...the clouds appear to be parting...tried neighbors...found pattern...looked at odds...found another pattern...went to n,n+3...found pattern there too...seeing pattern between patterns...could it be...better check...
     
  18. Jun 5, 2004 #17

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Solutions : relatively prime pairs among

    [tex] 2^x + 1, 2^{12-x} +1 ; x=1,2,3,4,5 [/tex]

    i.e. (3,2049) (5,1025) (9,513) (17,257) (33,129)

    Only last 2 pairs survive : 17,257 and 33,129

    PS : With tracks of length m,n (relatively prime) the number of unbuildable lengths is :

    [tex]N = (n-1)(m-1)/2[/tex]
     
    Last edited: Jun 5, 2004
  19. Jun 11, 2004 #18
    The formula is correct. I can't believe that, in coming up with the problem, I subtracted one from the factors of 2^blah instead of adding one. You may have found two solutions instead of the lone one I had expected, but thankfully it turns out there is some solution after all.
     
  20. Jun 11, 2004 #19

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you have a proof for why this is true ? I'd love to see it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Brain Teaser #94
  1. Brain Teaser #19 (Replies: 4)

  2. President Brain teaser (Replies: 12)

  3. Brain teaser question (Replies: 10)

Loading...