IMO 2022 · 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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{2n(n-1)+1=n^2+(n-1)^2}. \]

Solution

Regard the cells as vertices of a graph, with an edge between two adjacent cells. This graph has \[ E=2n(n-1) \] edges.

For \(n=1\), the only cell is a valley and gives exactly one uphill path, as required. Henceforth let \(n\ge 2\).

Lower bound. For each cell \(v\), let \(p(v)\) be the number of uphill paths ending at \(v\), and let \(d^-(v)\) be the number of its neighbours containing smaller numbers.

Every cell is the endpoint of an uphill path: repeatedly moving to a smaller neighbour must eventually reach a valley, and reversing this sequence gives such a path. Thus \(p(v)\ge 1\).

If \(v\) is a valley, then \(p(v)=1\). Otherwise, partitioning paths according to their penultimate cell gives \[ p(v)=\sum_{\substack{u\text{ adjacent to }v\\u\text{ contains a smaller number}}}p(u) \ge d^-(v). \] Consequently, if there are \(a\) valleys, the total number of uphill paths is at least \[ a+\sum_v d^-(v)=a+E\ge E+1. \] Here each edge contributes once to the sum, and the cell containing \(1\) is a valley.

We now construct a square attaining this bound.

Construction lemma. In every rectangular grid, one can select a set \(T\) of cells such that:

  • the graph consisting of the selected cells and all adjacency edges between them is a tree;
  • no two unselected cells are adjacent;
  • at least one end cell of the bottom row is selected.

Proof. Fix the width and induct on the number of rows. For one row, select every cell.

Suppose a selection has been made in a rectangle. By reflecting it horizontally if necessary, we may assume that the leftmost cell of its bottom row is selected. Write the columns of the selected bottom-row cells as \[ 1=c_1<c_2<\cdots<c_k. \]

Append a new bottom row. In this new row, select every cell except those in columns \[ c_{k-1},c_{k-3},c_{k-5},\ldots, \] stopping when the index becomes nonpositive.

The newly unselected cells are pairwise nonadjacent: between any two of their columns lies another \(c_i\). Moreover, each lies directly below an old selected cell. Thus no two unselected cells in the enlarged rectangle are adjacent.

The selected cells in the new row form disjoint horizontal blocks. Each block contains exactly one column \(c_i\) whose new cell is selected. Indeed, the excluded columns alternate among the \(c_i\), the last column \(c_k\) is not excluded, and if \(c_1\) is excluded then it is the very first column of the rectangle.

Therefore each new block is a path attached to the old selected tree by exactly one vertical edge. Adding these blocks preserves connectedness and creates no cycle, so the enlarged selected graph is a tree.

Finally, the rightmost cell of the new row is selected, since every excluded column is strictly smaller than \(c_k\). This proves the induction. \(\square\)

Apply the lemma to the \(n\times n\) board. Let \(T\) have \(t\) cells, and choose a root in its tree.

Place the numbers \(1,\ldots,t\) in the cells of \(T\) in nondecreasing order of their distance from the root, breaking ties arbitrarily. Place the remaining numbers in the unselected cells in any order.

The root is a valley. Every other cell of \(T\) has exactly one smaller neighbour: its parent in the rooted tree. All its other neighbours in \(T\) are children, and every unselected neighbour has a number greater than \(t\). It follows, successively along the tree, that \[ p(v)=1\qquad(v\in T). \]

Every unselected cell \(w\) has all its neighbours in \(T\), and all these neighbours contain smaller numbers. Hence \[ p(w)=\deg(w). \]

There are no edges between unselected cells, while the tree on \(T\) has \(t-1\) edges. Therefore \[ \sum_{w\notin T}\deg(w)=E-(t-1). \] The total number of uphill paths in this construction is consequently \[ \sum_v p(v) =t+\sum_{w\notin T}\deg(w) =t+E-(t-1) =E+1 =2n(n-1)+1. \]

This attains the lower bound and proves the answer.

The solution was checked against the official IMO shortlist solutions.