92
$\begingroup$

Can rotations and translations of this shape

Tile

perfectly tile some equilateral triangle?


I originally asked this on math.stackexchange where it was well received and we made some good progress. Here's what we learnt:

  • Because the area of the triangle has to be a multiple of the area of the tile, the triangle must have side length divisible by $5$ (where $1$ is the length of the short edges of the tile).
  • The analogous tile made of three equilateral triangles can tile any equilateral triangle with side length divisible by three.
  • There is a computer program, Burr Tools, which was designed to solve this kind of problem. Josh B. used it to prove by exhaustive search that there is no solution when the side length of the triangle is $5$, $10$, $15$, $20$ or $25$. The case of a triangle with side length $30$ would take roughly ten CPU-years to check using this method.
  • Lee Mosher pointed me in the direction of Conway's theory of tiling groups. This theory can be used to show that if the tile can cover an equilateral triangle of side length $n$ then $a^nb^nc^n=e$ in the group $\left<a,b,c\;\middle|\;a^3ba^{-2}c,a^{-3}b^{-1}a^2c^{-1},b^3cb^{-2}a,b^{-3}c^{-1}b^2a^{-1},c^3ac^{-2}b,c^{-3}a^{-1}c^2b^{-1}\right>$. But sadly it turns out that we do have that $a^nb^nc^n=e$ in this group whenever $n$ divides by $5$.
  • In fact one can use the methods in this paper of Michael Reid to prove that this tile's homotopy group is the cyclic group with $5$ elements. I think this means that the only thing these group theoretic methods can tell us is a fact we already knew: that the side length must be divisible by $5$.
  • These group theoretic methods are also supposed to subsume all possible colouring arguments, which means that any proof based purely on colouring is probably futile.
  • The smallest area that can be left uncovered when trying to cover a triangle of side length $(1,\dots,20)$ is $($$1$$,\,$$4$$,\,$$4$$,\,$$1$$,\,$$5$$,\,$$6$$,\,$$4$$,\,$$4$$,\,$$6$$,\,$$5$$,\,$$6$$,\,$$4$$,\,$$4$$,\,$$6$$,\,$$5$$,\,$$6$$,\,$$4$$,\,$$4$$,\,$$6$$,\,$$5$$)$ small triangles. In particular it's surprising that when the area is $1\;\mathrm{mod}\;5$ one must sometimes leave six triangles uncovered rather than just one.
  • We can look for "near misses" in which all but $5$ of the small triangles are covered and in which $4$ of the missing small triangles could be covered by the same tile. There's essentially only one near miss for the triangle of side $5$, none for the triangle of side $10$ and six (1,2,3,4,5,6) for the triangle of side $15$. (All other near misses can be generated from these by rotation, reflection, and by reorienting the three tiles that go around the lonesome missing triangle.) This set of six near misses are very interesting since the positions of the single triangle and the place where it "should" go are very constrained.

I'd also be interested in learning what kind of methods can be used to attack this sort of problem. Are there any high-level approaches other than the tiling groups? Or is a bare hands approach most likely to be successful?  

$\endgroup$
26
  • 3
    $\begingroup$ @Vincent That claim comes from this paper (Conway and Lagarias. Tiling with polyominoes and combinatorial group theory. 1990.) I think the argument is that colouring arguments can only be used to disprove the existence of signed tilings in which some copies of an "anti-tile" are allowed to appear. The tile homotopy group always detects whether or not a signed tiling exists and can sometimes tell you more. I think all this is best explained in the Michael Reid paper which I linked to above. $\endgroup$ Apr 13, 2017 at 11:51
  • 7
    $\begingroup$ Unfortunately, a Linear Program won't prove it. For $n$ from 8 to at least 40, it is possible to tile the $n$-by-$n$ equilateral triangle with a fractional combination of trapezoid tiles. (By "fractional combination", I mean placing trapezoid tiles with positive real weights, such that every triangle is covered by a total weight of 1.) $\endgroup$ Apr 13, 2017 at 21:45
  • 3
    $\begingroup$ @NoamD.Elkies I added some links to images of near tilings. $\endgroup$ Apr 13, 2017 at 22:20
  • 5
    $\begingroup$ Two comments: 1. A trick that can dramatically improve exhaustive search is to quit as soon as you get an empty region whose area is not a multiple of 5. I'm not sure if there is any freely available efficient implementation, though. It is not implemented in general-purpose SAT solvers. 2. You could try constructing the space of all signed tilings that are near-tilings to see if this space exhibits some structure that might suggest a proof that a tiling is impossible. $\endgroup$ Apr 14, 2017 at 20:10
  • 2
    $\begingroup$ After playing around quite a bit, I tend to believe now (say, with 60% probability...) that a tiling exists for n big enough. It would be sufficient to show that the tile is a rep-tile with a factor 5k, because then it would tile a triangle of side 30k. :) A brute force search for rep-tilings with factor 10 may just be at the limit of what is still computationally possible. $\endgroup$
    – Wolfgang
    Apr 15, 2017 at 14:35

5 Answers 5

79
$\begingroup$

It seems that one can color a 15-15-15-30 trapezoid with the given tiles. Here is a picture (sorry about adjacent figures that are the same color, I used random colors so hopefully there are no ambiguities):

enter image description here

In particular, OP pointed out that these scaled 1-1-1-2 trapezoids can tile any equilateral triangle whose side length is a multiple of three. So the original tile can tile any equilateral triangle whose side length is a multiple of 45.

I bet we didn't see answers for smaller $n$ due to an Aztec-diamond-like boundary condition with the corners.

$\endgroup$
9
  • 5
    $\begingroup$ How did you find this trapezoid tiling? $\endgroup$ Apr 16, 2017 at 22:40
  • 4
    $\begingroup$ One can also obtain a tiling of the $15-15-15-30$ trapezoid as follows: There is a tiling (with the original tiles) of the $15-7-15-22$ trapezoid. The former trapezoid is the latter trapezoid attached to a $15-8-15-8$ parallelogram. This parallelogram of course has the obvious tiling. $\endgroup$ Apr 17, 2017 at 0:12
  • 12
    $\begingroup$ @Joseph O'Rourke I saw that Josh B (the person who did many Burr Tools experiments) found a tiling of a rhombus with side length 15. So I figured a trapezoid of that size might be big enough to be tileable, and used a SAT solver on it. $\endgroup$ Apr 17, 2017 at 0:23
  • 1
    $\begingroup$ One can also use a good exact cover solver. I used sage.combinat.matrices.dlxcpp.OneExactCover from Sage. (One shouldn't use OneExactCover though, because this is a slow pure Python implementation of the DLX algorithm.) $\endgroup$ Apr 17, 2017 at 0:51
  • 4
    $\begingroup$ @Vepir Why not go big and ask whether a row of $1000001$ equilateral triangles can tile a big equilateral triangle? $\endgroup$ Apr 18, 2017 at 13:24
37
$\begingroup$

Since nobody has posted it, here's the smallest triangle tilable by the 'straight pentiamond', ie a side-30 triangle. Simple backtracking program, takes 0.5 seconds to show no tilings of the side-20 triangle, 4:39 for the side 25. Took 12 minutes to find 120 tilings for the side-30 before I stopped it.enter image description here

$\endgroup$
7
  • 3
    $\begingroup$ Can you adapt your code for the heptiamond case? We know from Reid that there exists a solution (see my answer) but he doesn't seem to have published his result, nor has he said how small the triangle can be. $\endgroup$ Dec 27, 2019 at 17:05
  • 2
    $\begingroup$ Nothing to 35 or less for the straight heptiamond. 35 was 8 minutes. Running 42,49 now. $\endgroup$ Dec 27, 2019 at 23:11
  • 2
    $\begingroup$ Also running the straight enneiamond (9-iamond). Nothing up to 39, running 42,45 now. $\endgroup$ Dec 28, 2019 at 2:11
  • 1
    $\begingroup$ Running straight 11-iamond. Nothing for 33 or 44, 55 running $\endgroup$ Dec 28, 2019 at 3:23
  • 1
    $\begingroup$ Finding another tiling for the higher cases I5, I7 etc is looking increasingly unlikely. I'm also trying to count the tilings for the I5 case, over 20 000 so far after 220 hours, simple backtracking program, placed about 68 000 000 pieces per tiling found. Finding one by hand would be a mission indeed. $\endgroup$ Jan 7, 2020 at 10:56
18
$\begingroup$

There was a conference in July 2007 at the University of Minnesota—Duluth in honor of Joseph Gallian's 65th birthday. At that conference, Michael Reid gave a talk about tilings, and among other things, he discussed this exact problem. Reid has shown that this "pentiamond" tiles all equilateral triangles with side length ≥30 (provided the side length is divisible by 5, of course). He has also shown that it is a "rep-tile": it tiles a copy of itself, scaled by a factor of k, if and only if k ≥ 11.

Naturally, one can generalize this problem by considering tiles consisting of 7, 9, 11, … triangles in a row. Reid conjectures that every such tile tiles all sufficiently large equilateral triangles whose area is a multiple of the area of the tile, as well as all sufficiently large scaled copies of itself. He has found a tiling of an equilateral triangle for the heptiamond case, but does not know what the smallest such triangle is.

It seems that Reid has never published these results. I've emailed him to see if he can supply more details of the tilings mentioned here.

$\endgroup$
5
  • 2
    $\begingroup$ Amazing! It sounds like he's well ahead of us. I was actually interested in the general conjecture from the start (a solution would let me kill this tricky problem), but I thought that making the problem more concrete would make it more interesting for a wider audience. $\endgroup$ Apr 20, 2017 at 23:35
  • $\begingroup$ As I understand the statement of the tricky problem, there is no tile as the area of the unit edge square and the unit edge triangle are not commensurable. Now if they have commensurable areas... . Gerhard "That Would Be Rather Tricky" Paseman, 2017.04.20. $\endgroup$ Apr 20, 2017 at 23:49
  • $\begingroup$ @GerhardPaseman The problem is to find a tile that can almost tile both of them. In particular such that the uncovered area is as small as possible relative to the area of the tile. You can look at the discussion page linked to from there if you want to see more detail. $\endgroup$ Apr 21, 2017 at 7:50
  • 2
    $\begingroup$ Did you hear anything back from Michael Reid? $\endgroup$ Apr 29, 2017 at 13:32
  • 1
    $\begingroup$ @OscarCunningham : Unfortunately not. You might try contacting him yourself. His email address is available on his website: cflmath.com/~reid/Polyomino/index.html $\endgroup$ Apr 29, 2017 at 20:52
15
$\begingroup$

I do not know whether the triangular region with size a multiple of 5 is tileable in general, but I can address the question in the last paragraph:

I'd also be interested in learning what kind of methods can be used to attack this sort of problem. Are there any high-level approaches other than the tiling groups?

Apparently, one can get extra mileage out of coloring arguments by considering semigroups rather than groups. Here is a conceptual proof, based on a coloring argument with 6 colors, that the size 5 triangular region is not tileable. After the preliminary work is done, the actual proof is very short. (The setup is completely general, but I have not figured out yet whether this method would be fruitful for proving or disproving tileability for larger sizes divisible by 5.)

We imagine that the region is broken into small triangles, which we call cells. Per usual conventions, "tile" means a congruent copy of the given shape with 5 cells ("prototile") located anywhere in the region.

Definition. A color is an element of $\{1,2,3,4,5,6\}$ (viewed modulo 6). A coloring is an assignment of a color to each cell of the region.

Let us situate the triangular region of size $n$ so that the base of the big triangle is horizontal and the triangle is above it. This region is divided into horizontal strips formed by small triangles with alternating orientations, with $2n-1, 2n-3, \ldots, 1$ cells, each strip zigzagging from the left side of the region to the right.

Proposition 1. There is a periodic coloring of a triangular region of any size with the following properties:

  1. The lower left corner cell is colored $1$.

  2. In every horizontal strip, the colors increment by $1$ as one zigzags through its cells from left to right.

  3. The colors of two cells sharing a horizontal side differ by $3$.

  4. For each tile situated anywhere in the region, its cells have distinct colors; let us label the tile (or its position) by the unique color which does not occur.

Example of such a coloring where n=5: Example

Proposition 2. For size 5 triangular region, the distribution of the colors is as follows: ($1^5 2^4 3^5 4^3 5^5 6^3$). Furthermore, the tiles containing corner cells are labelled $4$ if oriented clockwise and $6$ if oriented counterclockwise.

It is clear that in any tiling of a triangular region, each corner cell is covered by a unique tile. Moreover, if the region has size 4 or more, these tiles are distinct. Let us call them corner tiles. Each corner tile has one of two possible orientations (clockwise and counterclockwise).

Proposition 3. In any tiling of size 5 triangular region, the three corner tiles are either all oriented clockwise or all oriented counterclockwise.

Since 5$<$3+3, if two corner tiles had the opposite orientation, they would overlap.


Proof of non-tileability for size 5 triangular region: Since the region has 25 cells, any tiling has 5 tiles. Labelling them as in Proposition 1, by Proposition 2 there are exactly 2 tiles labelled $4$ and 2 tiles labelled $6$. This contradicts Proposition 3, because either all 3 corner tiles are labelled $4$ or they are all labelled $6$.

The main obstacle to generalizing this argument to larger size triangular regions is that since the corners of the region would be too far apart, Proposition 3 does not generalize. Clearly, one would need tighter control over how tiles are situated in the middle of the region. Perhaps, different colorings (or even combinations of colorings) can be exploited. Nonetheless, even in this form, Proposition 1 and the analog of Proposition 2 for a given size region impose some restrictions on potential locations of the tiles. For example, for size 10 there is a unique tile labeled $1$, a fact which can perhaps be exploited to drastically decrease search space of a brute force search algorithm.

$\endgroup$
3
  • $\begingroup$ Thanks for this! These insights could probably be combined with Timothy Chow's comment above to yield a fast computer program. I might implement this when I have the time. $\endgroup$ Apr 16, 2017 at 7:34
  • $\begingroup$ Retrospectively, I see that this kind of argument, along with the same 6-color coloring scheme, was proposed by Wolfgang in the comments. $\endgroup$ Apr 16, 2017 at 14:30
  • 3
    $\begingroup$ Better 2 people invent the wheel than nobody. But I am more and more convinced that for this specific tile, colorings essentially only yield "boundary constraints", meaning that for big n everything is possible. Nevertheless, some of the constraints should indeed have the potential to make computer searches more efficient. $\endgroup$
    – Wolfgang
    Apr 16, 2017 at 16:55
2
$\begingroup$

This does not answer the question, but I would like to update an assertion in the post.

A triangle of side 4 can hold three of the tiles with a hole in the center. 25 of these patterns can be repeated to cover all but 25 unit triangles of a triangle of side 20. Of course, one can use this for near optimal (if not optimal) partitions of triangles of side length 4k for k a positive integer.

Unless you are familiar with the group theoretic methods mentioned in the post above, I would not use them to dismiss coloring attempts. A pure argument by coloring may not work, but it may point to an argument that does. The checkerboard coloring aids me in a proof that the triangle of side 5 does not admit a tiling with the given tile.

Edit 2017.04.13. GRP: I will toss out an idea which comes from shearing the triangle into half a square. Perhaps it will lead somewhere.

Do a "square checkerboard" coloring of the triangle. Starting from the top, color the first two rows of triangles black, then the next two white, then the next two black. Another way to state this is to color the top diamond (two triangles joined by an edge) black, the next two top diamonds white, the next top three black, on down to the bottom triangles which will be black if n is odd, and white if n is even. Each tile covers either one white diamond and one black diamond and a half of some color, or it covers three halves of one color and two halves of another.

The idea is that this coloring produces more white diamonds than black diamonds when n is odd, and vice versa when n is even, as well as n triangles of one color. This should imply that a certain number of the tiles have to be oriented in a horizontal direction, and the hope is that (as five is not a multiple of 3) that this will lead to contradicting the existence of a tiling. End Edit 2017.04.13. GRP.

Gerhard "Give Simple Intuition A Chance" Paseman, 2017.04.13.

$\endgroup$
2
  • $\begingroup$ I updated my wording to be a bit kinder to colouring arguments. $\endgroup$ Apr 13, 2017 at 16:56
  • $\begingroup$ I just realized that I misinterpreted the notation regarding the triangle of side 20, as it actually represents 20 triangles of differing sizes. So the example above may be of interest, but clearly is not an optimal covering for sizes larger than 8. Gerhard "It Looks Very Pretty Though" Paseman, 2017.04.13. $\endgroup$ Apr 13, 2017 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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