This was also Canada IMO TST # 4

This was proposed by Matthew Brennan and James Rickards, Canada (SnowEverywhere and me respectively). The "origin story" is we were doing a joint Canada-Mexico training camp in Mexico in 2017, and one night Matt and I decided to make a problem together. Somehow $n$ walls got put down, and an hour later we'd come up with this. There were variants too; one variant had the knights equipped with a fragile pole vaulting stick allowing them to vault over a wall exactly once. In the end such additions seemed to be unnecessary...

This is a nice problem and no solution is posted yet, so I'll post one. A shame it wasn't selected for the IMO. The only possible value of $k(\mathfrak L)$ is $n+1$. Morgana's strategy (lower bound). The walls divide the plane into $\tbinom n2 + n + 1$ regions. (This can be easily proven with induction.) There are $\tbinom n2$ doors, each of which reduces the number of regions by at most $1$. Thus there are at least $n+1$ different regions. Merlin's strategy (upper bound). Orient the plane so no wall is vertical. Color the north side of each wall red and the south side blue. We claim this results in exactly $n+1$ regions. There are multiple ways to see this; here's one. Imagine modifying the walls at each intersection so that the door is "opened up," as follows: Now imagine scanning from left to right. Since all walls had red north and blue south, none of the new walls ever "doubles back" to the left; more formally, every vertical line intersects each new wall once. Thus, there are $n+1$ regions, identified by the number of new walls above the region for each $0 \le k \le n$. To see that each of these regions is connected, simply walk to the left or right!

The only possible value is $k(\mathcal{L})=n+1$. Consider the graph $G=(V,E)$ that has vertices the regions bound by the $n$ lines where $2$ vertices are connected iff there is a bridge joining them. Induction gives $|V|=\frac{n^2+n+2}{2}$ and $|E|=\binom{n}{2}$. Let $cc(G)$ denote the number of connected components of $G$ then $k(\mathcal{L})=cc(G)$. A standard result from graph theory gives: $$|E| \geq |V|-cc(G) \Rightarrow cc(G) \geq |V|-|E|=n+1$$This means that Morgana can always place at least $n+1$ knights. We now show Merlin can ensure this is all she can place. Claim: Merlin can colour the walls such that $G$ is cycle-free Proof: If the graph has a cycle then following this cycle round say anticlockwise, the wall on the left will always be the same colour as when you cross a bridge the same colour wall is on your left. Hence there is a finite region $P$ bound by the $n$ lines such that all the interior sides of the walls of $P$ are the same colour. It therefore suffices to show Merlin can colour the walls so this can't happen. Pick a point $x$ in the plane such that $x$ is not contained in any region of finite area and $x$ does not lie on any of the $n$ lines. Colour the side of each line containing $x$ red and the other side blue. Consider a finite region $P$. Note that the exterior sides (half-planes) of all of the lines forming $P$ do not have a common point and also the intersection of the interior sides of all the lines forming $P$ is $P$ itself which has finite area. Hence neither of these intersections can contain $x$ so it is impossible for all the interiors of sides of $P$ to be the same colour proving the claim. Using the above colouring $G$ is cycle free hence $cc(G)=|V|-|E|=n+1$ so with this colouring Morgana can place at most $n+1$ knights. So in fact $k(\mathcal{L})=n+1$.

Solution carried by awang11: The answer is $n+1$. To show that this is indeed the lowest possible, we can easily compute that there are $\tfrac{1}{2}n^2+\tfrac{1}{2}n+1$ regions in the labyrinth. Sinde there are $\tbinom{n}{2}$ doors, the number of connected components is at least $$\tfrac{1}{2}n^2+\tfrac{1}{2}n+1-\tbinom{n}{2} = n+1.$$ Now we show $n+1$ is always achievable. It suffices to demonstrate the following: Claim: Pick any infinite labyrinth region $T$, and color the walls such that $T$ is on the red side of all the walls. Then there will be $n+1$ connected components. Proof: For each region $X$ in the labyrinth, label it with the number of walls $W$ such that $X$ is on the blue side of $W$. Note that any regions connected with doors must be labeled with the same number, and that regions which share a wall have labels differing by $1$. Then it suffices to show that there are $n+1$ distinct labels; since $T$ is labeled with $0$, it suffices to show that some region is labeled with $n$, i.e. some region lies on the blue side of all the walls. To see this, zoom out until it looks like all the walls pass through a single point; then it is clear that there is some infinite region $T'$ "opposite" to $T$ such that every wall passes between $T$ and $T'$. Thus $T'$ is on the blue side of every wall.

Finally got around to writing up this one. Had to redo some details on the way. This is quite difficult; I thought it was 30 mohs, but previously thought it was 25. I claim that the answer is $k(\mathfrak{L}) = n$ for any $n$-walled labyrinth $\mathfrak{L}$. First, we show that no matter how Merlin paints the walls, Morgana can always place $\geq n+1$ knights. First, note that drawing any $n$ lines without any three concurrent always yields $\tbinom{n}{2} + \tbinom{n}{1} + \tbinom{n}{0}$ regions in the plane. This is easy to prove via induction; $2$ lines does indeed yield $4$ regions, and assuming $k$ lines yields $\tbinom{k}{2} + \tbinom{k}{1} + \tbinom{k}{0}$ regions, if we draw another line not passing through any intersection point, then it intersects each of the previous $k$ lines, and thus splits $k + 1$ existing regions, creating $k + 1$ new regions. Indeed,\[\tbinom{k}{2} + \tbinom{k}{1} + \tbinom{k}{0} + (k+1) = \tbinom{k+1}{2} + \tbinom{k+1}{1} + \tbinom{k+1}{0}\]as desired. Each intersection creates a door connecting two regions. There are $\tbinom{n}{2}$ doors and $\tbinom{n}{2} + \tbinom{n}{1} + \tbinom{n}{0}$ regions. Let a compound be a group of regions that are all connected via doors; i.e a knight can travel through the entire compound if placed in one of its regions. At most one knight can be placed in each compound. We want a bound on the number of compounds. Note that for each door, we can combine at one region with another hence each door reduces the number of compouds by at most $1$. Since by our initial count each region is a compound, the final number of compounds is $\geq \tbinom{n}{1} + \tbinom{n}{0} = n + 1$ as desired. Now, we show that Merlin can paint the walls such that Morgana can only place exactly $n + 1$ knights; i.e there are exactly $n + 1$ compounds. Rotate the labyrinth so that no wall is horizontal; Merlin can just color every wall opened up to the right red and every corresponding wall opened up to the left blue. I claim that this yields exactly $n + 1$ compounds. Label each region by the number of walls that $x$ is on the blue side of. Clearly connected regions must be labeled with the same number. There must exist a point on the blue side of all walls hence the maximum possible label is $n$, and such a label must exist. Labels range from $0 \to n$, and thus there are exactly $n+1$ connected compounds, as desired. $\blacksquare$

Nice! The answer is always \(n+1\). Proof of \(k\ge n+1\): Consider a graph where the vertices represent the \(\binom{n+1}2+1\) regions and edges represent the \(\binom n2\) doors. Then if the graph has \(k\) connected components of size \(x_1\), $\ldots$, \(x_k\), the number of edges satisfies \[\binom n2\ge(x_1-1)_+\cdots+(x_k-1)\ge\binom{n+1}2+1-k,\]hence \(k\ge n+1\). Proof of \(k\le n+1\): We will show we can paint the walls such that \(k=n+1\). Take a long line \(\ell\) that intersects all the walls, and pick points \(P_0\), \(P_1\), $\ldots$, \(P_n\) in order on \(\ell\) such that \(\ell\) intersects exactly one of the \(n\) walls on segment \(P_iP_{i+1}\) for each \(i\). Paint the walls so that all the blue walls face \(P_0\). For each region, select an interior point \(R\), and label the region with the number of walls that intersect segment \(P_0R\). Observe that any two rooms connected by a door have the same label, so it suffices to show at least \(n+1\) labels exist. But the points \(P_0\), \(P_1\), $\ldots$, \(P_n\) lie in regions labeled 0, 1, $\ldots$, \(n\), respectively, so we are done.

The answer is $n+1$. Claim 1. $k(\mathfrak{L}) \ge n+1$ Proof. We'll prove by induction that $n$ walls divide into $\frac{n^2+n+2}{2}$ regions (without considering the doors). The base case is trivial. Assume it's true for $n$. If a new line is added, it will intersect $n$ lines and thus produced $n+1$ regions. It's enough to verify that $\frac{n(n+1)+2}{2}+n+1=\frac{(n+1)(n+2)+2}{2}$. Now we start adding the $\binom{n}{2}$ doors. Each door removes at most $1$ region so there will be at least $$\frac{n^2+n+2}{2}-\binom{n}{2}=n+1$$regions. Thus $k(\mathfrak{L}) \ge n+1$. Claim 2. $n+1$ knights is achievable for a labyrinth with $n$ walls. Proof. We prove by induction. Orient our view such that the walls is not vertical (this is possible since there are finitely many walls). Paint every wall facing up red and every wall facing down blue. Assume that it's achievable for $k$ walls. Adding a new line (with red facing up) generate an extra region so for $k+1$ we can place $k+2$ knights (The picture shows for $k=3$).

We claim that the number $k(\mathfrak{L})$ (or the image of $\mathfrak{L}$ under the function $k$) is always equal to $\boxed{n+1}$. This means that for every possible labyrinth $\mathfrak{L}$ King Arthur makes, No matter how Merlin colors it, Morgana can always place $n+1$ knights and Merlin can color it in such a way so that Morgana is forced to play $\textit{exactly}$ $n+1$ knights and $\textbf{no more.}$ First Comments: This problem is one of those worth trying for a long time. Very beginner friendly (even if it does not seem so): it teaches how to $\textbf{read a long problem and stay interested at it}$, $\textbf{construct a readable diagram given unfriendly constraints}$ and $\textbf{a very nice combinatorial insight}$!

$\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Getting the Formalities Out.}$ As the name of this Section suggests, here we'll remove what makes the problem intimidating --- and reserving the core/essential part (of what makes this problem hard) for later. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \textbf{0: Side vs one half of it.}$ Convention introduction: define a $\textit{side}$ or a $\textit{wall}$ (used interchangably) in the usual sense, and define a $\textit{half-side}$ in the same manner as you would a half-plane: it consists of one half/one side of a $\textit{side}$ or $\textit{wall}$. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \textbf{1: Graph.}$ As post $\#9$ mentions, make a graph $G(\mathfrak{L})$ out of the labyrinth $\mathfrak{L}$ where the vertices represent the \[ 2 + 2 + 3 + 4 + \ldots + n = \dfrac{n(n+1)}{2}+1 \]regions, and the edges represent the \[ n \ \text{choose} \ 2 \](pairs of) regions which are connected by a wall-intersection or door (as each intersection contains $\textit{exactly one door}$.) $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \textbf{2: Morgana's Components.}$ Notice that the (maximum) number of knights Morgana can place is equal to the number of connected components in $G(\mathfrak{L})$. This is because one knight can access all regions which are connected to the starting point of the knight --- imagine this as $\textit{the region a (particular) knight rules over.}$ $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \textbf{3: Merlin's trees and tight bounds.}$ In a connected component $\mathcal{C}$, the maximum value of \[ |V(\mathcal{C})|-|E(\mathcal{C})| \]is equal to $1$. It is well known that equality happens iff that component is a tree. Now observe that \[ n+1 = |V(G(\mathfrak{L}))|-|E(G(\mathfrak{L}))| = \sum_{\mathcal{C} \ \text{conn. comp.}} |V(\mathcal{C})|-|E(\mathcal{C})| \leq \sum_{\mathcal{C} \ \text{conn. comp.}} 1 = k(\mathfrak{L}) \]and Morgana can ensure that he can place $n+1$ knights in $n+1$ different connected components. $\blacksquare$ $\color{magenta} \rule{25cm}{3pt}$ $\color{magenta} \textbf{Merlin's Cycles vs All Possible Labyrinths.}$ Here we play as Merlin in dealing against King Arthur's labyrinth-constructing abilities. Note that after $\color{green} \textbf{getting the formalities out}$, what matters most to Merlin in ensuring that \[ k(\mathfrak{L}) \equiv n+1 \]is ensuring that no cycles exist within the graph $G(\mathfrak{L})$. $\color{magenta} \rule{25cm}{0.4pt}$ $\color{magenta} \textbf{Strategy.}$ Merlin will pick an unbounded region of $\mathfrak{L}$ and place a laser pointer there. $\textit{Without Loss of Generality}$ assume that all walls are $\epsilon$ nanometers thick and made of glass. Then Merlin will command the pointer to do a $360^{\circ}$ check and burns the $\textbf{half-side}$ of the wall that hits the laser first in red. Then he proceeds to buy blue paint buckets to color the uncolored $\textbf{half-sides}$ manually in blue. (Or in a more mathematical sense, project that point towards each wall, and color the $\textit{touched}$ half-side in red, and color the opposite half-side blue.) This should work. $\blacksquare$ $\blacksquare$ $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{Why? Geometry (kinda).}$ The most mathematically rigorous part (see Figure 1 in attachment for a concrete diagram.) First, before getting into the main argument, note that when a cycle of connected regions form, they will crowd in on another region(s). Call that region by the polygon $\mathfrak{P}$. (forgive me for the $\text{mathfrak}$ conversion of what should've been a $\text{mathcal}$) For that region to have a cycle circling around it, its walls (a.k.a. sides) must either have all of its $\textit{inner half-sides}$ (with respect to the polygon) red, or all of its $\textit{outer half-sides}$ red. The former is easily eliminated, as this implies that the $\textit{laser pointer}$ is inside the bounded region of the polygon $\mathfrak{P}$. $\color{red} \rule{25cm}{0.4pt}$ To prove that the latter is also impossible, we'll fix one side $\mathcal{S}$ of $\mathfrak{P}$ and lay it flat on its side. Consider the highest point $H$ of the flattened polygon $\mathfrak{P}'$. Speaking in order (from the left vertex of $\mathcal{S}$ travelling cyclically to the right vertex of $\mathcal{S}$ through the path $``\mathfrak{P}-\mathcal{S}"$), the vertex before $H$ should be lower than $H$, and so is the vertex after. So, there exists a side $\mathcal{P}$ with a positive slope followed by a side $\mathcal{N}$ with a negative slope. So, the laser pointer must exist to the left of $H$, due to both sides $\mathcal{P}$ and $\mathcal{S}$ forcing it to be in $\mathfrak{R}_{L}$; but it must also exist to the right side of $H$, due to sides $\mathcal{N}$ and $\mathcal{S}$ (forcing it to be in $\mathfrak{R}_{R}$.) This creates a contradiction. So no cycles can form with this strategy. $\blacksquare$ $\blacksquare$ $\blacksquare$ Bonus: as in the official SL solution, I will prove at Motivation that all possible colorings must form with this procedure. (That means there are exactly as many possible colorings as there are unbounded regions)

Finally I write this up. The answer is $k(\mathfrak L) = n+1$ only. Lower bound: I claim that we must always have $k(\mathfrak L) \geq n+1$. It is well-known (say, by induction) that $n$ lines cut the plane into $\tbinom{n+1}{2}+1$ regions. Now suppose we add in each door one by one; each door can only decrease the number of knights by at most $1$, so we achieve a bound of $\tbinom{n+1}{2}-\tbinom{n}{2}+1 = n+1$. Construction: We provide a coloring that achieves exactly $n+1$ knights. Say a component is a set of regions such that one knight can traverse all of the regions in the set; it suffices to construct $n+1$ components in the labyrinth. Now here is the main idea: fix a line $\ell$ above all of the intersection points. Now for each of the $n$ walls, paint the side of the wall that intersects with $\ell$ red, and the other side blue. I claim that this always results in $n+1$ components. Indeed, note that each region in a component has an equal number of interior blue walls, and moreover two regions separated by a wall differ by exactly $1$ interior blue wall. As the number of blue walls ranges from $0$ to $n$ inclusive, there must be exactly $n+1$ components. End proof.

I think my solution is a little bit different, but still the same in spirit. Call two regions connected if two knights placed in these regions can meet each other. A maximal collection of regions any two of which are connected shall be called a campus. A broken line bordering a campus will be called its fence. Notice that fences also have two sides, one of which is blue and the other is red. Here is the key claim: the number of campuses is one plus the number of fences. To prove our claim, let $G$ be a graph with vertices as campuses and an edge between two campuses if and only if they share a fence. A little case check confirms that $G$ is indeed a tree, and hence our claim is proved. For the lower bound, consider a circle covering all the intersection points of the given lines. This circle intersects the given $n$ lines at $2n$ points. Note that each fence contains at most 2 of those $2n$ points, and hence there are at least $n$ fences. Therefore, Morgana can place at least $n+1$ knights, one in each campus. For the upper bound, orient the labyrinth so that no wall goes from north to south. Merlin shall paint those sides of the walls facing north in blue and those facing south in red. This ensures that every fence is unbounded, that is they all extend towards infinity. For otherwise, a bounded fence $\mathcal{F}$ would contain line segments of both positive and negative slope. However, this means both colors present on one side of $\mathcal{F}$, contradiction. Therefore, there are exactly $n$ fences (recall the circle intersection argument above), and hence $n+1$ campuses.

We claim the answer is $n+1$ for a given set of $n$ lines. First, we will prove the answer is $\geq n+1$. Notice that if we have a graph $G$ with vertices as regions and doors as edges then the graph has ${n+1} \choose 2$ $+1$ vertices and $n \choose 2$ edges. Thus, $G$ has at least $n+1$ connected components as desired. Now, let us show Morgana can guarantee the answer to be $n+1$. Consider the following construction. Select some arbitrary infinite region $R$ and color the lines such that the semi plane which contains the red side also contains $R$, also let the score of a region by the number of such semi planes it is contained within. Notice that the score of $R$ is $n$ and there exists a region $S$ where the score of $S$ is zero. Also, notice that the scores of two regions that share an edge differ by $1$ and the score of two regions that share a corner differ by $0$ or $2$ and are connected by a door if their scores differ by $0$. Thus, we notice that all regions with an equal score share a connected component and every score from $0$ to $n$ inclusive exists by discrete continuity. Thus, there are $n+1$ connected components as desired.

We claim that the only possible value is $k(\mathfrak{L} )=n+1.$ Let regions mean connected parts of plane with consideration of doors. We will prove the desired equality by bounding the $k(\mathfrak{L} )$ from two sides. Lower bound $k(\mathfrak{L} )\geq n+1$. By induction it's trivial that $n$ lines of common position divide plane onto $\tbinom {n+1}{2} +1$ regions and every of $\tbinom n2$ doors lessen this number by at most $1,$ so there are at least $n+1$ different regions. Then it's suffice for Morgana to place a knight in each $\Box$ Upper bound $k(\mathfrak{L} )\leq n+1$. Let Merlin acts as follows. Pick any of given line $\ell$ (we call it as color-generating) and paint it's side arbitrarily. Now for every other line $\ell '$ consider composition $\phi$ of rotation by angle from $(0;\pi)$ and of translation which summary maps $\ell \mapsto \ell ';$ finally paint sides os $\ell '$ in such way that they will coincide with sides of $\phi (\ell ).$ We'll prove by induction on $n$ that with this coloring there are at most $n+1$ regions. Base case $n=0$ is trivial. Now take labyrinth with $n$ walls and remove it's color-generating line; clearly we get labyrinth with $n-1$ walls and same kind of coloring, so it has at most $n$ regions. [asy][asy] unitsize(1cm); draw((2.48,-1)--(4,4)); draw((1,3.44)--(6,2.8)); draw((1,1.94)--(6,1.76)); draw((1,0.86)--(6,0.23)); label("red",(4,4),E); label("blue",(4,4),W); label("red",(1,3.44),N); label("blue",(1,3.44),S); label("red",(1,1.94),N); label("blue",(1,1.94),S); label("red",(1,0.86),N); label("blue",(1,0.86),S); label("Color-generating line",(2.48,-1),S); label("1",(3,3.5)); label("1",(3.8,2.4)); label("2",(3,2.5)); label("2",(3.8,1.4)); label("3",(2.8,1.1)); label("3",(3.4,0)); label("4",(2.3,0)); [/asy][/asy] Observe that with returning of $\ell$ we add $n$ parts $n-1$ of which are connected with already existing parts, so we added at most $1$ region. This completes the inductive step $\Box$

We claim that the answer is only $n+1$. Let the $n$ walls divide the plane into $\tfrac{n^2+n+2}{2}$ rooms. Interpret the rooms as vertices in a graph. Connect an edge between two vertices that are one door apart. Each intersection of lines brings one door to it, and each door will connect one edge. The number of connected components in this graph will be at least $v-e=n+1$. Now, consider a direction as north that is not parallel with any wall. Always color the north wall red. Note that in this way, we are able to orient every single door so that they face east-west. Therefore, each connected "wall" will go straight from east infinity to west infinity without ever going in the other direction. Thus, there are $n+1$ regions.

The answer is $n+1$ only. There must be at least $n+1$ regions because each door reduces the number of connected components by at most $1$, but there are $\tbinom{n}{2}+n+1$ connected components at first without doors, so there must be at least $n+1$ with doors. We now prove that Merlin can guarantee exactly $n+1$ regions. Rotate the plane so that no line is horizontal and color the "right side" (i.e. the side that a leftwards-pointing ray from arbitrarily far right hits) red. To prove that this works, we will add in lines one by one such that each line only intersects unbounded regions. It can be proved inductively that any configuration can be achieved in this manner: clearly this is doable for $n=1$, and to go from $n-1$ to $n$, we consider the convex hull of all intersection points of the $n$-line configuration and pick one of its edges, which is part of a line that only intersects unbounded regions. The key claim is that the addition of such a line only increases the number of connected components by $1$, which finishes by induction (since we have $1+1=2$ connected components when we have $1$ line). WLOG suppose that the red side of the newly added line $\ell$ is the one contained in the newly created unbounded regions. Consider the slopes of the lines other than $\ell$, which must be increasing as we move from the "bottom" of $\ell$ to the "top" (otherwise two lines will intersect to the "right" of $\ell$). As such, moving along $\ell$ in this manner, we encounter some (possibly zero) lines with negative slope, followed by some (possibly zero) lines with positive slope. For the lines with negative slope, we encounter the blue side first, and the opposite is true for the lines with positive slope. It is then clear to see that every new unbounded region is part of the connected component of one of its "diagonal neighbors" on the "blue side" of $\ell$, except for An unbounded region formed from $\ell$, one line with negative slope, and one line with positive slope An unbounded region formed only by $\ell$ and the line with maximal slope, if this slope is negative An unbounded region formed only by $\ell$ and the line with minimal slope, if this slope is positive There is evidently only one of these. On the other hand, if some previously unbounded region is "diagonally adjacent" to some others before $\ell$ is added, then it must still be "diagonally adjacent" to these other regions (and exactly these other regions) after $\ell$ is added—essentially, the obvious corresponding graph does not change aside from adding new vertices and edges containing these vertices. Therefore exactly one connected component is added when $\ell$ is added, as desired. $\blacksquare$

Each pair of lines form a door, so there are ${n\choose 2}$ doors. There are $\frac{n^2+n+2}{2}$ regions by induction, so the number of connected components is at least $$\frac{n^2+n+2}{2} - {n\choose 2}=n+1$$since each door decrease the number of connected components by at most $1$. Thus, Morgana can place at least $n+1$ knights. We now show that for any labyrinth $\mathfrak{L}$, Merlin can paint the walls so that there are exactly $n+1$ connected components. This is if and only if there are no cycles. We only have a cycle if all the walls surrounding a polygon formed by segments are the same colour. We orient the plane so that the $y$-axis is not parallel to any wall. Now let Merlin colour the bottom side of each wall, so we cannot have a polygon with outer wall colour the same, so we cannot have a cycle. Thus equality is attained in the bound, giving $n+1$.

The answer is always $k=n+1$. To show that $k\geq n+1$, consider a graph with vertices as the regions fromed by the walls and edges are doors. As there are $\frac {n^2}{2}+\frac n2+1$ vertices and $\binom n2$ edges, it follows that there are at least $n+1$ distinct chains/cycles in the graph. Morgana can simply place a knight in each one. We now show that there is a painting that Merlin can do which achieves $n+1$. Again, we look at the graph considered above; our goal is for it to be acyclic. Claim: If the graph contains a cycle then one finite region has walls that are all the same color Proof. Suppose the cycle crosses between $\ell$ and $\ell_1$. Then, as it is a cycle, it must cross $\ell$ again, say at $\ell_2$. However, we know that the triangle formed by $\ell,\ell_1,\ell_2$ has one color on its inside. Thus take another line $L$ which crosses through said triangle; it forms a monochromatic region with less lines passing through it than the original triangle. Repeat this until there is a monochromatic region. $\blacksquare$ By contrapositive it suffices to find a coloring whose graph has no cycles. This is easily done by coloring the topmost side of a wall blue after rotating none vertical. Remark: Does the proof of the claim count as ``local''? I am not sure lol

Okay I kind of cheated because I remember once upon a time I read the solution Anyhow I'll try to include motivation for the part I read before. First test cases $n=1,2,3$. Notice that the minimal number of connected components possible (see below) is always $n+1$. So we conjecture $k(\mathfrak{L})=n+1$. Create a graph on $\binom{n+1}{2}+1$ vertices; each region is a vertex, and we draw edges between vertices with doors. Hence there are $\binom{n}{2}$ edges. Suppose there are $c$ connected components and components have $v_1,\dots,v_c$ vertices. Now \[v_1+\dots+v_c=\binom{n+1}{2}+1\]\[\binom{n}{2}\ge (v_1-1)+\dots+(v_c-1)=\binom{n+1}{2}+1-c\]\[c\ge \binom{n+1}{2}-\binom{n}{2}+1=n+1.\] Now that we have the lower bound, realize the graph must be acyclic for equality to hold. So the graph essentially never returns to an original point if we continue walking through doors. To put it another way, we really just need to plop Camelot onto the coordinate plane and find some coloring where some linear quantity continues to increase (I guess you can say monovariant). This is pretty easy. Rotate the walls so that nothing is parallel to an axis. We need intersections to always go north-south. Color all west walls red. Verify that this works. GG

We claim that $\boxed{k (\mathfrak{L}) \text{always evaluates to } n + 1}$. There are two parts to this problem: Show that Morgana may always place at least $n + 1$ knights. Show that Merlin may restrict Morgana to $n + 1$ knights. Claim: Morgana may always place at least $n + 1$ knights. Proof. Note that the $n$ walls divide $\mathfrak{L}$ into $\binom{n}{2} + n + 1$ rooms, which can be shown easily using induction. Now when any two rooms become linked, the number of knights Morgana may place decreases by one. As there are exactly $\binom{n}{2}$ such junction points, where two rooms are linked, Morgana may place at least $n+1$ knights. $\square$ Claim: Merlin can restrict Morgana to $n + 1$ knights. Proof. Consider inducting. We begin with a base case of $n = 3$ for which we consider the following construction: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -20.338245137156832, xmax = 7.909828116135345, ymin = -5.013169633194467, ymax = 11.695013353322649; /* image dimensions */ pen qqwwzz = rgb(0,0.4,0.6); pen ccqqqq = rgb(0.8,0,0); /* draw figures */ draw((xmin, 1.6686390526375092*xmin + 18.818990843072935)--(xmax, 1.6686390526375092*xmax + 18.818990843072935), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -0.005617977526012814*xmin + 0.26462082503989537)--(xmax, -0.005617977526012814*xmax + 0.26462082503989537), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -1.518716576978608*xmin-2.19897901572302)--(xmax, -1.518716576978608*xmax-2.19897901572302), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -1.518716576978608*xmin-2.9189123799351364)--(xmax, -1.518716576978608*xmax-2.9189123799351364), linewidth(0.7) + ccqqqq); /* line */ draw((xmin, 1.6686390526375092*xmin + 17.92556359052733)--(xmax, 1.6686390526375092*xmax + 17.92556359052733), linewidth(0.7) + ccqqqq); /* line */ draw((xmin, -0.005617977526012814*xmin-0.1648318122507083)--(xmax, -0.005617977526012814*xmax-0.1648318122507083), linewidth(0.7) + ccqqqq); /* line */ /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Clearly Morgana is restricted to at most $4$ knights. Now at each step consider adding a labyrinth with the blue side facing ``up". Assume that this is valid till step $n = k$. Then for step $n = k + 1$ consider adding an additional wall $\ell$, with blue side facing ``up". Note that $\ell$ forms exactly $n$ new regions. We now claim, Those $n$ new regions are connected by doorways. Specifically Morgana may place only one new knight in the new regions. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(8cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -26.264027172639693, xmax = 14.847600604375463, ymin = -10.69265302710821, ymax = 15.449650812424501; /* image dimensions */ pen qqwwzz = rgb(0,0.4,0.6); pen ccqqqq = rgb(0.8,0,0); pen cczzqq = rgb(0.8,0.6,0); /* draw figures */ draw((xmin, 1.6686390526375092*xmin + 18.818990843072935)--(xmax, 1.6686390526375092*xmax + 18.818990843072935), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -0.005617977526012814*xmin + 0.26462082503989537)--(xmax, -0.005617977526012814*xmax + 0.26462082503989537), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -1.518716576978608*xmin-2.19897901572302)--(xmax, -1.518716576978608*xmax-2.19897901572302), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, -1.518716576978608*xmin-2.9189123799351364)--(xmax, -1.518716576978608*xmax-2.9189123799351364), linewidth(0.7) + ccqqqq); /* line */ draw((xmin, 1.6686390526375092*xmin + 17.92556359052733)--(xmax, 1.6686390526375092*xmax + 17.92556359052733), linewidth(0.7) + ccqqqq); /* line */ draw((xmin, -0.005617977526012814*xmin-0.1648318122507083)--(xmax, -0.005617977526012814*xmax-0.1648318122507083), linewidth(0.7) + ccqqqq); /* line */ draw((xmin, 0.3614457829988953*xmin + 6.291231082116232)--(xmax, 0.3614457829988953*xmax + 6.291231082116232), linewidth(0.7) + qqwwzz); /* line */ draw((xmin, 0.3614457829988953*xmin + 5.833803817662006)--(xmax, 0.3614457829988953*xmax + 5.833803817662006), linewidth(0.7) + ccqqqq); /* line */ draw((-18.22379383039011,-2.8479858808953105)--(-6.753514297307741,1.9132622254162777), linewidth(0.7) + dotted); draw((-6.753514297307741,1.9132622254162777)--(5.866006247685216,-2.822183748382315), linewidth(0.7) + dotted); draw((-13.918193005367874,6.313733532021089)--(1.637558045394618,8.659442022935476), linewidth(0.7) + dotted); draw((-24.010912437112584,-1.2480898926371342)--(-11.942859538604383,0.9124310858366489), linewidth(0.7)); draw((-11.942859538604383,0.9124310858366489)--(-6.448963334168424,4.647045920055603), linewidth(0.7)); draw((-6.448963334168424,4.647045920055603)--(4.569693660121675,3.258139576751031), linewidth(0.7)); /* dots and labels */ label("$n = 3 \mapsto n = 4$", (-6.5,-10), dir(90)); dot((-18.22379383039011,-2.8479858808953105),dotstyle); dot((5.866006247685216,-2.822183748382315),dotstyle); dot((-6.753514297307741,1.9132622254162777),dotstyle); dot((-13.918193005367874,6.313733532021089),dotstyle); dot((1.637558045394618,8.659442022935476),dotstyle); dot((-24.010912437112584,-1.2480898926371342),dotstyle); dot((-11.942859538604383,0.9124310858366489),dotstyle); dot((-6.448963334168424,4.647045920055603),dotstyle); dot((4.569693660121675,3.258139576751031),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] An example for $n = 3$ going to $n = 4$ is shown, with the black line representing the new connected set of regions. Now to prove this note that our new wall $\ell$ intersects every other line at some junction, $\mathcal{J}$, with four different corners. The two ``corners" with common colors either face strictly down or up. Meanwhile the ``corners" that are composed of both a blue and a red wall are lateral. Then it is easy to see that there must exist some ``lateral path" following along $\ell$ such that each region is joined to the previous, resulting in a new section of $n$ connected regions. $\square$ Now the two claims combined imply $k(\mathfrak{L}) = n + 1$ as desired.

We claim that $k(\mathfrak{L}) = n+1$. To show Morgana can always achieve $n+1$. We notice that the plane is always divided into $\frac{n^2 + n + 2}{2}$ regions and each of the $\binom {n}{2}$ doors reduces the amount of knights by at most 1. So we get $k(\mathfrak{L}) \ge \frac{n^2 + n + 2}{2} - \binom {n}{2} = n+1$. Now to show that Merlin can guarantee $n+1$ knights, we rotate the lines so that none are vertical and color each of the upper portions red and the lower portions blue. Now notice a cycle must mean there is a polygon with all of its sides being the same color, but this is impossible because of the way we colored the lines so we are done.

We claim the answer is $\mathfrak{L}(n)=n+1$. Bound: $\mathfrak{L}(n) \geq n+1$, Since there are $\binom{n}{2} + n + 1$ regions formed by $n$ lines, and there are $\binom{n}{2}$ doors, since each door will decrease the number of nights by at most $1$, hence the number of nights is at least $n+1$. Construction: We show this by induction, base case $n=3$ is trivial, now assume this holds for $k$, we show for $k+1$, let $\ell$ be the new line, we colour it such that the upper corner is of same colour, while lateral corners are different colours, we can see that this only $1$ extra knight, hence we are done.

We first rephrase the problem as follows. We are given $n$ lines in the plane in general position. We then give each line an orientation (e.g. direction of flow). These lines divide the plane into $\frac{n^2+n+2}{2}$ regions. Make a graph with these regions as vertices, and for each intersection point between two lines, connect the two regions out of the four where one region entirely flows towards the other. We wish to find the minimum number of different connected components of this graph that we can form. We claim that the answer is $n+1$ connected components (regardless of the configuration of lines). Since the graph has ${n\choose 2}$ edges (one for each intersection), there will be at least $\frac{n^2+n+2}{2}-{n\choose 2}=n+1$ connected components. Note further that equality holds if and only if all connected components have the minimum possible number of edges (in other words, it is a tree). Thus, it suffices to show that we can orient the edges so that no cycle is formed. The rest of the solution is the following claim. Claim: Rotate the plane if necessary so that no line is vertical. Then, we orient every line to flow towards the direction of increasing $x$ coordinate. If this is done, the resulting graph has no cycles. Consider a region (may be finite or infinite). The only edges in the graph involving this region happen when two consecutive edges of the region do not flow in the same direction and instead both flow either towards or away from their intersection point. Note that all lines flow from left to right, and all regions are convex. This means that, if we have a vertex of the region where both lines flow away from it, due to convexity the region must lie entirely between the two lines, and thus said point is the leftmost point. Similar reasoning shows that both lines flowing towards a vertex means it's the rightmost point of the region. Thus, a region can connect with at most one region sharing the leftmost point, and at most one region sharing the rightmost point. Thus we clearly cannot form a cycle, as this will only create chains of regions in order from left to right (eventually it reaches a "leftmost" or "rightmost" region).

$ $