



Store




CTK Exchange
mr_homm
Member since May2205

Jul1705, 02:03 PM (EST) 

"4 Travelers problem  a new solution"

Looking at this problem recently, I decided to try to get a purely geometric solution without going to higher dimensions. I started from the observation (which had already made by another reader) that if two travelers meet, then the line joining them must remain parallel to its original orientation as they move forward. This fact, and everything else in the following proof, hinges on two simple geometrical facts about similar triangles: 1: For any triangles ABC and A'B'C', if ABA'B' andAB/A'B' = s, and likewise BCB'C' and BC/B'B'=s, then the same is true of the third side, i.e., ACA'C' and AC/A'C'=s. 2: For any two triangles ABC and A'B'C', if ABA'B' and BCB'C' and ACA'C', then if AB/A'B' = s, BC/B'C' = AC/A'C' = s. Informally, these two facts just say that if you rescale a SideAngleSide portion of a triangle without turning it, then the whole triangle rescales without turning, and that if you keep the sides from rotating, rescaling one side forces the whole triangle to rescale together. These are really just very basic and wellknown facts about triangles, but I have phrased them the way I did to emphasize that you can think of them as transitivity properties. As the travelers move, the lines connecting them form triangles, and these triangles will move and their side lengths will change. These properties let you copy scaling and orientation information from known triangle sides onto unknown sides. Now to start the main proof, notice that if two travelers at A and B meet at point M where their paths cross, then at a later time they are at new positions A' and B' and have both covered the same fraction of their distances to M (because they travel at constant speed), so the conditions for Fact 1 are satisfied for triangles ABM and A'B'M. Therefore ABA'B'. Conversely, if ABA'B', then Fact 2 shows that A'B'/AB = A'M/AM, so A'M=0 implies A'B=0. Hence when A' arrives at M, so does B'. This will of course also be true for any other pair of travelers who will meet each other. To summarize, two travelers meet if and only if the line joining them remains parallel to its original position as they move. Next, make a diagram showing the initial positions of the travelers, A, B, C, and D, and connecting pairs of travelers who are known to meet with line segments. This diagram is simultaneously a geometric picture of the travelers, and a graph showing who will meet, since travelers will meet if and only if they are connected by an edge in this graph. In the problem as stated, A, B, and C all meet each other, and so do A, B, and D. Therefore the graph consists of two triangles ABC and ABD with common base AB. Suppose that as time passes, A'D'/AD = s. Then Fact 2 applied to ABD shows that A'B'/AB = s. Since AB is also on ABC, Fact 2 now shows that A'C'/AC = s as well. 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. That completes the proof for the original problem. However, there is more: This method solves the problem under much more general conditions. Suppose we have a diagram as above for any number of travelers. Then for travelers X and Y on the graph, X meets Y if there is a path of triangles, each triangle sharing an edge with the next, with X on the first triangle and Y on the last one. This works because if there is any such path, we can always shorten it as follows: Let the start of the path be the triangles ABC, BCD sharing BC. If Y=B or Y=C, then Y is actually present on the second triangle, and we can delete the first one, shortening the path. If Y=A, then the proof for the original problem shows that we can add an edge connecting Y to D. Y now connects to all three edges of BCD, so no matter which side BCD shares with the next triangle in the path, we can delete both ABC and BCD from the path and connect Y directly to the shared side of this next triangle. Again, this shortens the path. Therefore, if there is any path at all from X to Y, we can add edges to the graph until there is a path consisting of a single triangle. Hence X and Y are connected by an edge, so X meets Y. Notice that if X any Y are "triangleconnected" in this way, and Y and Z are triangleconnected, then by concatenating the paths, X and Z are triangleconnected. This means that "triangleconnected" is transitive, and it is of course symmetric (X connects to Y if and only if Y connects to X, just reverse the path). If we discard all travelers and edges that are not part of triangles (we cannot prove anything about those travelers anyway), then it is also reflexive (X connects to X, because, trivially, there is a triangle containing X and X). Therefore it breaks the graph into equivalence classes, i.e., triangleconnected components. Then the paragraph above proves that we are justified in adding edges until every triangleconnected component becomes a complete graph (every vertex connected to every other vertex). Therefore, in each triangleconnected component, every traveler meets every other traveler. For example, if A meets B and C, and B meets C and D, and C meets D and E, and D meets E and F, then A meets E, but not necessarily F. Or for another example, if A and B meet each other, and they also both meet every other traveler, then every traveler meets every other traveler. There is still one further surprise here. Since this method works by showing that each edge in a triangleconnected component scales by the same factor as every other edge in that component, it follows that when any edge shrinks to length zero, they all do AT THE SAME TIME. Hence the travelers not only all meet each other, they all meet at the same time. This is only possible if the paths of all the travelers all intersect at a single common point. Therefore, the paths are not in general position after all! Although there was no special assumption in the problem about how the paths met (that's what general position means, after all), this conclusion shows that as a matter of fact, the meetings of the travelers as described in the statement are only possible if all the paths are coincident. This is a very strong conclusion, perhaps too strong. Is there a flaw here somewhere? If so, I cannot find it. Anyway, I think this is a fun and interesting way to approach the problem. Stuart Anderson 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


mr_homm
Member since May2205

Jul1705, 07:19 PM (EST) 

1. "RE: 4 Travelers problem  a new solution"
In response to message #0

OOPS! Shortly after I posted, I found the problem. Fact 2 is only true if the triangle is nondegenerate. If the points are collinear, the conclusion that all 3 sides shrink in proportion is not valid. This doesn't invalidate the entire approach, but it does modify it. Now we know that 3 travelers all meet each other if and only if their paths are coincident OR their positions stay are collinear. All the reasoning I used above on the graph still works, provided we look only at paths that contain all nondegenerate triangles. Note that as part of that proof, new edges were constructed, so how do we know these also form nondegenerate triangles? We don't, but it doesn't matter. These new edges were construced using Fact 1 not Fact 2, so they still scale the same as the nondegenerate triangles from which they were constructed. In addition to this, the graph now has components connected by degenerate triangle paths, since this type of path also provides a transitive, symmetric, reflexive relation on the vertices. It is both impossible and unnecessary to enrich this component into a complete graph by adding edges. Impossible because Fact 1 depends on equal scales and we don't have this any more, and unnecessary because all the points in such a component stay on their common moving line, so each pair must meet. Once again, we must leave out vertices that are not part of any triangle. The conclusion is now as follows: The travelers in any nondegeneratetriangleconnected component all meet at once because their paths are all coincident, and the travelers in any degeneratetriangleconnected component all meet each other (perhaps at different times) because they all stay on a common moving line. If the whole graph is a connected component of either type of path, then all the travelers meet each other. The degenerate triangle path is the solution to the original problem, and the nondegenerate triangle path is the solution to the problem I accidentally solved in the post above, where the traveler's locations are assumed to be in general position rather than their paths. We also get the interesting result that under the assumption that every traveler meets every other, then the travelers remain always collinear, or their paths are all coincident. Stuart Anderson 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



alexb
Charter Member
1616 posts 
Jul1905, 02:05 PM (EST) 

6. "RE: 4 Travelers problem  a new solution"
In response to message #1

>Now we know that 3 travelers all meet each other if and only >if their paths are coincident OR their positions stay are >collinear. 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.) 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Jul2805, 11:35 AM (EST) 

8. "RE: 4 Travelers problem  a new solution"
In response to message #6

>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 Cevalike 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 3d 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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 






alexb
Charter Member
1616 posts 
Aug1005, 04:46 PM (EST) 

10. "RE: 4 Travelers problem  a new solution"
In response to message #8

I made a page from the above: http://www.cuttheknot.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


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Aug1005, 11:05 PM (EST) 

11. "RE: 4 Travelers problem  a new solution"
In response to message #10

>I made a page from the above: > >http://www.cuttheknot.org/4travelers/CevaAndMenelaus.shtml >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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



alexb
Charter Member
1616 posts 
Jul1805, 09:37 PM (EST) 

2. "RE: 4 Travelers problem  a new solution"
In response to message #0

>Next, make a diagram showing the initial positions of the >travelers, A, B, C, and D, and connecting pairs of travelers >who are known to meet with line segments. This diagram is >simultaneously a geometric picture of the travelers, and a >graph showing who will meet, since travelers will meet if >and only if they are connected by an edge in this graph. In >the problem as stated, A, B, and C all meet each other, and >so do A, B, and D. Therefore the graph consists of two >triangles ABC and ABD with common base AB. Suppose that as >time passes, A'D'/AD = s. Then Fact 2 applied to ABD >shows that A'B'/AB = s. Since AB is also on ABC, Fact 2 >now shows that A'C'/AC = s as well. 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.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



mr_homm
Member since May2205

Jul1905, 00:46 AM (EST) 

3. "RE: 4 Travelers problem  a new solution"
In response to message #2

You said: >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 nondegeneratetriangleconnected component, and part of which is a degeneratetriangleconnected 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. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




alexb
Charter Member
1616 posts 
Jul1905, 01:16 AM (EST) 

4. "RE: 4 Travelers problem  a new solution"
In response to message #3

>This is correct of course. 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 http://mathworld.wolfram.com/GeneralPosition.html 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Jul1905, 11:08 AM (EST) 

5. "RE: 4 Travelers problem  a new solution"
In response to message #4

>>This is correct of course. > >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. 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 selfsimilar as the travelers move. Therefore, travelers in general position > nondegenerate > selfsimilar > all sides vanish if any side vanishes > lines are concurrent. Conversely, lines not concurrent > sides do not vanish simultaneously > not selfsimilar > 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 > >http://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. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Store
Copyright © 19962017 Alexander Bogomolny

