
Problem 9.3. All natural numbers from 1 to 1998 inclusive are written 9 times (so that there are 9 ones, 9 twos and so on) in the
cells of a rectangular table with 9 rows and 1998 collumns, so that the difference between any two elements lying in one and the same column is no greater than 3 . Find the maximum possible value of the smallest sum amongst all 1998 sums of the elements lying in one and the same column.


Solution: Consider the placement of the ones in the columns. If they are all in a single column, then the minimum sum of elements lying in one column is 9 . Let all ones lie in exactly 2 columns. Therefore there are at least 5 ones in a single column and thus the minimal sum is no greater that $5 \cdot 1+4 \cdot 4=21$. If all ones are placed in exactly 3 columns, then the sum of all numbers in these three columns is at most $9 \cdot 1+9 \cdot 4+9 \cdot 3=72$. Hence the minimal sum is at most $72: 3=24$. If all ones are placed in exactly 4 columns, then the sum of all numbers in these columns is at most $9 \cdot 1+9 \cdot 4+9 \cdot 3+9 \cdot 2=90$ and therefore the minimal sum is at most $90: 4$, i.e., 22 . It is impossible to have ones in more than 4 columns, because in that case the total number of $2 \mathrm{~s}, 3 \mathrm{~s}$ and $4 \mathrm{~s}$ does not suffice to fill the remaining cells. Therefore the required sum is at most 24 .

|  | 1 | 1 | 1 | 2 | 2 | 2 | 7 | 8 | $\ldots$ | 1998 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
|  | 1 | 1 | 1 | 2 | 2 | 2 | 7 | 8 | $\ldots$ | 1998 |
| The following example | 1 | 1 | 1 | 2 | 2 | 2 | 7 | 8 | $\ldots$ | 1998 |
| shows that this sum can | 3 | 3 | 3 | 5 | 5 | 5 | 7 | 8 | $\ldots$ | 1998 |
| be 24, consequently the | 3 | 3 | 3 | 5 | 5 | 5 | 7 | 8 | $\ldots$ | 1998 |
| answer is 24: | 3 | 3 | 3 | 5 | 5 | 5 | 7 | 8 | $\ldots$ | 1998 |
|  | 4 | 4 | 4 | 6 | 6 | 6 | 7 | 8 | $\ldots$ | 1998 |
| 4 | 4 | 4 | 6 | 6 | 6 | 7 | 8 | $\ldots$ | 1998 |  |
|  | 4 | 4 | 4 | 6 | 6 | 6 | 7 | 8 | $\ldots$ | 1998 |
