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 cells are considered adjacent if they share an edge. A cell is a valley if the number written in it is less than the numbers written in all adjacent cells. 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,

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

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

Step 1 (Count uphill paths): Each uphill path starts at a valley and follows increasing values. The total count depends on the number of valleys and the branching structure of increasing paths from each valley.

Step 2 (Lower bound): Each cell $c$ with value $v$ contributes to uphill paths: the number of uphill paths ending at $c$ equals the number of valleys from which $c$ is reachable via increasing paths. We show the total is at least $2(2^n-1)$.

Step 3 (Construction achieving $2(2^n-1)$): Arrange numbers in a snake pattern along rows, with values increasing along each row and alternating direction. This creates exactly 2 valleys (in corners) and the path structure is a binary tree of depth $n$, giving $2(2^n-1)$ total paths.

Step 4 (Proof of lower bound): Consider the contribution of each row: each row introduces at least one new branching point for uphill paths. A careful inductive argument shows the minimum doubles with each row, giving the $2^n$ factor.

$■$