Problem 9.5. A square $n \times n(n \geq 2)$ is divided into $n^{2}$ unit squares colored in black or white such that the squares at the four corners of any rectangle (containing at least four squares) have no the same color. Find the maximum possible value of $n$.

Sava Grozdev, Svetlozar Doychev
9.5. We shall show that the desired value is equal to 4 .

Let $(i, j)$ be the unit square in the $i$-th row and the $j$-th column of a $4 \times 4$ square. It is easy to check that if the squares $(1,1),(1,2),(2,1),(2,3)$, $(3,2),(3,4),(4,3),(4,4)$ are white and the other - black, then the condition of the problem is satisfied.

To prove that for $n \geq 5$ there is no a coloring with the required properties it is enough to deal only with the case $n=5$ (any $n \times n$ square contains a $5 \times 5$ square). Consider an arbitrary black-white coloring of a $5 \times 5$ square. At least 13 of the unit squares have the same coloring, for example, black. Three cases are possible.

Case 1. One of the rows, say $l$, contains only black squares. Then one of the other rows contains at least 2 black squares. Hence the corners of the rectangle with two vertices at these squares and the other two in $l$ are black.

Case 2. One of the rows, say $l$, contains exactly 4 black squares. Then one of the other rows contains at least 3 black squares. Then at least two of them
do not correspond to the white square in $l$. Hence the corners of the rectangle with two vertices at these squares and the other two in $l$ are black.

Case 3. Any row contains at most 3 black squares. Then at least 3 rows contain exactly 3 black squares, say the rows $1,2,3$ from above. We call a column black (white) if its upper square is black (white). There are exactly 3 black columns. If a row contains 2 black squares that lie in black columns, then obviously there is a rectangle with black corners. Otherwise, two of the black squares in row 2 and two of the black squares in the two white columns are black corners of a rectangle.

The solution is completed.