Maths Olympiad Prep

Track / Stage 7 / 71 of 300 #1471 of 1964

Problem 1471

National olympiad second round; IMO P1/P4
Geometry Difficulty 7.1 Prove it

Finitely many convex subsets of R3\mathbb R^3 are given, such that every three have non-empty intersection. Prove that there exists a line in R3\mathbb R^3 that intersects all of these subsets.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Projection onto a Plane:
Consider any plane π\pi in R3\mathbb{R}^3. For each convex subset KR3K \subseteq \mathbb{R}^3, project KK onto the plane π\pi. Denote the projection of KK onto π\pi by P(K)P(K). Since KK is convex, P(K)P(K) is also a convex set in the plane π\pi.

2. Application of Helly's Theorem in the Plane:
By the problem's condition, every three of the original convex subsets in R3\mathbb{R}^3 have a non-empty intersection. This property is preserved under projection. Therefore, every three of the projected convex sets P(K)P(K) in the plane π\pi also have a non-empty intersection.

Helly's theorem states that for a finite collection of at least d+1d+1 convex sets in Rd\mathbb{R}^d, if the intersection of every d+1d+1 of these sets is non-empty, then the intersection of all the sets is non-empty. In our case, d=2d=2 (since we are in the plane π\pi), and every three (i.e., d+1d+1) of the projected convex sets have a non-empty intersection. Therefore, by Helly's theorem, the intersection of all the projected convex sets P(K)P(K) is non-empty. Let pπp \in \pi be a point in this intersection.

3. Constructing the Stabbing Line:
Consider the line LL in R3\mathbb{R}^3 that passes through the point pp and is normal to the plane π\pi. This line LL intersects the plane π\pi at the point pp.

4. Intersection with Original Convex Sets:
Since pp is in the intersection of all the projections P(K)P(K), the line LL intersects each original convex set KK at some point. This is because the projection of KK onto π\pi contains pp, and thus KK must intersect the line LL at some point above or below pp in R3\mathbb{R}^3.

5. Generalization to Higher Dimensions:
The argument can be generalized to any dimension nn. If we have finitely many convex subsets in Rn\mathbb{R}^n such that every nn of them have a non-empty intersection, we can project these sets onto an (n1)(n-1)-dimensional hyperplane and apply Helly's theorem in Rn1\mathbb{R}^{n-1}. The same reasoning shows that there exists a line in Rn\mathbb{R}^n that intersects all the convex subsets.

Therefore, we have shown that there exists a line in R3\mathbb{R}^3 that intersects all the given convex subsets.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.