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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.