Exercise 5. In a grid of size $n \times n$, some cells are white and some are black. We assume that for any pair of columns and any pair of rows, the 4 cells formed by the intersections of these two columns and these two rows are never all the same color. Find the largest value of $n$ for which this is possible.
Solution to Exercise 5: We will show that it is not possible for \( n \geqslant 5 \), and that it is possible for \( n \leqslant 4 \).

To do this, we first observe that if it is possible for an \( n \), it is possible for all \( k \leqslant n \). Indeed, if we take an \( n \times n \) grid satisfying the hypotheses, and then restrict ourselves to the sub-grid formed by the first \( k \) rows and columns, this sub-grid also satisfies the hypotheses. Therefore, to conclude, it suffices to show that it is not possible for \( n=5 \) and to provide a construction for \( n=4 \).

In the case \( n=5 \), consider a \( 5 \times 5 \) colored grid. For each column, there is at least one color present at least 3 times, according to the pigeonhole principle. Therefore, there are 3 columns for which this color is the same (by symmetry, let's say 3 columns containing at least 3 white cells), for the same reason. Let's call these columns \( a \), \( b \), and \( c \). There are at least 3 white cells in column \( a \), and we call the rows \( x \), \( y \), and \( z \). If column \( b \) or column \( c \) contains at least 2 white cells in rows \( x \), \( y \), and \( z \), then (for example, if cells \((b, x)\) and \((b, y)\) are white) the intersections of rows \( x \) and \( y \) with columns \( a \) and \( b \) are all white. Otherwise, on each of the two columns \( b \) and \( c \), the cells in the last two rows are white, and thus by considering these two rows and columns \( b \) and \( c \), we find that the grid does not satisfy the hypothesis.

For the case \( n=4 \), the following construction works:

![](https://cdn.mathpix.com/cropped/2024_06_04_7f99ab0e41c82ac4a4c9g-06.jpg?height=422&width=437&top_left_y=1296&top_left_x=844)

Grader Comments: For this exercise, the writing is often unclear. Some students overuse the phrase "without loss of generality" to consider a very specific case. However, often students do not identify enough symmetries in the problem to reduce it to a single case. A tip to avoid mistakes is to specify which generality is preserved before using the phrase, to ensure that one has not overused the formula. For example, in the case \( n=5 \): "There are three cells of the same color in the first column. Without loss of generality, and by swapping the color of each cell in the grid, we can assume that these three cells are white." However, after writing this, we are no longer allowed to make the same assumption for the three cells of the same color in the second column.