Each of the numbers $1,2,3 \ldots, 25$ is arranged in one of the cells of a $5 \times 5$ board. In each row, they appear in increasing order, from left to right. Find the maximum and minimum possible values for the sums of the numbers in the third column.
Solution

We can number the rows and columns of the board with the numbers from 1 to 5, from top to bottom and from left to right. Additionally, we can denote the number written in the row numbered $i$ and the column numbered $j$ by $a_{ij}$, as indicated in the figure below:

| $a_{11}$ | $a_{12}$ | $a_{13}$ | $a_{14}$ | $a_{15}$ |
| :--- | :--- | :--- | :--- | :--- |
| $a_{21}$ | $a_{22}$ | $a_{23}$ | $a_{24}$ | $a_{25}$ |
| $a_{31}$ | $a_{32}$ | $a_{33}$ | $a_{34}$ | $a_{35}$ |
| $a_{41}$ | $a_{42}$ | $a_{43}$ | $a_{44}$ | $a_{45}$ |
| $a_{51}$ | $a_{52}$ | $a_{53}$ | $a_{54}$ | $a_{55}$. |

In each row $i$, we know that

$$
a_{i1} < a_{i2} < a_{i3} < a_{i4} < a_{i5}
$$

Notice that if we swap the positions of two rows, the property above remains true and the sum of the elements in each column remains the same. Thus, by performing swaps between the rows until the elements of the third column are in ascending order from top to bottom, the problem reduces to calculating the maximum and minimum sums of the elements of the third column for this configuration of the board. To estimate the maximum sum, notice that $a_{53}$ is at most 23, since $a_{53} < a_{54} < a_{55}$. There are at least 5 integers on the board greater than $a_{43}$, namely, $a_{44}, a_{45}, a_{53}, a_{54}$, and $a_{55}$. Therefore, the maximum value of $a_{43}$ is 20. Since $a_{33} < a_{34} < a_{35}$, $a_{33} < a_{43}$, and there are at least 5 integers greater than $a_{43}$, there are at least 8 integers on the board greater than $a_{33}$, and thus its value is at most 17. We will repeat this argument two more times, using that:

$$
\begin{aligned}
& a_{23} < a_{24} < a_{25} \\
& a_{23} < a_{33}
\end{aligned}
$$

and

$$
\begin{aligned}
& a_{13} < a_{14} < a_{15} \\
& a_{13} < a_{23}
\end{aligned}
$$

to conclude that there are at least 11 integers greater than $a_{23}$ and 14 integers greater than $a_{13}$. Therefore, $a_{23}$ is at most 14 and $a_{13}$ is at most 11. This shows that the sum of the elements of the third row is at most

$$
23 + 20 + 17 + 14 + 11 = 85
$$

It remains to show that this estimate can actually be achieved. It suffices to exhibit a configuration of the board satisfying the mentioned rules, as shown by the board on the left in the next figure.

| 1 | 6 | 11 | 12 | 13 |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 7 | 14 | 11 | 16 |
| 3 | 8 | 17 | 18 | 19 |
| 4 | 9 | 20 | 21 | 22 |
| 5 | 10 | 23 | 24 | 25 |

| 1 | 2 | 3 | 16 | 21 |
| :---: | :---: | :---: | :---: | :---: |
| 4 | 5 | 6 | 17 | 22 |
| 7 | 8 | 9 | 18 | 23 |
| 10 | 11 | 12 | 19 | 24 |
| 13 | 14 | 15 | 20 | 25 |

To estimate the minimum sum, notice that at least two elements, namely, $a_{11}$ and $a_{12}$, are less than $a_{13}$. Therefore, $a_{13}$ is at least 3. Next, repeating the previous strategy, there are at least 5, 8, 11, and 14 elements on the board that are less than $a_{23}$, $a_{33}$, $a_{43}$, and $a_{53}$, respectively. Thus, the minimum sum of the elements of the third column is

$$
3 + 6 + 9 + 12 + 15 = 45
$$

To show that this sum is actually possible, it suffices to see the board on the right in the last figure.