IMO 2022 Problem 6

Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from $1$ to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of $n$ , the smallest possible total number of uphill paths in a Nordic square.

Author: Nikola Petrović