Olimpiadas de Matemáticas
Página de preparación y problemas

Sea $n\gt 1$ un entero. A lo largo de la pendiente de una montaña hay $n^2$ estaciones, todas a diferentes altitudes. Dos compañías de teleférico, $A$ y $B$, operan $k$ teleféricos cada una. Cada teleférico realiza el servicio desde una estación a otra de mayor altitud (sin paradas intermedias). Los teleféricos de la compañía $A$ parten de $k$ estaciones diferentes y acaban en $k$ estaciones diferentes; igualmente, si un teleférico parte de una estación más alta que la de otro, también acaba en una estación más alta que la del otro. La compañía $B$ satisface las mismas condiciones. Decimos que dos estaciones están unidas por una compañía si uno puede comenzar por la más baja y llegar a la más alta con uno o más teleféricos de esa compañía (no se permite otro tipo de movimientos entre estaciones).

Determinar el menor entero positivo $k$ para el cual se puede garantizar que hay dos estaciones unidas por ambas compañías.