Международная олимпиада 2022, Осло, Норвегия, 2022 год

Пусть $n$ — целое положительное число. Нордическим квадратом будем называть любую таблицу $n \times n$, клетки которой заполнены числами от 1 до $n^2$ так, что каждое число использовано по одному разу и в каждой клетке записано ровно одно число. Две клетки назовем соседними, если у них есть общая сторона. Долиной назовем любую клетку, такую что во всех соседних с ней клетках записаны числа, большие чем в ней. Подъемом назовем последовательность, состоящую из не менее чем одной клетки, такую что
   1. первая клетка в последовательности — долина;
   2. каждая следующая клетка последовательности является соседней с предыдущей;
   3. числа, записанные в клетках последовательности, расположены в порядке возрастания.
   Для каждого заданного $n$ найдите наименьшее возможное количество всем подъемов в нордическом квадрате.

Комментарий/решение

Пусть V — количество долин в квадрате. Количество подъемов будет минимальным, когда структура таблицы максимально "упорядочена" и количество путей из долин к другим клеткам ограничено.

​Рассмотрим клетку с числом 1. Она всегда является долиной.

Любая клетка, соседняя с "1", образует подъем длины 2: (1, x). Таких соседей у клетки может быть от 2 (в углу) до 4 (в центре).

​Оценка количества

​Для каждой клетки c таблицы обозначим через f(c) количество подъемов, заканчивающихся в этой клетке.

​Если c — долина, то f(c) = 1 (подъем из одной этой клетки).

​Если c — не долина, то f(c) = \sum f(s_i), где s_i — все соседние клетки, в которых записаны числа меньше, чем в c.

​Чтобы минимизировать общую сумму всех f(c), нам нужно, чтобы у каждой клетки было как можно меньше соседей с меньшими числами. В идеале — ровно один.

​Если у каждой клетки (кроме одной долины с числом 1) есть ровно один сосед с меньшим числом, то структура подъемов превращается в дерево, корнем которого является число 1. В таком дереве количество подъемов (путей из корня) равно количеству узлов, то есть n^2.

​Можно ли достичь n^2?

​Да, если мы заполним таблицу "змейкой" или по спирали от 1 до n^2. В этом случае:

​Число 1 — единственная долина.

​Для любого числа k > 1, у него есть только один сосед меньше него (число k-1).

​Следовательно, для каждой клетки существует ровно один путь (подъем), ведущий в нее из долины 1.

​В такой конфигурации общее количество подъемов равно количеству клеток в таблице.

​Ответ

​Наименьшее возможное количество всех подъемов в нордическом квадрате n \times n равно n^2.

​Хотите, я покажу пример заполнения такой таблицы для n=3, чтобы наглядно продемонстрировать, почему подъемов будет именно 9?