
1. In a table consisting of $n$ by $n$ small squares some squares are coloured black and the other squares are coloured white. For each pair of columns and each pair of rows the four squares on the intersections of these rows and columns must not all be of the same colour.

What is the largest possible value of $n$ ?


1. We will prove that $n=4$ is the largest possible $n$ for which an $n \times n$-table can be coloured according to the rules. The following figure shows a valid colouring for $n=4$.

![](https://cdn.mathpix.com/cropped/2024_04_17_ea22e3414b6ace40dc6dg-1.jpg?height=305&width=305&top_left_y=704&top_left_x=881)

Now we prove that there is no colouring of the squares in a $5 \times 5$-table satisfying the requirements. Suppose, for contradiction, that such a colouring exists. Of the squares in each row either the majority is black, or the majority is white. We may suppose that there are at least three rows for which the majority of the squares is black (the case where there are at least three rows for which the majority of the squares is white is treated in an analogous way). We now consider the squares in these three rows. Of these 15 squares at least 9 are black.

If there is a column in which each of the three rows has a black square, then each other column can contain at most one black square in these three rows. The total number of black squares in the three rows will therefore be no more than $3+1+1+1+1=7$, contradicting the fact that the number should be at least 9 .

Hence, in each column at most two of the three rows have a black square. We consider the number of columns with two black squares in the three rows. If there are more then three, then there are two columns in which the same two rows have a black square, which is impossible. It follows that the number of black squares in the three rows is no more than $2+2+2+1+1=8$, again contradicting the fact that this number should be at least 9 .

Hence, it is impossible to colour a $5 \times 5$-table according to the rules. It is clear that it also will be impossible to colour an $n \times n$-table according to the rules if $n>5$.
