IMO 2022 - P6

[Matías V5]

Sea $n$ un número entero positivo. Un cuadrado nórdico es un tablero $n \times n$ que contiene todos los números enteros del $1$ a $n^2$ de modo que cada celda contiene exactamente un número. Dos celdas diferentes son adyacentes si comparten un mismo lado. Una celda que solamente es adyacente a celdas que contienen números mayores se llama un valle. Un camino ascendente es una sucesión de una o más celdas tales que:

1. la primera celda de la sucesión es un valle,
2. cada celda subsiguiente de la sucesión es adyacente a la celda anterior, y
3. los números escritos en las celdas de la sucesión están en orden creciente.

Hallar, como función de $n$, el menor número total de caminos ascendentes en un cuadrado nórdico.