Олимпиада имени Леонарда Эйлера 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$$