Covering a $ 31\times 31 $ square grid with $1\times 1, 2\times 2$ and $3\times 3$ tiles
I want to solve the following problem :
A $31\times 31$ square grid is completely tiled by $1\times 1$, $2\times 2$ and $3\times 3$ tiles. What is the minimum number of $1\times 1$ tiles required.
My approach so far :
I have tried to cover the grid with as little $1\times 1$ tiles as possible. The following is one such arrangement
So here I have used six $1\times 1$ tiles. Now the question is whether I can cover the grid using fewer than six $1\times 1$ tiles. If the number of $1\times 1$, $2\times 2$ and $3\times 3$ tiles is $x,y$ and $z$ respectively, then $9x+4y+z=961$. Is this going to help to show that the arrangements for $z=1,2,3,4,5$ are / are not possible?
$\endgroup$ 13 Answers
$\begingroup$You can do it with only one $1 \times 1$ piece.
Note that any rectangle $6 \times n$ with $n \ge 1$ can be covered easily because those $n$ can be written as a sum of $2$s and $3$s.
If you look at a $13 \times 13$ square, you can cover it by putting a $1 \times 1$ piece on its center and splitting the rest into four $6 \times 7$ rectangles.
Then, to complete the $31 \times 31$ square, you add a $13 \times 18$ rectangle and a $18 \times 31$ rectangle.
You can't do it without a $1 \times 1$ piece, because if you tile the square with a repeating
$\left(\begin{array}{rr} 1 & -1 \\ 0 & 0 \\ -1 & 1 \end{array}\right)$
pattern, the sum of all the numbers in a $31 \times 31$ square is $1$, but the sum over any $2 \times 2$ or $3 \times 3$ square is $0$.
$\endgroup$ 1 $\begingroup$Starting from a corner, you can fill a square $27\times 27$ with $81$ tiles $3\times 3$, then two stripes $26 \times 4$ with $52$ tiles $2\times 2$ and you get a free space $5\times 5$ with a $1\times 1$ corner removed. This can be filled with one tile $3\times 3$, three tiles $2\times 2$ and three tiles $1 \times 1$.
$\endgroup$ $\begingroup$Here is a solution with 3 1x1 squares
