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:

(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.

APMO 2015 Problem 4

Given n blue lines and n red lines in the plane such that no two lines are parallel to each other, show that there is a circle that intersects with the set of blue lines in exactly 2n-1 points, and intersects with the set of red lines in exactly 2n-1 points.

Proof:

We will prove a more specific condition, that there exists a circle such that for each color, is tangential to one line and intersects with the rest at two points each. The intuition is to find a red and blue line that "bundle" the rest of 2n-2 lines, then a circle big enough and tangential to both this red and blue line indeed intersects the rest of 2n-2 lines at two points each.

To find such two lines, it suffices to take the blue and red lines that span the largest angle between them. Even these two lines may not be unique, it is not hard to show that a sufficiently big circle tangential to them intersects each of other lines at two points.

Q.E.D.