(IMO 2013, more difficult)

A configuration of 4027 points in the plane is called Colombian if it consists of 2013 red points and 2014 blue points, and if no three of these points are collinear. By drawing lines, the plane is divided into regions. A drawing of lines is called good for a Colombian configuration if the following two conditions are satisfied:

- no drawn line passes through a point of the configuration;
- no region contains points of different colors.

Find the smallest value of $k$ such that, for every Colombian configuration of 4027 points, there exists a good drawing of $k$ lines.
The answer is 2013. To show this, and as with any problem of this type, we need to show two things:

1) $k \geqslant 2013$. Indeed, if we consider a regular 2016-gon whose vertices alternate between red and blue, with a 2014th blue point somewhere else in the plane, then we need at least 2013 lines to properly separate the points: each arc of the circle defined by two of our points must be cut, and a line cuts at most two arcs.
2) Let's show that 2013 is sufficient: note that for any pair of points of the same color $A$ and $B$, we can draw two lines that separate them from the rest of the points, since it is enough to take two parallels on either side of $(A B)$ sufficiently close to $A$ and $B$ so that no other point is in the region. Now consider the convex hull of our points, we distinguish two cases: If there is a red point on the convex hull, we can separate it from the rest of the points with a line, then pair the remaining red points to separate them as seen previously. Otherwise, there are only blue vertices on the convex hull, but then by taking two consecutive ones $C$ and $D$, we can separate them from the rest of the points with a single line parallel to $(C D)$ and close to $C$ and $D$: this is the advantage of the convex hull. Then, we conclude as before with the remaining 2012 points: we pair the points, which gives us 2012/2 $=1006$ pairs, and we need 2 lines per pair, so we have a total of $2 \times 1006+1=2013$ lines.

## 7 Counting/ Potpourri (Raphael)

## “Sum”

## Proposition 1.

The size of the union of two sets is the sum of the size of each set minus the size of their intersection. We denote this as

$$
|A \cup B|=|A|+|B|-|A \cap B| \text {. }
$$

Proof. We try with the formula $|A|+|B|$. However, we notice that the elements that are in both $A$ and $B$ have been counted twice, so we need to subtract $|A \cap B|$ to get the correct result. Finally, the correct formula is $|A|+|B|-|A \cap B|$.