[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 n0.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 n0.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 < n0.5 Clearly the optimal k >  = n0.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:

  1. If L doesn't intersect with any line inside E, then at most the two regions touching E become almost blue-bounded.
  2. If L intersects with exactly one line M inside E, then at most M is added to S.
  3. If L intersects with lines M1, M2, ..., Md inside E, then at most M1 and Md 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
Powered by Github Pages, Pelican, pyScss.