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!