5. What is the maximum number of cells that can be painted on a $6 \times 6$ board so that it is impossible to select four painted cells such that the centers of these cells form a rectangle with sides parallel to the sides of the board.

#
# Solution

Let $n$ be the number of cells that can be painted. Denote by $x_{1}, x_{2}, \ldots, x_{6}$ the number of painted cells in the 1st, 2nd, ..., 6th columns, respectively. Then $x_{1}+x_{2}+\ldots+x_{6}=n$. Let's count the number of pairs of cells in the columns that can form the sides of the desired rectangle. In the first column, there are $\frac{x_{1}(x_{1}-1)}{2}$ such pairs, and similarly in the others $\frac{x_{2}(x_{2}-1)}{2}, \ldots, \frac{x_{6}(x_{6}-1)}{2}$. Then the total number of such pairs is $\frac{x_{1}(x_{1}-1)}{2}+\ldots+\frac{x_{6}(x_{6}-1)}{2}=\frac{x_{1}^{2}+\ldots+x_{6}^{2}}{2}-\frac{x_{1}+\ldots+x_{6}}{2} \geq \frac{1}{2} \frac{(x_{1}+\ldots+x_{6})^{2}}{6}-\frac{n}{2}=$ $=\frac{n^{2}}{12}-\frac{n}{2}=\frac{n^{2}-6 n}{12} \cdot$ Each such pair corresponds to a pair of rows in which they lie, and there are a total of such pairs $C_{6}^{2}=\frac{6!}{2!4!}=15$. Then if $\frac{n^{2}-6 n}{12}>15$, two different pairs of painted cells in different columns will correspond to the same pair of rows, and the four found cells will form the desired rectangle. Therefore, $\frac{n^{2}-6 n}{12}<15$, solving the inequality we get that $n \leq 16$. For $n=16$, the cells can be painted as follows:

![](https://cdn.mathpix.com/cropped/2024_05_06_80ed060e188e62f2da87g-4.jpg?height=268&width=372&top_left_y=282&top_left_x=97)

## Recommendations for Checking

1) Proven only that $n \leq 16$ - 4 points.
2) Only an example for $n=16$ is provided - 3 points.