2022 IMO Problems/Problem 6

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.

Video solution

https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems]

Solution

The minimum total number of uphill paths in a Nordic square is $2n(n-1)+1$

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 $2n(n-1)$ such adjacent pairs (each with at least one unique uphill path). 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 $2n(n-1)+1$ .

The diagram below shows a general family of constructions of Nordic squares that achieve 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 pathway of finite descent from each pair of adjacent cells is unique, and all terminate at the "1" valley, therefore the above-derived minimum is achieved. $\blacksquare$

- Griphomaniac (talk) 13:16, 21 July 2022 (EDT)

2022 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

2022 IMO Problems/Problem 6

Contents

Problem

Video solution

Solution

See Also