5
$\begingroup$

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

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

1 Answer 1

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 and acknowledge you have read our privacy policy.

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