Four Travelers Problem. Solution by Stuart Anderson

Manifesto | Index | What's new | rss feed

| Bookmark |

| Follow us

| Recommend | Contact |

Solution to the 4 Travelers problem

The following is based on the proof to the Four Travelers problem posted by Stuart Anderson at the CTK Exchange. To remind, here is the problem:

Four roads on a plane, each a straight line, are in general position. Along each road walks a traveler at a constant speed. Their speeds, however, may not be the same. It's known that traveler #1 met with Travelers #2, #3, and #4. #2, in turn, met #3 and #4 and, of course, #1. Show that #3 and #4 have also met.

First, consider the case of two travelers moving at constants speeds on two intersecting roads. Denote the point of intersection C and position of the travelers P(t) and Q(t), to make the dependency on time explicit. For the convenience sake, however, I shall use P and Q in lieu of P(t) and Q(t), for a generic t, and, for another moment t', P' and Q' in lieu of P(t') and Q(t'). Obviously, the travelers may only meet at the intersection C.

Lemma 1

The travelers meet at C iff for any t and t', PQ||P'Q'.

Proof

If, for any t and t', PQ||P'Q', the triangles PQC and P'Q'C are similar, so that

(1)	P'C/PC = Q'C/QC,

then P'C = 0 implies Q'C = 0, and vice versa. Which exactly means that the two travelers reach the intersection C simultaneously (and meet there.)

Assume now that the travelers do meet at C. Since both move with constant speeds, we have

(2)	P'P''/PP'' = Q'Q''/QQ'',

for any three t, t', t''. If we take t'' to designate the time they met at C, then

P'' = P(t'') = C = Q(t'') = Q'',

which reduces (2) to (1). By SAS, (1) implies the similarity of triangles PQC and P'Q'C, from which PQ||P'Q', as required. (Lemma 1 has a simple dynamic illustration.)

Next, consider the case of three travelers, P, Q, and R moving on three straight lines that satisfy a relaxed condition that no two are parallel. (It is possible to implicitly exclude this possibility by imposing an additional requirement that the three speeds be different.)

Lemma 2

Assume the three travelers P, Q, R meet each other. Then either the roads are concurrent (and the three meet at the same point at the same time) or, at all times, P, Q, and R are collinear.

Proof

From Lemma 1 we know that the lines joining the travelers remain parallel:

(3)	PQ\|\|P'Q', PR\|\|P'R', QR\|\|Q'R'.

Assume that the points are not collinear. Then (3) implies the similarity of triangles PQR and P'Q'R', with the following consequence: if one of the sides of triangle P'Q'R' shrinks to 0, so do the other two sides. In other words, the three travelers all meet at the same time and, therefore, at the same place, so that the three roads are concurrent.

If the roads are not concurrent, the travelers necessarily remain collinear at all times.

(Lemma 2 admits an alternative demonstration. The latter is illustrated with a Java applet.)

Lemma 2 leads directly to a solution of the problem and its generalization. If three travelers A, B, C meet pairwise, they must be collinear at all times. I.e., the third traveler is collinear with A and B. Applied to the three travelers A, B, D, the reasoning shows that D, too, is collinear with A and B. All four A, B, C, and D are therefore collinear. If there is an additional traveler E such that the three of A, B, and E, also meet, then all five are collinear. The number of travelers may indeed be arbitrary.

40617490