A configuration of points in the plane is called Colombian if it consists of red points and 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 such that for any Colombian configuration of points, there is a good arrangement of lines.

Solution:

Let's generalize: we can solve this problem for any coloring of points where . In this case, I claim that is the answer. For the rest of the proof, when I say "partition" a certain set of points I mean to create regions in which no two of these points can be colored differently and reside in the same region.

To show that at least lines are necessary, consider the configuration where the points are the vertices of a regular -gon and are colored such that every edge of this polygon except one is incident to points of differing colors. There clearly must be a line passing through each of the edges incident to points of differing colors and since every line can pass through at most two such edges, we have the desired result.

To show that lines are sufficient, we proceed with induction on . Note that the base case of is trivial. Now, consider the convex hull of a Colombian configuration with points.

If there are two adjacent vertices on this convex hull that are colored differently, call these points special and then use the induction hypothesis to partition the other points with lines. If the two special points happen to be separated from one another, since they are an edge of the convex hull we can just add a line separating them from all other points. If they are not separated, then one of them is in a region with every other point colored differently. Add a line to separate this point from all other points. In both cases, we are clearly done.

If there are two adjacent vertices on this convex hull that are colored similarly, separate them from the other points with a line and use the induction hypothesis to partition the other points with lines. In this case, we are done as well.