Maths Olympiad Prep

Library / /17 of 24

, 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 2550=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 QQ' 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 QQ'.
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 TT' 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 RR^* contains no cell of the trimino TT'. The cells marked with \bullet form the rectangle R(T)R(T) together with TT. Denote by CC the top right cell in TT'; 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 TT' is above bb. This is clear if TT' is horizontal. And if TT' is vertical then having cells under bb mean having cells in RR^* which is forbidden. So indeed the whole of TT' is above bb, implying that R(T)R(T') is above line bb'. Then R(T)R(T') does not overlap R(T)R(T) again. The case where CC is in region II is analogous; here TT' is to the right of line dd and R(T)R(T') is to the right of line dd'. 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 QQ'. By area considerations then (n+1)281226=9808(n+1)^2 \ge 8 \cdot 1226 = 9808 and so n+19808=99.035...n+1 \ge \sqrt{9808} = 99.035.... It follows that n99n \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.