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 5 of 5: Show this construction has exactly

2n^2-2n+1

paths

Previous step Next step

2n^2-2n+1

Detailed analysis

Since $1$ is the unique valley, every uphill path starts at its cell. The complement of $T$ has no adjacent cells, so after a path leaves $T$ it cannot have two consecutive outside cells; with the increasing tree order, each directed edge has exactly one associated continuation to a valley. Thus the $2n(n-1)$ nontrivial paths counted in the lower bound, together with the one-cell path at $1$ , are all the paths, giving equality.