# Tiling a $13 \times 11$ rectangle with squares

What is the smallest number of integer-sided squares required to tile a $13 \times 11$ rectangle without overlaps?

• I believe this is the same question that I have asked a couple of weeks ago. I might be wrong because I might misunderstand the question :) – Oray Mar 26 '16 at 21:11
• This isn't the same - here the squares cannot overlap and we're not trying to make a grid, just cover the rectangle – rnaylor Mar 26 '16 at 21:13
• @maylor hmm you are right, sorry about that :) – Oray Mar 26 '16 at 21:14
• @Oray How is this anything like your post? – Paul Evans Mar 27 '16 at 11:06
• @PaulEvans i know i said sorry already :) – Oray Mar 27 '16 at 11:08

It's:

6 squares.

Because:

I originally came up with the solution by trying to divide up the $13\times 11$ rectangles into similar-ish quarters and saw this $5, 6, 7, 4, 8$ pattern that magically produced only one $1\times 1$ square in the middle bit.
The more I though about it the more I was convinced I wouldn't be gobsmacked by a smaller number of squares working.
So here's the rigor:
The area that needs to be covered is $143 = 13 \times 11$.
Generating all possible combinations of $5$ or less squares, less than or equal to $11\times 11$, that exactly cover a $143$ area yields:
(1, 5, 6, 9)
(2, 3, 3, 11)
(2, 3, 7, 9)
(3, 3, 5, 10)
(3, 6, 7, 7)
(1, 1, 2, 4, 11)
(1, 1, 4, 5, 10)
(1, 2, 5, 7, 8)
(1, 3, 4, 6, 9)
(2, 4, 5, 7, 7)
(2, 5, 5, 5, 8)
(3, 3, 3, 4, 10)
(3, 3, 5, 6, 8)
None of these work because the only one that has all combinations of pairs adding up to $13$ or less is:
(2, 5, 5, 5, 8)
And that doesn't fit into a $13\times 11$ rectangle.
All combinations of $6$ squares, less than or equal to $11\times 11$, that cover a $143$ area with no pairs adding up to more than $13$ are:
(4, 4, 5, 5, 5, 6)
(2, 2, 5, 5, 6, 7)
(2, 3, 4, 5, 5, 8)
(1, 3, 5, 6, 6, 6)
(1, 4, 4, 5, 6, 7)
(2, 3, 3, 6, 6, 7)
Of these, only (1, 4, 4, 5, 6, 7) fits into a $13\times 11$ rectangle.
So $6$ is the minimal number of squares, as shown below.
Of course, all rotations and mirror images also work.