# [Math] International Mathematical Olympiad (IMO) 2014 Problem 6

A set of lines in the plane is in 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 area; we call these its finite
regions. Prove that for all sufficiently large *n*, in any set of
*n* lines in general position it is possible to color at least
*n*^{0.5} of the lines blue in such a way that none of its finite regions
has a completely blue boundary.

It looks like a problem where we prove asymptotic bound in computation theory,
but interestingly the statement holds for all *n*.

Proof:

We describe an algorithm that colors at least *n*^{0.5} lines blue while
keeping the condition satisfied.

Let *S* be the set of lines that we couldn't color blue. As we proceed, we
pick a line not yet colored and not in *S*. It is then colored blue, and
then we add non-blue lines touching regions that are therefore bounded by all
but one blue lines to *S*. The algorithm halts as all lines are either
blue or in *S*. We call these regions almost blue-bounded regions.

The key observation is that the second blue line adds at most 2 lines to
*S*, the third 4, ..., and the (*k* − 1)*th* blue line adds at most
2(*k* − 2) lines to *S*. So we could color the *k* − *th* line blue
if and only if 2[1 + 2 + ... + (*k* − 2)] + (*k* − 1) < *n*, or *k* − 1 < *n*^{0.5}
Clearly the optimal *k* > = *n*^{0.5}

The devil is in the detail of proving this observation. After we color the k-th line say, L, it intersects with other blue lines at k-1 points, which forms k-2 segments. Each such segment E adds at most two lines to S:

- If
*L*doesn't intersect with any line inside*E*, then at most the two regions touching*E*become almost blue-bounded. - If
*L*intersects with exactly one line*M*inside*E*, then at most*M*is added to S. - If
*L*intersects with lines*M*_{1},*M*_{2}, ...,*M*_{d}inside*E*, then at most*M*_{1}and*M*_{d}get added to*S*.

So these *k* − 2 segments at most add 2(*k* − 2) lines to *S*.
Now, beyond the first or the (*k* − 2)*th* segment, if *L* doesn't
intersect with any other line then we're done. Otherwise, at most the line that
intersects with *L* at a point closest to the segment gets added to
*S*, so at most 2 more lines are added to *S*, giving a total of
2(*k* − 1).

Q.E.D.

post by Shen-Fu Tsai

References:

[1] | International Mathematical Olympiad |