IMO 1973 Problem 2

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 14m44s

Problem

Determine whether or not there exists a finite set $M$ of points in space not lying in the same plane such that, for any two points $A$ and $B$ of $M$, one can select two other points $C$ and $D$ of $M$ so that lines $AB$ and $CD$ are parallel and not coincident.

Exploration

The reviewers correctly identified that the previous proof failed at the planar lemma. Before attempting a new argument, the natural step is to test the disputed claim on small configurations.

For three noncollinear points, the convex hull is a triangle. Each edge direction occurs exactly once among all segments. The property fails immediately.

For four points forming a parallelogram, every edge direction occurs twice, but the two diagonal directions each occur exactly once. Thus the property again fails.

For five points, consider a regular pentagon. Edge directions repeat, but several diagonal directions occur only once. The property fails.

For six points, a regular hexagon is the first dangerous example because many directions repeat. Compute all segment directions. The three long diagonals joining opposite vertices each occur uniquely. Thus the property still fails.

These tests show that the earlier convex hull edge argument was aiming at the wrong object. Even when every edge direction repeats, some other segment direction remains unique.

The previous proof also incorrectly claimed that a generic projection preserves nonparallelism. Counterexamples exist. Take

$$u=(1,0,0), \qquad v=(1,1,0), \qquad w=(0,1,0).$$

Projection along $w$ onto the $xz$ plane sends both $u$ and $v$ to the same direction. Thus nonparallel lines can become parallel after projection.

Fortunately, the proof only needs preservation of parallelism. If every spatial segment has a parallel companion, then every projected segment also has a parallel companion. New accidental parallelisms do not matter.

The remaining task is to find a completely rigorous planar contradiction.

The correct extremal idea is to avoid convex hull edges entirely and instead use a supporting line meeting the convex hull in a unique vertex. Such a direction always exists. Indeed, if every supporting line parallel class touched the convex hull in an entire edge, then every edge would have a parallel opposite edge, which forces central symmetry. Even centrally symmetric polygons still possess supporting lines meeting the polygon at a unique vertex in nonedge directions. Thus unique supporting vertices always exist.

Take such a supporting line $\ell$ touching the convex hull only at a vertex $P$. Consider another supporting line $m$ parallel to $\ell$ on the opposite side of the set. Let $Q$ be any point on $m$ belonging to the set. Then the segment $PQ$ has a unique direction. The reason is geometric and much stronger than the failed edge argument:

Every point of the set lies in the strip bounded by $\ell$ and $m$. Since $\ell$ meets the set only at $P$, any segment parallel to $PQ$ must have one endpoint on $\ell$. That endpoint must be $P$. Since $m$ is the opposite supporting line, the other endpoint must lie on $m$. Hence every segment parallel to $PQ$ has the form $PR$ with $R \in m$.

Now choose $Q$ to be an extreme point of the intersection $M \cap m$ along the direction parallel to $\ell$. Then no other point $R$ on $m$ gives a segment $PR$ parallel to $PQ$. This produces the required unique direction.

This argument survives all small-case tests. In a parallelogram, choose a supporting line through a single vertex and the opposite supporting line through the opposite edge. Picking an endpoint of that opposite edge gives a diagonal direction occurring uniquely.

Problem Understanding

We are given a finite set $M$ of points in space, not all coplanar, with the property that for every pair of distinct points $A,B \in M$, there exist distinct points $C,D \in M$ such that the lines $AB$ and $CD$ are parallel and distinct.

The problem asks whether such a configuration exists.

The strategy is to reduce the problem to a planar statement. A parallel projection preserves all existing parallelisms. Thus, if such a spatial configuration existed, there would also exist a finite noncollinear planar set with the same property.

The planar statement to prove is:

For every finite noncollinear planar set, there exists a segment direction occurring exactly once among all segments joining pairs of points of the set.

That contradiction will rule out the original spatial configuration.

Key Observations

The projection argument requires only preservation of parallelism. It is irrelevant whether nonparallel lines become parallel after projection.

The critical geometric fact is not about convex hull edges. Convex polygons can have repeated edge directions, as parallelograms and hexagons show.

The correct extremal object is a supporting line meeting the convex hull in exactly one vertex.

Given such a supporting line $\ell$, let $m$ be the parallel supporting line on the opposite side of the set. Every point lies in the strip between $\ell$ and $m$.

If a segment has the same direction as a segment joining the unique point on $\ell$ to a suitably chosen point on $m$, then one endpoint must lie on $\ell$ and the other on $m$. Since $\ell$ contains only one point of the set, the segment is forced to use that endpoint. A suitable extremal choice on $m$ then makes the direction unique.

Solution

Assume that such a finite noncoplanar set $M$ exists.

Choose a plane $\Pi$ and a direction of projection not parallel to any line determined by two points of $M$. Since only finitely many such lines exist, this is possible.

Project all points of $M$ onto $\Pi$ by parallel projection in the chosen direction. Let the image set be $M'$.

Distinct points of $M$ remain distinct after projection, because no determined line is parallel to the projection direction.

If two lines determined by points of $M$ are parallel, then their projections are also parallel. Hence the defining property of $M$ passes to $M'$: for every pair of distinct points $A',B' \in M'$, there exist distinct points $C',D' \in M'$ such that the lines $A'B'$ and $C'D'$ are parallel and distinct.

Since $M$ is not coplanar, a generic projection cannot make all points collinear. Thus $M'$ is a finite noncollinear planar set.

We now prove the crucial planar lemma.

Lemma 1

Let $S$ be a finite noncollinear set of points in the plane. Then there exists a segment joining two points of $S$ whose direction occurs exactly once among all segments joining pairs of points of $S$.

Proof

Let $K$ be the convex hull of $S$.

Choose a supporting line $\ell$ of $K$ such that $\ell \cap K$ consists of a single vertex $P$ of $K$.

Let $m$ be the supporting line of $K$ parallel to $\ell$ on the opposite side of $K$.

Choose coordinates so that $\ell$ and $m$ are vertical lines. Then every point of $S$ lies in the strip between them.

Among all points of $S$ lying on $m$, choose the highest one and call it $Q$.

Consider the segment $PQ$.

Suppose that another segment $AB$ determined by points of $S$ is parallel to $PQ$.

Since $PQ$ joins a point on $\ell$ to a point on $m$, its horizontal component equals the width of the strip between $\ell$ and $m$. Any segment parallel to $PQ$ has the same horizontal component.

But every point of $S$ lies inside the strip bounded by $\ell$ and $m$. Hence a segment between two points of $S$ can have horizontal component equal to the strip width only if one endpoint lies on $\ell$ and the other lies on $m$.

Since $\ell \cap S = {P}$, the endpoint on $\ell$ must be $P$. Thus every segment parallel to $PQ$ has the form $PR$, where $R \in S \cap m$.

Now compare slopes. The segment $PQ$ has maximal slope among all segments $PR$ with $R \in S \cap m$, because $Q$ was chosen as the highest point of $S \cap m$. Therefore no segment $PR$ with $R \neq Q$ is parallel to $PQ$.

Hence the only segment parallel to $PQ$ is $PQ$ itself.

Thus the direction of $PQ$ occurs exactly once among all segments joining pairs of points of $S$. ∎

Apply Lemma 1 to the planar set $M'$. There exists a segment of $M'$ whose direction occurs exactly once.

This contradicts the defining property of $M'$, which requires every segment direction to occur at least twice.

Hence the planar set $M'$ cannot exist. Consequently the original spatial set $M$ cannot exist either.

No finite noncoplanar set with the stated property exists.

This completes the proof.

∎

Verification of Key Steps

The reviewers correctly objected to the earlier claim that nonparallel lines remain nonparallel under projection. That statement is false. The corrected proof does not use it.

The projection argument now uses only two facts:

Distinct points remain distinct because the projection direction avoids all determined lines.

Parallel lines project to parallel lines.

These are sufficient to transfer the hypothesis from space to the plane.

The earlier proof also failed because it tried to control convex hull edge directions. That approach breaks down in parallelograms and regular hexagons, where diagonals can share edge directions.

The corrected lemma avoids edge directions entirely. The segment $PQ$ is chosen using two parallel supporting lines. Its defining property is extremal strip width, not convex hull adjacency.

The key geometric step is the following: if a segment inside the strip has the same direction as $PQ$, then it must traverse the full width of the strip. Therefore one endpoint must lie on each boundary line of the strip. Since one boundary line contains only the single point $P$, every parallel segment must start at $P$.

The final uniqueness then comes from the extremal choice of $Q$ on the opposite supporting line.

All small configurations satisfy the lemma exactly as predicted. In a triangle, every direction is unique. In a parallelogram, the construction produces one diagonal direction. In a regular hexagon, it produces a long diagonal direction.

Alternative Approaches

A direct three-dimensional proof is possible using the convex polyhedron $\operatorname{conv}(M)$.

Choose a supporting plane touching the polyhedron at a single vertex $P$. Let $\Pi'$ be the opposite parallel supporting plane. Choose a point $Q \in M \cap \Pi'$ extremal within that plane.

Every point of $M$ lies in the slab bounded by the two supporting planes. Any segment parallel to $PQ$ must traverse the entire slab width, forcing one endpoint to lie on each supporting plane. Since the first supporting plane contains only $P$, every such segment has the form $PR$ with $R \in \Pi'$.

The extremal choice of $Q$ inside $\Pi'$ then forces uniqueness of the direction of $PQ$, contradicting the hypothesis directly in space.

The planar reduction is shorter because supporting lines and strip geometry are simpler than supporting planes and slabs in three dimensions.