19
$\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$
3
  • 5
    $\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$ Aug 20, 2020 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, 2020 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, 2020 at 4:14

3 Answers 3

14
+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$" />

$\endgroup$
1
  • $\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, 2020 at 2:57
10
$\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).

$\endgroup$
4
  • 2
    $\begingroup$ Nice! But, for $n>5,$ we run into a problem, no? $\endgroup$ Aug 1, 2020 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, 2020 at 2:55
  • 1
    $\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$ Aug 1, 2020 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$ Aug 1, 2020 at 6:52
2
$\begingroup$

Here's another way of constructing these. I start with the area of the first N squares, eg for 1 to 9 the area is 285 which is 3x5x19. Then I try to tile a torus of 15x19, then klein bottles of 15x19 and 19x15, finally a manifold (real projective plane) of those dimensions. This all fails for 9, so I use two sets and try torus, klein bottles, rpp for whichever rectangle sizes are convenient. Sooner or later one will work. Here are two sets for 1 to 9 in a 19x30 klein bottle, doubled and flipped so it forms a patch which tiles the plane by translation only. The resulting four sets of squares 1 to 9 are coloured differently. enter image description here

For 1 to 10 I had to use three sets on a 33x35 torus so I get a translation-only patch with three sets. I told the tiling program to make sure each of the three sets was linked into one self touching area, but if such a tiling did not exist we could use disjoint sets too. enter image description here

It seems that when we allow multiple sets like this, the probability of a tiling increases with N but a proof is not in my skill set. I might try a few larger N to see whether my program can manage the tiling in reasonable time. One thing I noticed is that the area always seems to be nicely composite, rather than a prime or near prime.

Here is another triple set for 1 to 11, on a cylinder. Note that the sets are contiguous, blue and orange join when wrapped top and bottom. enter image description here

And here's a two-set tilings for 1 to 11 using a 44x23 Klein bottle. This took my program 86 hours to find. enter image description here

Just found a 1 to 15 with two sets on a cylinder. enter image description here

Here's a triple 1 to 12 on a toroid enter image description here

$\endgroup$
6
  • 2
    $\begingroup$ This is a very interesting development. One thing to note is that the area must be "nicely composite" (for $n>2$) because of the sum of the first $n$ squares is $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.$ This is definitely something to look into! $\endgroup$ Jan 11, 2021 at 4:14
  • $\begingroup$ Ah of course... so there are at least three factors. I wrote a tiny program to list them out, it seems the biggest problem will be the occasional number like 226 for which the sum of squares has prime factorisation 113, 151, 227 and only one candidate rectangle, 227 x 17063. But using a few hundred copies of the set of squares will easily fix this. Just not so easy to find the tiling. $\endgroup$ Jan 11, 2021 at 5:48
  • 2
    $\begingroup$ I'm a little confused by this. You mention using multiple sets. I am assuming this means using two regions $R_1$ and $R_2$ to get a dihedral tiling of the plane. However, you mentioned that finding a single region $R$ (monohedral tiling) for $n=9$ is not possible However, in another answer a user found one for 9 and 10 (i.stack.imgur.com/Dt3Kv.png). It seems that tiling a torus, cylinder, klein bottle and rpp are harder to do than tiling the plane (since the program failed). Which program are you using to compute this? $\endgroup$ Jan 11, 2021 at 20:41
  • $\begingroup$ My method is not comprehensive, it is significantly simplified compared to any method that attempts to find the minimal such region. I search only on rectangular regions with wrap from left to right and/or top to bottom, with or without flipping while wrapping.There are typically many other ways to accomplish repeated planar tilings. I didn't even search all the possible rectangle-based regions for the 1 to 9 case. My method was simply to demonstrate that allowing multiple sets of the squares (non-congruent on their own) to be combined into a single region might lead to an answer to your query $\endgroup$ Jan 12, 2021 at 0:38
  • 1
    $\begingroup$ Ok, I see now. I think the main reason the program won't give the $n=9$ monohedral tiling is because of the "wrapping." It is not necessary for a tiling of the plane to tile any finite rectangle, hence it is possible for even an exhaustive search to yield no result. However, multiple regions is quite an interesting idea to explore. $\endgroup$ Jan 12, 2021 at 2:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .