5. The cells of an $n \times n$ square are colored black and white with the condition that no four cells, located at the intersection of two rows and two columns, can all be the same color. What is the largest possible value of $n$?
Solution. An example for $n=4$ is shown in the figure on the right. We will prove by contradiction that it is impossible to color a $5 \times 5$ square in this way. Let's call a row predominantly black if it has more black squares than white, and predominantly white otherwise. Among the five rows, there will be either three predominantly black rows or three predominantly white rows; without loss of generality, let's assume we have found three predominantly black rows. In these rows, there are at least nine black cells.

| B | W | B | W |
| :---: | :---: | :---: | :---: |
| B | B | W | W |
| W | B | B | W |
| W | W | W | B |

Now we consider only these three rows. If in some column (let's call it A) there are three black cells, then the remaining four columns have at least six black cells. Therefore, there will be a column (let's call it B) where there are two black cells. Then, taking columns A and B and the two rows where the two black cells of column B are located, we get a contradiction.

Thus, in each column, there are no more than two black cells. But this is only possible if there are at least two black cells in at least four columns. Since there are only three ways to color two out of three cells black, in some two columns the coloring is the same, and we again get a contradiction.