Brain Teaser #94: Find Machine Specs for Proprietary Production Plant

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

 

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

 

[davilla]

2.5 cm, 4.5 cm

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.

 

[Gokul43201]

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.

 

[Gokul43201]

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

 

[davilla]

The number of unachievable lengths for any pair (L, L+1) is L(L-1)/2.

Nice formula. How did you come across it?

If the pair has 2 evens then there are an infinite number of unachievables

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

 

[Gokul43201]

Nice formula. How did you come across it?

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 ?

 

[davilla]

Eventually, I did come across a stronger form ...
Will we see that sometime ?

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

 

[Gokul43201]

How about a hint ??

 

[Hurkyl]

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

Is that a challenge?

 

[Dazed&Confused]

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.

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.

 

[Gokul43201]

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 2ⁿ, 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.

 

[Gokul43201]

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

Did you mean "the numbers need to be relatively prime (or co-prime) to have a finite number of unmakeables" ?

 

[davilla]

For non-consecutive numbers, there does not appear to be a polynomial pattern.

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

the numbers need to be relatively prime

That's it.

 

[Gokul43201]

So you refuse to throw in a hint ?

 

[Gokul43201]

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

 

[Gokul43201]

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

 

[davilla]

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

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

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.

 

[Gokul43201]

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

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

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