A Passing Fancy

[plainglazed]

Six (really tiny) racecars all set out in the same direction starting at the intersection of a figure eight shaped track. Each travels at a unique constant integer speed (greater than 0). The intersection of the figure eight is the only spot on the track where the racecars can pass one another. If the six cars can race in this manner for an indefinitely long time, what is the minimum speed of the fastest of the six cars?

[CaptainEd]

if speeds are 1,2,4,8,16,32, then the answer is 32

[Guest]

if speeds are 1,2,4,8,16,32, then the answer is 32

This too was my first thought. Unfortunately it is wrong!

With the speeds; 1,2,4,8,16 & 32, The fastest car will make 32 figure 8s (regardless of track length) every time the slowest car accomplishes a single figure 8. This means the fastest car would need to be able to pass the slowest car 32 times but the slowest car would have been at the intersection only twice.

[CaptainEd]

Thank you thoughtfulfellow. Woops!

[Guest]

Let's unbundle the figure eight to a simple cycle. Then cars can pass one another only at 0 and 180 degrees if start is at 0.

Let's take two cars with successive angular speeds ω_i and ω_i+1. The fastest car "i+1" can make indefenetly many rounds before car "i" reaches it's first 180 degrees but "i" has to pass it only at 180 degrees. Thus the minimum difference of their angular speeds can be ω_i+1=3ω_i so that after they start, "i" is at 180 degrees for it's first time while "i+1" is at the same point for it's second time only. They will meet again at 0 degrees. Same rational.

Linear speed of each car is z=rω thus ω=z/r. Thus z_i+1=3z_i. This gives us the minimum speed of car "2" if car "1" has the minimum speed z₁=1, which is z₂=3. Minimum speed of car "3" is z₃=9. This goes on until car "6" which has minimum speed z₆=3⁵=243.

Basil from Athens

[Guest]

Spoiler for an almost solution :

and then the aid of a spread sheet, I came out with a speed of 18 for the fastest racer and a total track length of 18. For those that wish to check my work: For the fastest racer to meet the other cars at the intersection of the figure 8, then the speed must be in a ratio of 1/2, 2/3, 3/4, 4/5 etc. Plugging these into a spreadsheet, (I used lotus 123) and examining the grid for integral speeds, it appeared that the ideal speeds would be 9, 12. 15. 16. 17, and 18. Then I used a spread sheet to verify that this works. Examining the sheet for the time at which each racer was passed, I unfortunately found that this worked out for all but one racer. Further examined and tried speeds of 10 15 16 18 19 and 20, but once again one racer failed the test.

Maybe someone with more time or a better approach can finish this solution

[Guest]

Let's unbundle the figure eight to a simple cycle. Then cars can pass one another only at 0 and 180 degrees if start is at 0.

Let's take two cars with successive angular speeds ω_i and ω_i+1. The fastest car "i+1" can make indefenetly many rounds before car "i" reaches it's first 180 degrees but "i" has to pass it only at 180 degrees. Thus the minimum difference of their angular speeds can be ω_i+1=3ω_i so that after they start, "i" is at 180 degrees for it's first time while "i+1" is at the same point for it's second time only. They will meet again at 0 degrees. Same rational.

Linear speed of each car is z=rω thus ω=z/r. Thus z_i+1=3z_i. This gives us the minimum speed of car "2" if car "1" has the minimum speed z₁=1, which is z₂=3. Minimum speed of car "3" is z₃=9. This goes on until car "6" which has minimum speed z₆=3⁵=243.

Basil from Athens

One of us is not reading the problem correctly.

By my interpretation if the fastest car travels greater than double the speed of the slowest car, then it will overtake the slowest car at some point other than the intersection. When it reaches the slowest car, it must pass or crash. Since the problem said passing must only be at intersections, the limit of the ratio of fastest car to slowest car can not be greater than 2:1.

[bhramarraj]

Let us consider only two cars A & B on the track. Then faster car A can pass the slower car B only when both cars meet at the intersection point (say X) that too when both are moving in the same direction. so when B completes one circle (note one circle is half of 8) to reach X, A has to complete three circles to reach X and to be moving in the same direction as of B.

Now let us add one more car C, on the track. To reach the X, to pass A & B, and to be moving in the same direction as of A & B, C also has to complete three circles, otherwise it will collide with other cars or will have to overtake them between the tracks.

So I think this is not possible to have more than two cars on the track which pass each other only at X.

[CaptainEd]

I'm glad you hold our feet to the fire, but try a 1:3 ratio, as bhramarraj suggests. I think it works and is the max ratio. I agree with you that more multiplication is doomed to failure

I disagree with your last statement, bhramarraj, although I agree with the max limit on their ratio being 3. But, if cars A, B, and C have speeds in ratio 1:2:3, it appears that each pair can drive around without crashing, even the 2:3 pair. Somehow we have to squeeze in the other cars between them (multiplied up to integer speeds, of course).

[Guest]

I'm glad you hold our feet to the fire, but try a 1:3 ratio, as bhramarraj suggests. I think it works and is the max ratio. I agree with you that more multiplication is doomed to failure

I disagree with your last statement, bhramarraj, although I agree with the max limit on their ratio being 3. But, if cars A, B, and C have speeds in ratio 1:2:3, it appears that each pair can drive around without crashing, even the 2:3 pair. Somehow we have to squeeze in the other cars between them (multiplied up to integer speeds, of course).

Thank you, You are right, That's probably the key I was missing to set things right. I will examine 6, 9, 12. 15. 16. 17, and 18. and suspect that 6 of these seven will work Back to the spreadsheet, unfortunately I will not be able to for a while to verify this hypothesis.

[Guest]

However, if any of the 6 cars meet, they will crash. (Working with simple factoring, 6 and 9 will eventually intersect at some multiple of 18). I may have misinterpreted, but isn't our goal to have all six of the numbers indefinitely avoid intersecting?

[Guest]

Also, there may need to be a minimum length of track where avoiding crashes is impossible for any speed combination. (I'm sure it would be longer than, let's say, 4 times the combined length of the cars)

[Molly Mae]

The track can be a circle of any radius where p is the passing point.

The length of the track (L) must be the least common multiple of all 6 racer speeds and it must be the least common multiple of any two racer speeds. For any configuration that meets this criteria, the racers should always meet at p (and 2p, if you're using the figure 8).

[CaptainEd]

I'm sure your concern is valid, Valic. I've been making an assumption--that two cars can "cross" as well as "pass" at the intersection. Under that assumption,

thoughtfulfellow shows that if the ratio is greater than 2:1 (except for 3:1, as basil points out), the faster car will overtake the slower at some point other than the intersection.

But it looks like if the ratio is less than 2:1, the faster car will slowly lap the slower car, and will only intersect at the least common multiple of circuits, as Molly Mae said.

So, the assemblage of cars must have speeds where ratio of any two speeds can be any ratio less than 2:1, but you can also have 3:1.

First, four cars. They can be 2,3,4,6.

You can't squeeze a car between 2 and 3, because it would be too small compared to 6.

you can't squeeze a car between 4 and 6, because it would be too big compared to the 2.

So let's double the values: 4, 6, 8, 12. can't get enough numbers between 6 and 8. So triple it:

6,9,12,18. Now squeeze between 9 and 12 thus: 6, 9, 10, 11, 12, 18.

But can we do better by ignoring the 3:1 ratio? Just make everything fit between 1 and 2?

The smallest sequence of 6 in a row with ratios <= 2:1 is 5,6,7,8,9,10

What a marvelous puzzle, plainglazed! Each step brought surprises, thank you. (Sure hope my answer is right...at least it's better than my first one)

Edited September 2, 2011 by CaptainEd

[Guest]

i suspect the answer is...

12 16 18 24 32 36

[Guest]

ah, can also divide my nubmers by 2; final answer:

6 8 9 12 16 18

Edited September 2, 2011 by phillip1882

[Guest]

I'm sure your concern is valid, Valic. I've been making an assumption--that two cars can "cross" as well as "pass" at the intersection. Under that assumption,

thoughtfulfellow shows that if the ratio is greater than 2:1 (except for 3:1, as basil points out), the faster car will overtake the slower at some point other than the intersection.

But it looks like if the ratio is less than 2:1, the faster car will slowly lap the slower car, and will only intersect at the least common multiple of circuits, as Molly Mae said.

So, the assemblage of cars must have speeds where ratio of any two speeds can be any ratio less than 2:1, but you can also have 3:1.

First, four cars. They can be 2,3,4,6.

You can't squeeze a car between 2 and 3, because it would be too small compared to 6.

you can't squeeze a car between 4 and 6, because it would be too big compared to the 2.

So let's double the values: 4, 6, 8, 12. can't get enough numbers between 6 and 8. So triple it:

6,9,12,18. Now squeeze between 9 and 12 thus: 6, 9, 10, 11, 12, 18.

But can we do better by ignoring the 3:1 ratio? Just make everything fit between 1 and 2?

The smallest sequence of 6 in a row with ratios <= 2:1 is 5,6,7,8,9,10

What a marvelous puzzle, plainglazed! Each step brought surprises, thank you. (Sure hope my answer is right...at least it's better than my first one)

Thanks much Captain Ed. But if cars can "cross" in this track, then wouldn't the only remaining fail point be if the cars rear-ended each other? If that were the case, would the shape of the continuous track likely be moot? Could we then safely conclude that for any continuous track of finite length, the first (fastest) of any chain of constantly moving cars would at some time collide with the last (slowest) in that chain (in other words, no combination of speed values would indefinitely work)?

[Guest]

captian ed: i believe each number needs at least one common factor with each other number, or a differance of 1.

with your car speeds, 7 and 10 will crash.

7 10 14 20 21 30 28 40 35 50 42 60 49 0 56 10 63 20 0 30 7 40 14 50 21 60 28 0 35 10 42 20 49 30 56 40 63 50 0 60 7 0 14 10 21 20 28 30

with my speeds, i think 9 and 16 may crash at some point. what a tricky problem!

[CaptainEd]

Well, part of what I said was true--"every step brought surprises".

Valic, if I understand your objection, they can only avoid rear-ending if they arrive at the intersection at precisely that moment, and the faster overtakes the slower. (We're ignoring the ludicrous situation of all six arriving at the same moment, each overtaking the next...)

Phillip, thanks for waking me up. Now that you point out 7 and 10 fail, I"m at a loss again. It looks to me now that, expressed as integers with common factors taken out, any two compatible speeds have to differ by one or two. So 3:5 works, 5:7 works, 7:8 and 7:9 work, but 7:10 does not. (also 9 vs. 16 or 8 vs 18).

I think...(and I don't have the six car speeds now, either)

[Molly Mae]

Where n is the number of equally spaced passing points, the maximum number of cars at constant speed will be 2^n. (I can't prove this)

When there is only one place to pass, the ratio of speed must be 2:1. With two places to pass the ratio of fastest car to slowest car can be, at best, 3:1. The first car must travel the whole track 1.5 times while the slowest car must travel half the track. If the fastest car is any faster or the slowest car is any slower, they crash on the first curve.

I don't think you're going to fit six cars without a third passing point.

It actually might only accommodate n+1 (2:4:6 in a figure 8). But again, I don't have proof of this yet.

EDIT: Personal note

Where x is the speed of the fastest racer and y is the speed of any other racer, x mod y must == a factor of x (or 0)

Edited September 2, 2011 by Molly Mae

[Guest]

okay so here's what i now have.

1 2 3 is the smallest speeds for 3 cars.

2 3 4 6 is the smallest speeds for 4 cars.

10 12 15 20 30 is the smallest speeds for 5 cars.

110 132 165 220 330 390 (???)

[CaptainEd]

are you sure 12 and 30 can coexist for 5 cars? Similarly, I doubt the 2nd and 6th car.

6 8 9 10 12 works, I think

Edited September 2, 2011 by CaptainEd

[plainglazed]

Predict smooth sailing ahead for the Cap'n. Very pleasing responses from all - looks like fun. Hate that am caught up here at work.

[Guest]

okay i am offically calling this impossible.

though i can't prove it rigorously,

3 and 5 don't work, niether does 5 and 7, 11 13, etc.

for 3 and 5:

 3  5

 6 10

 9  0

12 5

 0 10

 3   0

 6  5

9 10

as molly said for every pair x and y, x mod y must result in a number that evenly divides into x (or be 0).

[CaptainEd]

3:5 does work. The ratio is 1 : 1 2/3.

Let's speak of the track as two loops.

When slow car reaches the intersection first time, the fast car has gone 2/3 around the next loop, so he's ahead of the slow car, in the same loop.

WHen slow reaches the second time, the fast guy has gone 3 1/3 times, so he's in the other loop

When slow reaches the third time, the fast guy just overtakes him.

As far as I can tell, any successful ratio, reduced to lowest terms, must be one of:

2n : 2n + 1

2n : 2n - 1

2n -1 : 2n + 1

In the last case, the fast car overtakes the slow car at the intersection, in the other cases, the fast car crosses the slow car at the intersection (both drivers closing their eyes, I'm sure)

[Guest]

just wanted to quickly comment: 2 and 6 do indeed work.

let the track be of length 12.

then:

2 6

4 0

6 6

8 0

10 6

0 0

and the captian is right of couse 3:5 does work.

6 10

9 15

12 20

15 25

18 0

21 5

24 10

27 15

0 20

3 25

6 0

9 5

12 10

15 15