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.

Author: Nikola Petrović

==============================

Solution:

The total number of uphill sequences can be counted in another way as downhill sequences: starting from each cell, keep going down to a lower neighbor until reaching a valley. Let $a_i$ be the number of downhill sequences starting from cell of height $i$. We can count the sequences of a Nordic board as we build it in the following way. 

Starting from an empty Nordic board, pick a cell to have height $1$ and write down $a_1$, then pick another to have height $2$ and write down $a_2$, and so on until the Nordic board is completed. The rule for $a_i$ is: sum up all existing $a_j$s adjacent to the cell of height $i$, or if all neighbors are empty then $a_i=1$ (meaning that the cell is a valley). What is the minimum of $S=a_1+a_2+\ldots+a_{n^2}$?

There are $2n(n-1)$ pairs of unordered adjacent cells, each contributing at least $1$ to $S$. Moreover as we write down $a_1=1$, it doesn't have contribution from any pair of unordered adjacent cells. Thus $S\geq 2n(n-1)+1$. What is the condition for equality? There are two sub-conditions:

(i) Except for $a_1$, all $a_i$s that are equal to $1$ are adjacent to exactly one other $1$ when written down.

(ii) All $a_i$s larger than $1$ are adjacent to only $1$s and no empty cells or $a_j$s larger than $1$ when written down.

This translates to the following operation. Starting from an empty $n\times n$ board, mark some of its cells one by one such that all marked cells (except for the first one) are adjacent to exactly one marked cell when marked, and when done there are no adjacent unmarked cells. If this is possible, then the minimum is $2n(n-1)+1$. Below we prove that it's always possible.

Proof:

We will mark the cells row by row. We begin with the first row, where all are marked and only the leftmost and rightmost can be skipped. In the second row we mark every other cell. Below are possible outcomes of the first two rows where $1$ denotes marked cell and $0$ is unmarked.

$\begin{array} {ccccc} 0&1&1&1&1 \\ 1&1&0&1&0\\ \end{array}$

Starting from the third row, we proceed from one end where the previous row has $0$ to the other end in the only possible way. In the example below we only show the previous and current rows, and the current row is marked in red.

$\begin{array} {cccccccccccc} 0&1&1&0&1&0&1&1&1&0&1&1 \\ \color{red}{1}&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ \end{array}$

If the previous row has $1$ at both ends, then proceed from either end to the other in one of two possible ways, for example:

$\begin{array} {cccccccccccc} 1&1&1&0&1&0&1&1&1&1&1&1 \\ \color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1\\ \end{array}$

or

$\begin{array} {cccccccccccc} 1&1&1&0&1&0&1&1&1&1&1&1 \\ \color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}0\\ \end{array}$

The only time things may go wrong is when both ends of the previous row is $0$, for example the operation could not succeed in this example.

$\begin{array}{cccc}0&1&1&0\\ \color{red}1&\color{red}?&\color{red}?&\color{red}1\\ \end{array}$

However, this can be avoided. We can have $1$ at both ends of the second row and then proceed. At every new row, if the previous row has $1$ at exactly one end, then the other end of the current row will be $1$. If the previous row has $1$ at both ends, then at least one of the two possible ways of marking the current row avoids $0$ at both ends. By induction, no row would have $0$ at both ends.

$\diamond$