A table consists of 100 unit cells. A block is a square consisting of 4 unit cells of the table. A set of blocks covers the table (i.e. each cell of the table is covered by some block of ) but no blocks of cover the table. Find the largest possible value of n.
Solution
Consider an infinite table divided into unit cells. Any square consisting of 4 unit cells of the table we also call a block. Fix arbitrary finite set of blocks lying on the table. Now we will consider arbitrary finite sets of unit cells of the table covered by . For any such set denote by the least possible number of blocks of that cover all cells from . We have the following properties. . If then . . . For the set shown in the Fig.1, we have ; for the set shown in the Fig.2, we have . . Let be any rectangle of the table. Then . This estimate is proved by consideration of different ways in which the cells and can be covered by the blocks of . For this figures we have, respectively, the following estimates: Fig. 3 : Case 1) or Case 2) ; Fig. ; Fig. ; Fig. ; Fig. ; Fig. 8 : . 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 can attain the value 10; in all other figures we have in fact . . Let be any square of the table. From previous properties it follows that . We claim that in fact . This easily follows from the Fig. 9 and remark 2 (using two different ways of dividing into 2 rectangles ). Now we can finish the solution of the problem. Let be given table, be its central square. We have . One can easily verify that (applying the properties ). So, . On the other hand, Fig. 10 shows that can be attained.