Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 (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 $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:

2022 IMO 6.png

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.

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_IMO_Problems/Problem_6&oldid=176199"