Tiling the plane with consecutive squares

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.

Solution 1:

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

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.) $n=6$ given by user "None"" />

and $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.

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

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

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

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

$n=8$ using two non-symmetrically bitten rectangle rectangles to form a symmetrically bitten one" />

Here is a solution for $n=9$. $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$.)

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

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

$n=6$" />

Solution 2:

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

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