IMO 1996 SL C4

Origin: FIN | Category: Combinatorics

Problem

Determine whether or not there exist two disjoint infinite sets $A$ and $B$ of points in the plane satisfying the following conditions:

No three points in $A \cup B$ are collinear, and the distance between any two points in $A \cup B$ is at least $1$.
There is a point of $A$ in any triangle whose vertices are in $B$, and there is a point of $B$ in any triangle whose vertices are in $A$.

Solution

Suppose that such sets of points $A$ and $B$ exist. First, we observe that there exist five points $A, B, C, D, E \in A$ such that their convex hull does not contain any other point of $A$. Indeed, take any point $A \in A$. Since any two points of $A$ are at distance at least $1$, the number of points $X \in A$ with $XA \leq r$ is finite for every $r>0$. Thus it is enough to choose four points $B, C, D, E \in A$ that are closest to $A$. Now consider the convex hull $C$ of $A, B, C, D, E$.

Suppose that $C$ is a pentagon, say $ABCDE$. Then each of the disjoint triangles $ABC$, $ACD$, $ADE$ contains a point of $B$. Denote these points by $P, Q, R$. Then $\triangle PQR$ contains some point $F \in A$, so $F$ is inside $ABCDE$, a contradiction.

Suppose that $C$ is a quadrilateral, say $ABCD$, with $E$ lying within $ABCD$. Then the triangles $ABE$, $BCE$, $CDE$, $DAE$ contain some points $P, Q, R, S \in B$ that form two disjoint triangles. It follows that there are two points of $A$ inside $ABCD$, which is a contradiction.

Finally, suppose that $C$ is a triangle with two points of $A$ inside. Then $C$ is the union of five disjoint triangles with vertices in $A$, so there are at least five points of $B$ inside $C$. These five points make at least three disjoint triangles containing three points of $A$. This is again a contradiction.

It follows that no such sets $A$ and $B$ exist.