8. (5 points) In the cells of a $(2 k+1) \times(2 n+1)$ table, where $k \leqslant n$, the numbers 1, 2, and 3 are arranged such that in any $2 \times 2$ square, there are all three different numbers. What is the maximum value that the sum of the numbers in the entire table can take?
Answer: $9 k n+6 n+5 k+3$.

## Solution:

Throughout the solution, the first of the specified sides of the rectangle will be horizontal, and the second will be vertical.

We will prove this estimate by induction on $k+n$. As the base case, consider a strip $(2 n+1) \times 1$ (for $k=0$). For this strip, the sum of the numbers is obviously no more than $6 n+3$, i.e., three times the number of cells.

Now we will prove the inductive step. Consider the top-left $2 \times 2$ square of the rectangle $(2 n+1) \times(2 k+1)$. In it, there are at least two non-threes, and at least one of them is on the side or in the corner of the rectangle. We will call this cell the marked cell.

First case: $n>k$ and the marked cell is on the long (horizontal) side of the rectangle (possibly in the corner). We will divide the rectangle into three parts:

1) A rectangle $2 \times 1$ containing the marked cell and the corner cell. In this rectangle, the sum of the numbers is no more than $2+3=5$, since at least one of the cells contains a non-three.
2) A rectangle $2 \times 2 k$ below the first rectangle. This, in turn, can be divided into $k$ squares $2 \times 2$, in each of which the sum is no more than 9.
3) The remaining rectangle $(2(n-1)+1) \times(2 k+1)$. Since $n>k, n-1 \geqslant k$, we can apply the inductive hypothesis to this rectangle. Therefore, the sum of the numbers in it is no more than $9(n-1) k+6(n-1)+5 k-3=9 k n+6 n-4 k-3$.

The total sum of the numbers is no more than $5+9 k+9 k n+6 n-4 k+3=9 k n+6 n+5 k+2$.

Second case: $n>k$ and the marked cell is on the short (vertical) side of the rectangle. We will divide the rectangle into three parts:

1) A rectangle $1 \times 2$ containing the marked cell and the corner cell. In this rectangle, the sum of the numbers is no more than $2+3=5$, since at least one of the cells contains a non-three.
2) A rectangle $2 n \times 2$ to the left of the first rectangle. This, in turn, can be divided into $n$ squares $2 \times 2$, in each of which the sum is no more than 9.
3) The remaining rectangle $(2 n+1) \times(2(k-1)+1)$. Since $n>k$, the inequality $n \geqslant k-1$ also holds, and we can apply the inductive hypothesis to this rectangle. Therefore, the sum of the numbers in it is no more than $9 n(k-1)+6 n+5(k-1)+3=$ $9 k n-3 n+5 k-2$.

The total sum of the numbers is no more than $5+9 n+9 k n-3 n+5 k-2=9 k n+6 n+5 k+3$.

Finally, the third case $k=n$. Without loss of generality, we can assume that the marked cell is on the vertical side of the rectangle. We will divide the rectangle into three parts:

1) A rectangle $1 \times 2$ containing the marked cell and the corner cell. In this rectangle, the sum of the numbers is no more than $2+3=5$, since at least one of the cells contains a non-three.
2) A rectangle $2 k \times 2$ to the left of the first rectangle. This, in turn, can be divided into $k$ squares $2 \times 2$, in each of which the sum is no more than 9.
3) The remaining rectangle $(2 k+1) \times(2(k-1)+1)$. Since $k \geqslant k-1$, we can also apply the inductive hypothesis to this rectangle. Therefore, the sum of the numbers in it is no more than $9 k(k-1)+6 k+5(k-1)+3=9 k^{2}+2 k-2$.

$5+9 k+9 k^{2}+2 k-2=9 k^{2}+11 k+3$, as required.

Thus, the estimate is proved.

The example is constructed as follows: $n+1$ horizontal lines, starting from the top and skipping one, are filled with threes. The remaining horizontal lines are filled with alternating twos and ones, starting with a two.