6
$\begingroup$

I need help figuring out this math puzzle: I have a $11\times13\text{ cm}$ rectangle and I need help figuring out the least number of squares I need to cover the rectangle without overlap. I'm told the answer should be at most 5. If you can, provide a picture to help me understand.

$\endgroup$
18
$\begingroup$

I can prove there is no 5-square solution. The partitions of $11\times 13 = 143$ into sums of five squares can be enumerated: $$ \matrix{1^2 &+ 1^2 &+ 2^2 &+ 4^2 &+ 11^2\cr 1^2 &+ 1^2 &+ 4^2 &+ 5^2 &+ 10^2\cr 1^2 &+ 2^2 &+ 5^2 &+ 7^2 &+ 8^2\cr 1^2 &+ 3^2 &+ 4^2 &+ 6^2 &+ 9^2\cr 2^2 &+ 4^2 &+ 5^2 &+ 7^2 &+ 7^2\cr 2^2 &+ 5^2 &+ 5^2 &+ 5^2 &+ 8^2\cr 3^2 &+ 3^2 &+ 3^2 &+ 4^2 &+ 10^2\cr 3^2 &+ 3^2 &+ 5^2 &+ 6^2 &+ 8^2\cr }$$ All but one of these can be eliminated out of hand, by looking at the two largest squares: $a \times a$ and $b \times b$ squares can't fit in a rectangle without overlapping unless the rectangle has one dimension at least $a+b$. The remaining possiblility is $2^2 + 5^2 + 5^2 + 5^2 + 8^2$, but it's easy to see that an $8 \times 8$ square and three $5 \times 5$ squares won't fit in the rectangle.

EDIT: There's no tiling of the $11 \times 13$ rectangle with $5$ squares even if you don't require integer sides. It's best to work up to $5$ tiles one at a time.

With one tile ($a \times a$) you can only tile an $a \times a$ rectangle.

With two tiles, both must be $a \times a$, and you get an $a \times 2a$ rectangle. Henceforth, I'll leave out the $a$, and assume the greatest common divisor of edge lengths is $1$, so call this $1 \times 2$.

enter image description here

With three tiles, at least one must be on an edge of your rectangle, and the rest of the rectangle is a two-tile rectangle. There are two cases, depending on how that two-tile rectangle is oriented:

enter image description here

With four tiles, you could put another square on one side of a three-tile rectangle, or you could have four equal squares, each taking one corner of a $2 \times 2$ square. There are five possibilities.

enter image description here

With five tiles, you could put one square on one side of a four-tile rectangle, obtaining a $4 \times 7$, $7 \times 3$, $5 \times 1$, $4 \times 5$, $4 \times 2$, $8 \times 5$, $3 \times 8$, $7 \times 2$ or $5 \times 7$ rectangle. Or if no square takes a whole side of the rectangle, you must have one square in each of the four corners of the rectangle and one square not on a corner. If so, it's not hard to see that this non-corner square must be on an edge, let's say the right edge. On the left edge, the two squares may be the same size (resulting in a $6 \times 5$ rectangle) or different sizes. If they are different sizes, the smaller one must be the same size as its neighbour to the right, resulting in a $7 \times 6$ rectangle.

enter image description here

(I hope) that's all the possibilities, not counting rotations and reflections. None of the possibilities has an $11$ to $13$ ratio.

$\endgroup$
  • $\begingroup$ I am not looking for 5x5 squares, I want the least number of squares you can put into the rectangle. I got 6 but I heard that 5 is possible as well. $\endgroup$ – Cheesy cat Sep 9 '16 at 0:01
  • 7
    $\begingroup$ What if we allow the squares to have non-integer side lengths? $\endgroup$ – stewbasic Sep 9 '16 at 0:02
  • $\begingroup$ @stewbasic well, it doesn't say it needs to be integer side lengths $\endgroup$ – suomynonA Sep 9 '16 at 0:05
  • 2
    $\begingroup$ @Cheesycat You misunderstood the answer. It is not about 5x5 squares. It is about coverings with 5 squares having integer side lengths, and proves that none such exist. $\endgroup$ – dxiv Sep 9 '16 at 0:09
  • 2
    $\begingroup$ I think your second argument is missing some cases. For the case of one square touching two corners, there is $4^2+3^2+1^2+1^2+1^2=4\times7$ for example. For the case of 4 corner squares there is $3^2+3^2+4^2+2^2+2^2=6\times7$. $\endgroup$ – stewbasic Sep 9 '16 at 1:53
12
$\begingroup$

Suppose it is possible to cover the rectangle without overlap using $5$ or fewer squares.

Clearly the side length of each square is at most $11$. Suppose we have a square with side length $11$. It must be axis aligned, so removing this square leaves a rectangle of size $11\times a$ where $a\leq 2$. Each square inside this rectangle has area at most $a^2$, so this rectangle requires at least $11a/a^2>5$ squares, a contradiction.

So we may assume all the squares have size less than $11$. In particular no square can cover two corners of the rectangle. But each corner of the rectangle must also be the corner of a square, so we need four of the squares to cover the rectangle's corners (call them the corner squares). Suppose the corner squares have sizes $a,b,c,d$, so $a+b,c+d\leq11$ and $b+c,a+d\leq13$. Each edge of the rectangle touches two corner squares, which either cover the edge or leave a gap. Since $a+b+c+d\leq22$, one of the length $13$ sides has a gap.

If a side of the rectangle has a gap, then this section of the edge must be an edge of the final square. Since the final square has size less than $11$, this can only happen for one edge. We may suppose the size $a$ and $d$ squares leave a gap, so $a+b=c+d=11$ and $b+c=13$. Thus $$ b=11-a,\,c=a+2,\,d=9-a. $$ The size of the final square is $13-(a+d)=4$. The total area of the rectangle is $$ 11\times13=4^2+a^2+b^2+c^2+d^2=4a^2-36a+222. $$ Solving, $$ a=\frac92\pm\frac1{\sqrt2}. $$ Explicitly drawing, we see that neither solution works. So it is not possible with 5 or fewer squares.

$\endgroup$
10
$\begingroup$

There is a way to get 143 using 4 squares, but they would overlap. 9x9, 7x7, 3x3, 2x2 is probably what your teacher got. The way to do it in 6 is 7x7, 6x6, 5x5, 2 4x4, 1x1.

$\endgroup$
  • 2
    $\begingroup$ If you could overlap (which you can't) then 2 would finish the job. $\endgroup$ – Cheesy cat Sep 8 '16 at 23:37
  • 1
    $\begingroup$ Yea, 11x11 and 11x11 would be super obvious $\endgroup$ – suomynonA Sep 8 '16 at 23:37
  • $\begingroup$ Two 4x4s, right? $\endgroup$ – Dan Uznanski Sep 8 '16 at 23:44
  • $\begingroup$ Yes, editing that $\endgroup$ – suomynonA Sep 8 '16 at 23:45
  • 1
    $\begingroup$ @Agawa001 Sorry, I didn't really get what you meant. Can you explain what you mean? $\endgroup$ – suomynonA Sep 9 '16 at 2:26
4
$\begingroup$

The maximum number of 1x1 squares you can fit into this rectangle would be $11*13=143$

$\endgroup$
  • 3
    $\begingroup$ Why downvote an answer which correctly answers the question ? Probably the OP has forgotten a supplementary condition... $\endgroup$ – Jean Marie Sep 8 '16 at 23:07
  • 3
    $\begingroup$ @JeanMarie No, the OP asks for the least amount of squares and this answers the maximum. Additionally, $1 \times 1$ came out of nowhere. So it is hard to see how this is a good answer in any way. $\endgroup$ – 6005 Sep 8 '16 at 23:18
  • $\begingroup$ Yes I was asking for the least about of squares you can fit in a 11x13 rectangle that is less then 5. The number I got is 6 but It needs to be less then 5. $\endgroup$ – Cheesy cat Sep 8 '16 at 23:20
3
$\begingroup$

The given rectangle can be divided in to either 3 columns containing 1,2,2 squares or 2 columns containing 4,1 or 3,2 squares. Both possibilities, even using non integer side lengths, won't give 11 x 13. It cannot be done using 5 squares.

The least has to be 6. The one you got.

$\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.