Олимпиада имени Леонарда Эйлера 2025-2026 учебный год, I тур регионального этапа

В электронную таблицу, где две строки и $n$ столбцов, в произвольном порядке записаны все натуральные числа от 1 до $2n$ (в каждой клетке — одно число). В полдень каждого дня компьютер случайным образом выбирает столбец, где число из верхней строки больше числа из нижней, и меняет эти два числа местами, а затем случайным образом переставляет числа в верхней строке. В момент, когда в каждом столбце верхнее число оказывается меньше нижнего, процесс заканчивается. Докажите, что такой процесс не может происходить дольше, чем $n^2$ дней. ( М. Магин, Р. Баринов )

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

Пусть $S$ сумма всех чисел, расположенных в верхней строке таблицы.

В полдень выбирается столбец, где верхнее число $a$ больше нижнего $b$ ($a > b$). После их обмена в верхнюю строку вместо $a$ попадает $b$. Следовательно, новая сумма $S'$ будет равна $S - (a - b)$. Так как $a$ и $b$ различные натуральные числа и $a > b$, то $a - b \ge 1$. Таким образом, сумма $S$ уменьшается как минимум на 1 каждый день.

Последующая случайная перестановка чисел внутри верхней строки не меняет их набор, а значит, оставляет сумму $S$ неизменной.

Максимально возможное значение суммы $S$ достигается, когда в верхней строке стоят $n$ наибольших чисел (от $n+1$ до $2n$):

$$S_{max} = (n+1) + (n+2) + \dots + 2n = \frac{(n+1 + 2n)n}{2} = \frac{3n^2 + n}{2}$$

Минимально возможное значение $S$ достигается, когда в верхней строке стоят $n$ наименьших чисел (от 1 до $n$):

$$S_{min} = 1 + 2 + \dots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2}$$

Процесс завершится, когда в каждом столбце верхнее число станет меньше нижнего. Это гарантированно произойдет не позже, чем сумма $S$ уменьшится от своего максимума до минимума. Максимальное количество шагов (дней) $D$:

$$D \le S_{max} - S_{min} = \frac{3n^2 + n}{2} - \frac{n^2 + n}{2} = \frac{2n^2}{2} = n^2$$