Felipe tells Roberto that he managed to place 1226 triminos 1×3 on a certain grid square Q so that they do not have common points, not even vertices. Without knowing the dimensions of Q, Roberto answers, "If what you say is true then one can place 1250 triminos 1×3 on your square, under the same conditions." Is Roberto right?
Solution
Yes, Roberto is right. To prove this, we first show that the least n for which 1226 triminos 1×3 can be placed on an n×n square without common points (including vertices) is n=99. Next, take a 99×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=1250 triminos satisfies the conditions and, clearly, any greater grid square can accommodate 1250 trimino too.
So let Q be an n×n square containing 1226 triminos 1×3 without common points (including vertices). Extend Q to an (n+1)×(n+1) square Q′ by adjoining an additional bottom row and additional leftmost column, with n+1 cells in each of them. To each trimino T add 5 cells to the left and under it so that T and these 5 cells form a rectangle R(T) with dimensions 2×4. The definition of R(T) is illustrated in the figures, for horizontal and vertical triminos.
The 2×4 rectangles defined in this way may stick out of Q but are contained in the bigger square Q′. The point of the construction is that the rectangles R(T) do not overlap, i.e., no two of them have cells in common. Indeed, let T and T′ be arbitrary triminos. By symmetry assume that T is vertical. Enclose it in a 3×5 rectangle as shown in the figure.
Note that by hypothesis this rectangle R∗ contains no cell of the trimino T′. The cells marked with ∙ form the rectangle R(T) together with T. Denote by C the top right cell in T′; it is also the top right cell of R(T′). Suppose that C is under line a. Then so is the entire rectangle R(T′) by its definition, hence R(T′) does not overlap with R(T). The same follows if C is to the left of line c. Suppose that C is in region I, i.e., between the lines c,d and above line b. Then the entire T′ is above b. This is clear if T′ is horizontal. And if T′ is vertical then having cells under b mean having cells in R∗ which is forbidden. So indeed the whole of T′ is above b, implying that R(T′) is above line b′. Then R(T′) does not overlap R(T) again. The case where C is in region II is analogous; here T′ is to the right of line d and R(T′) is to the right of line d′. Finally the case of C in region III is obvious.
In summary, we obtain 1226 non-overlapping rectangles 2×4 in the (n+1)×(n+1) square Q′. By area considerations then (n+1)2≥8⋅1226=9808 and so n+1≥9808=99.035.... It follows that n≥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.