Argentine National Olympiad 2015

Yes, Roberto is right. To prove this, we first show that the least $n$ for which 1226 triminos $1\times 3$ can be placed on an $n\times n$ square without common points (including vertices) is $n=99$. Next, take a $99\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\cdot 50=1250$ triminos satisfies the conditions and, clearly, any greater grid square can accommodate 1250 trimino too.

So let $Q$ be an $n\times n$ square containing 1226 triminos $1\times 3$ without common points (including vertices). Extend $Q$ to an $(n+1)\times (n+1)$ square $Q^{\prime }$ 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\times 4$. The definition of $R(T)$ is illustrated in the figures, for horizontal and vertical triminos.





The $2\times 4$ rectangles defined in this way may stick out of $Q$ but are contained in the bigger square $Q^{\prime }$. 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^{\prime }$ be arbitrary triminos. By symmetry assume that $T$ is vertical. Enclose it in a $3\times 5$ rectangle as shown in the figure.



Note that by hypothesis this rectangle $R^{\ast }$ contains no cell of the trimino $T^{\prime }$. The cells marked with $\bullet$ form the rectangle $R(T)$ together with $T$. Denote by $C$ the top right cell in $T^{\prime }$; it is also the top right cell of $R(T^{\prime })$. Suppose that $C$ is under line $a$. Then so is the entire rectangle $R(T^{\prime })$ by its definition, hence $R(T^{\prime })$ 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^{\prime }$ is above $b$. This is clear if $T^{\prime }$ is horizontal. And if $T^{\prime }$ is vertical then having cells under $b$ mean having cells in $R^{\ast }$ which is forbidden. So indeed the whole of $T^{\prime }$ is above $b$, implying that $R(T^{\prime })$ is above line $b^{\prime }$. Then $R(T^{\prime })$ does not overlap $R(T)$ again. The case where $C$ is in region II is analogous; here $T^{\prime }$ is to the right of line $d$ and $R(T^{\prime })$ is to the right of line $d^{\prime }$. Finally the case of $C$ in region III is obvious.

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