5
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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$:

enter image description here

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).

$\endgroup$
5
  • $\begingroup$ Excellent answer, thank you! $\endgroup$ Jan 8 at 23:06
  • $\begingroup$ Can you explain why there will be solutions for $m > k+5$ in the general case? $\endgroup$ Jan 9 at 0:00
  • 1
    $\begingroup$ $n=5$ is not possible after all: puzzling.stackexchange.com/questions/114378/… $\endgroup$ Jan 9 at 7:30
  • $\begingroup$ In the general case, we have a solution with $k$ rectangles, and we have the ability to enlarge any solution by 3 or 4 rectangles via the same constructions as in the $1\times3$ case. This means we can obtain $k,k+3,k+4,k+3+3,k+3+4,k+4+4,k+3+3+3,\ldots$ and so everything beyond $k+5$ is attainable. $\endgroup$ Jan 9 at 7:36
  • $\begingroup$ Oh I see now. Thanks for the clarification. I was missing the fact that $m+3$ can be made for any $k$. $\endgroup$ Jan 9 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.