International Zhautykov Olympiad

Consider an infinite table divided into unit cells. Any $2 \times 2$ square consisting of 4 unit cells of the table we also call a block. Fix arbitrary finite set $M$ of blocks lying on the table. Now we will consider arbitrary finite sets of unit cells of the table covered by $M$. For any such set $\Phi$ denote by $|\Phi|$ the least possible number of blocks of $M$ that cover all cells from $\Phi$. We have the following properties. $1^{\circ}$. If $\Phi_{1} \subseteq \Phi_{2}$ then $\left|\Phi_{1}\right| \leq\left|\Phi_{2}\right|$. $2^{\circ} \cdot\left|\Phi_{1} \cup \Phi_{2}\right| \leq\left|\Phi_{1}\right|+\left|\Phi_{2}\right| \cdot$. $3^{\circ}$. For the set $A$ shown in the Fig.1, we have $|A|=2$; for the set $B$ shown in the Fig.2, we have $|B|=3$. $4^{\circ}$. Let $C$ be any rectangle $3 \times 6$ of the table. Then $|C| \leq 10$. This estimate is proved by consideration of different ways in which the cells $X$ and $Y$ can be covered by the blocks of $M$. For this figures we have, respectively, the following estimates: Fig. 3 : Case 1) $|C| \leq 2+2+3+1+1$ or Case 2) $|C| \leq 1+1+1+1+1+1+1+1$; Fig. $4:|C| \leq 3+3+1+1+1$; Fig. $5:|C| \leq 2+2+3+1+1$; Fig. $6:|C| \leq 3+3+1+1+1$; Fig. $7:|C| \leq 2+2+3+1+1$; Fig. 8 : $|C| \leq 3+3+1+1+1+1$. Remark 1. In the Fig 3. the first case means that the four marked cells are covered by at most 3 blocks; the second case means that the marked cells are covered by 4 different blocks. Remark 2. The Fig 8. presents the only case where $|C|$ can attain the value 10; in all other figures we have in fact $|C| \leq 9$. $5^{\circ}$. Let $D$ be any $6 \times 6$ square of the table. From previous properties it follows that $|D| \leq 20$. We claim that in fact $|D| \leq 19$. This easily follows from the Fig. 9 and remark 2 (using two different ways of dividing $D$ into 2 rectangles $3 \times 6$ ). Now we can finish the solution of the problem. Let $E$ be given $10 \times 10$ table, $D$ be its central $6 \times 6$ square. We have $|D| \leq 19$. One can easily verify that $|E \backslash D| \leq 20$ (applying the properties $1^{\circ}-4^{\circ}$ ). So, $|E| \leq|D|+|E \backslash D| \leq 19+20=39$. On the other hand, Fig. 10 shows that $n=39$ can be attained.