5. The natural numbers $1,2, \ldots, 64$ are written in the cells of an $8 \times 8$ table such that for all $k=1,2,3, \ldots, 63$ the numbers $k$ and $k+1$ are in adjacent cells. What is the maximum possible value of the sum of the numbers on the main diagonal?
5. The natural numbers $1,2, \ldots, 64$ are written in the cells of an $8 \times 8$ table such that for all $k=1,2,3, \ldots, 63$ the numbers $k$ and $k+1$ are in adjacent cells. What is the maximum possible value of the sum of the numbers on the main diagonal?

Answer: 432.

Estimate. We color the cells of the table in a checkerboard pattern so that the cells on the chosen main diagonal are white. Without loss of generality, we can assume that the number 1 is not above the diagonal. We find the maximum value of the smallest number that falls on the diagonal. Since adjacent numbers are in cells of different colors, and there are only 12 white cells below the diagonal, one of the numbers from 1 to 26 must fall on the diagonal. The remaining numbers on the diagonal are guaranteed to have the same parity, so their sum does not exceed the sum of the even numbers from 52 to 64. Therefore, we conclude that the sum of the numbers on the diagonal has an upper bound:

$$
26+52+54+56+58+60+62+64=432
$$

An example of a suitable arrangement of numbers is shown in Fig. 6.

| 52 | 51 | 50 | 49 | 44 | 43 | 34 | 33 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 53 | 54 | 55 | 48 | 45 | 42 | 35 | 32 |
| 6 | 7 | 56 | 47 | 46 | 41 | 36 | 31 |
| 5 | 8 | 57 | 58 | 59 | 40 | 37 | 30 |
| 4 | 9 | 16 | 17 | 60 | 39 | 38 | 29 |
| 3 | 10 | 15 | 18 | 61 | 62 | 63 | 28 |
| 2 | 11 | 14 | 19 | 22 | 23 | 64 | 27 |
| 1 | 12 | 13 | 20 | 21 | 24 | 25 | 26 |

Fig. 6: to the solution of problem 5.

## Criteria

+ Correct solution - 7 points.

$\pm$ Correct upper bound on the sum of the numbers on the diagonal is proven - 4 points.

干 A correct example of an arrangement with the maximum sum of numbers on the diagonal is provided - 3 points.

- Correct answer without further progress - 1 point.