Problem 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. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) 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.
 

Solution

  Given a pair of adjacent cells, we can always continue walking "downhill" until we reach a valley, so any pair of adjacent cells is the highest pair in at least one uphill path. There are $2n(n-1)$ such pairs, and the cell containing $1$ alone also constitutes an uphill path, so there must be at least $2n(n-1) + 1$ uphill paths.

A construction obtaining exactly $2n(n-1) + 1$ is given as follows. We first construct a tree of $T$ cells such that every cell not in the tree is only adjacent to cells in the tree. A diagram of such a tree for $n=9$ is given below; this readily generalizes to any multiple of $3$, and to non-multiples of $3$ by removing the leftmost and/or the rightmost column. We place the numbers from $1$ to $T$ as follows: $1$ is placed in an arbitrary cell of the tree, and then each number is placed adjacent to exactly one number that was already placed. (Using a depth-first-search order works, for example.) The numbers $T+1$ to $n^2$ are placed arbitrarily in the remaining cells.



[asy] unitsize(16); for(int i=0; i < 10; i=i+2) { fill((0,i)--(3,i)--(3,i+1)--(0,i+1)--cycle,grey); fill((6,i)--(9,i)--(9,i+1)--(6,i+1)--cycle,grey); } for(int i=1; i < 9; i=i+2) { fill((3,i)--(6,i)--(6,i+1)--(3,i+1)--cycle,grey); } for(int i=1; i < 10; i=i+3) { fill((i,1)--(i,9)--(i+1,9)--(i+1,1)--cycle,grey); } fill((3,0)--(4,0)--(4,1)--(3,1)--cycle,grey); fill((5,0)--(6,0)--(6,1)--(5,1)--cycle,grey); for(int i=0; i < 10; ++i) { draw((i,0)--(i,9)); draw((0,i)--(9,i)); } [/asy]

 
Tree for $n=9$.


It follows that each pair of adjacent cells is the highest pair in exactly one uphill path, because the lower number in the pair lies in the tree and there is a unique way to go downhill from there to the unique valley at $1$, so there must be exactly $2n(n-1) + 1$ uphill paths in total.