Q11 Matemática  (IMO Shortlist 2020)

Existe um inteiro $n>1$. Existem estações $n^2$ na encosta de uma montanha, todas em altitudes diferentes. Cada uma das duas empresas de teleféricos, $A$ e $B$, opera teleféricos de $k$; cada teleférico oferece uma transferência de uma das estações para uma mais alta (sem paradas intermediárias). Os teleféricos $k$ de $A$ têm $k$ diferentes pontos de partida e $k$ diferentes pontos de chegada, e um teleférico que começa mais alto também termina mais alto. As mesmas condições valem para $B$. Dizemos que duas estações estão ligadas por uma empresa se se pode partir da estação mais baixa e chegar à mais alta usando um ou mais carros dessa empresa (não são permitidos outros movimentos entre as estações). Determine o menor inteiro positivo $k$ para o qual se pode garantir que existem duas estações ligadas por ambas as empresas. Proposto por Tejaswi Navilarekallu, Índia