Aha, that's right. So, if the four roads are in general position, then A, B, C are collinear and so are A, B, D, thus all four are collinear.

An elementary (or a less abstract) way to prove the above is this:

take three noncollinear points one on each of the three nonconcurrent lines and try to move the points along their lines so that the sides of the triangle they form remain parallel. A simple drawing will show that this is impossible.

In geometric terms:

Let there be a triangle and three directions. There exists one and only one triangle inscribed into the given one with sides parallel t the given directions. (1. "Inscribed" means having vertices one the sides, one per side. 2. There must be a qualification that stipulates a certain orientation of the triangle and a related one for the inscribed triangle.)

I was very happy to see that you have put this proof with the other 4 travelers proofs on your website. After you take away the stuff about graph theory, what is left is a pretty good elementary proof for the 4 travelers problem, I think. The Java applet that lets you try to move the travelers around a triangle while keeping their joining segments in their original orientation is a very nice demonstration of what happens when you assume they aren't collinear. Very nice!

Since I've been looking at Ceva's and Menelaus' Theorems lately, it is on my mind that their conclusions look a lot like the alternate cases you get in the lemma I used for the 4 travelers problem, namely that 3 travelers are either collinear (Menelaus) or their paths are concurrent (Ceva). Now upon looking at it further, I think you can use the 4 travelers problem to prove both Ceva's and Menelaus' Theorems.

As usual, let ABC be a triangle, and let D lie on BC, E on CA, F on AB. Let travelers d, e, and f start at time t=0 from D, E, and F along lines AD, BE, and CF. Assume that they all meet each other (pairwise). Focus on two of the travelers, say d and d. Start two other travelers d' and e' from D and E along DC and EC, also at t=0, and give them speeds so that d' meets e at B and e' meets d at A. You can always do this by choosing the correct speeds.

Now the 4 travelers problem shows that d' meets e' at C. Let's look at the times of travel (vx means velocity of traveler x):

(1): EA/ve' = DA/vd because d and e' meet at A
(2): DB/vd' = EB/ve because e and d' meet at B
(3): EC/ve' = DC/vd' because d' and e' meet at C.

Combining these gives
(4): (EA/EC)(DC/DB)(EB/DA) = ve/vd,
and multiplying this together with the two other equations we get by cyclic permutation gives the familiar

(5): (EA/EC)(DC/DB)(FB/FA) = 1,
which is the condition for Ceva and Menelaus.

Conversely, in the three cyclic equations like (4), we can choose vd arbitrarily, then choose ve to satisfy the first of the equations, then choose vf compatible with ve in the second equation. In the third equation, we have no more choices, but (5) ensures that the third equation is equivalent the product of the first two, so it is automatically satisfied. Similarly, (4) and its permutations make it possible to choose vd', ve', and vf' to satisfy (1)-(3) and their permutations. (Note: because they drop out of (4), vd', ve' and vf' can be chosen independently when focusing on each pair of travelers. The vd' used with d and e need not equal the vd' used with d and f.) The timings then imply that each traveler meets each of the others.

Therefore the condition that travelers d, e, and f all meet pairwise is equivalent to the hypothesis of Ceva and Menelaus. Now by the lemma I used in proving the 4 travelers problem, the travelers d, e, and f are all collinear (Menelaus) or their paths are coincident (Ceva).

This is quite an interesting (to me, at least) connection, because in the original 4 travelers problem as posed, the parallelism of the travelers or the concurrency of their paths is in neither the statement nor the conclusion, but occur in the body of the proof. Further, the original form of the 4 travelers problem excluded the Ceva-like case by requiring the lines to be in general position. It is only when you look at both the case of general position lines and the general position travelers that the connection to Ceva and Menelaus appears.

Note that I don't think this is the "best" way to prove Ceva and Menelaus, because other ways are simpler, but it makes a connection I haven't seen anywhere. It also has the failing that it doesn't tell you when you get the Ceva conclusion and when you get the Menelaus conclusion. I am sure that if you accout for the directions the travelers are going along their paths (signed distances, basically), then you can get the conclusions nicely separated, but I haven't done the work for that.

Also, since there is a three dimensional proof for the 4 travelers problem, it'should be possible to turn it into a 3-d proof of Ceva and Menalaus. Basically, let A', A", B', B", C', and C" be points vertically displaced from A, B, and C. Lift the lines AD, BE, CF up to A'D, B'E, C'F. Then the travelers meeting condition becomes the condition that these three lifted lines all meet pairwise. If A'D and B'E meet, then they are coplaner, so the lines A'E and B'D are also coplanar, hence they meet. A'E is confined to a vertical plane through AC and B'D is confined to a vertical plane through BC, hence they meet at a point directly above or below C. This is C". From here on, the argument is the same as above, with the vertical heights of A', A", B', B", C', and C" replacing the travel times. It may be easier to separate the Ceva and Menelaus conclusions here, by looking at which of A', B', and C' are above the ABC plane. I'll have to think about that and see how it works.

--Stuart Anderson

Many thanks,
Alex

https://www.cut-the-knot.org/4travelers/CevaAndMenelaus.shtml

>and when you get the Menelaus conclusion. I am sure that if
>you accout for the directions the travelers are going along
>their paths (signed distances, basically), then you can get
>the conclusions nicely separated, but I haven't done the
>work for that.

In fact (5) comes out squared, with Ceva corresponding to +sqrt(1), Menelaus to -sqrt(1).

Very nice. Thank you again.
Alex

Thanks! It makes me very happy that you liked my idea. I see you even found and corrected some typos of mine.

>In fact (5) comes out squared, with Ceva corresponding to
>+sqrt(1), Menelaus to -sqrt(1).

I posted (5) in the heat of discovery (I was actually working out the details as I wrote the post), and it escaped my attention that (5) came out squared. As you observed, this makes it very easy to separate the Ceva and Menelaus conclusions, which I hadn't gotten around to doing myself yet. Thanks for finishing off the details.
>
>Very nice. Thank you again.
>Alex

My pleasure.

--Stuart Anderson

>What if ABC is degenerate while ABD is not? Seems to me that
>then you can't derive |A'C'|/|AC| = s, so that the following
>breaks down.
>
>>Therefore, ACD
>>satisfies the requirements of Fact 1, and we can say that
>>|C'D'|/|CD| = s and C'D'||CD, and we can therefore conclude
>>that C meets D and add the edge CD to the graph.

This is correct of course. The theorem is actually not true in this case, because the existence of a nondegenerate triangle ABC forces the paths of A, B, and C to be coincident, violating the assumption that the paths are in general position. When I wrote the first post in this thread, I was not clear in my own mind that I had tacitly assumed that the travelers were in general position (hence no triangles were degenerate). In light of my second post, my first post should be regarded as explicitly making this assumption. Therefore, it only covers the case of travelers in general position and coincident paths.

As I mentioned at the end of my second post, it appears that the conclusion of the theorem is true only if you make the assumption uniformly for all travelers, that either all paths are in general position, or all travelers are in general position. You can't "mix and match" by assuming, e.g. that the positions of A, B, and C are in general position, while the paths of D, E and F are in general position. This kind of assumption gives a graph part of which is a nondegenerate-triangle-connected component, and part of which is a degenerate-triangle-connected component. As you observed, neither component can be extended to cover the whole graph, so you do not get the conclusion of the theorem.

By the way, when I see the phrase "general position" I usually interpret it to mean "don't assume anything special happens," a sort of placeholder to indicate that the theorem does not depend on any special assumptions. But it'seems from the context here that it means something stricter: "do assume nothing special happens," so that it is explicitly forbidden for any two lines to be parallel, any three lines to be coincident, or any three points to be collinear.

Have I been misinterpreting this phrase all these years? Embarrassing if so. Live and learn.

Then the proof must probably be by contradiction: if the points are not collinear, then the roads are concurrent by your argument, which would contradict the assumption of the roads being in "general poisition." The problem is there are 4 points, so that a mixup is possible.

>Have I been misinterpreting this phrase all these years?
>Embarrassing if so. Live and learn.

I think in terms of probabilties: there are special configurations whose probability is zero. E.g., random points are collinear with probability zero, same for the concurrency of random lines. When these are excluded the objects are said to be in general position. I believe this is common terminology. See

https://mathworld.wolfram.com/GeneralPosition.html

In general, yes, but I think the statement of the problem takes care of this. If all the lines are in general position, then all of the triangles are degenerate. After all this discussion and revision, I think it would be good at this point to state separately the main lemma that I originally didn't notice was needed:

If three travelers moving at constant velocity all meet each other, then they are collinear or their paths are concurrent. Fact 2 says that nondegenerate triangles will remain self-similar as the travelers move. Therefore, travelers in general position --> nondegenerate --> self-similar --> all sides vanish if any side vanishes --> lines are concurrent. Conversely, lines not concurrent --> sides do not vanish simultaneously --> not self-similar --> degenerate --> travelers are collinear.

Therefore, if all lines are in general position, all triangles are degenerate, and if all travelers are in general position, then all triangles are nondegenerate. So this mixed case cannot arise under the conditions of the problem.
>
>>Have I been misinterpreting this phrase all these years?
>>Embarrassing if so. Live and learn.
>
>I think in terms of probabilties: there are special
>configurations whose probability is zero. E.g., random
>points are collinear with probability zero, same for the
>concurrency of random lines. When these are excluded the
>objects are said to be in general position. I believe this
>is common terminology. See
>
>https://mathworld.wolfram.com/GeneralPosition.html

On the subject of probabilities, I tend to think in the same way as you do, that the special cases excluded by "general position" have probability zero. However, I notice something interesting about the present problem: If we don't assume the travelers meet, then the lines and the travelers will both be in general position with probability 1. However, conditional on the assumption that the travelers all meet, the probabilities of coincident lines or collinear travelers are now no longer independent. If we say that the lines are coincident with probability 0, then the lemma shows that the travelers are collinear with probability 1, and similarly, if the travelers are collinear with probability 0, then the lines are coincident with probability 1.

I suppose that this is really a pretty trivial observation, in that all theorems of geometry can be thought of as showing that something has a conditional probability of 1 but an unconditional probability of 0. (Of course, theroems are actually stronger than this, and have NO exceptions, rather than exceptions with probability 0.) What is interesting to me in this case is the symmetry between the assumption of general line position and general traveler position, both of which let you prove the same consequence.

Right. Sorry for staying a step behind.