5
$\begingroup$

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

$\endgroup$
  • $\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$ – Oray Mar 26 '16 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$ – rnaylor Mar 26 '16 at 21:13
  • $\begingroup$ @maylor hmm you are right, sorry about that :) $\endgroup$ – Oray Mar 26 '16 at 21:14
  • $\begingroup$ @Oray How is this anything like your post? $\endgroup$ – Paul Evans Mar 27 '16 at 11:06
  • $\begingroup$ @PaulEvans i know i said sorry already :) $\endgroup$ – Oray Mar 27 '16 at 11:08
8
$\begingroup$

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.
enter image description here

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.