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?

[Molly Mae]

10, 15, 18, 20, 24, 30

Checking:

Every speed must be of a working ratio to every other speed. Unfortunately, I just found that 10 and 18 don't like each other. Also, 15 and 20 (3:4) doesn't seem to work. 18:20 (9:10) also doesn't work.

Working ratios I've found thus far:

1:2

3:5

1:3

2:3

5:6

Edited September 2, 2011 by Molly Mae

[CaptainEd]

I question 15:24 = 5:8. I think the fast one passes the slow one before the slow crosses the fourth time.

[Molly Mae]

I question 15:24 = 5:8. I think the fast one passes the slow one before the slow crosses the fourth time.

And of course you're right. =P

As much as I can get them to work well with the fastest car, I can't seem to get them to work well with each other. I actually edited the post above about the time you were replying.

[CaptainEd]

I love these simply stated problems that keep showing weird interactions. I'm finding it easy to be a critic, and hard to see how to generate "the next candidate" solution.

[Molly Mae]

120, 180, 216, 240, 300, 360

==

20, 30, 39, 40, 50, 60

How did I even get that?

Checking now

Edited September 2, 2011 by Molly Mae

[Molly Mae]

Typo. 36 = 39. Donno how that happened, but it confused the....yeah...

[CaptainEd]

worse yet, neither 36 nor 39 goes with 20. Neither does 50. Sigh! pesky constraints...

[Guest]

I think I may have a unique an out-of-the-box solution to this problem:

The OP has told us that the racers are "really tiny." plainglazed did not tell us what the racers were small in comparison to. Therefore, I conclude that the racers must be very small in comparison to the track. The rules state that no racer can pass another is at the intersection of the figure-eight track. The rules do not say, however, that the racers must drive in a straight line around the track.

Suppose the racers all start out facing the same direction and at different speeds. Quickly, the pack has become a line due to the differing speeds. Once this happens, all but the last racer begin to swerve across the track following a sine wave pattern with their amplitudes sufficient to keep them a constant distance from the trailing racer as they cross the center of the track. Therefore, the fastest racer would be swerving across the track a further distance from the center than the next fastest until you get back to the slowest racer which is traveling only along the center of the track.

Another possibility is that each racer follows a different curve around the turns of the figure-eight such that their difference in speed is negated.

The minimum speed in both cases above for the fastest racer would simply be 6. Oh, and you'd no longer need to be concerned with the passing points.

Edited September 2, 2011 by Egghead

[CaptainEd]

30, 35, 36, 40, 42, 45

Had to get it by hand, because I don't have any programming language available but Excel macros. And they DON'T excel...

Thanks, again, plainglazed and everyone who doesn't let wrong answers get by.

[Guest]

I like Egghead's solution! Giving the track a width greater than the combined widths of all six cars (no matter how "really tiny") means that, with skillful driving, the cars can indefinitely avoid crashing regardless of speed value combinations

[plainglazed]

Nicely done CaptainEd - I believe you have it. Thanks for sticking with it. Although am pretty sure how to simply and quickly check if a given set of six speeds creates a steady state, I do not know how to prove a minimum speed for the fastest car so also just used a spreadsheet.

I too like the out of the box offering of Egghead and of Valic4 but only mentioned the "really tiny" bit to suggest when they do pass one another (at the intersection only), they do it instantaneously.

[CaptainEd]

Thank you, plainglazed. Once I finally had the ratio constraints, I was able to enumerate candidates, so the optimality proof is by exhaustion--I tried all smallest speeds from 1 to 39

I turned my ratio constraints around and asked, "if N is the smallest speed, what are the other speeds that can go with it?". Then, given that candidate list, I discarded ones that didn't fit with enough of its mates. Pretty soon, I could discard N and move on.

Here's the process, from N = 1 to infinity (30, as it turned out):

1) break N into its list of factors (including 1 and N).

2) Start a list of candidate speeds with the singleton N.

3) for each factor F, append N + F and N + 2F to the list, if not already present

4) (manually) throw away each candidate that can't find 5 companions that work with it. (in a few cases, such a candidate could work with its companions, but the companions collided with each other...)

Edited September 2, 2011 by CaptainEd

[Guest]

After applying to spreadsheet

racers at speeds of 4, 6 ,8, 9 & 10 on a track of length 8 will work as a solution. Since I overlooked the 3:1 ratio as a possibility, there are probably other ratios that I skipped so I will examine further.

[CaptainEd]

once again, I doubt 4 and 10 are compatible. Also, what does it mean to have a length of 8? The speeds we have are just relative to each other.

[plasmid]

Call the total length of the eliptical track 1 "unit".

If two cars are traveling at speeds A units/sec and B units/sec where A is the faster car, then the faster car will lap the slower car at time T sec where

A units/sec x T sec - B units/sec x T sec = 1 unit

T (A-B) = 1

T = 1 / (A-B)

They cross after the first car travels a distance of (A units/sec x T sec)

distance until crossing = AT = A (1/(A-B) ) = A / (A-B)

To cross at the intersection, the crossing point must be at a distance of N/2 units where N is an integer

A / (A-B) = N / 2

Well, if we're given a value for A, then we can take the formula A / (A-B) = N / 2 and solve for B

2A / N = A-B

B = A - 2A / N = A(N-2)/N

If we set A=1, then the possible values for B are 1/3, 2/4, 3/5, 4/6, ... Of course, A and B must be integers, so you would have to multiply both A and B by the denominator of B. This means that the ratio of A to B must be one of 3:1, 4:2, 5:3, 6:4, ... (of the form N+2:N)

But there are six cars. So the ratio of A to B must be one of 3:1, 4:2, 5:3, 6:4, ... (of the form N+2:N), as must the ratio of A to C, and B to C, and A to D, and B to D...

I am currently too tired to complete the solution to this problem though

[plainglazed]

yes indeed, plasmid. thanks for the math.

cars A and B will cross at the intersection if the crossing point is at a distance of N as well as N/2. This gives us the ratio of N+1/N as well as N+2/N for some integer N that all pairs of cars must demonstrate.

my math is not strong enough to prove a min for the fastest car.

[CaptainEd]

Don't forget reducing to lowest terms.

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)

[plasmid]

Finally finished with a murderous labor day weekend at work.

yes indeed, plasmid. thanks for the math.

cars A and B will cross at the intersection if the crossing point is at a distance of N as well as N/2. This gives us the ratio of N+1/N as well as N+2/N for some integer N that all pairs of cars must demonstrate.

my math is not strong enough to prove a min for the fastest car.

Yes, but since N can be any integer, the set {N} is contained within the set {N/2}... that is, for example, if cars A and B will cross after 12 laps, they will cross after 24/2 laps, so that possibility would be accounted for with my approach.

Don't forget reducing to lowest terms.

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)

Um... I don't follow what you're talking about?

If a car is traveling at speed A km/h and is faster than another car traveling at B km/h, then the distance between the two cars will increase by (A-B) km/h. So A will lap B after some amount of time T where

(A km/h - B km/h) x T h = [Total length of the track in km]

You can calculate where they cross, and if it's after traveling N/2 times the total length of the track (where N is an integer), then they will cross at the intersection.

If the fastest car travels at speed A, then there must be some speed B for the second fastest car such that A:B = N+2:N for some integer N. There also must be some speed C slower than B such that A:C = N+2:N for some other integer N, etc for cars D, E, and F. Similarly, B:C, B:D, B:E, B:F, C:D, C:E, C:F, D:E, D:F, E:F must have such a ratio.

Solving for N

A N = B (N+2)

(N+2)/N = A/B

1 + 2/N = A/B

2/N = A/B -1

N = 2 / (A/B - 1) = 2 / [(A-B)/B] = 2B / (A-B)

I could not find an elegant way of logik-ing out the optimal solution, so I resorted to making a spreadsheet. Rows are values for the faster speed of a pair, columns are values for the slower speed for a pair, elements are N = 2B / (A-B), and are visible only if they are integers. (So numbers are only visible if the speed in row A and column B are compatible.)

Manually inspecting this worksheet, the best solution I could find was

48, 45, 44, 42, 40, 36

[Guest]

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?

4,6,7,8,12

I find it by math. but don't know to use spoiler tool to hide it.

Sorry

[CaptainEd]

I agree that the solution you gave works, but I don't see how it conforms to your criterion that A:B = (N+2):N for some integer N. In particular, how do 45 and 42 meet this criterion?

This is why plainglazed and I think it needs to be extended to say that either A:B=(N+2):N or A:B=(N+1):N.

Are you sure 7 and 12 work together without collision? I believe 12 runs into 7 before 7 gets to the intersection for the third time.

Edited September 7, 2011 by CaptainEd

[plasmid]

I agree that the solution you gave works, but I don't see how it conforms to your criterion that A:B = (N+2):N for some integer N. In particular, how do 45 and 42 meet this criterion?

This is why plainglazed and I think it needs to be extended to say that either A:B=(N+2):N or A:B=(N+1):N.

Ah, I can see how that would be rather confusing.

N = 28

A:B = 30:28 = 45:42

Similarly, each of the other ratios between all pairs of speeds can be reduced to a ratio of the form N+2:N

[bhramarraj]

Let us assume there are three cars A, B, and C on the track.

Say A is the fastest, and C is the slowest car.

Now imagine B crosses C at the intersection X, then ratio of their speeds, to meet the condition that they cross each other, at no place other than X, will be 2:1 or 3:1, if the cars are allowed to cross irrespective of their direction of movement at X.

Then, A & B should also have the speed ratio 2:1 or 3:1, to meet above condition.

So the ratio of speeds between A, B, and C would be 4:2:1 or 6:3:1 or 6:2:1 or 6:3:1.

In each case we see that when B reaches X, after completing two or three circles, C completes one circle (one circle is half of 8) of the track, and none of B & C overtakes each other.

Now A being the fastest of the three must complete 4 or 6 circles in the same time. So in any case A has to cross C before C reaches X.

[CaptainEd]

Bhramarraj, As you point out, speed ratios of 4:1 and 6:1 are too big--the faster car overtakes the slower car before the slower one can get to the intersection.

However, other speed ratios are possible. Try 3:2 or 4:3 or 5:3. Plasmid and I have different statements of the possibilities, but we agree on what possibilities there are, and there are plenty more than 2:1 and 3:1.

Edited September 8, 2011 by CaptainEd

[plasmid]

Lol, I just realized Cap'n...

the three ratios you mentioned

2n : 2n + 1

2n : 2n - 1

2n -1 : 2n + 1

can be re-written

1. 2n : 2n + 1

= 4n : 4n + 2

= N : N + 2 (just set N=4n)

2. 2n : 2n - 1

= 4n : 4n - 2

= 4(n-1) + 4 : 4(n-1) + 2

(set N = 4(n-1) + 2)

= N + 2 : N

3. 2n -1 : 2n + 1

= 2(n-1) + 1 : 2(n-1) + 3

(set N = 2(n-1) + 1)

= N : N + 2

All solutions using your ratios will also be a ratio of the form N : N+2

The three cases you describe cover all my solutions of the form N = 4n, N = 4(n-1)+2, and N = 2(n-1)+1

The cases N = 4n and N = 4(n-1)+2 cover all even numbers for N

The case N = 2(n-1)+1 covers all odd numbers for N

We really did have the same answer the entire time!

[CaptainEd]

Yes Plasmid, I figured that out when you posted your answer and accepted 45:42 as being N+2:N, by transforming it into 30:28. For me, it is an example of N+1:N (15:14), (and therefore represents a "cross" rather than an "overtake"--not that this difference matters in the OP; we've both assumed that both crosses and overtakes are permitted at the intersection). And since your suite of six speeds is valid according to my view of the constraints, I figured we would agree on the same solutions. So you'll probably agree with my suite in post #35. This is an interesting puzzle!

Edited September 8, 2011 by CaptainEd