Maths Olympiad Prep

Library / /4 of 13

Combinatorics Difficulty 6.3 National olympiad Find the answer

A 10×1010 \times 10 table consists of 100 unit cells. A block is a 2×22 \times 2 square consisting of 4 unit cells of the table. A set CC of nn blocks covers the table (i.e. each cell of the table is covered by some block of CC ) but no n1n-1 blocks of CC cover the table. Find the largest possible value of n.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider an infinite table divided into unit cells. Any 2×22 \times 2 square consisting of 4 unit cells of the table we also call a block. Fix arbitrary finite set MM of blocks lying on the table. Now we will consider arbitrary finite sets of unit cells of the table covered by MM. For any such set Φ\Phi denote by Φ|\Phi| the least possible number of blocks of MM that cover all cells from Φ\Phi. We have the following properties. 11^{\circ}. If Φ1Φ2\Phi_{1} \subseteq \Phi_{2} then Φ1Φ2\left|\Phi_{1}\right| \leq\left|\Phi_{2}\right|. 2Φ1Φ2Φ1+Φ22^{\circ} \cdot\left|\Phi_{1} \cup \Phi_{2}\right| \leq\left|\Phi_{1}\right|+\left|\Phi_{2}\right| \cdot. 33^{\circ}. For the set AA shown in the Fig.1, we have A=2|A|=2; for the set BB shown in the Fig.2, we have B=3|B|=3. 44^{\circ}. Let CC be any rectangle 3×63 \times 6 of the table. Then C10|C| \leq 10. This estimate is proved by consideration of different ways in which the cells XX and YY can be covered by the blocks of MM. For this figures we have, respectively, the following estimates: Fig. 3 : Case 1) C2+2+3+1+1|C| \leq 2+2+3+1+1 or Case 2) C1+1+1+1+1+1+1+1|C| \leq 1+1+1+1+1+1+1+1; Fig. 4:C3+3+1+1+14:|C| \leq 3+3+1+1+1; Fig. 5:C2+2+3+1+15:|C| \leq 2+2+3+1+1; Fig. 6:C3+3+1+1+16:|C| \leq 3+3+1+1+1; Fig. 7:C2+2+3+1+17:|C| \leq 2+2+3+1+1; Fig. 8 : C3+3+1+1+1+1|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|C| can attain the value 10; in all other figures we have in fact C9|C| \leq 9. 55^{\circ}. Let DD be any 6×66 \times 6 square of the table. From previous properties it follows that D20|D| \leq 20. We claim that in fact D19|D| \leq 19. This easily follows from the Fig. 9 and remark 2 (using two different ways of dividing DD into 2 rectangles 3×63 \times 6 ). Now we can finish the solution of the problem. Let EE be given 10×1010 \times 10 table, DD be its central 6×66 \times 6 square. We have D19|D| \leq 19. One can easily verify that E\D20|E \backslash D| \leq 20 (applying the properties 141^{\circ}-4^{\circ} ). So, ED+E\D19+20=39|E| \leq|D|+|E \backslash D| \leq 19+20=39. On the other hand, Fig. 10 shows that n=39n=39 can be attained.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.