[Math] 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

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.