Covering a $ 31\times 31 $ square grid with $1\times 1, 2\times 2$ and $3\times 3$ tiles

$\begingroup$

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$ 1

3 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

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy