Problem 6

Let

n

be a positive integer. A Nordic square is an

n\times n

board containing all the integers from

1

n^2

so that each cell contains exactly one number. An uphill path is a sequence of one or more cells such that: (a) the first cell in the sequence is a valley, meaning the number written is less than all its orthogonal neighbours; (b) each subsequent cell in the sequence is orthogonally adjacent to the previous cell; and (c) 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.

Step 2 of 5: Add the one-cell path at the global valley

Previous step Next step

2n^2-2n+1

Detailed analysis

Besides these $2n(n-1)$ nontrivial paths, the single cell containing $1$ is always a valley, giving one more uphill path of one cell. Hence every Nordic square has at least $2n(n-1)+1=2n^2-2n+1$ uphill paths.