What is the smallest number of integer-sided squares required to tile a $13 \times 11$ rectangle without overlaps?
-
$\begingroup$ 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 :) $\endgroup$– OrayCommented Mar 26, 2016 at 21:11
-
2$\begingroup$ This isn't the same - here the squares cannot overlap and we're not trying to make a grid, just cover the rectangle $\endgroup$– rnaylorCommented Mar 26, 2016 at 21:13
-
$\begingroup$ @maylor hmm you are right, sorry about that :) $\endgroup$– OrayCommented Mar 26, 2016 at 21:14
-
$\begingroup$ @Oray How is this anything like your post? $\endgroup$– Paul EvansCommented Mar 27, 2016 at 11:06
-
$\begingroup$ @PaulEvans i know i said sorry already :) $\endgroup$– OrayCommented Mar 27, 2016 at 11:08
1 Answer
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.