# What is the fewest number of squares required to cover a $11\times13\text{ cm}$ rectangle without overlap?

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.

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

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:

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.

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.

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

• 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. – Cheesy cat Sep 9 '16 at 0:01
• What if we allow the squares to have non-integer side lengths? – stewbasic Sep 9 '16 at 0:02
• @stewbasic well, it doesn't say it needs to be integer side lengths – suomynonA Sep 9 '16 at 0:05
• @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. – dxiv Sep 9 '16 at 0:09
• 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$. – stewbasic Sep 9 '16 at 1:53

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.

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.

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

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

• Why downvote an answer which correctly answers the question ? Probably the OP has forgotten a supplementary condition... – Jean Marie Sep 8 '16 at 23:07
• @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. – 6005 Sep 8 '16 at 23:18
• 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. – Cheesy cat Sep 8 '16 at 23:20

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.