Q11 Matemática  (IMO Shortlist 2019)

Em um plano plano em Camelot, o Rei Arthur constrói um labirinto $\mathfrak{L}$ consistindo de $n$ paredes, cada uma das quais é uma linha reta infinita. Não existem duas paredes paralelas e não existem três paredes com um ponto comum. Merlin então pinta um lado de cada parede inteiramente vermelho e o outro lado inteiramente azul. Na interseção de duas paredes há quatro cantos: dois cantos diagonalmente opostos onde um lado vermelho e um lado azul se encontram, um canto onde dois lados vermelhos se encontram e um canto onde dois lados azuis se encontram. Em cada uma dessas interseções, há uma porta de duas vias conectando os dois cantos diagonalmente opostos nos quais os lados de cores diferentes se encontram. Depois que Merlin pinta as paredes, Morgana coloca alguns cavaleiros no labirinto. Os cavaleiros podem atravessar portas, mas não podem atravessar paredes. Seja $k(\mathfrak{L})$ o maior número $k$ tal que, não importa como Merlin pinte o labirinto $\mathfrak{L},$ Morgana sempre pode colocar pelo menos $k$ cavaleiros tal que não haja dois deles podem se encontrar. Para cada $n,$ quais são todos os valores possíveis para $k(\mathfrak{L}),$ onde $\mathfrak{L}$ é um labirinto com $n$ paredes?