Maths Olympiad Prep

Library / Argentine National Olympiad /16 of 23

Argentine National Olympiad, 2015

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Argentina

Felipe tells Roberto that he managed to place 1226 triminos 1×31\times 3 on a certain grid square QQ so that they do not have common points, not even vertices. Without knowing the dimensions of QQ, Roberto answers, "If what you say is true then one can place 1250 triminos 1×31\times 3 on your square, under the same conditions." Is Roberto right?

Figure 1

Solution

Yes, Roberto is right. To prove this, we first show that the least nn for which 1226 triminos 1×31\times 3 can be placed on an n×nn \times n square without common points (including vertices) is n=99n=99. Next, take a 99×9999\times 99 square. In its first row one can place 25 triminos without point in common; they leave uncovered the 24 cells whose position numbers are divisible by 4. Do the same with all odd-numbered rows 1, 3, 5, ..., 99, of which there are 50. This arrangement of 25⋅50=125025 \cdot 50 = 1250 triminos satisfies the conditions and, clearly, any greater grid square can accommodate 1250 trimino too.

So let QQ be an n×nn \times n square containing 1226 triminos 1×31\times 3 without common points (including vertices). Extend QQ to an (n+1)×(n+1)(n+1) \times (n+1) square Q′Q' by adjoining an additional bottom row and additional leftmost column, with n+1n+1 cells in each of them. To each trimino TT add 5 cells to the left and under it so that TT and these 5 cells form a rectangle R(T)R(T) with dimensions 2×42\times 4. The definition of R(T)R(T) is illustrated in the figures, for horizontal and vertical triminos.

Figure 2

Figure 3

The 2×42\times 4 rectangles defined in this way may stick out of QQ but are contained in the bigger square Q′Q'.
The point of the construction is that the rectangles R(T)R(T) do not overlap, i.e., no two of them have cells in common. Indeed, let TT and T′T' be arbitrary triminos. By symmetry assume that TT is vertical. Enclose it in a 3×53\times 5 rectangle as shown in the figure.

Figure 4

Note that by hypothesis this rectangle R∗R^* contains no cell of the trimino T′T'. The cells marked with ∙\bullet form the rectangle R(T)R(T) together with TT. Denote by CC the top right cell in T′T'; it is also the top right cell of R(T′)R(T').
Suppose that CC is under line aa. Then so is the entire rectangle R(T′)R(T') by its definition, hence R(T′)R(T') does not overlap with R(T)R(T). The same follows if CC is to the left of line cc. Suppose that CC is in region I, i.e., between the lines c,dc, d and above line bb. Then the entire T′T' is above bb. This is clear if T′T' is horizontal. And if T′T' is vertical then having cells under bb mean having cells in R∗R^* which is forbidden. So indeed the whole of T′T' is above bb, implying that R(T′)R(T') is above line b′b'. Then R(T′)R(T') does not overlap R(T)R(T) again. The case where CC is in region II is analogous; here T′T' is to the right of line dd and R(T′)R(T') is to the right of line d′d'. Finally the case of CC in region III is obvious.

In summary, we obtain 1226 non-overlapping rectangles 2×42 \times 4 in the (n+1)×(n+1)(n+1) \times (n+1) square Q′Q'. By area considerations then (n+1)2≥8⋅1226=9808(n+1)^2 \ge 8 \cdot 1226 = 9808 and so n+1≥9808=99.035...n+1 \ge \sqrt{9808} = 99.035.... It follows that n≥99n \ge 99, as stated, so the starting discussion completes the proof.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.