|
|
 |
Условие
В таблице $n\times n$ стоят все целые числа от 1 до $n^2$, по одному в клетке. В каждой строке числа возрастают слева направо, в каждом столбце – снизу вверх. Докажите, что наименьшая возможная сумма чисел на главной диагонали, идущей сверху слева вниз направо, равна $1^2+2^2+\ldots+n^2$.Решение
Будем называть лесенкой следующую часть таблицы из $n+(n-1)+\ldots+1$ клеток: самый левый столбец, следующий столбец без верхнего числа, следующий столбец без двух верхних чисел, ..., самый правый столбец без верхних $n-1$ чисел.
Пример. Двигаясь от самого левого столбца лесенки к самому правому, заполняем их снизу вверх числами 1, 2, ... по возрастанию: в первом столбце лесенки будут стоять числа от $1$ до $n$, во втором – от $n+1$ до $2n-1$ и т.д. Заполнив лесенку, заполняем оставшиеся клетки таблицы по тому же принципу: двигаясь от самого левого столбца таблицы к самому правому, заполняем их снизу вверх оставшимися числами по возрастанию. Тогда таблица будет удовлетворять условию, а сумма чисел на главной диагонали будет равна $$n+[n+(n-1)]+[n+(n-1)+(n-2)]+\ldots +[n+\ldots +1]=n^2+(n-1)^2+\ldots +2^2+1^2,$$ что и требуется.
Оценка. Первый способ. Пусть $a_1 < a_2 < \dots < a_n$ – числа на главной диагонали (порядок, в котором они там стоят, нам неизвестен). Для каждого $a_k$ покрасим само $a_k$ и все числа, стоящие либо под $a_k$ в том же столбце, либо слева от $a_k$ в той же строке, в цвет номер $k$. Тогда чисел каждого цвета будет ровно $n$, и каждое число лесенки, кроме чисел главной диагонали, будет покрашено ровно в два цвета – «цвет строки» и «цвет столбца» (а каждое число на главной диагонали – только в один свой цвет).
Заметим, что $a_k$ больше всех остальных чисел цвета $k$ и больше всех чисел, цвет которых имеет номер меньше $k$ (так как $a_k > a_{k-1} > \ldots > a_1$). Тем самым $a_k$ не меньше, чем количество чисел с цветами от 1 до $k$. Но таких чисел ровно $n+(n-1)+\ldots+(n-(k-1))$, поскольку чисел цвета 1 – ровно $n$, чисел цвета 2, но не цвета 1, – ровно $n-1$, ..., чисел цвета $k$, но ни одного из цветов $1, 2, \ldots, k-1$, – ровно $n-(k-1)$.
Отсюда $a_1+\ldots+a_n\geqslant n+[n+(n-1)]+\ldots+ [n+(n-1)+\ldots+2+1]=n^2+(n-1)^2+\ldots+1^2$.
Второй способ. Пусть $a_1 < a_2 < \dots < a_n$ – числа на главной диагонали. Рассмотрим некоторое $a_k$. Если число из лесенки находится в одной строке или в одном столбце с одним из диагональных чисел $a_1, a_2, \dots, a_k$, то оно не превосходит его, и значит, не превосходит $a_k$, числа $x > a_k$ могут находиться только в строках и столбцах с числами $a_{k+1}, \ldots, a_n$ – таких чисел всего $1+2+\ldots + (n-k)$. Все остальные $(n+k+1)+\ldots +n$ чисел лесенки не больше $a_k$, то есть $a_k\geq (n+k+1)+\ldots +n$. Складывая, получаем точную оценку на $a_1+a_2+\ldots +a_n$.
Третий способ. Пронумеруем все диагонали, параллельные главной и лежащие не выше её, числами от $1$ до $n$ снизу вверх. Пусть $a_1 < a_2 < \dots < a_n$ – числа на главной диагонали. Проведём из чисел $a_1,a_2,\dots,a_{n-1}$ единичные стрелки влево или вниз в клетки $(n-1)$-й диагонали (это, очевидно, возможно). Из $a_n$ же проведём одну из двух стрелок на $(n-1)$-ю диагональ.
Далее действуем аналогично. Именно, пусть мы уже провели стрелки в клетки $k$-й диагонали так, что пути по стрелкам из $a_1,\dots,a_k$ не имеют общих клеток. Берём клетки $k$-й диагонали, в которые приходят пути из $a_1,\dots,a_{k-1}$, и проводим из них стрелки в клетки $(k-1)$-й диагонали. Из оставшейся клетки проводим любую стрелку на $(k-1)$-ю диагональ.
Теперь нетрудно доказать оценку. Из клеток $a_1,\ldots,a_k$ ведут $k$ путей, причём их начала длины $n,n-1,\ldots,n-k+1$ соответственно не имеют общих клеток. Число $a_k$ не меньше всех чисел, встречающихся на этих путях; поэтому $a_k\geq n+(n-1)+\ldots+(n-k+1)$. Суммируя, получаем $$ a_1+\ldots+a_n\geq n+(n+(n-1))+\ldots+(n+(n-1)+\ldots+1) =n\cdot n+(n-1)\cdot (n-1)+\ldots+1\cdot 1. $$ Замечание. Это же решение можно оформить по-другому. Рассмотрим только расстановку различных натуральных чисел в диагоналях $1,2,\ldots,n$. Докажем, что если в каждой диагонали поставить числа сверху вниз по возрастанию, то расстановка чисел в этом треугольнике по-прежнему будет удовлетворять условиям. Для этого, если $b_1 < \dots < b_k$ и $c_1 < \dots < c_{k-1}$ – числа в $k$-й и $(k-1)$-й диагоналях, надо доказать, что $b_i\geq c_i$ при всех $i=1,2,\dots,k-1$. Это доказывается, например, тем же проведением стрелок; есть и другие способы.
После этого в новой расстановке число $a_k$ не меньше, чем все числа в первых $k$ столбцах треугольника, то есть $a_k\geq n+(n-1)+\ldots+(n-k+1)$, откуда и следует оценка.
