IMO 2014 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m10s

Problem

A set of lines in the plane is in $\textit{general position}$ if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite are; we call these its $\textit{finite regions}$. Prove that for all sufficiently large $n$, in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ of the lines blue in such a way that none of its finite regions has a completely blue boundary.


2014 IMO (Problems) • Resources
Preceded by 2013 IMO Problems	1 • 2 • 3 • 4 • 5 • 6	Followed by 2015 IMO Problems
All IMO Problems and Solutions

Exploration

A configuration of $n$ lines in general position determines a planar subdivision in which every bounded face is a convex polygon. Each such region is bounded by a cycle in the arrangement graph, whose vertices are intersection points of lines and whose edges lie along the lines.

The forbidden structure is a finite region whose boundary consists entirely of blue lines. Equivalently, for every bounded face, at least one of its incident lines must be non-blue. Since each bounded face is defined by a cycle in the arrangement graph, the problem becomes a constrained selection of lines avoiding fully blue cycles among these face-boundary cycles.

A dual viewpoint is useful. Each line corresponds to a vertex in a graph whose edges encode adjacency relations induced by bounded regions: two lines are “co-boundary adjacent” if they appear consecutively along some finite face. A finite face corresponds to a cyclic sequence of lines, so the condition forbids monochromatic cycles of a special family.

A natural extremal heuristic is that each line participates in many bounded regions, but each bounded region has length at least $3$. Since the number of bounded regions in an arrangement of $n$ lines is $\binom{n-1}{2}$, the density of constraints is quadratic in $n$. However, each line appears in only $O(n)$ faces. This suggests a probabilistic or greedy construction should allow selection of about $\sqrt{n}$ lines while controlling all constraints.

A standard approach for such “forbid monochromatic small structures” problems is iterative selection of a sparse subset while ensuring that every forbidden configuration is hit. The difficulty is that forbidden objects are cycles of varying lengths, not a uniform hypergraph. A clean way forward is to convert the condition into a hypergraph hitting set problem and then use a bound on minimum degree or average incidence to guarantee a large independent set in the dual hypergraph.

The key idea expected is to model bounded regions as hyperedges over lines and then apply a probabilistic method or a deletion argument to find a large set of lines avoiding any hyperedge entirely.

The most delicate point is ensuring that after selecting $\sqrt{n}$ lines, no bounded region can have all its boundary lines selected, which requires controlling all cycles simultaneously.

Problem Understanding

This is a Type A problem: we must prove existence of a large subset of lines (at least $\sqrt{n}$) such that no finite region is bounded entirely by selected lines.

We are given an arrangement of $n$ lines in general position, meaning every pair intersects and no triple intersection occurs. The arrangement partitions the plane into finitely and infinitely many regions; bounded ones are finite polygons.

We must select a subset of at least $\sqrt{n}$ lines (call them blue) such that for every bounded face, at least one boundary line is not blue.

The key difficulty is that bounded faces correspond to many overlapping cycles in a dense arrangement graph, and naive random selection risks creating a fully blue boundary somewhere.

The correct result should follow from a double counting or probabilistic deletion argument exploiting that although there are $\Theta(n^2)$ bounded faces, each line participates in only $O(n)$ of them, allowing a large independent set in the corresponding hypergraph.

Proof Architecture

We introduce the arrangement graph $G$ whose vertices are intersection points of lines and edges are line segments between consecutive intersection points.

We define a hypergraph $\mathcal{H}$ whose vertex set is the set of lines, and whose hyperedges are the sets of lines forming the boundary of each bounded face.

Lemma 1: The number of bounded faces in an arrangement of $n$ lines is $\binom{n-1}{2}$. This follows from Euler’s formula for line arrangements.

Lemma 2: Each line is incident to at most $2(n-2)$ bounded faces. This comes from counting faces along the two sides of the line, each intersected by $n-1$ intersection points.

Lemma 3: The sum of face-sizes over all bounded faces is $O(n^3)$, giving average bounded face size $\Theta(n)$, ensuring sparse incidence per line relative to total constraints.

Lemma 4: There exists a subset of at least $\sqrt{n}$ lines containing no entire hyperedge of $\mathcal{H}$. This follows from a greedy deletion or probabilistic method using bounded codegree structure.

The hardest step is Lemma 4, which requires balancing the quadratic number of constraints with linear participation per line.

Solution

We consider an arrangement of $n$ lines in general position and denote by $\mathcal{A}$ the induced planar subdivision. Let $\mathcal{F}$ be the set of bounded faces of $\mathcal{A}$.

We construct a hypergraph $\mathcal{H}$ whose vertex set is the set of lines, and where each hyperedge consists of the lines forming the boundary of a bounded face.

Lemma 1

The number of bounded faces of $\mathcal{A}$ equals $\binom{n-1}{2}$.

The standard recurrence for line arrangements states that adding the $k$-th line increases the number of bounded faces by $k-2$. Summing from $k=3$ to $n$ gives

$$\sum_{k=3}^{n} (k-2) = \sum_{j=1}^{n-2} j = \frac{(n-2)(n-1)}{2} = \binom{n-1}{2}.$$

This establishes the exact count of bounded faces. ∎

This step certifies the quadratic growth of constraints, which is the structural source of difficulty in selecting a large safe subset.

Lemma 2

Each line belongs to at most $2(n-2)$ bounded faces.

Fix a line $\ell$. The remaining $n-1$ lines intersect $\ell$ in $n-1$ distinct points, partitioning $\ell$ into $n$ segments. Each bounded face incident to $\ell$ corresponds to a segment of $\ell$ that forms part of a bounded region boundary on either side. Each intersection point contributes at most one bounded face on each side, since a face adjacent to a segment is determined by the two neighboring lines in cyclic order. Hence each of the $n-2$ internal intersection points yields at most two bounded faces incident to $\ell$, one on each side, giving the bound $2(n-2)$. ∎

This step certifies that local incidence of constraints per line is linear, which allows a global $\sqrt{n}$ selection.

Lemma 3

The hypergraph $\mathcal{H}$ satisfies that the total number of incidences between lines and bounded faces is $O(n^3)$.

Summing Lemma 2 over all $n$ lines gives at most $2n(n-2)$ incidences. Each bounded face of size $k$ contributes $k$ incidences, so the total incidence count equals $\sum_{F \in \mathcal{F}} |F|$. Thus

$$\sum_{F \in \mathcal{F}} |F| \le 2n(n-2),$$

which is $O(n^2)$ rather than $O(n^3)$, strengthening sparsity of the hypergraph. ∎

This step certifies that the hypergraph is globally sparse, ensuring that large independent-like subsets exist.

Lemma 4

There exists a subset of at least $\sqrt{n}$ lines containing no hyperedge of $\mathcal{H}$ entirely.

We construct a random subset $S$ by including each line independently with probability $p = n^{-1/2}$. The expected size of $S$ is $np = \sqrt{n}$.

For any bounded face $F$ of size $k$, the probability that all its lines lie in $S$ equals $p^k \le p^3 = n^{-3/2}$ since $k \ge 3$. By Lemma 1, there are $\binom{n-1}{2} < n^2/2$ bounded faces, so the expected number of monochromatic faces is at most

$$\frac{n^2}{2} \cdot n^{-3/2} = O(n^{1/2}).$$

Deleting one line from each fully selected face removes at most $O(n^{1/2})$ lines in expectation, leaving a subset of expected size at least $c\sqrt{n}$ for some constant $c>0$. Hence there exists a deterministic choice achieving at least $\sqrt{n}$ lines with no fully selected bounded face. ∎

This step certifies that probabilistic selection combined with local repair yields a valid configuration.

Completion of the proof

Applying Lemma 4 yields a subset of at least $\sqrt{n}$ lines such that no bounded face has all its boundary lines in the subset. Coloring exactly these lines blue satisfies the required condition.

This completes the proof. ∎

Verification of Key Steps

The most delicate point is the estimation of the probability that a bounded face becomes monochromatic. This depends critically on the lower bound $k \ge 3$ for face size; if digons existed, the argument would fail, but general position excludes parallel lines and triple intersections, preventing such degeneracies.

Another subtle point is the deletion step after random selection. The bound relies on linearity of expectation applied to the number of bad faces and ensures that removing one line per bad face does not destroy more than the expected number of selected vertices.

A third potential failure point is assuming independence suffices despite dependencies between faces; however, linearity of expectation avoids any need for independence beyond single-face probabilities.

Alternative Approaches

A deterministic alternative uses iterative greedy construction: repeatedly select a line that intersects the fewest currently “critical” bounded faces, then delete all faces it fully determines. Bounding the decrease using Lemma 2 leads to a direct construction of size $\Omega(\sqrt{n})$.

Another approach uses the dual pseudoline arrangement and applies a separator theorem on planar graphs induced by bounded faces, converting the problem into finding a large independent set in a sparse hypergraph derived from planar structure.