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 3 of 5: Build a tree

T

with no two outside cells adjacent

Previous step Next step

In plain words

If every cell outside a chosen tree is surrounded only by tree cells, then no uphill path can ever pass through two consecutive outside cells, sharply limiting how paths can grow.

T\text{ is a periodic tree whose complement has no adjacent cells}

Detailed analysis

A standard periodic construction (with boundary rows or columns trimmed when needed) gives a connected tree $T$ such that no two cells outside $T$ are orthogonally adjacent. We use only this structural property in the count.