Tiling of a grid using triominoes

combinatoricspolyominotiling

I want to tile a $12 \times 12$ grid using L-shaped triominoes. There must be no overlaps or missing spaces, and I know that it is possible to do so.

Now, I want to know about a new condition: each row and column intersects the same number of triominoes. Intuitively it doesn't seem to work, is there a rigorous proof? I have been unable to make one.

I've previously proven each row/column intersects 8 triominoes, and determined the bottom row must look something like this:

A A a A A a A A a A A a
A a a A a a A a a A a a

No other way to fit. So I think that if each two rows have to be like that, we can only vary the 3×2 blocks, which still result in the same intersection. Trivially, every column 2 differs from column 1, even though rows are invariant

Here, I am wondering if there is any irregular way of arrangement that can overcome the issues. I have been unable to come up with any as of so far, is there any way to rigorously prove the non-existence?

Best Answer

It's not possible.

As you mentioned, we can consider an edge of the square. It needs to have $8$ trominoes, each of which will intersect it in either one or two cells, so there must be four trominoes taking up one cell on the bottom row and four taking up two cells. Call these Type A and Type B trominoes.

Consider one of the Type A trominoes:

       AA
_______*A_____

There is only one way to fill the cell marked with *:

      BAA
______BBA_____

This means that we can asssociate each type A tromino with a unique type-B tromino by looking at the cell in its "elbow", and vice versa to locate the A tromino from the B tromino. Since there are four of each, they'll need to be paired up one-to-one.

But now consider the corner of the grid! We have two possibilities up to symmetry:

|X        | Y
|XX___    |YY___

In the first case, both the western and southern edges demand contradictory placements of A-type trominoes:

|AA       |
|XA       |XAA
|XX___    |XXA__

And in the second case, there is no way to pair up the tromino with a type-A tromino on the southern edge in a way consistent with our requirements.

Related Solutions

Properly drawing a Penrose tiling using the pentagrid method

The problem in your code is

 var nextVertex = intersectionPt

which should really be

 var nextVertex = [0, 0]

(or at least a constant for all the tiles you generate).

The formula $\sum_{j=0}^4 n_j \mathbf e_j$ for the corner locations produces coordinates in a fixed coordinate system -- it's not relative to the intersection you start out with!

So the gaps you're seeing correspond to the distances between intersection points in the pentagrid, which you're erroneously adding to the tile coordinates.

A different problem that might bother you after you fix that is that the tiles you generate are too large compared to your pentagrid. You seem to be making the spacing between neighboring pentagrind lines equal to side length of the rhombs -- but the average distance between the "ribbons" corresponding to pentagrid lines is clearly longer than that. The tile side length is the width of a ribbon, and there's plenty of space left over between the ribbons!

A Penrose tiling with several roughly vertical ribbons marked
(Image from https://www.ams.org/publicoutreach/feature-column/fcarc-ribbons)

This is not a problem for generating an infinite tiling, but it will make it difficult to predict which part of the pentagrid to look for intersections in, if you want to find all the tiles in a particular area of the coordinate system.

Curiously, none of your references seem to mention this difference in scale explicitly -- those that give actual formulas seem to assume that the lines on the pentagrid are unit spaced and that the rhomb sides are a unit apart. However, those references also don't actually show the complete pentagrid in the same plane as the finished Penrose tiling. Apparently in their view the pentagrid is only there to define which coordinate sets in $\mathbb Z^5$ correspond to corner points in the tiling, but the actual tiles live in a completely different coordinate system.

If you want each tile corner to appear roughly in the vicinity of the region of the pentagrid that corresponds to it, you need to scale one of the coordinate systems to match. Your sources don't give you the scaling factor to use, so let's derive it. We'll keep the tile side lengths as $1$, and figure out how far apart the pentagrid lines must be.

Suppose we're in the region of the pentagrid in your question with 5-coordinate tuple $(0,0,0,0,0)$, and we now move some large distance $D$ due right. What is the five-tuple corresponding to the region we land in, if the grid spacing is $G$?

Well, we move past $\frac DG$ red lines, crossing them at right angles. The orange lines make an angle of $72^\circ$ with the red ones, so the number of them we cross is an integer close to $\frac DG \cos 72^\circ$. The rounding becomes negligible when we let $D$ got to infinity, so just pretend it is $\frac DG\cos 72^\circ$ exactly. Similarly, the green lines make an angle of $144^\circ$ to the red ones, so the number of them we cross is $\frac DG \cos 144^\circ$. (The factor $\cos 144^\circ$ is negative, corresponding to the fact that we cross these lines in the direction of decreasing region coordinates). And so forth with the cyan and blue, with angles of $216^\circ$ and $288^\circ$.

All in all, we end up with the 5-coordinates, up to rounding $$ (n_0,n_1,n_2,n_3,n_4) \approx \bigl(\tfrac DG,\tfrac DG\cos 72^\circ,\tfrac DG\cos 144^\circ,\tfrac DG\cos 216^\circ,\tfrac DG\cos 288^\circ\bigr). $$

The coordinates of the tile corner corresponding to that region is $$ \sum_{j=0}^4 n_j \mathbf e_j = \sum_{j=0}^4 n_j \bigl(\cos(j\cdot 72^\circ), \sin(j\cdot 72^\circ)\bigr). $$ We're just interested in the $x$-coordinate, so plug in the $n_j$s above to get $$ x \approx \frac DG \sum_{j=0}^4 \cos^2(j\cdot 72^\circ) = \frac DG \sum_{j=0}^4 \frac{1 - \cos(j\cdot 144^\circ)}2 = \frac DG \cdot \frac{5-\sum_{j=0}^4 \cos(j\cdot 144^\circ)}2 = \frac DG \cdot \frac52 . $$ (The last equals sign is because the sum of cosines is the change in $x$-coordinate from going all the way around a pentagram with unit sides).

If this $x$ is to grow at the same average rate as $D$, we must set $$ G = \frac52. $$

Beware, however, that even if you scale the grid by this factor, you still won't get closer than the tiles being "roughly in the vicinity" of the grid intersections that represent them. The nice images in the presentations you link to make it look like each rhombus will contain the grid intersection it comes from -- but it's not possible to align the grid such that this is always the case, nor such that every tile corner is inside the grid region that you compute its location from.

The pentagrid contains places where five grid lines almost but not quite meet in a point, like in this region of your pentagrid:

five lines almost meet

In this particular almost-intersection the fit is loose enough that we can see it's not exact -- but if your continue the pentagrid far enough, you will eventually find places where almost-intersections like this take place within arbitrarily small areas. The configuration has 6 internal regions and 10 actual intersections, and each of those intersections generates a full-sized tile in the final tiling. The 10 tiles come together in this pattern:

the part of the tiling arising from a single almost-intersection

whose diameter is somewhat larger than the pentagrid spacing! Clearly not all of the tiles can lie directly above their defining intersection.

(We can see a differently oriented instance of this pattern in your buggy picture. Those tiles have particularly small gaps between them because the intersections that represent them are close together).

Does a tiling being monohedral and monogonal imply that it is isohedral or isogonal

Let $\alpha_4 = 0. a_1 a_2 a_3 \ldots_4 $ be an irrational number in base 4 subject to $|a_i - a_{i+1} | = 1$.
(There are many ways to construct this, like starting from any irrational number in base 4 to determine the "height of the peaks".)

Consider unit squares laid out in the plane, where the lower left corner is $(m + \frac{1}{4} a_{|n| + 1 } , n )$, for integer $m, n$.
This is essentially rows of unit squares stacked upon each other, and shifted left/right by $1/4$ from the row above/below it, though in a aperiodic way.

It is monohedral as all tiles are unit squares.
It is monogonal as each vertex is a T with incident edges of length $1$ (for the leg of the T), and lengths $3/4, 1/4$ (for the arms of the T). We allow for reflections of the T.
It is neither isohedral nor isogonal as the only symmetries of the tiling are left/right translations due to the aperiodic nature.

Best Answer

Related Solutions

Properly drawing a Penrose tiling using the pentagrid method

Does a tiling being monohedral and monogonal imply that it is isohedral or isogonal

Related Question