Vasiniev N. 5.

Let $k$ and $n$ be natural numbers, $k \leq n$. Arrange the first $n^2$ natural numbers in an $n \times n$ table so that the numbers in each row are in increasing order, and at the same time, the sum of the numbers in the $k$-th column is a) the smallest; b) the largest.
a) Example. If the numbers are arranged as shown in the table - first filling the first $k$ columns, row by row, with numbers from 1 to $k n$, and then filling the remaining $n-k$ columns with the remaining numbers (in any order, as long as the condition of increasing numbers in each row is met) - then the sum of the numbers in the $k$-th column will be equal to $1 / 2 k n(n+1)$.

$$
\begin{array}{|rrrr|r|rr|}
\hline 1 & 2 & \ldots & k-1 & k & n k+1 & \ldots \\
k+1 & k+2 & \ldots & 2 k-1 & 2 k & & \\
2 k+1 & 2 k+2 & \ldots & 3 k-1 & 3 k & & \\
\ldots & \ldots & \ldots & \ldots & & & \\
(n-1) k+1 & \ldots & \ldots & n k-1 & n k & \ldots & n^{2} \\
\hline
\end{array}
$$

Estimate. Let $a_{1}, a_{2}, \ldots, a_{n}$ be the numbers in the $k$-th column, numbered in ascending order: $a_{1}<a_{2}<\ldots<a_{n}$. Consider the numbers that stand in the same rows as $a_{1}, a_{2}, \ldots, a_{i}$ and in the first $k$ columns. These $k i$ numbers do not exceed $a_{i}$, so $a_{i} k_{i} i=1,2, \ldots, n$, we get

$a_{1}+a_{2}+\ldots+a_{n} \geq 1 / 2 k n(n+1)$

b) Replace each number $a$ in the table with ($n^{2}+1-a$) and then reverse the order of the numbers in each row. Clearly, this is a one-to-one transformation of the set of tables of numbers $1,2, \ldots, n^{2}$ that satisfy the condition of the problem. Under this transformation, each number in the $k$-th column of the new table $A^{\prime}$ is equal to the number in the same row and in the ($n+1-k$)-th column of the old table $A$; therefore, the sum of the numbers in the $k$-th column of the table $A^{\prime}$ is equal to $n\left(n^{2}+1\right)-S$, where $S$ is the sum of the numbers in the ($n+1-k$)-th column of $A$. Therefore, it is sufficient to solve part a) for the column with number $n+1-k$. Consequently, the maximum sum in the $k$-th column is $n\left(n^{2}+1\right)-1 / 2(n+1-$ $k) n(n+1)=1 / 2 n\left((n-1)^{2}+k(n+1)\right)$

## Answer

a) $1 / 2 k n(n+1)$;
b) $1 / 2 n\left((n-1)^{2}+k(n+1)\right)$.

Submit a comment