We have 19 triminos (2 x 2 squares without one unit square) and infinite amount of 2 x 2 squares. Find the greatest odd number $n$ for which a square $n$ x $n$ can be covered with the given figures.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: combinatorics, covering, Tables
09.08.2024 17:13
Example for $9\times 9$ is just trial and error. We present two approaches for the bound. First approach. Let the square be covered with \( x \) G-triominoes and \( y \) \( 2 \times 2 \) squares; clearly \( 3x + 4y = n^2 \). Color black the cells located in odd rows and columns. There are exactly \( \left( \frac{n+1}{2} \right)^2 \) colored squares, and since each \( 2 \times 2 \) square covers exactly one colored square, and each G-triomino covers at most one colored square, we have \( x+y \geq \left( \frac{n+1}{2} \right)^2 \). Hence, \( y \geq \frac{(n+1)^2}{4} - x \) and therefore \( n^2 = 3x + 4y \geq 3x + 4\left( \frac{(n+1)^2}{4} - x \right) = (n+1)^2 - x \), from which \( x \geq 2n+1 \). Since \( x \leq 19 \), it follows that \( n \leq 9 \). Second approach. Color the odd columns in black (and the even ones in white). There are \( \frac{n(n+1)}{2} \) black squares and \( \frac{n(n-1)}{2} \) white squares, i.e., the black squares exceed the white ones by \( n \). On the other hand, each G-triomino contributes to the difference "number of black - number of white" by \( 1 \) or \( -1 \), since a G-triomino covers \( 2 \) black and \( 1 \) white or \( 1 \) black and \( 2 \) white squares. If the number of those of the first type is \( a \) and of the second type is \( b \), then \( a+b = 19 \), \( a-b = n \), but \( b \geq \frac{n+1}{2} \) since each column has an odd number of black squares, implying there must be a cell part of a trionimo of the second type. Hence \( \frac{n+1}{2} \leq b = \frac{(a+b) - (a-b)}{2} = \frac{19-n}{2} \), whence \( n \leq 9 \).