Problem: Let $n$ be a positive integer.
A \emph{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.
An \emph{uphill path} is a sequence of one or more cells such that:
\begin{enumerate}
  \ii the first cell in the sequence is a \emph{valley},
  meaning the number written is less than all its orthogonal neighbors,

  \ii each subsequent cell in the sequence is orthogonally
  adjacent to the previous cell, and

  \ii the numbers written in the cells in the sequence are in increasing order.
\end{enumerate}
Find, as a function of $n$, the smallest possible total number
of uphill paths in a Nordic square.

\end{enumerate}

Solution: Answer: $2n^2-2n+1$.

\paragraph{Bound.}
The lower bound is the ``obvious'' one:
\begin{itemize}
  \ii For any pair of adjacent cells, say $a > b$,
  one can extend it to a downhill path (the reverse of an uphill path)
  by walking downwards until one reaches a valley.
  This gives $2n(n-1)=2n^2-2n$ uphill paths of length $\ge 2$.

  \ii There is always at least one uphill path of length $1$,
  namely the single cell $\{1\}$ (or indeed any valley).
\end{itemize}

\paragraph{Construction.}
For the construction, the ideas it build a tree $T$ on the grid
such that no two cells not in $T$ are adjacent.

An example of such a grid is shown below for $n=15$ with $T$ in yellow
and cells not in $T$ in black; it generalizes to any $3 \mid n$,
and then to any $n$ by deleting the last $n \bmod 3$ rows
and either/both of the leftmost/rightmost column.

\begin{center}
\begin{asy}
  size(11cm);
  defaultpen(fontsize(8pt));
  filldraw(box( (0,0),(15,-15) ), black, black+2);
  int L = 0;
  void go(int x, int y) {
    ++L;
    filldraw(shift(x,-y-1)*unitsquare, paleyellow,black);
    label("$"+(string)L+"$", (x+0.5,-y-0.5));
  }
  for (int m=0; m<=2; ++m) {
    go(6*m, 0);
    go(6*m+1, 0);
    go(6*m+2, 0);
    for (int j=0; j<7; ++j) {
      go(6*m+1, 2*j+1);
      go(6*m+1, 2*j+2);
      go(6*m, 2*j+2);
      go(6*m+2, 2*j+2);
    }

    if (m != 2) {
      go(6*m+3, 0);
      go(6*m+3, 1);
      go(6*m+4, 1);
      go(6*m+5, 1);
      go(6*m+5, 0);
      for (int j=1; j<7; ++j) {
        go(6*m+4, 2*j);
        go(6*m+4, 2*j+1);
        go(6*m+3, 2*j+1);
        go(6*m+5, 2*j+1);
      }
      go(6*m+4,14);
    }
  }
\end{asy}
\end{center}

Place $1$ anywhere in $T$ and then place all the small numbers at most $|T|$
adjacent to previously placed numbers (example above).
Then place the remaining numbers outside $T$ arbitrarily.

By construction, as $1$ is the only valley, any uphill path must start from $1$.
And by construction, it may only reach a given pair of terminal cells in one
way, i.e.\ the downhill paths we mentioned are the only one.
End proof.