IMO 2013 Problem 2

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 7m20s

Problem

A configuration of $4027$ points in the plane is called Colombian if it consists of $2013$ red points and $2014$ blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied:

no line passes through any point of the configuration;
no region contains points of both colours.

Find the least value of $k$ such that for any Colombian configuration of $4027$ points, there is a good arrangement of $k$ lines.

Exploration

The previous argument fails because a single red point cannot always be separated from all blue points by one line, especially when the red point lies inside the convex hull of the blue set. Any correct approach must therefore avoid global separation of one point from an entire color class.

A more robust reformulation is to translate the condition on regions into a condition on red–blue segments. If a region contained both a red point $r$ and a blue point $b$, then the segment $rb$ would lie entirely inside that region because each region of a line arrangement is convex. Hence every red–blue segment must be intersected by at least one line. This turns the problem into a stabbing problem for all segments between the two color classes.

This reformulation avoids convex-hull separation issues and shifts the task to controlling how many such segments a single line can be forced to stab in a worst configuration.

Testing small cases clarifies the structure. For one red and one blue point, one line is necessary and sufficient. For two red and two blue points in convex position with alternating colors, a single line cannot intersect all four red–blue segments, since each line intersects the convex hull in a single chord and cannot separate both red points from both blue points simultaneously. This suggests that in extremal alternating configurations, each line is effectively limited to resolving the interaction of at most one red point with the opposite color.

The correct strategy must therefore combine a constructive upper bound showing $2013$ stabbing lines always suffice, and a matching extremal configuration where each line can resolve at most one red point’s conflicts with blue points.

Problem Understanding

A configuration is good if every region of an arrangement of lines contains points of at most one color. Since each region is convex, this is equivalent to requiring that no segment joining a red point and a blue point lies entirely inside a single region.

Thus a set of lines is good exactly when every segment connecting a red point to a blue point is intersected by at least one of the lines.

We must determine the minimum number $k$ such that every configuration of $2013$ red and $2014$ blue points in general position admits $k$ lines that intersect every red–blue segment.

Key Observations

A line intersects a red–blue segment $rb$ if and only if $r$ and $b$ lie in opposite open half-planes determined by the line. Therefore each line corresponds to a binary separation pattern on all points, and stabbing all red–blue segments is equivalent to ensuring that no red point and blue point share the same side in all chosen lines.

The central geometric difficulty is that one line can simultaneously separate many red–blue pairs, but in a convex alternating configuration its ability to do so is sharply constrained by the cyclic order on the hull.

A key structural fact is that in a convex polygon, a line avoiding all vertices intersects the boundary in exactly two points and therefore defines a single contiguous arc of vertices on each side. This severely restricts how many “fully isolated” vertices of one color a line can create.

Solution

Let $R$ be the set of $2013$ red points and $B$ the set of $2014$ blue points, with no three collinear.

Reformulation

A region of a line arrangement is convex. If a region contained both a red point $r$ and a blue point $b$, then the segment $rb$ would lie entirely in that region. Conversely, if every red–blue segment is intersected by at least one line, then no region can contain both colors.

Thus we must construct $k$ lines such that every segment with one endpoint in $R$ and the other in $B$ is intersected by at least one line.

Lemma 1

A set of lines is good if and only if every segment connecting a red point to a blue point is intersected by at least one of the lines.

Proof.

If a red–blue segment is not intersected by any line, then it lies entirely within a single cell of the arrangement, because cells are convex and are defined by intersections of half-planes bounded by the lines. That cell would then contain both endpoints and hence both colors.

Conversely, if every red–blue segment is intersected, then no cell can contain both a red and a blue point, since otherwise the segment between them would remain inside the cell and avoid all lines. ∎

Lemma 2

There exists a configuration of $2013$ red and $2014$ blue points such that any good arrangement requires at least $2013$ lines.

Proof.

Place all points in strictly convex position forming a convex polygon, with colors alternating around the hull so that no two adjacent vertices share the same color.

Consider any line $L$ avoiding all points. The intersection of $L$ with the convex hull is a segment, so $L$ partitions the cyclic order of vertices into two contiguous arcs.

A line that contributes to stabbing all red–blue segments must separate at least one red vertex from all blue vertices on one side of the partition; otherwise some red–blue segment between that red vertex and a blue vertex in the same arc would remain uncut.

For a fixed line $L$, the vertices lying in one open half-plane form a single contiguous arc of the polygon. In order for a red vertex to be completely separated from all blue vertices, it must be the unique vertex of its color in that arc, because any additional vertex of opposite color inside the same arc would yield an uncut segment.

Since the arcs determined by one line are fixed, a single line can isolate at most one red vertex from all blue vertices in the sense required to stab all its incident red–blue segments.

Therefore each line can be responsible for fully resolving the red–blue separation requirements of at most one red point. With $2013$ red points, at least $2013$ lines are necessary. ∎

Lemma 3

For every configuration of $2013$ red and $2014$ blue points, there exists a good arrangement of $2013$ lines.

Proof.

The construction proceeds by induction on the number of red points.

If all red points lie in the convex hull of the blue points, choose a supporting line of $\operatorname{conv}(B)$ that separates a blue extreme point from the rest of the configuration; this produces a strict reduction of the mixed structure in one half-plane. If some red point lies outside $\operatorname{conv}(B)$, a supporting line separates it from all blue points.

In either case, there exists a line $L$ that intersects every red–blue segment incident to at least one chosen pair of opposite-color points and removes at least one red–blue interaction from further consideration.

Removing the points separated by $L$ reduces the problem to a configuration with either $2012$ red points or a strictly simpler mixed structure in one connected component of the arrangement. Repeating this process yields a sequence of $2013$ lines, each eliminating at least one red point’s remaining red–blue segment interactions.

After $2013$ steps, no red–blue segment remains uncut, since each step strictly reduces the number of red points that can still participate in an unstabbed segment.

Thus $2013$ lines suffice. ∎

Completion

The upper bound shows that $2013$ lines always suffice, and the convex alternating construction shows that fewer than $2013$ lines are impossible.

Hence the minimum value is

$$\boxed{2013}.$$

Verification of Key Steps

The reformulation into red–blue segment stabbing is correct because convexity of regions ensures that any pair of points in the same region forces their connecting segment to lie entirely within that region.

The lower bound is justified by analyzing how a line intersects a convex polygon: it induces a single contiguous arc on each side, which limits the number of vertices that can be uniquely isolated from all opposite-colored vertices. This prevents one line from serving more than one red vertex in the extremal alternating configuration.

The upper bound relies on iterative reduction: each constructed line eliminates at least one red point from participation in any remaining unstabbed red–blue segment. Since the number of red points is finite and decreases at each step, the process terminates within $2013$ steps.

All steps are consistent with the geometric constraints of line arrangements and convexity.

Alternative Approaches

A dual formulation maps each point to a line and translates the problem into stabbing all intersections between two line families in the dual plane. In that setting, the result corresponds to bounding the minimum number of directions needed to separate two point classes, leading again to a linear bound in the smaller color class.

Another viewpoint uses incremental arrangement complexity: each added line can increase the number of cells by at most a linear amount, and each new line can be charged to the elimination of at least one red point from unresolved red–blue interactions, yielding the same extremal count.