In the following board, we must place all the numbers from 1 to 25, following these rules:

- In each row, the 5 numbers placed must form a strictly increasing sequence when read from left to right.
- In each column, the 5 numbers placed must form a strictly increasing sequence when read from top to bottom.

![](https://cdn.mathpix.com/cropped/2024_05_01_463eeeabc25d438954b1g-11.jpg?height=518&width=532&top_left_y=1430&top_left_x=839)

The main diagonal of the board is the diagonal painted in the graph.

a) Show that after placing the numbers, the smallest number placed on the main diagonal is always greater than or equal to 5, and the largest number placed on the main diagonal is greater than or equal to 15.

b) Place the numbers on the board so that on the main diagonal we find the numbers 5, 9, 12, 14, and 15.

c) Show that it is impossible to place the numbers so that the sum on the main diagonal is less than 55.
Solution

a) Let's place the following letters to represent the numbers placed on the board, as shown in the following figure:

| $M$ | $N$ | $P$ | $Q$ | $E$ |
| :---: | :---: | :---: | :---: | :---: |
| $R$ | $S$ | $T$ | $D$ |  |
| $U$ | $V$ | $C$ |  |  |
| $W$ | $B$ |  |  |  |
| $A$ |  |  |  |  |

Observe that, by the rules,

- $A$ is greater than the numbers $M, R, U$ and $W$.
- $B$ is greater than the numbers $M, R, U, W, N, S$ and $V$.
- $C$ is greater than the numbers $M, R, U, N, S, V, P$ and $T$.
- $D$ is greater than the numbers $M, N, P, Q, R, S$ and $T$.
- $E$ is greater than the numbers $M, N, P$ and $Q$.

We can thus conclude that any number on the main diagonal is always greater than at least 4 distinct numbers and, therefore, they are all greater than or equal to 5.

b) We can first place the following numbers to achieve the desired numbers on the main diagonal.

| 1 | 2 | 3 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 6 | 7 | 8 | 9 |  |
| 10 | 11 | 12 |  |  |
| 13 | 14 |  |  |  |
| 15 |  |  |  |  |

Finally, we fill in the rest of the cells, for example, in the following way:

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

c) Let's order the numbers $A, B, C, D$ and $E$ from smallest to largest, obtaining

$$
\alpha\theta$ and thus,

$$
\sigma \geq 15
$$

From $(*),(* *),(* * *),(\star)$ and $(\star \star)$, we get that

$$
A+B+C+D+E=\alpha+\beta+\gamma+\theta+\sigma \geq 5+9+12+14+15
$$