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 4 of 5: Fill

T

first so

1

is the only valley

Previous step Next step

1\in T,\quad T\ \text{filled by adjacency, then the rest arbitrarily}

Detailed analysis

Place $1$ in a cell of $T$ , then fill the rest of $T$ with $2,3,\ldots$ so that each new number's cell is adjacent to an already-filled cell (always possible since $T$ is connected), and finally fill the remaining cells (outside $T$ ) arbitrarily with the larger numbers. Since every outside cell is adjacent only to $T$ -cells filled before all outside numbers, and $T$ was filled in increasing connected order from $1$ , the only valley in the whole board is the cell holding $1$ .