CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site
|Store|

CTK Exchange

 Subject: "4 Travelers problem -- a new solution" Previous Topic | Next Topic
 Conferences The CTK Exchange This and that Topic #625 Printer-friendly copy     Email this topic to a friend Reading Topic #625
mr_homm
Member since May-22-05
Jul-17-05, 02:03 PM (EST)

"4 Travelers problem -- a new solution"

Subject     Author     Message Date     ID
4 Travelers problem -- a new solution mr_homm Jul-17-05 TOP
RE: 4 Travelers problem -- a new solution mr_homm Jul-17-05 1
RE: 4 Travelers problem -- a new solution alexb Jul-19-05 6
RE: 4 Travelers problem -- a new solution mr_homm Jul-28-05 8
RE: 4 Travelers problem -- a new solution alexb Jul-28-05 9
RE: 4 Travelers problem -- a new solution alexb Aug-10-05 10
RE: 4 Travelers problem -- a new solution mr_homm Aug-10-05 11
RE: 4 Travelers problem -- a new solution alexb Jul-18-05 2
RE: 4 Travelers problem -- a new solution mr_homm Jul-19-05 3
RE: 4 Travelers problem -- a new solution alexb Jul-19-05 4
RE: 4 Travelers problem -- a new solution mr_homm Jul-19-05 5
RE: 4 Travelers problem -- a new solution alexb Jul-19-05 7

 Conferences | Forums | Topics | Previous Topic | Next Topic
mr_homm
Member since May-22-05
Jul-17-05, 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 nondegenerate-triangle-connected component all meet at once because their paths are all coincident, and the travelers in any degenerate-triangle-connected 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

alexb
Charter Member
1616 posts
Jul-19-05, 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.)

mr_homm
Member since May-22-05
Jul-28-05, 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 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

alexb
Charter Member
1616 posts
Jul-28-05, 11:40 AM (EST)

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

 This is truly amazing. I have to have a closer look at this. Probably sometime over the weekend. Many thanks,Alex

alexb
Charter Member
1616 posts
Aug-10-05, 04:46 PM (EST)

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

 I made a page from the above: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

mr_homm
Member since May-22-05
Aug-10-05, 11:05 PM (EST)

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

 >I made a page from the above: >>https://www.cut-the-knot.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

alexb
Charter Member
1616 posts
Jul-18-05, 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.

mr_homm
Member since May-22-05
Jul-19-05, 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 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.

alexb
Charter Member
1616 posts
Jul-19-05, 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. Seehttps://mathworld.wolfram.com/GeneralPosition.html

mr_homm
Member since May-22-05
Jul-19-05, 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 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.

alexb
Charter Member
1616 posts
Jul-19-05, 02:07 PM (EST)

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

 >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. Right. Sorry for staying a step behind.

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) Educational Press (Conference)   |--No Child Left Behind (Public)   |--Math Wars (Public)   |--Mathematics and general education (Public)

You may be curious to have a look at the old CTK Exchange archive.

Search:
Keywords: