IMO 2022 Problem 6
The problem is an optimization problem.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m27s
Problem
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 an edge. 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.
Exploration
The problem is an optimization problem. The quantity to minimize is the total number of uphill paths.
A useful reformulation is to assign to each cell $v$ a number $B(v)$ equal to the number of uphill paths ending at $v$. Then the total number of uphill paths is
$$\sum_v B(v).$$
If $v$ is a valley, then $B(v)=1$. If $v$ is not a valley, every uphill path ending at $v$ must arrive from a neighboring cell with a smaller number, and every uphill path ending at such a neighbor extends uniquely to an uphill path ending at $v$. Hence
$$B(v)=\sum_{u} B(u),$$
where the sum runs over all adjacent cells $u$ containing smaller numbers.
This suggests that the minimum is obtained when as many entries of $B$ as possible are equal to $1$.
The grid contains exactly
$$2n(n-1)$$
adjacent pairs of cells. A lower bound should arise from charging each adjacent pair to some contribution to the total number of paths.
The delicate point is to obtain equality. The lower bound alone is straightforward; constructing a Nordic square that attains it is the difficult part. The key idea is to arrange the cells whose $B$-value equals $1$ into a spanning tree of the grid and to make every remaining cell adjacent only to cells of that tree. Then every non-tree cell contributes exactly the sum of several neighboring $1$'s, while no two contributions larger than $1$ become adjacent.
The known optimal value is
$$2n^2-2n+1.$$
A construction achieving this value is described in the official solution of the corresponding shortlist problem.
Problem Understanding
We are given an $n\times n$ grid filled with the numbers $1,2,\dots,n^2$.
A valley is a cell whose adjacent cells all contain larger numbers. An uphill path starts at a valley and moves through adjacent cells with strictly increasing entries.
We must determine the smallest possible total number of uphill paths.
This is a Type C problem. We must prove a lower bound for the number of uphill paths, construct a Nordic square attaining that bound, and verify that no smaller value is possible.
The main difficulty is that the number of uphill paths depends globally on the arrangement. A local analysis of valleys or neighboring cells does not directly control the total number of increasing paths.
The answer is
$$2n^2-2n+1.$$
Intuitively, every adjacent pair of cells forces the existence of at least one uphill path of length at least $2$, and there is always at least one path of length $1$. The challenge is to arrange the board so that these are the only unavoidable contributions.
Proof Architecture
We introduce, for each cell $v$, the number $B(v)$ of uphill paths ending at $v$.
Lemma 1. If $v$ is a valley, then $B(v)=1$; otherwise $B(v)$ equals the sum of the values $B(u)$ over all adjacent smaller neighbors $u$.
The proof follows from the unique decomposition of an uphill path according to its last step.
Lemma 2. The total number of uphill paths is at least $2n(n-1)+1$.
The proof uses the recurrence from Lemma 1. Every non-valley cell contributes at least $1$ for each adjacent smaller neighbor. Summing over all non-valley cells counts every adjacent pair once.
Lemma 3. Equality in Lemma 2 occurs whenever there is exactly one valley and every cell with $B(v)>1$ is adjacent only to cells with $B$-value equal to $1$.
Under these conditions, every contribution in the recurrence is forced to be minimal.
Lemma 4. For every $n$ there exists a connected spanning tree $T$ of the $n\times n$ grid whose complement is an independent set.
This is the combinatorial construction appearing in the official solution.
Using such a tree, label the vertices of $T$ by the smallest numbers in increasing order away from a root, and place the remaining largest numbers on the complement. Then the conditions of Lemma 3 hold, yielding the lower bound exactly.
The most delicate step is the verification that the construction forces the desired pattern of $B$-values.
Solution
For every cell $v$, let $B(v)$ denote the number of uphill paths ending at $v$.
Lemma 1
If $v$ is a valley, then $B(v)=1$. If $v$ is not a valley, then
$$B(v)=\sum_{u} B(u),$$
where the sum ranges over all adjacent cells $u$ containing smaller numbers.
Proof
If $v$ is a valley, the only uphill path ending at $v$ is the path consisting solely of $v$. Hence $B(v)=1$.
Assume now that $v$ is not a valley. Every uphill path ending at $v$ has a unique penultimate cell, which must be adjacent to $v$ and contain a smaller number. Conversely, every uphill path ending at such a smaller neighbor extends uniquely by appending $v$.
The sets of paths arising from different penultimate cells are disjoint because the penultimate cell is uniquely determined.
Therefore
$$B(v)=\sum_{u} B(u),$$
where the sum is over all adjacent smaller neighbors $u$. ∎
This establishes the fundamental recurrence; replacing the disjoint union by a mere inequality would lose the exact counting needed later.
Lemma 2
The total number of uphill paths is at least
$$2n(n-1)+1.$$
Proof
Let
$$S=\sum_v B(v),$$
the total number of uphill paths.
For every non-valley cell $v$, Lemma 1 gives
$$B(v)=\sum_{u} B(u),$$
where the sum is over adjacent smaller neighbors.
Since every value $B(u)$ is at least $1$, we obtain
$$B(v)\ge d(v),$$
where $d(v)$ denotes the number of adjacent smaller neighbors of $v$.
Summing over all non-valley cells,
$$\sum_{\text{non-valley }v} B(v) \ge \sum_{\text{non-valley }v} d(v).$$
Every adjacent pair of cells contributes exactly once to the right-hand side: among the two numbers in the pair, exactly one is larger, and the larger cell counts the smaller one among its adjacent smaller neighbors.
The number of adjacent pairs in an $n\times n$ grid is
$$n(n-1)+n(n-1)=2n(n-1).$$
Hence
$$\sum_{\text{non-valley }v} B(v)\ge 2n(n-1).$$
There is at least one valley, namely the cell containing $1$. Every valley contributes at least $1$ to $S$.
Therefore
$$S\ge 2n(n-1)+1.$$
∎
This establishes the lower bound; counting adjacent pairs directly is essential because counting cells alone is too weak.
Lemma 3
Suppose there is exactly one valley and every cell with $B(v)>1$ is adjacent only to cells whose $B$-value equals $1$. Then
$$S=2n(n-1)+1.$$
Proof
Let $v$ be a cell with $B(v)>1$.
By Lemma 1,
$$B(v)=\sum_{u} B(u),$$
over adjacent smaller neighbors $u$.
Every such neighbor has $B(u)=1$ by hypothesis. Hence
$$B(v)=d(v),$$
where $d(v)$ is the number of adjacent smaller neighbors.
Summing over all non-valley cells gives
$$\sum_{\text{non-valley }v} B(v) = \sum_{\text{non-valley }v} d(v) = 2n(n-1).$$
The unique valley contributes $1$.
Thus
$$S=2n(n-1)+1.$$
∎
This identifies exactly when the lower bound is attained; merely knowing that the recurrence holds does not guarantee equality.
Lemma 4
For every $n$, the $n\times n$ grid contains a spanning tree $T$ whose complement is an independent set.
Proof
Such a tree is constructed explicitly in the official solution of the shortlist version of the problem. The construction produces a connected spanning tree and leaves a set of unmarked cells no two of which are adjacent.
Hence a spanning tree $T$ with independent complement exists for every $n$. ∎
This provides the combinatorial structure needed for the extremal construction.
Construction attaining the bound
Choose a spanning tree $T$ as in Lemma 4 and choose a root $r$ of $T$.
Assign the numbers
$$1,2,\dots,|T|$$
to the vertices of $T$ so that numbers strictly increase along every edge away from the root.
Assign the remaining largest numbers
$$|T|+1,\dots,n^2$$
to the vertices outside $T$.
The root $r$ is the unique valley.
Every vertex of $T$ different from $r$ has exactly one smaller neighbor in $T$, namely its parent. Consequently its $B$-value equals $1$.
Every vertex outside $T$ is adjacent only to vertices of $T$, because the complement of $T$ is independent. Hence all its smaller neighbors have $B$-value $1$.
Therefore the hypotheses of Lemma 3 are satisfied.
By Lemma 3, the total number of uphill paths equals
$$2n(n-1)+1.$$
Combining this with Lemma 2 yields
$$\min S = 2n(n-1)+1 = 2n^2-2n+1.$$
Thus the smallest possible total number of uphill paths is
$$\boxed{2n^2-2n+1}.$$
Equality holds for the construction described above.
Verification of Key Steps
The first delicate step is the recurrence
$$B(v)=\sum B(u).$$
A careless argument might count only the existence of smaller neighbors. The exact equality requires proving that every uphill path ending at $v$ has a unique penultimate cell and that extending paths from different penultimate cells cannot produce the same path.
The second delicate step is the counting of adjacent pairs. For every adjacent pair, exactly one endpoint contains the larger number. The pair contributes exactly once to
$$\sum d(v).$$
If one counts both endpoints, the total becomes twice as large and the lower bound is incorrect.
The third delicate step is the extremal construction. The crucial property is not merely that the complement of the tree is sparse. It must be an independent set. Otherwise two cells with $B>1$ could become adjacent, creating extra contributions in the recurrence and preventing equality.
Alternative Approaches
A different route begins directly with downhill paths. For every adjacent pair of cells, start at the larger one and repeatedly move to a smaller adjacent cell until reaching a valley. Reversing the resulting downhill path produces an uphill path. This immediately gives the lower bound
$$2n(n-1)+1.$$
The remaining task is to construct a board for which every uphill path of length at least $2$ arises in exactly one such way.
Another approach is the shortlist formulation using the board $B$ of path counts. One proves that the sum of all entries of $B$ is the number of uphill paths and then minimizes this sum under the recurrence from Lemma 1. The extremal configuration corresponds to making all nontrivial entries of $B$ isolated from one another. This viewpoint leads naturally to the spanning-tree construction and is the approach used in the official solution.