
Problem 6. A square table of size $7 \times 7$ with the four corner squares deleted is given.

Figure 4.

a) What is the smallest number of squares which need to be colored black so that a 5 -square entirely uncolored Greek cross (Figure 4) cannot be found

![](https://cdn.mathpix.com/cropped/2024_06_03_e679746950d7d3832835g-014.jpg?height=206&width=204&top_left_y=840&top_left_x=451)
on the table?

b) Prove that it is possible to writte integers in each square in a way that the sum of the integers in each Greek cross is negative while the sum of all integers in the square table is positive.


Solution. Denote the square in row $i$ and column $j$ by $(i, j)$. Note that a cross is uniquely determined by its central cell. The cross with central cell $(i, j)$ is denoted by $C_{i j}, 2 \leq i, j \leq 6$. The number of all crosses is 25 .

a) The squares $(1, i),(i, 1),(7, i),(i, 7), i=2, \ldots, 6$, are included in exactly one cross; the squares $(2,2),(2,6),(6,2),(6,6)$ are included in exactly 3 crosses; the squares $(2, i),(i, 2),(6, i)$, $(i, 6), i=3,4,5$ - in exactly 4 crosses and finally, the squares $(i, j), 3 \leq i, j \leq 5$, are included in exactly 5 crosses. Since $C_{22}$ contains a colored square, then at least one of $(1,2),(2,1),(2,2)$, $(2,3),(3,2)$ should be colored. Similarly, at least one of $(2,7),(1,6),(2,6),(2,5),(3,6)$, at least one of $(7,2),(6,1),(6,2),(5,2),(6,3)$ and at least one of $(6,7),(7,6),(6,6),(6,5),(5,6)$ are colored. Any of them is contained in at most four crosses (the first two in each quintuple in 1 cross, the third one in 3 crosses and the remaining two - in 4 crosses). Denote by $x$ the number of the colored squares among $(i, j), 3 \leq i, j \leq 5$. The number of crosses containing a colored square is not greater than $4.4+5 x$, whence

$$
16+5 x \geq 25
$$

Thus, $x \geq 2$ and the number of the colored cells is at least 6 .

Suppose that the number of the colored squares is 6 . Then $x=2$. Moreover, acording (1) there exists at most one Greek cross containing more than one colored square. If two squares with a common side or a common vertex are colored, then it is easy to check that there are two crosses with at least two colored squares each. Therefore, the squares $(4,4),(3,3),(3,5),(5,3)$, $(5,5)$ should be uncolored. With no loss of generality, let the two colored squares be $(4,3)$ and $(4,5)$. But now the crosses $C_{34}$ and $C_{54}$ do not contain colored squares.

To prove that the minimal number of colored squares is 7 , color for example the squares $(2,5),(3,2),(3,3),(4,6),(5,4),(6,2),(6,5)$.

b) Let us write -5 in each of the colored squares from a) and 1 in the remaining squares. Since every Greek cross contains a colored square, the sum of the numbers in its squares does not exceed $1+1+1+1-5=-10$ and we are done.

## XLV National Mathematics Olympiad: 3rd round, April 1997
