IMO 2019 Shortlisted Problems

First we show by induction that the $n$ walls divide the plane into $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1$ regions. The claim is true for $n=0$ as, when there are no walls, the plane forms a single region. When placing the $n^{\text{th }}$ wall, it intersects each of the $n-1$ other walls exactly once and hence splits each of $n$ of the regions formed by those other walls into two regions. By the induction hypothesis, this yields $\left(\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1\right)+n=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1$ regions, proving the claim.

Now let $G$ be the graph with vertices given by the $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1$ regions, and with two regions connected by an edge if there is a door between them.

We now show that no matter how Merlin paints the $n$ walls, Morgana can place at least $n+1$ knights. No matter how the walls are painted, there are exactly $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ intersection points, each of which corresponds to a single edge in $G$. Consider adding the edges of $G$ sequentially and note that each edge reduces the number of connected components by at most one. Therefore the number of connected components of $G$ is at least $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+1-\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n+1$. If Morgana places a knight in regions corresponding to different connected components of $G$, then no two knights can ever meet.

Now we give a construction showing that, no matter what shape the labyrinth is, Merlin can colour it such that there are exactly $n+1$ connected components, allowing Morgana to place at most $n+1$ knights.

First, we choose a coordinate system on the labyrinth so that none of the walls run due north-south, or due east-west. We then have Merlin paint the west face of each wall red, and the east face of each wall blue. We label the regions according to how many walls the region is on the east side of: the labels are integers between 0 and $n$.

We claim that, for each $i$, the regions labelled $i$ are connected by doors. First, we note that for each $i$ with $0⩽i⩽n$ there is a unique region labelled $i$ which is unbounded to the north.

Now, consider a knight placed in some region with label $i$, and ask them to walk north (moving east or west by following the walls on the northern sides of regions, as needed). This knight will never get stuck: each region is convex, and so, if it is bounded to the north, it has a single northernmost vertex with a door northwards to another region with label $i$.

Eventually it will reach a region which is unbounded to the north, which will be the unique such region with label $i$. Hence every region with label $i$ is connected to this particular region, and so all regions with label $i$ are connected to each other.

As a result, there are exactly $n+1$ connected components, and Morgana can place at most $n+1$ knights.

---

Alternative solution.

We give another description of a strategy for Merlin to paint the walls so that Morgana can place no more than $n+1$ knights.

Merlin starts by building a labyrinth of $n$ walls of his own design. He places walls in turn with increasing positive gradients, placing each so far to the right that all intersection points of previously-placed lines lie to the left of it. He paints each in such a way that blue is on the left and red is on the right.

For example, here is a possible sequence of four such lines ${\ell }_1,{\ell }_2,{\ell }_3,{\ell }_4$ :



We say that a region is "on the right" if it has $x$-coordinate unbounded above (note that if we only have one wall, then both regions are on the right). We claim inductively that, after placing $n$ lines, there are $n+1$ connected components in the resulting labyrinth, each of which contains exactly one region on the right. This is certainly true after placing 0 lines, as then there is only one region (and hence one connected component) and it is on the right.

When placing the $n^{\text{th }}$ line, it then cuts every one of the $n-1$ previously placed lines, and since it is to the right of all intersection points, the regions it cuts are exactly the $n$ regions on the right.



The addition of this line leaves all previous connected components with exactly one region on the right, and creates a new connected component containing exactly one region, and that region is also on the right. As a result, by induction, this particular labyrinth will have $n+1$ connected components.

Having built this labyrinth, Merlin then moves the walls one-by-one (by a sequence of continuous translations and rotations of lines) into the proper position of the given labyrinth, in such a way that no two lines ever become parallel.

The only time the configuration is changed is when one wall is moved through an intersection point of two others:





Note that all moves really do switch between two configurations like this: all sets of three lines have this colour configuration initially, and the rules on rotations mean they are preserved (in particular, we cannot create three lines creating a triangle with three red edges inwards, or three blue edges inwards).

However, as can be seen, such a move preserves the number of connected components, so in the painting this provides for Arthur's actual labyrinth, Morgana can still only place at most $n+1$ knights.