Authors: Bogdanov I.I., Chennokov G.R.

In a rectangular table with 9 rows and 2004 columns, the numbers from 1 to 2004 are arranged, each appearing 9 times. In each column, the numbers differ by no more than 3. Find the minimum possible sum of the numbers in the first row.
Evaluation. By rearranging the columns if necessary, we will henceforth assume that the numbers in the first row are in non-decreasing order. Let $a_{i}$ be the $i$-th number in the first row. Consider the sum $S=\left(a_{1}-1\right)+\left(a_{2}-1\right)+\left(a_{3}-1\right)+$ $\left(a_{4}-2\right)+\ldots+\left(a_{i}-(i-2)\right)+\ldots+\left(a_{2003}-2001\right)+\left(a_{2004}-2001\right)$

We will prove that $S \geq 0$. Denote the $i$-th term in our sum by $d_{i}$. If there are no negative terms in this sum, everything is obvious. Clearly, $a_{2004} \geq 2001, a_{2} \geq a_{1} \geq 1$, so $d_{1}, d_{2}, d_{2004} \geq 0$.

Let $d_{i} < 0$.

Thus, for any negative $d_{i}$, the sum of it with the next term is positive, so by combining such terms in pairs, we obtain a sum of non-negative terms.

Therefore, $a_{1}+a_{2}+\ldots+a_{2004} \geq 1+1+1+2+\ldots+2001+2001=2003 \cdot 2002: 2+1=2005004$.

Example of a table for which the estimate is achieved:

|  |  |  |  |  | $k$ |  |  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2 | $\overline{4}$ |  | . | $\cdots$ | +2 |  |  |  |  |  |  |
|  | $\bar{A}$ |  |  | $\cdots$ | +2 |  |  |  |  |  |  |
|  | $\overline{4}$ | 4 | I. | $\cdots$ | $k+2$ | $\cdots$ | 2000 | 2001 | zou |  |  |
|  | $\bar{A}$ |  |  | $\cdots$ | +2 | ... | 2000 | 2001 | 2002 |  |  |
|  | I |  |  | $\cdots$ | $k+2$ | $\cdots$ |  | 2001 |  |  |  |
|  |  |  |  | $\cdots$ | $k+2$ | $\cdots$ |  | 2002 |  |  |  |
|  |  |  |  | $\cdots$ | $k+3$ | $\cdots$ |  | 2002 | onn: |  |  |
|  |  |  |  |  | $k+3$ |  | 901 | 00 |  |  |  |

(The first two and the last four columns are arranged slightly differently than the others).

## Answer

2005004