6
$\begingroup$

A triangle $T(n)$ is a polyomino with columns on the same base with lengths $1, 2, 3, \cdots, n$.

In this slide deck (original PPT, images may be corrupt), Friedman looks at tilings of these triangles by exactly two tiles. I'm wondering what single tiles can tile triangles. So far, I have been only able to find tilings by smaller right trominoes (and monominoes, of course), such as this one:

enter image description here

In the deck, Friedman identifies some properties of tiling sets that can tile triangles, which limits the possibilities if the tileset has only one tile:

  • Tiles must have the diagonal property; i.e. the ability to cover more diagonal cells (red, marked with a dot) than those below them (green, marked with a square):

enter image description here

  • Tiles must have the bottom property; i.e. the ability to cover more bottom cells (red, marked with a dot) than those above them (green, marked with a square):

enter image description here

This already limits possible tiles to only triangles for small polyominoes. The T-tetromino and the polyomino below have both these properties:

enter image description here

(Clearly, it cannot tile a triangle. Other examples are similar if the tiles are small... but its not clear what may happen if the tiles are much bigger.)

If the rectangular hull is not square, we can place a tile so that its hull is vertical or horizontal. The tile in the top corner must be vertical, and the one in the bottom must be horizontal. Therefore there must be at least one transition between horizontal and vertical. This is useful to eliminate certain infinite patterns. For example, the T-tetromino can fit in the top corner in only one way. The next open diagonal cell and its neighbors can only be tiled with vertical tetrominoes; and so all diagonal cells can only be tiled with vertical dominoes. But we eventually need a horizontal tile; since this is impossible there is no tiling of triangles by the T-tetromino.

enter image description here

This is called the "orientation theorem" in the deck.

enter image description here

A region/tile is called balanced if it has the same number of black and white squares under the checkerboard coloring. Triangles are never balanced, so they cannot be tiled by a tile that is balanced.

All these above bring us quite far. My question is:

Are there any other shapes that can tile triangles?

(An earlier version of this question said the only tilings I could find were by other triangles. Those look feasible, but I have not in fact be able to find one of those either. Note that none of the properties mentioned above can be used to rule out triangular tiles.)

$\endgroup$
4
  • 1
    $\begingroup$ Can you explain why e.g. the T tetromino doesn't satisfy both the diagonal and bottom properties? (Obviously it can't tile a triangle, but I don't see why it doesn't meet both of those criteria.) $\endgroup$ Apr 29 at 0:02
  • 1
    $\begingroup$ You are right I made a mistake! The T tetromino gives a good example of why the orientation theorem is useful; will update the question. $\endgroup$ Apr 29 at 0:20
  • 1
    $\begingroup$ Do you have any examples of triangles beyond the L tromino tiling strictly larger triangles? I haven't found any. $\endgroup$ Apr 29 at 1:02
  • 2
    $\begingroup$ Hmmm I thought it would be easy enough following a pattern of the tromino but now that I tried it it is not so easy (if possible) after all. An interesting problem in itself. $\endgroup$ Apr 29 at 1:38
4
$\begingroup$

With the help of a computer, I found a tiling of $T(32)$ by $T(3)$. No tilings exist for $T(k)$, with $3 < k < 32$ by $T(3)$.

enter image description here

Here are some additional observations for tilings of $T(n)$ by $T(m)$:

  • The two corners at the extremes of the diagonal can be tiled only one way.

  • All other tiles along the orthogonal edges must be part of a $m \times (m + 1)$ rectangle (if $m > 2$). This is easily proven by analyzing a handful of cases that can occur at the borders.

  • Because of symmetry, we can fix a rectangle in the third corner, and putting all of the above together, we can deduce some additional constraints by counting rectangles of different orientations on the orthogonal sides: $$n = (2+k)m + \ell(m + 1) = (1 + k')m + (1 + \ell')(m + 1),$$ where $k, k', \ell, \ell' \geq 0$.

    This identity adds a number-theoretic flavor to what the possibilities are, similar to tilings of rectangles by rectangles.

  • Along the diagonal, we also have some constraints: either all diagonal cells of a tile coincide with the region diagonal, or fewer (one or zero) cells do. The latter type can only be multiples of $m$ diagonal cells apart. (For example, there are two such tiles in the image in this answer, and they are $3\times 8$ cells apart.)

  • We can potentially speed up the tiling algorithm by exploiting these two constraints at the borders and tile them first. I have not tried it yet.

Update: Using the trick Jaap Scherphuis mentioned in the comments, I managed to also find that the only tilings of $T(k)$ for $32 < k < 40$ are extensions of $T(32)$ in that all can be obtained by adding rows of width 3 or 4 to $T(32)$, so $T(35)$, $T(36)$, and $T(39)$. See for example $T(39)$ below. I also found that no tilings of $T(k)$ by $T(4)$ exists for any $4 < k < 55$.

Which of the combinations you bar has a serious effect on the timing if the tiling does exist. One pair will occur naturally because of the order of the tiles (assuming you try the tiles out in the same order in the search); if you bar this pair instead of the other one, the algorithm will be (substantially) slower than not using this trick at all when the tiling exists.

enter image description here

$\endgroup$
3
  • $\begingroup$ What program did you use to locate this tiling? None of the tiling software I tried was able to solve this (at least, not in the time I was willing to wait for). $\endgroup$ May 2 at 0:45
  • $\begingroup$ I coded my own program (for exactly the reason most available solvers are either slow or too specific). $\endgroup$ May 2 at 2:06
  • 2
    $\begingroup$ Most solvers would get bogged down by all those 3x4 rectangles that can be filled in 2 ways. From the look of that solution, you cut those out, letting the reflected versions of those rectangles be forbidden configurations. Was that the only trick you needed to crack this tiling problem? $\endgroup$ May 5 at 8:37

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.