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 Software Saturday, 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 nonparallel.
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 Software Saturday, February 12, 2005
Yes.
Dmitri Papichev
Saturday, February 12, 2005
So we're supposed to prove that two nonparallel 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 nonparallel.
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 nonparallel."
The zaxis 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 "warmup" 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
Recent Topics
Fog Creek Home
