8.4. In an $n \times n$ grid, each cell is colored either white or black. For what smallest $n$ is it always true (i.e., for any coloring) that there exists a rectangle whose vertices coincide with the centers of four cells of the same color?
Answer: $n=5$. Proof. We will prove that for $n=5$ (and thus for $\mathrm{n}>5$) such a rectangle will exist. Consider the bottom row of the table. In it, there are at least 3 cells of the same color. Let's assume for definiteness that these are white cells. Then consider the three columns with these cells at the base, i.e., we consider a smaller table of size $5 \times 3$, the bottom row of which consists of three white cells. If in any of the four remaining rows of this smaller table there are two white cells, then the desired "white" rectangle is formed by their centers and the centers of the corresponding cells in the bottom row.

![](https://cdn.mathpix.com/cropped/2024_05_06_7d23fcdecceec49c9f5fg-2.jpg?height=359&width=334&top_left_y=1314&top_left_x=267)
Now, suppose in each of these four rows there are at least two black cells. Then among these four rows, there will be at least two rows with the same arrangement of black cells, since there are only 3 different arrangements of two black (denoted by b) cells, namely: (bb?), (b?b), and (?bb)), and thus their centers form a "black" rectangle. An example of coloring a $4 \times 4$ square for which there is no such rectangle is shown in the figure (it is easy to verify that for this example, there are no "monochromatic" rectangles even with sides not parallel to the grid lines).