Problem 11.8. In a $28 \times 35$ table, some $k$ cells are painted red, another $r-$ in pink, and the remaining $s-$ in blue. It is known that

- $k \geqslant r \geqslant s$
- each boundary cell has at least 2 neighbors of the same color;
- each non-boundary cell has at least 3 neighbors of the same color.

What is the smallest value that the quantity $k-s$ can take?

(A cell is called boundary if it is adjacent to the edge of the table. Neighbors are cells that share a common side.)
Answer: 28.

Solution. From the condition, it is easy to understand that each cell can have no more than one neighbor of a different color.

We will prove that the coloring of the table must be "striped," meaning that either each row or each column is completely colored in one color. To do this, it is sufficient to show that either all pairs of adjacent cells of different colors are horizontal neighbors, or all such pairs are vertical neighbors.

![](https://cdn.mathpix.com/cropped/2024_05_06_28b5ece3789ad9441c8ag-6.jpg?height=313&width=259&top_left_y=401&top_left_x=597)

Fig. 17: Solution to problem 11.8

Consider any pair of adjacent cells of different colors - if there are cells of different colors in the table, such a pair will exist. The other neighbors of these cells match their colors, so the boundary separating the colors will continue in both directions (Fig. 17), and further, until it reaches the edges of the table.

This means that any boundary between different colors must run from edge to edge of the table, and on each side of it will be a strip of cells of the same color. But this means that vertical and horizontal boundaries cannot coexist simultaneously. Therefore, either all boundaries are horizontal, or all boundaries are vertical, and the coloring is "striped" in any case. (The width of each strip should be at least 2 cells - however, this does not matter for the solution.)

This means that either the number of cells of each color is divisible by the height of the table, or by its width, as is the difference $k-s$. On the other hand, this difference cannot be equal to 0, because in this case $k=r=s$ and the total number of cells is $3k$, but the number $28 \cdot 35$ is not divisible by 3. Therefore, $k-s \geqslant 28$ or $k-s \geqslant 35$.

The equality $k-s=28$ is possible if the red cells occupy 12 columns (28 cells each), the pink cells occupy the same number, and the blue cells occupy 11 columns. If the columns of one color are placed together, all the conditions of the problem will be satisfied.