2022 IMO Problems/Problem 6

Problem

Let be a positive integer. A Nordic square is an board containing all the integers from to 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 , the smallest possible total number of uphill paths in a Nordic square.

Solution

The minimum total number of uphill paths in a Nordic square is

Proof: For every pair of adjacent cells in the grid, there is at least one pathway that begins at the higher valued cell, steps to the lower valued cell, and then continues stepping to lower adjacent cells until (by finite descent) a valley is reached. When reversed, this forms an uphill pathway that terminates at that exactly that pair of adjacent cells

There are such adjacent pairs (and therefore unique uphill paths). In addition, the cell containing the value 1 will always be a valley which, by itself, forms an additional (singleton) uphill path. Therefore the minimum total number of uphill paths is at least .

The diagram below shows families of constructions of Nordic square that achieves this lower bound, thus proving the claim:

In these constructions, numbers are progressively inserted into the white spaces in ascending order emanating outwards from the "1" in the corner in the directions of the red arrows, and the remaining j largest numbers are then inserted into the cells labelled as "mountains". In this manner, the pathways of finite descent that originate from each pair of adjacent cells is unique and all terminate at the "1" valley - Griphomaniac (talk) 13:16, 21 July 2022 (EDT)