Tiling a square with 3:1 rectangles

Question

It is known that a square can be tiled with $n$ rectangles whose length is double their width for any $n > 4$. In particular, no two rectangles can overlap and no part of any rectangle is outside the square. The rectangles can be of different size.

I am now investigating the same problem for rectangles whose length is triple their width. Clearly if we can tile a square with $m$ rectangles then we can also tile it with $m+4$ rectangles using the "building up" method from the video. Also by placing the square into a $2 \times 2$ square grid (adding 3 additional squares), we can also tile it with $m+9$ rectangles. Using these two facts I was able to show that we can tile a square for any $n > 26$. However I still don't know which $n \leq 26$ do not have a tiling (other than the trivial ones). How can I find them?

I am also interested in the general version of this problem, ie., when the length of the rectangles is $k$ times their width.

Answer 1

Given a solution with $m$ rectangles, we can turn it into a solution with $m+3$ rectangles by subdividing one of the rectangles into four smaller copies of half the side length. We can also do $m+4$ via the method you described. Here is a construction that produces $m+5$:

With these extensions and the base case $n=3$, we can get every integer except $n=1,2,4,5$; I haven't gone through a careful proof that all of these are impossible, but it's not too hard for $4$ and I suspect $5$ is doable with a bit of casework.

The general problem with $1\times k$ rectangles will have the trivial $m=k$ solution and the ability to extend solutions from $m$ to $m+4$ and $m+n^2-1$ for all $n$; this means that there will always be solutions past $k+5$. I expect each of $k+1,k+2,k+5$ could be tackled in generality, thereby solving the problem in all cases, but it might be fairly annoying to handle everything that comes up (especially in the $k+5$ case).