Four Ships in the Ocean The four ships (A, B, C, and D) cruise through the ocean, each with their own constant speed and their own direction, in a straight line. Ships A, B, and C have all met in the ocean separately by pairs (for two ships to meet they should pass each other at virtually no distance, so, in mathematical sense, they should be at the same place at the same). Ship D has met ships A and B. Prove that ship D has also met ship C before, or will meet ship C later. Dmitri Papichev Saturday, February 12, 2005 I guess we're supposed to assume that the ocean is an infinite plain, not an ocean like the one  on the earth which takes you in circles. Michael H. Pryor Fog Creek SoftwareSaturday, February 12, 2005 Yes, you are absolutely right on that. Dmitri Papichev Saturday, February 12, 2005 Errata: Should read: "in mathematical sense, they should be at the same place at the same time" P.S. It would be nice to be able to correct your own postings. Dmitri Papichev Saturday, February 12, 2005 I'd be interested to see the proof, since with the given facts C & D can be on parallel courses. Philo Philo [MSFT] Saturday, February 12, 2005 No, all four courses are non-parallel. Dmitri Papichev Saturday, February 12, 2005 Regarding what philo noted, I guess we're supposed to assume that "and their own direction" means each ship is not travelling on the same degree course as any other ship (or that no two ships have a parallel course) Michael H. Pryor Fog Creek SoftwareSaturday, February 12, 2005 Yes.  Dmitri Papichev Saturday, February 12, 2005 So we're supposed to prove that two non-parallel lines on an infinite plane will intersect? Lou Saturday, February 12, 2005 No. We know the ship courses intersect, that is given. We need to prove that the ships arrive to the point where their courses intersect at the same time. Dmitri Papichev Saturday, February 12, 2005 This is easy if you draw it out. The question could have been a lot more specific however. Given:   A has met B,C, and D   B has met A,C, and D   no courses can be parallel   we are on an "infinite, flat" plane. Have C and D met? Solution: Draw the path of A as the traditional X axis. Draw the path of B as the traditional Y axis. C must cross both A and B so draw it as a line starting at Y = -n  and crossing at X=n  (45degree line). (any line will do however) D must also cross both A and B, and cannot be parallel to A, B or C.  therefore, by examination you can see that any line you draw for C (with any slope) will cross D.             |            C             |        /             |      / ------------------------------  A             |    /             |  /             |/           /|             B BananaRunt Saturday, February 12, 2005 > D must also cross both A and B, and cannot be parallel to A, B or C.  therefore, by examination you can see that any line you draw for C (with any slope) will cross D. If the courses cross, that doesn't mean the ships met - their arrival at cross point could be separated by time. Dmitri Papichev Saturday, February 12, 2005 Given:   A has met B,C, and D   B has met A,C, and D   no 3 ships met together   no courses can be parallel   we are on an "infinite, flat" plane. Have C and D met? 3DTisZ Sunday, February 13, 2005 3DTisZ: Thanks, your version is clear :) We should not forget however that the other possibility is that C and D have not met yet, but will inevitably meet later. Dmitri Papichev Sunday, February 13, 2005 z |          / y   |      /   |    /   | /                  x   -------------------- Draw everything in a three dimensional space: x and y are spatial coordinates, while the z axis is time. A ships trajectory is a line in this space, and if two such lines meet, the ships have meet: same position at same time. > Ships A, B, and C have all met in the ocean separately by pairs. So the trajectories of A, B and C must be coplanar. > Ship D has met ships A and B. So D's trajectory is in the same plane as A, B and C's. > all four courses are non-parallel. It is therefore trivial that D's trajectory will cross C's. AlphaBeta Wednesday, February 16, 2005 Just having the trajectories cross is not enough to have them meet. They have to be at the crossing point at the same time. David Clayworth Wednesday, February 16, 2005 Just so we're clear here, is it a statement of the problem that none of the four courses are parallel? David Clayworth Wednesday, February 16, 2005 Alphabeta is correct. Brilliant solution. aaa Wednesday, February 16, 2005 The 6th post from the top states that "all four courses are non-parallel." The z-axis is time, the projection on the x y plane is location.  So when the  trajectories cross, the ships are at the same place at the same time. JHY Wednesday, February 16, 2005 Yes, AlphaBeta got it right. Congratulations :) Isn't that an amazing problem? It was offered (first known to me) in the late 70s to the students of the Physical and Mathematical Boarding High School at Moscow State University in Russia (well, USSR then). That school was definitely unique educational institution. The schoolkids were taught basically all mathematical disciplines as at, say, an engineering school in a regular university, or the first year or two of MSU Department of Mathematics curriculum. The problem was offered as a "warm-up" before staring a new topic - stereometry. When I want to give a good hint to those who are solving that problem, I usually mention that fact. Dmitri Papichev Saturday, February 19, 2005 That's pretty clever. David Clayworth Tuesday, February 22, 2005 > Ships A, B, and C have all met in the ocean separately by pairs - So the trajectories of A, B and C must be coplanar Brilliant solution, I must be growing rusty because that step eluded me even after it was explicitly mentioned. For those who are as slow as I am: all 3 trajectories lie on the plane defined by the 3 intersection points because each trajectory intersects the plane twice. WanFactory Monday, March 28, 2005   Fog Creek Home