# Problem 5. (Kuyanov F.)

Find all quadruples of natural numbers $a, b, c, d$, for which the following equations are satisfied

\[
\left\{
\begin{array}{l}
a+b=c d \\
c+d=a b
\end{array}
\right.
\]
Answer: $(2,2,2,2),(1,2,3,5),(2,1,3,5),(1,2,5,3),(2,1,5,3),(3,5,1,2),(5,3,1,2),(3,5,2,1),(5,3,2,1)$

Solution:

$\left\{\begin{array}{l}0=c d-a-b \\ 0=a b-c-d\end{array} \Rightarrow(a-1)(b-1)+(c-1)(d-1)=(c d-a-b)+(a b-c-d)+2=2\right.$

Each of $(a-1)(b-1)$ and $(c-1)(d-1)$ is a non-negative integer. If this is:

1 and $1 \Rightarrow(a, b, c, d)=(2,2,2,2)$

0 and $2 \Rightarrow(c-1)(d-1)=2 \Rightarrow\{c, d\}=\{2,3\},\{a, b\}=\{1, x\}, a+b=c d=6 \Rightarrow b=5$

2 and 0 will give a permutation. It remains to check that all the obtained sets satisfy the system of equations.

Criteria: Correct solution: 15 points (+)

No points are deducted for losing some cases with permutations of $1,2,3,5$

We consider statements of the form $a+b>3$ to be obvious.

No verification of the answer (and one-sided consequences in the solution): 13 points (+.)

Reduced to a manageable number of cases (e.g., proved that all numbers are less than 6): 8 points ( ${ }^{+} / 2$ )

Obtained the equality $(a-1)(b-1)+(c-1)(d-1)=(c d-a-b)+(a b-c-d)+2=2$ or similar: 8 points $(+/ 2)$

## Problem 6

(Singapore-2015) Some cells of a 9 by 9 square are painted black such that in every rectangle of six cells, exactly two are black. How many cells in total are painted? Provide a complete and justified answer to this question.

Answer: 27

Comment: It is sufficient to consider rectangles $2 \times 3$

## Solution:

Let's call the bottom left square (1,1). An example with 27 black cells: paint all cells $(a, b)$ black such that $(a-b)$ is divisible by 3.

Consider the $9 \times 9$ square without the cells $\{(1,1),(1,2),(1,3)\}$. The resulting figure can be tiled with thirteen $2 \times 3$ rectangles, in which there are 26 black cells. Clearly, the removed cells $\{(1,1),(1,2),(1,3)\}$ cannot all be black, as they are contained in a $2 \times 3$ rectangle.

Suppose that among the cells $\{(1,1),(1,2),(1,3)\}$ there are no black cells. The square without the cells $\{(1,1),(2,1),(3,1)\}$ can also be tiled with 13 $2 \times 3$ rectangles, so among $\{(1,1),(2,1),(3,1)\}$ there are no black cells. Similar reasoning shows that among $\{(3,1),(3,2),(3,3)\}$ there are no black cells. But then in the $2 \times 3$ rectangle from cells (1,1), $(2,1),(3,1),(1,2),(2,2),(3,2)$ we have found 5 white cells. Contradiction.

Now suppose that among the cells $\{(1,1),(1,2),(1,3)\}$ there are two black cells. Then in the $9 \times 9$ square there are 28 black cells in total. Following the earlier argument, we get that in the strips $\{(1,1),(2,1),(3,1)\},\{(3,1),(3,2),(3,3)\},\{(1,3),(2,3),(3,3)\}$ there are also two black cells each.

Among the cells $\{(2,1),(2,2),(2,3)\}$ all are white, as this strip together with the strip $\{(1,1),(2,1),(3,1)\}$ forms a $2 \times 3$ rectangle with only 2 black cells. Using this argument, we get that the cells are painted as in the table, in which we can again find a $2 \times 3$ rectangle with five white cells, leading to a contradiction.

| w | w | w |
| :--- | :--- | :--- |
| b | w | b |
| w | w | w |
| b | w | b |

Thus, among the cells $\{(1,1),(1,2),(1,3)\}$ there is exactly one black cell, which corresponds to the example with 27 black cells.

Criteria: Correct solution: 25 points (+)

Proved that if a coloring satisfying the condition exists, then it has 27 black cells, but did not prove the existence (did not provide an example): 17 points ( 4 )

Correctly proved that there cannot be two black cells next to each other: 13 points $(+/ 2)$

Only the correct answer and example: 8 points ( $($ )