Two runners start on opposite corners of a square field with side 1 km, and run around the edge with integral speeds in the clockwise direction. In terms of these speeds, when will they be the same distance apart as when they started?

We know a few things:

<o:p> </o:p>

1)      If time T is a solution for speeds A and B, then time T/2 is a solution for speeds 2*A and 2*B and in general time T/N is a solution for speeds N*A and N*B since the distances travelled are identical in these various cases.

2)      After 4 hours, a runner is always back where they started regardless of their speed since speeds are integral. During those 4 hours, the runner has gone around the track A times where A is the runner’s speed. Thus, 4 hours is a MAXIMUM solution since the runners begin in the desired position and will therefore be in the desired position again in 4 hours.

<o:p> </o:p>

By (1) above, we can assume that the speeds A and B have no common factors—we can solve without common factors and then divide the result by the GCD.

<o:p> </o:p>

Consider the speed of the faster runner (A) with respect to the slower. The faster runner is catching up at a rate of (A-B). The faster runner must travel 4 km with respect to the slower runner to once again be potentially opposite, and both runners must be at corners when this occurs. Since each runner arrives at a corner every 1/A and 1/B hrs, and since A and B have no common factors (by assumption), runners can BOTH be at corners only at integral hours.

<o:p> </o:p>

Since we’re considering only integral hours, speeds matter only mod 4 – a speed of 4, 8, or 12 will be in the same position on the hour marks; the same is true for speeds of 1, 5, and 9 or 2, 6, and 10. What controls the time to reach opposite corners, then is (A-B) mod 4. If (A-B) mod 4 = 1 or 3 then it takes the full 4 hours to reach opposite positions again. If (A-B) mod 4 = 2, then only 2 hours are needed, and if (A-B) mod 4 = 0 then only one hour is needed. (Try it!)

<o:p> </o:p>

The time in general, after removing the restriction that A and B have no common factors and employing (1) above, is

 

4 / (GCD(A,B) * c)

 

where c = 4 when (A-B)/GCD(A,B) = 0 mod 4, 2 when (A-B)/GCD(A,B) = 2 mod 4 and 1 otherwise.

<o:p> </o:p>

There’s likely a more elegant way to write this solution, but I believe it to be accurate.

Posted by Paul on 2009-01-15 22:23:20