# Squaring rectangles

it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can be tiled with n squares can be tiled as well with n+3 squares and any number of squares that is greater or equal to n+5.

A result of Dehn (not trivial) asserts that a rectangle can be tiled with finitely many squares if and only if it has integer lengths. Let R be such a rectangle and let m denote the least number of squares needed for a tiling of R. As we have already seen, R can be tiled with m+3 squares and any number greater or equal to m+5. Then there can be at most 6 classes of rectangles :

• those that cannot be tiled with any other number of squares,
• those that can be tiled with m+1 and m+4 squares,
• those that can be tiled with m+2 squares,
• those that can be tiled with m+1, m+2 and m+4 squares,
• those that can be tiled with m+2 and m+4 squares,
• those that can be tiled with m+4 squares.

It seems that any of these classes is not empty. However, it is not so easy to compute the class of a given rectangle (at least for me!). So my first question is about the existence of such an algorithm?

I feel that the first class contains all rectangles whose lengths are of the form (1,n) ; (2,2n+1) and (3,3n+2) and I don't know if there are others. Is it possible to determine all the rectangles of a class, or at least some subclasses in it?

So far, I have not found where this problem would have been studied before; all I know is some articles dealing with an asymptotic behavior of m with respect of the lengths of R. Please feel free to add any useful comment on this topic!

-
I believe (not certain) that the minimum number of squares which a $n \times (n+1)$ rectangle needs is $n+1$. –  Calvin Lin Aug 29 '13 at 15:59
Thanks Calvin.m=1 for a square as a square can be tiled with 1 square! –  Fractality Aug 29 '13 at 16:02
Consider the (5,6) rectangle. If you use the euclidean algorithm you will decompose it with a square of length 5 and 5 unit squares. However, this algorithm will not give you the minimum number as it is possible to put only 5 squares : 3 of length 2 and 2 of length 3. –  Fractality Aug 29 '13 at 16:04
Actually m=5 for the (5,6) since it is not possible to tile this rectangle with less than 5 squares. Now we check that we cannot tile it with 7 squares which means that (5,6) is in the class number 2 (of course I should find a better name for these classes...) –  Fractality Aug 29 '13 at 16:10
–  Erel Segal Halevi Nov 2 '13 at 21:05