Question 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. An *uphill path* is a sequence of one or more cells such that:
1. the first cell in the sequence is a *valley*, meaning the number written is less than all its orthogonal neighbors,
2. each subsequent cell in the sequence is orthogonally adjacent to the previous cell, and
3. 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. Two different cells are adjacent precisely when they share a common side. A valley contains a number smaller than the numbers in all its adjacent cells.
1. the first cell in the sequence is a *valley*, meaning the number written is less than all its orthogonal neighbors,
2. each subsequent cell in the sequence is orthogonally adjacent to the previous cell, and
3. 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. Two different cells are adjacent precisely when they share a common side. A valley contains a number smaller than the numbers in all its adjacent cells.