Ponder This Challenge - August 2001 - Points on a plane

Ponder This Challenge:

Puzzle for August 2001

This puzzle was sent in by Joel Ouaknine.

Suppose S is a finite set of points in the plane, such
that for any two points x,y in S, there is a third point
z in S, collinear with x and y (and different from x and y).
Show that all points of S are collinear.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Suppose that not all points are collinear. Then find three

  non-collinear points (a,b,o) in S such that the distance between o and
  the line spanned by ab is minimal. (By minimal I mean that no other
  triple (a',b',o') in S can achieve a smaller, strictly positive,
  distance.) Note that minimality is actually achieved since S is
  finite.

  By our assumption on S, there is a third point in S that lies on the
  ab line, call it c. Project o onto the abc line, yielding point e.
  (So e lies on abc, and oe is perpendicular to abc.) Clearly at least
  two of {a,b,c} lie on the same side of e, so without loss of
  generality assume that the points come in the following order: a, b,
  e, c. If you draw this, you will immediately see that the triple
  (a,o,b) achieves a strictly smaller distance than (a,b,o),
  contradicting our earlier assumption.

  A large number of readers have suggested proofs by induction. Here's why these don't work.
  Let Q(S) be the statement: "For two points x,y in S there is a third point z in S collinear with x,y".
  Let P(k) be the statement, "For any set S with k points which satisfies Q(S), we know S must be collinear."
  An inductive proof would say "P(3) is trivially true; if P(k-1) is true then P(k) is true." But this sort of proof won't work here.
  Suppose we know P(k-1) and are trying to prove P(k).
  We have a set S with k points which satisfies Q(S), and want to show that S is collinear.
  How are we going to apply P(k-1)? What set S' of k-1 elements satisfies Q(S')?
  If we just let S' be S with one element thrown away, then we don't know that it satisfies Q(S'), because given two points x,y in S', the third point z in S which is guaranteed by Q(S) might not lie in S'.
  So we have no set S' upon which to apply the inductive hypothesis, and no way to do the induction.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Amites Sarkar (08.01.2001 @ 11:07 AM EDT)
• Henry Bottomley (08.01.2001 @ 12:56 PM EDT)
• Ionel Santa (08.02.2001 @ 4:41 AM EDT)
• Dharmashankar Subramanian (08.02.2001 @ 3:21 PM EDT)
• Saibal Mitra (08.02.2001 @ 6:35 PM EDT)
• Jayavel Sounderpandian (08.08.2001 @ 2:59 AM EDT)
• Alexis Megas (08.08.2001 @ 12:24 PM EDT)
• Reddy Nanchary (08.08.2001 @ 1:22 PM EDT)
• Ross Millikan (08.08.2001 @ 2:52 PM EDT)
• Samantha Levin (08.08.2001 @ 4:50 PM EDT)
• Mukul Kumar (08.10.2001 @ 2:57 PM EDT)
• L Shankar Ram (08.14.2001 @ 1:09 AM EDT)
• Liuwei (08.20.2001 @ 3:13 AM EDT)
• Victor Chang (08.20.2001 @ 1:15 PM EDT)
• Ming Song (08.22.2001 @ 1:14 PM EDT)
• George Ross (08.23.2001 @ 1:04 AM EDT)
• Guangwu Xu (08.23.2001 @ 2:49 PM EDT)
• Nancy Schwarzkopf (08.23.2001 @ 9:48 PM EDT)
• David Fraser (08.28.2001 @ 5:39 AM EDT)
• Dave Biggar (08.28.2001 @ 9:18 AM EDT)