Kvant Math Problem 336

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m39s
Source on kvant.digital

Problem

A finite set of polygons is given in the plane, and every two of them have a point in common. Prove that there exists a line that has a point in common with each of these polygons.

S. V. Fomin

All-Union Mathematical Olympiad for School Students (1974, Grade 10)

Exploration

For two polygons the statement is immediate. If two polygons intersect, any line through a common point meets both.

For three polygons, suppose $P_1,P_2,P_3$ are pairwise intersecting. Choose points

$$A_{12}\in P_1\cap P_2,\quad A_{13}\in P_1\cap P_3,\quad A_{23}\in P_2\cap P_3.$$

If these three points are not collinear, they determine a triangle. Since polygons are convex, each polygon contains the side joining the two intersection points that belong to it. Thus $P_1$ contains $A_{12}A_{13}$, $P_2$ contains $A_{12}A_{23}$, and $P_3$ contains $A_{13}A_{23}$. Hence every polygon meets every line intersecting the triangle. In particular, any line through an interior point of the triangle meets all three polygons.

This suggests replacing each polygon by a convex set. A polygon is convex in the usual olympiad terminology, and the argument above uses convexity essentially.

The statement resembles Helly's theorem. A line in the plane corresponds to a point in the dual plane. For a convex polygon $P$, the set of all lines meeting $P$ is a convex set in the space of lines. If every two polygons intersect, then any two such sets of transversals have a common point, because a line through a point of intersection meets both polygons. If one can show that every three transversal sets have a common point, Helly's theorem in dimension $2$ would imply that all transversal sets have a common point, which is exactly the required line.

The delicate point is proving the claim for three polygons. The triangle argument above appears to do precisely that.

Problem Understanding

We are given finitely many polygons in the plane. Every two polygons have at least one common point. We must prove that there exists a single line intersecting every polygon.

This is a Type B problem. We must prove the stated existence claim.

The core difficulty is that pairwise intersection of the polygons does not imply that all polygons share a common point. One must convert the problem into a statement about lines intersecting polygons and then exploit convexity together with a Helly-type argument.

Proof Architecture

Let $\mathcal L(P)$ denote the set of all lines meeting a polygon $P$.

First lemma: for every convex polygon $P$, the set $\mathcal L(P)$ is convex in the parameter space of lines. This follows by representing a line by its normal direction and signed distance from the origin; for each direction, the admissible distances form an interval.

Second lemma: for any three polygons $P_1,P_2,P_3$ satisfying the pairwise intersection condition, there exists a line meeting all three. Choose pairwise intersection points and consider the triangle they determine; if the points are collinear, that common line already works.

Third lemma: the sets $\mathcal L(P_i)$ satisfy the hypothesis of Helly's theorem in the plane. By the second lemma, every three of them have nonempty intersection.

Applying Helly's theorem yields a common point of all sets $\mathcal L(P_i)$, which corresponds to a line meeting every polygon.

The most delicate part is the second lemma, especially the case when the three chosen intersection points are not collinear.

Solution

Represent every nonoriented line by an equation

$$x\cos\theta+y\sin\theta=p,$$

where $0\le \theta<\pi$ and $p\in\mathbb R$. Thus the set of all lines is identified with the $(\theta,p)$-plane.

For a polygon $P$, let $\mathcal L(P)$ be the set of points $(\theta,p)$ corresponding to lines that meet $P$.

We first show that $\mathcal L(P)$ is a convex subset of the $(\theta,p)$-plane. For a fixed value of $\theta$, define

$$m(\theta)=\min_{X\in P}(x\cos\theta+y\sin\theta), \qquad M(\theta)=\max_{X\in P}(x\cos\theta+y\sin\theta).$$

A line with parameters $(\theta,p)$ meets $P$ exactly when

$$m(\theta)\le p\le M(\theta).$$

Since $P$ is convex, $m$ is a concave function of $\theta$ and $M$ is a convex function of $\theta$. Consequently,

$$\mathcal L(P)={(\theta,p):m(\theta)\le p\le M(\theta)}$$

is convex.

Now consider any three polygons $P_1,P_2,P_3$ from the given family. Choose points

$$A_{12}\in P_1\cap P_2,\qquad A_{13}\in P_1\cap P_3,\qquad A_{23}\in P_2\cap P_3.$$

If $A_{12},A_{13},A_{23}$ are collinear, the line containing them meets all three polygons, because each polygon contains the two points assigned to it.

Assume that $A_{12},A_{13},A_{23}$ are not collinear. They form a triangle $T$.

Since $P_1$ is convex and contains $A_{12}$ and $A_{13}$, it contains the whole segment $A_{12}A_{13}$, which is a side of $T$. Similarly, $P_2$ contains the side $A_{12}A_{23}$ and $P_3$ contains the side $A_{13}A_{23}$.

Take any point $O$ in the interior of $T$. Every line through $O$ intersects the boundary of $T$ in two points belonging to different sides of the triangle. Hence such a line meets each of the three sides of $T$. Since each side lies in the corresponding polygon, every line through $O$ meets $P_1$, $P_2$, and $P_3$.

Thus there exists a line meeting all three polygons. Equivalently,

$$\mathcal L(P_1)\cap\mathcal L(P_2)\cap\mathcal L(P_3)\ne\varnothing .$$

We have proved that among the convex sets

$$\mathcal L(P_1),\mathcal L(P_2),\ldots,\mathcal L(P_n)$$

in the $(\theta,p)$-plane, every three have a common point.

By Helly's theorem in dimension $2$, the intersection of all these sets is nonempty:

$$\bigcap_{i=1}^n \mathcal L(P_i)\ne\varnothing .$$

A point of this intersection corresponds to a line meeting every polygon $P_i$. Hence there exists a line having a point in common with each polygon.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the convexity of $\mathcal L(P)$. For fixed $\theta$, the condition that a line meet $P$ is exactly that its signed distance $p$ lie between the minimum and maximum values of the linear functional $x\cos\theta+y\sin\theta$ on $P$. Since minima and maxima of linear functionals over a convex polygon vary respectively as concave and convex functions, the region between their graphs is convex. A careless argument that only checks convexity for a fixed direction $\theta$ would not establish convexity in the full two-dimensional parameter space.

The second delicate step is the claim that a line through an interior point of the triangle meets all three sides. Let the line intersect the boundary of the triangle at points $B$ and $C$. The segment $BC$ contains the interior point, so $B$ and $C$ lie on different sides of the triangle. Traversing $BC$ from $B$ to $C$, one must cross the third side as well, because the boundary of a triangle consists of exactly three sides. Hence the line intersects each side. If one merely says that the line enters and leaves the triangle, one obtains intersection with only two sides, which is insufficient.

The third delicate step is the use of Helly's theorem. The theorem applies to convex subsets of the plane. The parameter space of lines is two-dimensional, and the sets $\mathcal L(P_i)$ have already been shown convex. The previous lemma establishes the required condition that every three of them intersect. These are exactly the hypotheses of Helly's theorem.

Alternative Approaches

A proof can also be written entirely in projective duality. A point in the dual plane represents a line of the original plane. The set of dual points corresponding to lines meeting a convex polygon is a convex polygon in the dual plane. Pairwise intersections of the original polygons imply that every three dual polygons intersect, by the same triangle argument used above. Helly's theorem then yields a common dual point, corresponding to a transversal line.

The presented proof keeps the duality hidden inside the $(\theta,p)$ parametrization of lines. This makes the convexity of the transversal sets explicit and allows a direct application of Helly's theorem without introducing projective geometry.