5. What is the maximum number of cells in an $8 \times 8$ square that can be colored so that the centers of any four colored cells do not form the vertices of a rectangle with sides parallel to the edges of the square?
Answer: 24 cells.

Solution: Suppose that no less than 25 cells are marked. We will say that a pair of marked cells in the same row covers a pair of columns in which these cells are located. A prohibited quartet arises when a pair of columns is covered twice. If in one row there are $m$ marked cells, and in another $n>m+1$ marked cells, then by moving one marked cell from the second row to the first, the number of covered pairs in the first row will increase by $m$, and in the second row it will decrease by $n-1>m$, i.e., the total number of pairs will decrease. Thus, the minimum number of pairs for a given number of marked cells is achieved when the maximum number of cells in a row differs from the minimum by no more than 1. Let's consider two cases.

1) There is a column in which no more than two cells are marked. Let's strike it out, in which case seven columns will remain, i.e., 21 pairs. One of the possible distributions of 23 cells is seven rows with three cells and one row with two cells, which gives $7 \cdot 3+1=22$ marked pairs. By the pigeonhole principle, there will be a pair of columns covered twice. As shown above, with a different distribution of marked pairs, there will be more.
2) In each column, no fewer than three cells are marked. Since $8 \cdot 3<25$, there will be a row in which no fewer than four cells are marked. Let these be the first four cells in the bottom row. Above them, in each of the first four columns, there are at least two more cells - a total of at least eight. They are located in seven rows, therefore, two of them are in the same row. Together with the corresponding cells in the bottom row, they form a prohibited quartet. An example for 24 cells is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_370ded968c2be58e7d26g-6.jpg?height=434&width=436&top_left_y=2284&top_left_x=1481)