(IMO SL 2019 C4)

On a flat plain in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ lines, no two of which are parallel and no three of which are concurrent. For each wall, Merlin colors one side red and the other side blue.

At the intersection of two walls, there are 4 corners: two corners where a red side and a blue side intersect, one corner where two red sides intersect, and one corner where two blue sides intersect. At this intersection, there is a door connecting the two opposite corners where sides of different colors intersect.

After Merlin has colored the walls, Morgana places knights in the labyrinth. The knights can walk through the doors but not through the walls.

Let $k(\mathfrak{L})$ be the largest integer $k$ such that: no matter how Merlin colors the labyrinth $\mathfrak{L}$, Morgana can always place $k$ knights such that no two of them can ever meet. For a fixed $n$, what can the values of $k(\mathfrak{L})$ be for labyrinths $\mathfrak{L}$ consisting of $n$ lines?
We will show that the only possible value is $n+1$, regardless of the labyrinth $\mathfrak{L}$ chosen by King Arthur.

$-k(\mathfrak{L}) \geqslant n+1$: Let's count the number of regions formed by the $n$ walls of $\mathfrak{L}$. We perform an inversion of the figure to reduce it to a planar graph, which then has $S=\binom{n}{2}+1$ vertices (the $\binom{n}{2}$ intersections of the walls and the point at infinity), as well as $A=n^{2}$ edges (each wall is divided into $n$ parts by the other walls). Euler's formula gives the number of regions as

$$
F=A+2-S=\binom{n}{2}+n+1
$$

Consider any coloring of the labyrinth by Merlin. The number of doors created is equal to the number of intersections of the $n$ walls, which is $\binom{n}{2}$. If we call a connected component of the labyrinth a set of points connected by considering the doors, each door reduces the number of connected components of the labyrinth by at most 1, and consequently $\mathfrak{L}$ contains at least $n+1$ connected components. If Morgana places a knight in each of these connected components, she can then place $n+1$ knights who cannot meet in any case. Therefore, $k(\mathfrak{L}) \geqslant n+1$.

- $k(\mathfrak{L}) \leqslant n+1$: Now let's show that Merlin can always color the walls in such a way as to obtain at most $n+1$ connected components. For this, we perform a rotation of the figure so that no wall is horizontal, and consider the coloring where the left side of each wall is colored blue, and the right side is colored red. Then at the intersection of two walls, the door is on the "vertical" side, and if a knight placed at an arbitrary point always moves upwards (following walls if necessary), he can continue until infinity. Thus, each connected component of the labyrinth contains one of the infinite regions "at the top" (i.e., which have an infinite intersection with the hyperplane $y>0$). But there are only $n+1$ such regions since each line creates a new one. Therefore, Morgana can place at most $n+1$ knights.