Fog Creek Software
Discussion Board




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 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 Software
Saturday, 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

*  Recent Topics

*  Fog Creek Home