João managed to paint the squares of an $n \times n$ board in black and white such that the intersections of any two rows and any two columns were not made up of squares of the same color. What is the maximum value of $n$?

#
Solution

An example $\operatorname{with} n=4$ is given in the figure below:

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-30.jpg?height=317&width=308&top_left_y=1692&top_left_x=771)

We want to show now that, if $n \geq 5$, such a coloring is not possible. Consider then an $n \times n$ board with $n \geq 5$.

Analyzing the squares of the first row, at least three of them will be of the same color. Let's say this color is black (if it were white, it would make no difference to our subsequent analysis) and observe now the columns $A, B$, and $C$ that contain these three black squares. The second row must intersect these three columns in at least two white squares, otherwise, we would have four black intersections between the first two rows and two of these three columns.

Now suppose that the columns containing two black squares in the first row and two white squares in the second are columns $A$ and $B$ (if they were $A$ and $C$ or $B$ and $C$, the subsequent analysis would be the same). Starting from the third row, since we cannot have squares of the same color simultaneously in columns $A$ and $B$, the color distributions can only be the following two options: black and white or white and black. Thus, among rows 3, 4, or 5, two of them will have exactly the same color distribution. These two rows with the same color distribution intersect column $C$ in two squares, neither of which can be black or white, and this prevents the existence of a coloring satisfying the conditions of the problem.

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-31.jpg?height=534&width=346&top_left_y=607&top_left_x=952)

#