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 , in any set of lines in general position it is possible to colour at least lines blue in such a way that none of its finite regions has a completely blue boundary.

Note: Results with replaced by will be awarded points depending on the value of the constant .

Solution: I unfortunately could not get , but my proof works for all which would have netted me points at the IMO I think?

We proceed with (a quite standard application of) the probabilistic method. First, by using Euler's formula we can quickly find that the number of faces in our graph is at most . Moreover, since each intersection point can be the vertex of at most two triangles, we have that the number of triangular faces is at most . Therefore the worst-case scenario is when there are triangles and faces which are not triangles.

Now, color every line blue with probability . Then . Moreover, and . Un-coloring at least one line from every completely blue face, we expect at least blue lines. Letting then yields the desired result.