17
$\begingroup$

For which $n$ is it possible to find a region $R$ made of non-overlapping squares of side length $1,2,\ldots,n$ which tiles the plane?

$n=1$ is trivial, and $n=2$ works as well. However, for $n\geq3,$ I am unable to find $R$ that work. Obviously, we can try every possible combination for smaller values, but I want to know for arbitrary $n$ what the conditions are for $R$ to exist.

$\endgroup$
  • 4
    $\begingroup$ Incidentally, the case $n=\infty$ is also possible; the plane can be tiled with one square of each size. See math.smith.edu/~jhenle/stp for the paper and some visuals of the process. $\endgroup$ – Steven Stadnicki Aug 20 at 21:14
  • $\begingroup$ it seems clear that you ask that for each $k$ with $1\le k\le n$ the region $R$ contains exactly one square of side length $k$. Not that I know whether it would make a difference, but do you allow mirror images of $R$ in the tiling? All examples posted so far involve a region $R$ and its copy when rotated 180 degrees, and translations of these, no mirror images. $\endgroup$ – Mirko Aug 23 at 4:35
  • $\begingroup$ There are solutions (so far) for $n\le9$. As $n$ gets bigger it seems more difficult to put the squares together to find a region $R$ that tiles the plane. (At least, I don't have a solution for $n=10$.) But, I wonder if there are some $p<q<r$ (with $p\ge10$) such that: (a) there are no solutions for $p\le n\le q$, (b) there are some/many solutions for $q<n\le r$ (but not for all such $n$), and (c) there is a solution for every $n\ge r$ (because there are "enough many" squares, making it easier to combine and match them, compared to what may happen when $n$ is not big enough). $\endgroup$ – Mirko Sep 4 at 4:14
13
+50
$\begingroup$

Here is a solution with $n=7$. Edit. I added some comments expressing my belief that $n=7$ may well be the largest solution. (Well, I keep editing my answer, but at the end I came up with a solution for $n=8$ too. And, for $n=9$.) solution with n=7

Grid created with the help of Pattern designer for craft projects

A solution with $n=6$ was given by user "None" in the comments to the answer by Steven Stadnicki. While I am at it, let me visualize it too. The basic building block described in the comment by "None" could tile the plane in two slightly different ways, as shown in the pictures below. (The first of these two ways is probably more natural, regular, canonical, when starting with a "symmetrically bitten rectangle" as in the answer by Steven Stadnicki.) solution with <span class=$n=6$ given by user "None"" />

and solution with <span class=$n=6$ given by user "None", a variation" />

Edit. Here is one more picture (unsuccessful attempts for $n=8$). It presents no proof, but it seems to suggest that as $n$ gets bigger, it becomes more difficult to lump the big squares together and to add the smaller ones, along, without creating too many jagged lines that would prevent the resulting region to be fitted to itself in a suitable way to tile the plane. I would think that solutions with $n>7$ are rare, perhaps nonexistent.

non-solutions <span class=$n>7$" />

Another edit. Here are some comments on the features of that pattern that works for $n=7$. It looks like a pistol, as shown below. The sum of the side lengths of the leftmost and rightmost squares is $7+5=12$ which is exactly twice the side length of the bottom square $12=2\cdot6$. In addition to that, note how the lengths of the two notches, each labeled with $4$ in the picture, match. All these features make possible to rotate this pattern $180$ degrees, match the two copies of the $6$-square leaving just enough room for the $7$- and the $5$-squares, and also have these notches of length $4$ match. Take a look at the first picture in this answer. Note also that there are certain notches in the pattern $R$ that solves the case $n=6$, by "None", and those notches do not quite match in length. But also, that $R$ is more like a "rifle"-shape, with just one straight leftmost edge (going with the square of side length $6$), which seems a bit less complicated than the pistol-shape for $n=7$ (where there is a "broken" left edge, consisting of the left edges of squares with side lengths $7$ and $6$).

pattern for <span class=$n=7$" />

The above would suggest to me that one could come up with suitable equations (a system of equations) involving sums and differences of the side lengths of all squares (one square with side length $k$ for each $k$ with $1\le k\le n$) that would express necessary conditions that a tiling is possible for any particular $n$. While I didn't try to go into the details, I could easily imagine that these necessary conditions would soon (for $n\ge8$?) become unresolvable. I would think that something along these lines would be amenable to a computer-assisted proof (and would require some time and dedication). I hope this provides some clarification why I ventured to comment earlier that "I would think that solutions with $n>7$ are rare, perhaps nonexistent". It may be paradoxical that, as Steven Stadnicki pointed out in a comment, there is a solution when $n=\infty$, and I claim that there may be no solutions already for $n=8$, but $\infty$ is an entirely different beast. (Even if $\infty$ and $8$ look alike, just rotate one $90$ degrees to get the other.) I looked in the paper dealing with the $n=\infty$ case, and a basic step in the proof there is that authors take the smallest square that has not been taken care of yet, and throw in a bunch of other squares, that have not yet been used, to form certain L-shapes that would eventually be put together to tile the plane. There is an infinite supply of these "other squares" that are used to form an L-shape (together with the smallest square that has not been taken care of yet), and these "other squares" might become very big, and we don't have this luxury when we work with some specific $n<\infty$. There are also the so-called squared-rectangles (and there is also suitable notation developed there that might be useful if one were to write equations expressing some constraints for the present problem), but these squared rectangles do not use all squares with side lengths between $1$ and $n$, but only some of them. (For example, one of the smaller squared rectangles (size $33\times32$) uses squares (one each) with side lengths $1, 4, 7, 8, 9, 10, 14, 15, 18$ only (but not every square with side length $k$ for $1\le k\le18$). My experience with the "Pattern designer for craft projects" seems to convince, at least me, that once you try to use all $k$ with $1\le k\le n$ then these "almost equal but not exactly" side lengths are not easy to put together without either leaving holes or creating a too jagged boundary, resulting in a region $R$ that cannot tile the plane. (I am well aware that the actual math behind this might be complicated, but nevertheless I believe that this experience trying to come up with suitable patterns for $n=8$ or $n=9$ is quite enlightening, on an intuitive level, to get a feel what the problem looks like.) As just one more remark, one might want to see if the area of the region $R$ might be relevant or useful in some way (somehow enter into this system of equations expressing the constraints). These areas clearly form the sequence of square pyramidal numbers $1, 5, 14, 30, 55, 91, 140,...$ where for example $5=1^2+2^2$, $14=1^2+2^2+3^2$, $30=1^2+2^2+3^2+4^2$, etc.

Here is one more picture with attempts to come up with "something" when $n=8$ or $n=9$, in particular try to come up with a pistol-shaped pattern (unsuccessfully, but that is the point that I am trying to make).

unsuccessful <span class=$n=8$ or $n=9$" />

Ok, I will add another picture. It is kind of the same partition as I have at the beginning, for $n=7$, except that I made the region $R$ look different. Instead of the pistol-shape that I first came up with, this time I have a "two-corner bitten rectangle" although it is not a "symmetrically bitten rectangle". (One could say that I took the original $R$ and moved the square with side length $6$ from the bottom to the left.) The region $R$ is different (and simpler-looking) but the partition is the same in the sense that each square occupies exactly the same position in the plane as before.

same solution <span class=$n=7$ but different $R$" />

The realization that one could work with a "two-corner bitten rectangle" even if not a "symmetrically bitten rectangle" came useful and handy. I tried to come up with such a region $R$ for $n=8$ and was even lucky to get one so that if you take $R$ and a copy of it rotated $180$ degrees, and put them together, you obtain a "symmetrically bitten rectangle". This of course resolves the $n=8$ case positively (contrary to all the doubts that I had expressed earlier ... though I tend to remain generally doubtful regarding larger values of $n$). Here is the picture for $n=8$.

solution for <span class=$n=8$ using two non-symmetrically bitten rectangle rectangles to form a symmetrically bitten one" />

Here is a solution for $n=9$. solution for <span class=$n=9$ using a non-symmetrically bitten rectangle" />

Note that in the above solution for $n=9$ we use a region $R$ which is "rectangle" with two opposite corners that are bitten, though not symmetrically bitten. This is good enough since we could use $R$ and its image under $180$ degrees rotation to form strips which tile the plane (even if they ziz-zag a bit). A similar pattern is also observed in the solution for $n=7$, the version that uses $R$ that is a rectangle with two opposite corners bitten (and not the pistol-shaped $R$, even if one could argue that the resulting partitions are the same). This pattern is also observed in the solution for $n=8$, though in that case we were lucky to obtain a symmetrically bitten rectangle, taking a non-symmetrically bitten one and its image under $180$ degrees rotation. So (in addition to the OP) one might ask if for every $n$ we could obtain a rectangle with two opposite corners that are bitten, though not necessarily symmetrically bitten (using one square of length size $k$ for each $k$ with $1\le k\le n$). Note how in the region that solves $n=9$, above, the $9$-square goes with the $6$-square, while the $8$-square goes with the $7$-square, kind of resembling Gauss' way to find $1+2+\cdots+9=(9+6)+(8+7)+\cdots=15+15+\cdots$, well the analogy is not quite exact (since the smaller squares do not seem to be matched in such a nice way, and Gauss' way was $(9+1)+(8+2)+\cdots$ rather than $(9+6)+(8+7)+\cdots$) but there may be some pattern to look for. There is also a little bit of matching along these lines in the $n=8$ solution above, where we have $1+2+\cdots+8=(5+7)+(4+8)+\cdots=12+12+\cdots$ (used to form a region $R$ which is a "rectangle" with two opposite corners that are bitten).

I posted a related question about what I call $n$-squared, oppositely bitten rectangles, and in particular about trivially bitten, evenly bitten, or nicely bitten rectangles $R$ (all of which could be used to tile the plane). See Building "oppositely bitten rectangles" with consecutive squares

I found a $10$-squared, oppositely bitten rectangle, but it is not nicely bitten (nor evenly bitten, nor trivially bitten), and in particular I do not seem to be able to use it (together with its $180^o$ rotated image) to tile the plane. (As seen, these are two slightly different versions, depending on where you choose to put the square with side length $5$.)

<span class=$10$-squared, oppositely bitten rectangle" />

Here is a variation of the $n=6$ solution with a region $R$ in which the squares appear in an "almost" linear order.

<span class=$n=6$ "almost" linear solution" />

And, here is a comparison of several solutions for $n=6$. Note how for the two solutions on the left, we start with different regions $R$, but we obtain the same "symmetrically bitten rectangle" when we put $R$ and $^-R$ together (where $^-R$ is a copy of $R$ rotated $180^o$). For the other two solutions (which are essentially different from each other and from the first two), we do not obtain a symmetrically bitten rectangle when we put $R$ and $^-R$ together, but there is enough symmetry so we obtain a partition of the plane nevertheless.

variations on <span class=$n=6$" />

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Too many edits already,just add a comment. For the region $R$ given by "None" that solves the $n=6$ case I made two statements that I want to take back: (a) The two ways to use $R$ to tile the plane given above seem equally "canonical" to me (even if the first seemed "more canonical" to me earlier), (b) I said there were no matching notches in that example, but this is also not true: There are notches of length $1$ that match. There are even more matching notches in the "almost linear" solution for $n=6$, some of length $1$, some of length $5$, and one self-matching of length $4$. Thank you! $\endgroup$ – Mirko Aug 26 at 2:57
9
$\begingroup$

$n=3$, $n=4$, $n=5$ all tile the plane:

n=3

n=4

n=5

Each of these 'symmetrically bitten rectangle' shapes tiles the plane by translation (e.g., attach them along opposite long sides to form diagonal bands, then stack those diagonal bands next to each other).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice! But, for $n>5,$ we run into a problem, no? $\endgroup$ – MandelBroccoli Aug 1 at 1:41
  • 3
    $\begingroup$ @MandelBroccoli: $n = 6$ also tiles the plane the same way. From top left corner, place $6$, $5$, $3$, $4$ next to each other, top edges aligned. Put $2$ and $1$ below the three. Copy, rotate $180°$, and you get a $19 \times 10$ block with two $1 \times 4$ removed from diagonal corners (lower left and upper right). This also tiles the plane. $\endgroup$ – None Aug 1 at 2:55
  • $\begingroup$ Okay...but is there a way to prove that this works for all $n,$ or show that certain $n$ work? Will you always get a "symmetrically bitten rectangle"? $\endgroup$ – MandelBroccoli Aug 1 at 5:00
  • 1
    $\begingroup$ @MandelBroccoli I wouldn't be shocked if a construction existed for all $n$, but the one for $n=6$ is fundamentally different enough from the others that it's not clear that there's any pattern to continue. $\endgroup$ – Steven Stadnicki Aug 1 at 6:52

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.