Kvant Math Problem 301

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m43s
Source on kvant.digital

Problem

On the plane, $2n$ points are given—$n$ blue and $n$ red, with no three points lying on the same line. Prove that it is possible to draw $n$ line segments so that each segment has one endpoint at a red point and the other at a blue point, and no two segments have any point in common.

Fig. 1

S. Okhitin, 10th-grade student (Orenburg)

Exploration

For $n=1$ the statement is immediate. For $n=2$, if one red point and one blue point lie on one side of the line through the other two points, joining each red point to a blue point on the same side gives two disjoint segments. In any configuration a suitable pairing exists.

The natural idea is induction on $n$. To carry out an inductive step, one needs a way to split the set of points into two smaller independent problems. Since the colors occur equally often, a line passing through one red and one blue point is promising. If such a line leaves the same number of red and blue points on each side, then the segment joining those two points does not meet any segment drawn entirely on one side, and induction can be applied separately to the two sides.

The crucial question is whether there always exists a red-blue pair whose connecting line has equal numbers of red and blue points on each side.

Take a red point $R$ and rotate a line through $R$. Let $b(\ell)$ and $r(\ell)$ denote the numbers of blue and red points on one chosen side of the line. The quantity $b(\ell)-r(\ell)$ changes by $\pm1$ whenever the line passes through another point. After a rotation by $180^\circ$, the chosen side is replaced by the opposite side, so the value changes sign. Since it varies by unit steps, it must pass through $0$. At that position the line goes through some second point, and because the difference changes by $\pm1$, that second point must be blue. This yields the desired balancing line.

The single step most likely to hide an error is the proof that the balancing line necessarily passes through a blue point and gives equal numbers of red and blue points on both sides.

Problem Understanding

We are given $n$ red points and $n$ blue points in the plane, with no three points collinear. We must show that the points can be paired so that every pair consists of one red and one blue point, and the straight-line segments joining the paired points are pairwise disjoint.

This is a Type B problem. The task is to prove the existence of such a nonintersecting matching.

The core difficulty is finding a pairing that avoids intersections globally. A direct construction is hard because a choice of one segment can obstruct many others. The key is to find a red-blue segment that separates the remaining points into two smaller balanced sets, allowing induction.

Proof Architecture

Lemma 1. There exists a line through a red point and a blue point such that each open half-plane determined by the line contains equally many red and blue points.

Sketch. Fix a red point and rotate a line through it; track the difference between the numbers of blue and red points on one side. The value changes by $\pm1$ at each event and changes sign after a half-turn, forcing a zero.

Lemma 2. If a line through a red point $R$ and a blue point $B$ has equally many red and blue points in each open half-plane, then after joining $R$ to $B$, the points in each half-plane can be matched independently.

Sketch. Each half-plane contains the same number of red and blue points, so induction applies there.

Lemma 3. Segments drawn entirely in one open half-plane do not meet segments drawn entirely in the other open half-plane, and neither can meet the segment $RB$.

Sketch. The line containing $RB$ separates the two half-planes; any segment with endpoints in one half-plane remains entirely in that half-plane.

The hardest part is Lemma 1. Any mistake there would invalidate the induction.

Solution

We proceed by induction on $n$.

For $n=1$, there is one red point and one blue point. Joining them gives the required segment.

Assume the statement has been proved for every smaller positive integer, and consider a configuration consisting of $n\ge2$ red points and $n$ blue points.

We first prove the existence of a balancing line.

Choose a red point $R$. Let $\ell$ be a directed line through $R$. Denote by $D(\ell)$ the difference

$$D(\ell)=b(\ell)-r(\ell),$$

where $b(\ell)$ and $r(\ell)$ are respectively the numbers of blue and red points, excluding $R$, lying in the open left half-plane determined by $\ell$.

Because no three points are collinear, as $\ell$ rotates about $R$, the only moments at which $D(\ell)$ changes are those when $\ell$ passes through another point of the configuration. If the point crossed is blue, that point enters or leaves the left half-plane, and $D(\ell)$ changes by $\pm1$. If the point crossed is red, $D(\ell)$ also changes by $\pm1$.

Choose a position of $\ell$ that does not pass through any point other than $R$. Let its value be $D_0$.

After rotating $\ell$ by $180^\circ$, the left half-plane becomes the opposite half-plane. Among the remaining $2n-1$ points there are $n$ blue points and $n-1$ red points. Hence

$$D(\ell+\pi) =(n-r(\ell))-(n-1-r(\ell)) =-D(\ell).$$

Thus the value changes from $D_0$ to $-D_0$ during the half-turn.

Since $D(\ell)$ changes only by increments of $\pm1$, some transition must occur between a negative value and a nonnegative value, or between a positive value and a nonpositive value. Consequently there is a position at which the line passes through a second point $P$ and the values immediately before and after the passage are $-1$ and $0$, or $0$ and $1$, or $1$ and $0$, or $0$ and $-1$.

If $P$ were red, crossing it would change $D(\ell)$ by $-1$ or $+1$ in the opposite direction from crossing a blue point. In that case the value $0$ would already occur for a position of the line containing only $R$, contradicting the choice of the transition where the sign changes. Therefore the point $P$ is blue.

Let $B=P$. At the moment when the line passes through $R$ and $B$, the numbers of blue and red points on one side are equal. Since the total numbers of red and blue points outside ${R,B}$ are also equal, the numbers on the other side are equal as well.

Thus the line $RB$ has the property that each open half-plane contains equally many red and blue points.

Now draw the segment $RB$. Let the two open half-planes determined by the line $RB$ contain $k$ red and $k$ blue points on one side, and $n-1-k$ red and $n-1-k$ blue points on the other side.

If $k=0$, the first side contains no points. If $k>0$, by the inductive hypothesis the points in that half-plane can be joined by pairwise disjoint red-blue segments. Likewise, by the inductive hypothesis the points in the other half-plane can be joined by pairwise disjoint red-blue segments.

It remains to check that all obtained segments are mutually disjoint.

Any segment whose endpoints lie in one open half-plane is contained entirely in that half-plane, because an open half-plane is convex. Hence segments drawn in opposite half-planes cannot intersect.

The segment $RB$ lies on the separating line. Every other segment lies entirely within one of the open half-planes and therefore has no point in common with $RB$.

Thus all constructed segments are pairwise disjoint.

The segment $RB$ together with the inductively constructed matchings in the two half-planes yields a nonintersecting matching of all $2n$ points.

By induction, the statement holds for every $n$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the relation

$$D(\ell+\pi)=-D(\ell).$$

For a position of $\ell$ avoiding all other points, let the left half-plane contain $b$ blue points and $r$ red points. The opposite half-plane then contains $n-b$ blue points and $(n-1)-r$ red points. After a half-turn, the new left half-plane is exactly that opposite half-plane, so

$$D(\ell+\pi) =(n-b)-((n-1)-r) =-(b-r) =-D(\ell).$$

The second delicate step is showing that the balancing line passes through a blue point. At a crossing, the value of $D$ changes by exactly $1$ in magnitude. Since the values before and after the critical crossing have opposite signs or one of them is zero, the crossing is responsible for moving the difference through $0$. If the crossed point were red, the same transition would occur in the reverse direction, and a nearby position avoiding all points would already realize $D=0$. The critical passage is therefore through a blue point, producing a line containing a red point and a blue point.

The third delicate step is proving disjointness. A segment joining two points in the same open half-plane cannot leave that half-plane because open half-planes are convex. Hence every inductively produced segment remains strictly on one side of the line $RB$. Two segments belonging to different sides are separated by the line and cannot meet. Since $RB$ itself lies on the line, it cannot meet any segment lying entirely in an open half-plane.

Alternative Approaches

A different proof uses the Ham Sandwich Theorem. A line can be chosen that simultaneously bisects the red points and the blue points. Repeatedly applying such bisections produces a recursive decomposition of the point set into balanced subsets. One then joins appropriately chosen red-blue pairs across the decomposition tree and verifies that the resulting matching is noncrossing.

The inductive balancing-line argument is preferable here because it is completely elementary. It uses only counting and the continuous rotation of a line through a fixed point, avoiding any external geometric theorem while directly yielding the segment that initiates the induction.