Brain Teaser #94

1. Apr 28, 2004

davilla

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. Apr 28, 2004

gnome

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...

3. Apr 29, 2004

davilla

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
4. May 14, 2004

Gokul43201

Staff Emeritus
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.

5. May 14, 2004

Gokul43201

Staff Emeritus
Plz ignore my naivete, if the above is obvious. This is my first time here.

6. May 24, 2004

davilla

Nice formula. How did you come across it?

True. You could also make that into a stronger statement fairly easily.

7. May 24, 2004

Gokul43201

Staff Emeritus
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 ?

8. May 29, 2004

davilla

I don't think anyone's going to crank this one out by brute force.

9. May 30, 2004

Gokul43201

Staff Emeritus

10. May 30, 2004

Hurkyl

Staff Emeritus
Is that a challenge?

11. May 30, 2004

Dazed&Confused

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.

12. Jun 2, 2004

Gokul43201

Staff Emeritus
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.

13. Jun 2, 2004

Gokul43201

Staff Emeritus
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
14. Jun 5, 2004

davilla

There should be a pattern. The more interesting is the constructive proof of the formula.

That's it.

15. Jun 5, 2004

Gokul43201

Staff Emeritus
So you refuse to throw in a hint ?

16. Jun 5, 2004

Gokul43201

Staff Emeritus
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...

17. Jun 5, 2004

Gokul43201

Staff Emeritus
Solutions : relatively prime pairs among

$$2^x + 1, 2^{12-x} +1 ; x=1,2,3,4,5$$

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 :

$$N = (n-1)(m-1)/2$$

Last edited: Jun 5, 2004
18. Jun 11, 2004

davilla

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.

19. Jun 11, 2004

Gokul43201

Staff Emeritus
Do you have a proof for why this is true ? I'd love to see it.