Tiling Rectangles with Gaps by Ribbon Right Trominoes

Premalatha Junius, Viorel Nitica

Department of Mathematics, West Chester University, West Chester, PA, USA.

DOI: 10.4236/ojdm.2017.72010                

Abstract

We show that the least number of cells (the gap number) one needs to take out from a rectangle with integer sides of length at least 2 in order to be tiled by ribbon right trominoes is less than or equal to 4. If the sides of the rectangle are of length at least 5, then the gap number is less than or equal to 3. We also show that for the family of rectangles that have nontrivial minimal number of gaps, with probability 1, the only obstructions to tiling appear from coloring invariants. This is in contrast to what happens for simply connected regions. For that class of regions Conway and Lagarias found a tiling invariant that does not follow from coloring.

Keywords

Tiling Rectangles, Ribbon Tromino, Rectangle with Gaps, Gap Number, Coloring Invariants

1. Introduction

We study tiling problems for regions in a square lattice by tile sets made of polyominoes. Polyominoes were introduced by Golomb and the standard reference is the book Polyominoes [1] . We consider the tile set $\sum =\left\{T_1,T_2\right\}$ , where $T_1,T_2$ are right trominoes, and the tile set $\bar{\sum }=\left\{T_1,T_2,T_3,T_4\right\}$ , containing two more elements which are straight trominoes. See Figure 1. Only translations of the tiles $T_1,T_2,T_3,T_4$ are allowed in a tiling.

A $1\times 1$ square in the lattice is called a cell. We find the least number of cells one needs to take out from a rectangle $k\times l$ with integer height k and base l, in order for the resulting shape to be tiled by $\sum$ . Following [2] , we denote it by $M\left(k,l\right)$ and call it the gap number.

It is convenient to state the main results in cases sorted by the congruence classes modulo 3 for the height and modulo 2 for the base. As the tile set is

Figure 1. The tiles $T_1,T_2,T_3$ and $T_4$ .

symmetric about the line $x=y$ , the results for the cases not discussed below can be obtained via a symmetry.

Our main results are the following:

Proposition 1.1. If one of the sides of the rectangle has length 1 or 2, and $k,l\ge 1$ , the gap number is:

1) $M\left(3k,1\right)=3k$ ;

2) $M\left(3k,2\right)=0$ ;

3) $M\left(1,2l\right)=2l$ ;

4) if $l\equiv 1\left(\mathrm{mod}3\right),M\left(2,2l\right)=1$ ;

5) if $l\equiv 2\left(\mathrm{mod}3\right),M\left(2,2l\right)=2$ ;

6) if $l\equiv 0\left(\mathrm{mod}3\right),M\left(2,2l\right)=0$ .

The proof of Proposition 1.1 is immediate. For the rest of the paper both sides of the rectangle are of length at least 3. The following cases appear: $3k\times 2l$ , $3k\times \left(2l+1\right)$ , $\left(3k+1\right)\times 2l$ , $\left(3k+1\right)\times \left(2l+1\right)$ , $\left(3k+2\right)\times 2l$ , $\left(3k+2\right)\times \left(2l+1\right)$ , where $k,l\ge 1$ .

Theorem 1.2. Let $k,l\ge 1$ . If both sides of the rectangle are at least 3, the gap number is:

1) $M\left(3k,2l\right)=0$ .

2) a) If k is even, $M\left(3k,2l+1\right)=0$ .

b) If k is odd, $M\left(3k,2l+1\right)=3$ .

3) a) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=2$ .

b) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=4$ if $k=1$ or $l=2$ , and

$M\left(3k+1,2l\right)=1$ if $k\ge 2;l\ge 5$ .

c) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=0$ .

4) a) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+1,2l+1\right)=3$ if k even, $M\left(3k+1,2l+1\right)=0$ if k odd.

b) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+1,2l+1\right)=2$ .

c) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(4,2l+1\right)=4$ , and $M\left(3k+1,2l+1\right)=1$ if $k\ge 2$ .

5) a) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=1$ .

b) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=2$ .

c) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=0$ .

6) a) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=3$ if k odd, $M\left(3k+2,2l+1\right)=0$ if k even.

b) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=1$ .

c) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=2$ .

Corollary 1.3. The gap number of a $k\times l$ rectangle, $k,l\ge 2$ , for the tile set $\sum$ is always ≤4. If both sides of the rectangle are at least 5, then the gap number is less or equal to 3.

To prove Theorem 1.2 we use the following results of Conway-Lagarias [3] and Pak [4] .

Theorem 1.4. For any simply connected region that can be tiled by $\sum$ or $\bar{\sum }$ , the difference between the number of $T_1$ tiles and the number of $T_2$ tiles that appear in the tiling is an invariant.

We call a rectangle deficient if a cell is missing, and we call a rectangle with gaps if one or more cells are missing. Related results to our topic in the literature are about tiling deficient boards/rectangles by right trominoes, all four orientations allowed. Golomb [1] proved that all $2^n\times 2^n$ deficient boards can be tiled. Chu-Johnsonbaugh [5] [6] studied the general case of boards and deficient boards: any deficient $n\times n$ board is tilable if and only if n is not divisible by 3. Later Ash-Golomb [7] found that an $m\times n$ deficient rectangle $2\le m\le n;3|mn-1$ , has a tiling if and only if neither side has length 2, unless both of them do; or $m\ne 5$ . Furthermore, in all the exceptional cases, they found all missing cells for which tiling is possible. The paper [8] investigates tiling of a deficient board/rectangle by L-shaped tetrominoes and indicates all missing cells for which the tiling is possible and the papers [9] [10] investigate tiling of a deficient board/rectangle by P-pentominoes and indicate all missing cells for which the tiling is possible. Hochberg [2] studies the least number of cells that have to be taken out from a rectangle in order to be tiled by T-tetrominoes (the gap number).

One motivation to study tilings of rectangles with gaps by $\sum$ is to see if for such non simply connected regions there exist tilings invariants different from coloring invariants. We refer to [3] for a discussion of coloring invariants. We observe that, for rectangles with both sides at least 5, once the minimal number of holes is non trivial, the only obstructions to tilings are essentially coloring invariants. This fact is also true for the tile set $\bar{\sum }$ .

Theorem 1.5. 1) If a deficient rectangle with sides ≥5 has area multiple of 3 and if the missing cell is at distance ≥5 from the boundary, then the only obstructions to tiling by $\sum$ are coloring invariants.

2) Assume that a rectangle with sides ≥5 and with two gaps has area multiple of 3. If the missing cells are at distance ≥5 from the boundary and at horizontal and vertical distance ≥12 from each other, then the only obstructions to tiling by $\sum$ are coloring invariants.

3) Assume that a rectangle with sides ≥5 with three gaps has area multiple of 3. If the missing cells are at distance ≥9 from the boundary and at horizontal and vertical distance ≥12 from each other, then the only obstructions to tiling by $\sum$ are coloring invariants.

Corollary 1.6. For the family of rectangles that have nontrivial minimal number of gaps, with probability 1, the only obstructions to tiling by $\sum$ appear from coloring invariants.

We summarize the rest of the paper. In Section 2 we prove Theorem 1.2. In Section 3 we prove Theorem 1.5, 1). We actually describe all deficient rectangles that allow for tilings by $\sum$ . It turns out that, while obstructions different from coloring invariants may appear, they are all located close to the boundary of the rectangle. In Section 4 we prove Theorem 1.5, 2). In Section 5 we prove Theorem 1.5, 3). Several open questions of interest are mentioned in Section 6.

2. Proof of Theorem 1.2

We note that a $3\times 2$ or a $2\times 3$ rectangle can be tiled by two tiles from $\sum$ . This implies that any rectangle that has a side divisible by 3 and the other side even can be tiled by $\sum$ . We will also use a coloring argument. If a tiled region is colored with three different alternating colors, along the NW-SE diagonals, each tile in $\sum$ is colored by all three colors, so the number of cells in the tiled region covered by each color is one third of the area of the region.

Lemma 2.1. If l or k are even, then $M\left(3k,l\right)=0$ .

Proof. If l is even, then $l=2n,n$ an integer. The rectangle can be broken into $3\times 2$ pieces, so it can be tiled by $\sum$ . If k is even, then $3k=6n,n$ an integer. We have two sub cases depending whether l is even or odd. Suppose l is even; then $l=2m$ , so the rectangle is of size $6n\times 2m$ , which is tileable by $\sum$ . Suppose l is odd; then $l=2m+1$ , so we have a rectangle of the size $6n\times \left(2m+1\right)$ . We break it into two smaller rectangles of sizes $6n\times 2\left(m-1\right)$ and $6n\times 3$ . Both have a side divisible by 3 and the other side even. Hence, the whole rectangle is tileable by $\sum$ .

Lemma 2.2. If l and k are odd, then $M\left(3k,l\right)=3$ .

Proof. As $k,l$ odd, one has $k=2m+1,l=2n+1$ , $m,n$ integers. Break the rectangle into two smaller pieces of sizes $3k\times 2\left(n-1\right)$ and $3k\times 3$ . The first one can be tiled by $\sum$ . The second one, which has sizes $\left(6m+3\right)\times 3$ , can be divided into two smaller pieces of sizes $2\left(3m+1\right)\times 3$ and $1\times 3$ . The first one is tileable by $\sum$ . We use a $T_3$ tile to cover the $1\times 3$ rectangle. Hence, the initial $3k\times l$ rectangle can be tiled by $\bar{\sum }$ , using a single tile not in $\sum$ . However, the $3k\times l$ rectangle can not be tiled by $\sum$ . Indeed, by Theorem 1.4, the difference between the numbers of $T_1$ tiles and $T_2$ tiles is constant for any tiling by $\sum$ or by $\bar{\sum }$ . As we already have a tiling by $\bar{\sum }$ for which the difference is zero, for any tiling by $\sum$ the difference has to be zero. So we need to use an even number of tiles from $\sum$ . As the area of the $3k\times l$ rectangle is odd, this leads to a contradiction. Therefore, $M\left(k,l\right)\ge 3$ . Figure 2 shows a tiling with 3 missing cells, so $M\left(3k;l\right)=3$ . Regions I-III are of the sizes $3a\times 2b$ or $2a\times 3b$ .

Lemmas 2.1, 2.2 cover cases 1. and 2. The following lemma covers case 3.

Lemma 2.3. i) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=2$ .

ii) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=4$ for $k=1$ or $l=2$ , and

$M\left(3k+1,2l\right)=1$ for $k\ge 2,l\ge 5$ .

iii) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+1,2l\right)=0$ .

Figure 2. Lemma 2.2.

Proof. The proof of (iii) is similar to that of Lemma 2.1, splitting it in two cases, k odd/even. For (i) and (ii) with $k\ge 2;l\ge 5$ , possible tilings are shown in Figure 3, where the gray cells are the missing cells. In (a), Region I is of the size $\left(3k+1\right)\times 6b$ , so can be decomposed in $3a\times 2b$ or $2a\times 3b$ regions, and Region II is of the size $2a\times 3b$ . In (b), Regions I-IX are part of a cover of a $7\times 10$ rectangle and are of the size $3a\times 2b$ or $2a\times 3b$ . Region X is of size $7\times 6b$ and can be decomposed in $3a\times 2b$ or $2a\times 3b$ regions. Region XI is of size $3a\times 2b$ .

For (ii), $l\equiv 2\left(\mathrm{mod}3\right)$ , we discuss the cases $k=1$ or $l=2$ . Consider $k=1$ . The other case is similar. The rectangles are of size $4\times 2\left(3n^{\prime }+2\right)$ with $n^{\prime }$ integer. We have to take at least a square out. Assign a pair of coordinates to each square starting with the one in the lower left corner that has coordinates $\left(1,1\right)$ . Due to a coloring argument using three colors, if a square is taken out, then the sum of its coordinates is congruent to 2 modulo 3.

If a boundary cell is taken out, the remaining region can be tiled by horizontal and vertical trominoes and its invariant is 0. So, if the region can be tiled by $\sum$ , only an even number of tiles can be used. As the area of the region is odd, one has to take out at least 4 cells for a tiling to be possible.

If an interior cell is taken out, group the cell with a tile from $\sum$ to form a $2\times 2$ square that touches the boundary of the rectangle. This gives the only possible tiling of the region surrounding the cell. Taking the $2\times 2$ square out, creates a simply connected region that can be easily tiled by $\bar{\sum }$ and has invariant 1. This forces us to use an even number of tiles in order to tile the deficient rectangle, so due to the area constraint, one has to take out at least 4 cells for a tiling to be possible. Finally, note that if the first column of 4 cells is deleted from a rectangle, the rest can be tiled.

The following lemma covers case 4.

Lemma 2.4. i) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+1,2l+1\right)=3$ if k even,

$M\left(3k+1,2l+1\right)=0$ if k odd.

ii) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+1,2l+1\right)=2$ .

iii) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+1,2l+1\right)=4$ for $k=1$ , and

$M\left(3k+1;2l+1\right)=1$ for $k\ge 2$ .

Proof. As $2l+1$ is divisible by 3, first part of (i) follows from Lemma 2.2, and the second part from Lemma 2.1. For (ii), tilings are shown in Figure 4(a),

Figure 3. Lemma 2.3.

Figure 4. Lemma 2.4.

and Figure 4(b), depending on whether k is odd/even. For (iii), tilings for $k\ge 2$ depend on whether k is odd/even, as shown in Figure 4(c) and Figure 4(d). In (a), Region I is of the size $4\times 3a$ , Region II is of the size $3\times 2$ and Region III is of the size $6a\times (2l+1)$ . In (b), Region I-IV are either of the size $2\times 3$ or $3\times 2$ , and they form a rectangle of size $5\times 5$ with the center cell being taken out. Region V is of the size $2\times 3$ , Region VI is of the size $6a\times 5$ and Region VII is of the size $\left(7+2a\right)\times 6b$ . In (c), Region I-VIII are either of the size $3a\times 2b$ or of the size $2a\times 3b$ and form a $10\times 7$ rectangle, Region IX is of size $6a\times 7$ and Region X is of size $\left(10+6a\right)\times 6b$ . In (d), Region I-III are either of the size $3\times 4$ or $4\times 3$ , Region IV is of size $6a\times 7$ and Region V is of size $\left(7+6a\right)\times 6b$ .

Consider now case (iii) with $k=1$ . The rectangles are of size $4\times \left(6n^{\prime }+1\right)$ with $n^{\prime }$ integer. We have to take at least a square out. Assign a pair of coordinates to each square starting with the one in the lower left corner that has coordinates $\left(1,1\right)$ . Due to a coloring argument using three colors, if a square is taken out, then the sum of its coordinates is congruent to 2 modulo 3. If a boundary cell is taken out, the remaining region can be tiled by horizontal and vertical trominoes, so its invariant is 0. So, if the region is tileble by $\sum$ , only an even number of tiles can be used. As the area of the region is odd, one has to take out at least 4 cells for a tiling to be possible. If an interior cell is taken out, group the cell with a tile from $\sum$ to form a $2\times 2$ square that touches the boundary of the rectangle. This gives the only possible tiling of the region surrounding the cell. Taking the $2\times 2$ square out, creates a simply connected region that can be easily tiled by $\bar{\sum }$ and has invariant 2. This forces us to use an even number of tiles in order to tile the deficient rectangle, so due to the area constraint, one has to take out at least 4 cells for a tiling to be possible. Now it is easy to see that if we take out the first column consisting of 4 cells from a rectangle, the rest can be tiled.

The following lemma covers case 5.

Lemma 2.5. i) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=1$ .

ii) If $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=2$ .

iii) If $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+2,2l\right)=0$ .

Proof. The proof of (iii) is similar to that of Lemma 2.1, splitting it in two cases, k odd/even. For (i) and (ii) tilings are shown in Figure 5, with the missing cells colored gray. In (a), Regions I-III are either of the size $3a\times 2b$ or $2a\times 3b$ . In (b), Region I-IV are either of the size $3a\times 2b$ or $2a\times 3b$ .

The following lemma covers case 6.

Lemma 2.6. i) If $l\equiv 1\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=3$ if k odd,

$M\left(3k+2,2l+1\right)=0$ if k even.

ii) $l\equiv 2\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=1$ .

iii) $l\equiv 0\left(\mathrm{mod}3\right),M\left(3k+2,2l+1\right)=2$ .

Proof. As $2l+1$ is divisible by 3, first part of (i) follows from Lemma 2.1, and the second part from Lemma 2.2. Tilings for (ii) are shown in Figure 6, split in two cases, depending on k odd/even. In (a) Regions I, II, III, IV are $2\times 3$ or $3\times 2$ rectangle, Region V is a $6a\times 5$ rectangle and Region VI is a $\left(5+6a\right)\times 6b$ rectangle. In (b) Region I is a $6\times 2$ rectangle, Region II is a $6a\times 3$ rectangle, Region III is an $8\times 3$ rectangle, Region IV is a $\left(6a+8\right)\times 6b$ rectangle.

Tilings for (iii) are shown in Figure 7, split in two cases, depending on k odd/even. In (a) Regions I, III are $2\times 3$ rectangles, Region II is a $3\times 4$ rectangle, Region IV is a $3\times 2$ rectangle, Region V is a $6a\times 7$ rectangle and Region VI is a $\left(5+6a\right)\times 6b$ rectangle. In (b) Region I is a $6\times 4$ rectangle, Re

Figure 5. Lemma 2.5.

Figure 6. Lemma 2.6.

gion II is a $2\times 3$ rectangle, Region III is an $8\times 3$ rectangle, Region IV is a $6a\times 7$ rectangle and region V is a $\left(8+6a\right)\times 6b$ rectangle. This ends the proof of Theorem 1.2.

3. The Case of One Missing Cell

In this section we claim frequently, without showing the proofs, that certain tilings of deficient rectangles are possible. An easy way to check our claims is to use the free available software Polysolver [11] . Due to the similarity in the technique, we show detailed proofs only for Theorems 3.1, 3.2 and 3.3. In what follows it is convenient to label the cells in a rectangle by the coordinates of their lower left corner. We assume that the lower left corner of a rectangle has coordinates $\left(0,0\right)$ .

Theorem 3.1. A deficient rectangle $\left(6p+1\right)\times \left(6q+1\right),p,q\ge 1$ can be tiled by $\sum$ if and only if the missing cell has the sum of the coordinates congruent to 0 modulo 3 and is different from $\left(6p-2,2\right)$ or $\left(2,6q-2\right)$ .

Proof. Figure 8 shows the good cells in a $7\times 7$ square. For the general case, use first a coloring argument to show that the missing cell has the sum of the coordinates congruent to 0 modulo 3. To show that tiling is possible if the cell is different from $\left(6p-2,2\right)$ or $\left(2,6q-2\right)$ one checks, using a computer or by hand, that the statement is true for $7\times 7,7\times 13,13\times 7,13\times 13$ rectangles. If a rectangle is of bigger size, then place inside it one of the above deficient rectangles in positions translated from the origin by a vector with both coordinates multiple of 6. The remaining region can be decomposed in rectangles that can be tiled by $\sum$ . So the tiling of the whole deficient rectangle is possible. We show that removing the cell $\left(6p-2;2\right)$ or $\left(2;6q-2\right)$ gives a deficient rectangle that cannot be tiled. Due to the symmetry of the tile set about the line $y=x$ ,

Figure 7. Lemma 2.6.

Figure 8. Good cells in a $7\times 7$ square.

we consider only the first cell. We use the invariant from Theorem 1.4, which is valid only for simply connected regions. In order to apply it, we need to do a cut. Figure 9 shows all possible configurations of tiles that cover the upper left corner cell of the rectangle. In Figure 9(c) the cell * cannot be tiled. We are left with the cases in Figure 9(a) and Figure 9(b), and the cuts marked by thick lines in the figure. Again due to the symmetry of $\sum$ about $y=-x$ we can restrict to case a). A tiling of the region by $\bar{\sum }$ is shown in Figure 10. The tiling shows that the invariant is 1. Larger rectangles also have invariant 1. Indeed, we can place a $7\times 7$ rectangle in the upper left corner of the larger rectangle, tile it as in Figure 10, and tile the rest of the larger rectangle by bars from $\bar{\sum }$ . As the deficient larger rectangle has even area, it can be tiled only by an even number of tiles from $\sum$ , so its invariant has to be even. This leads to a contradiction that shows the impossibility of tiling.

Theorem 3.2. A deficient rectangle $\left(6p+2\right)\times \left(6q+2\right),p,q\ge 1$ can be tiled by $\sum$ if and only if the missing cell has the sum of the coordinates congruent to 1 modulo 3 and is different from $\left(2,2\right),\left(6p-1,2\right),\left(2,6q-1\right)$ or $\left(6p-1,6q-1\right)$ .

Proof. Figure 11 shows the good cells in a $8\times 8$ square. For the general case, use first a coloring argument to show that the missing cell has the sum of the

Figure 9. Tiling the upper and lower left corners.

Figure 10. Tiling a $7\times 7$ deficient square by $\bar{\sum }$ .

Figure 11. Good cells in a $8\times 8$ square.

coordinates congruent to 1 modulo 3. To show that tiling is possible if the cell is different from $\left(2,2\right),\left(6p-1,2\right),\left(2,6q-1\right)$ or $\left(6p-1,6q-1\right)$ one checks, using a computer or by hand, that the statement is true for $8\times 8,8\times 14,14\times 8,14\times 14$ rectangles. If a rectangle is of bigger size, then place inside it one of the above deficient rectangles in positions translated from the origin by a vector with both coordinates multiple of 6. The remaining region can be decomposed in rectangles that can be tiled by $\sum$ . So a tiling of the whole deficient rectangle is possible. To show that the removal of the cells $\left(2,2\right),\left(6p-1,2\right),\left(2,6q-1\right)$ or $\left(6p-1,6q-1\right)$ give deficient rectangles that cannot be tiled is done using the invariant as in Theorem 3.1. Figure 9 shows all possible cuts and tilings of $8\times 8$ deficient squares by bars, after the cuts, are shown in Figure 12.

Theorem 3.3. If a deficient rectangle $\left(6p+4\right)\times \left(6q+4\right),p,q\ge 1$ can be tiled by $\sum$ , then the missing cell has the sum of the coordinates congruent to 0 modulo 3 and are placed on NW-SE diagonals. The missing cell has to be the third or fifth cell on a diagonal of length 7, or be on a diagonal of length greater than 7 and not among the first two cells or the last two cells on that diagonal.

Proof. Figure 13 shows the good cells in a $10\times 10$ square. If the missing cell is at distance zero or one from the boundary, then it is easy to tile the deficient rectangle by $\bar{\sum }$ and show that tiling by $\sum$ leads to a contradiction. The other two candidates that are bad cells are in positions $\left(3,3\right)$ and $\left(6p,6q\right)$ . Due to the symmetry of $\sum$ it is enough to show that removing cell $\left(3,3\right)$ gives an untilable rectangle. The possible cuts are shown in Figure 14. Due to the symmetry of the tiling set, it is enough to study only one of them. A tiling of a deficient $10\times 10$ square with a cut by $\bar{\sum }$ are shown in Figure 15. The invariant is 1, so the deficient square cannot be tiled by $\sum$ .

Figure 12. Tiling a $8\times 8$ deficient square by $\bar{\sum }$ .

Figure 13. Good cells in a $10\times 10$ square.

Theorem 3.4. If a deficient rectangle $\left(6p+5\right)\times \left(6q+5\right),p,q\ge 1$ can be tiled by $\sum$ , then the missing cell has the sum of the coordinates congruent to 1 modulo 3 and are placed on NW-SE diagonals. The missing cell has to be the third cell on a diagonal of length 5, or the third, fourth, fifth or sixth on a diagonal of length 8, or be not among the first two cells or the last two cells on a diagonal of length greater or equal to 11.

Proof. The proof is similar to that of Theorem 3.3. The good cells in a $11\times 11$ square are shown in Figure 16.

Theorem 3.5. If a deficient rectangle $\left(6p+1\right)\times \left(6q+4\right),p,q\ge 1$ can be tiled by $\sum$ , then the missing cell has the sum of the coordinates congruent to 0 modulo 3 and are placed on NW-SE diagonals. The missing cell has to be the third or fifth cell on a diagonal of length 7, or be on a diagonal of length greater than 7 and not among the first two cells or the last two cells on that diagonal.

Proof. The proof is similar to that of Theorem 3.3. The good cells in a $7\times 10$ rectangle are shown in Figure 17.

Theorem 3.6. A deficient rectangle $\left(6p+2\right)\times \left(6q+5\right),p,q\ge 1$ can be tiled

Figure 14. Tiling the lower left corner.

Figure 15. Tiling a $10\times 10$ deficient square by $\bar{\sum }$ .

Figure 16. Good cells in a $11\times 11$ square.

by $\sum$ if and only if the missing cell has the sum of the coordinates congruent to 1 modulo 3 and is different from $\left(2,2\right),\left(6p-1,2\right),\left(2,6q+2\right)$ or $\left(6p-1,6q+2\right)$ .

Proof. The proof is similar to that of Theorem 3.2. The good cells in a $8\times 11$ rectangle are shown in Figure 18.

4. The Case of Two Missing Cells

In this section we prove Theorem 1.5, 2) The types of rectangles we need to consider are

$\left(6p+1\right)\times \left(6q+2\right),\left(6p+1\right)\times \left(6q+5\right),\left(6p+4\right)\times \left(6q+5\right).$

The case $\left(6p+1\right)\times \left(6q+2\right)$ . Using the coloring invariant it follows that the missing cells $C_0,C_1$ must have the sum of the coordinates 0, 1, respectively. Using the symmetry of the tile set about the line $y=x$ , we can assume that the x-coordinate of $C_0$ is less then the x-coordinate of $C_1$ or that the y-coordinate of $C_1$ is less than the y-coordinate of $C_0$ . In the first case, divide the rectangle in two sub-rectangles as in Figure 19(a). According to Theorem 3.1 each sub-rectangle is a deficient rectangle of type $\left(6p+1\right)\times \left(6q+1\right)$ with the missing cell having the sum of the coordinates 0, so it can be tiled by $\sum$ . In the second case, divide the rectangle in two sub-rectangles as in Figure 19(b). According to Theorem 3.2 the sub-rectangle of type $\left(6p+2\right)\times \left(6q+2\right)$ with

Figure 17. Good cells in a $7\times 10$ rectangle.

Figure 18. Good squares in a $8\times 11$ rectangle.

Figure 19. A rectangle with gaps split in deficient rectangles, case $\left(6p+1\right)\times \left(6q+2\right)$ .

the missing cell having the sum of the coordinates 1, can be tiled by $\sum$ . According to Theorem 3.6 the sub-rectangle of type $\left(6p+2\right)\times \left(6q+5\right)$ with the missing cell having the sum of the coordinates 1, can be tiled by $\sum$ .

The case $\left(6p+1\right)\times \left(6q+5\right)$ . Using the coloring invariant it follows that the missing cells $C_0,C_1$ must have the sum of the coordinates 0, 1, respectively. Using the symmetry of the tile set about the line $y=x$ , we can assume that the x-coordinate of $C_0$ is less than the x-coordinate of $C_1$ or that the y-coordi- nate of $C_1$ is less than the y-coordinate of $C_0$ . In the first case, divide the rectangle in two sub-rectangles as in Figure 20(a). According to Theorem 3.1 the sub-rectangle of type $\left(6p+1\right)\times \left(6q+1\right)$ with the missing cell having the sum of the coordinates 0, can be tiled by $\sum$ . According to Theorem 3.5 the sub-rec- tangle of type $\left(6p+1\right)\times \left(6q+4\right)$ with the missing cell having the sum of the coordinates 0, can be tiled by $\sum$ . In the second case, divide the rectangle in two sub-rectangles as in Figure 20(b). According to Theorem 3.4 the sub-rectangle of type $\left(6p+5\right)\times \left(6q+5\right)$ with the missing cell having the sum of the coordinates 1, can be tiled by $\sum$ . According to Theorem 3.6 the sub-rectangle of type $\left(6p+2\right)\times \left(6q+5\right)$ with the missing cell having the sum of the coordinates 1, can be tiled by $\sum$ .

The case $\left(6p+4\right)\times \left(6q+5\right)$ . Using the coloring invariant it follows that the missing cells $C_0,C_1$ must have the sum of the coordinates 0, 1, respectively. Using the symmetry of the tile set about the line $y=x$ , we can assume that the x-coordinate of $C_0$ is less then the x-coordinate of $C_1$ or that the y-coordinate of $C_1$ is less then the y-coordinate of $C_0$ . In the first case, divide the rectangle in two sub-rectangles as in Figure 21(a). According to Theorem 3.5 the sub-rectangle of type $\left(6p+1\right)\times \left(6q+4\right)$ with the missing cell having the sum of the coordinates 0, can be tiled by $\sum$ . According to Theorem 3.3 the sub rectangle of type $\left(6p+4\right)\times \left(6q+4\right)$ with the missing cell having the sum of the coordinates 0, can be tiled by $\sum$ . In the second case, divide the rectangle in two sub-rectangles as in Figure 21(b). According to Theorem 3.6 each

Figure 20. A rectangle with gaps split in deficient rectangles, case $\left(6p+1\right)\times \left(6q+5\right)$ .

Figure 21. A rectangle with gaps split in deficient rectangles, case $\left(6p+4\right)\times \left(6q+5\right)$ .

subrectangle is a deficient rectangle of type $\left(6p+2\right)\times \left(6q+5\right)$ with the missing cell having the sum of the coordinates 1, so they can be tiled by $\sum$ .

5. The Case of Three Missing Cell

In this section we prove Theorem 1.5, 3) The proof is similar to that in Section 4. Each rectangle with gaps is divided in two sub-rectangles, one with one hole and one with two holes that can be tiled using the results from sections 3 and 4. We need to consider the cases of

$\left(6p+1\right)\times \left(6q+3\right),\left(6p+3\right)\times \left(6q+3\right),\left(6p+3\right)\times \left(6q+5\right)$ rectangles. Due to the coloring argument, the sum of the coordinates of the missing cells $C_0,C_1,C_2$ are 0, 1 and 2 respectively.

The case $\left(6p+1\right)\times \left(6q+3\right)$ . We distinguish 6 sub cases, depending on the order of the x-coordinates of the cells $C_i$ :

1) $x_0<x_1<x_2$

2) $x_0<x_2<x_1$

3) $x_1<x_0<x_2$

4) $x_1<x_2<x_0$

5) $x_2<x_1<x_0$

6) $x_2<x_0<x_1$

Splittings of the rectangle in cases 1, 2, and 3 are shown in Figure 22. Cases 4 and 5 follows via a symmetry about the line $y=x$ and case 6 follows after a 180˚ counterclockwise rotation of the rectangle. We observe that a symmetry about the line $y=x$ reverses the order of the x-coordinates and interchanges the congruence classes 1 and 2 modulo 3 for the sum of the coordinates of a cell. So case 4 is reduced to case 1 and case 5 is reduced to case 2. We also observe that a 180˚ counterclockwise rotation reverses the order of the x-coordinates and interchanges the congruence classes 0 and 2 modulo 3 for the sum of the coordinates of a cell. So case 6 is reduced to case 4.

The case $\left(6p+3\right)\times \left(6q+3\right)$ . Cutting a strip of width 2 and length $6q+3$ from the rectangle, strip which can be tiled by $\sum$ , reduces this case to the previous one.

Figure 22. Splitting a rectangle with gaps, the case $\left(6p+1\right)\times \left(6q+3\right)$ .

The case $\left(6p+3\right)\times \left(6q+5\right)$ . Cutting a strip of width 4 and length $6p+3$ from the rectangle, strip which can be tiled by $\sum$ , reduces this case to the first one.

6. Conclusion

In this paper we study tilings of rectangles with gaps by the Conway-Lagarias tile set consisting of two ribbon right trominoes. For the class of simply connected regions there exists an invariant found by Conway and Lagarias that cannot be found by coloring [3] . We show that the gap number for rectangles with integers ides of length at least 2 is less than or equal to 4, and for rectangles with both sides greater or equal to 5 is less than or equal to 3. We also show that if we tile a rectangle, having the minimal number (≠0) of gaps, then, with probability 1, the only invariants for tiling are from coloring. As Conway-Lagarias tile set can be viewed as a degenerate case of more general tile sets, such as the tile set $T_n$ of ribbon L n-ominoes introduced in [12] and [13] , our result suggests that for rectangles with both sides large and for odd n, the gap number of $T_n$ is at most n. In addition, if a rectangle has the minimal number of gaps needed for a tiling to exist, then, with probability 1, all invariants for tiling are from coloring. This paper, in conjunction with [14] , which studies tilings of deficient rectangles by the tile set $T_4$ ; points out an interesting dichotomy between the behavior of $T_n$ , n even and that of $T_n$ , n odd. We show in [14] that the obstructions to tiling of deficient rectangles by $T_4$ are much more severe and we claim with high confidence that this is the case for all $T_n$ , n even. Other infinite family related to Conway-Lagarias tile set is the family of ribbon tiles of length n introduced by Pak [4] . For these tile sets we believe that for rectangles with both sides large the gap number is bounded by n. We also believe that the behavior for these tile sets is independent of the parity of n and similar to what happens for $T_n$ , n odd.

Acknowledgements

V. Nitica was partially supported by Simons Foundation Grant 208729.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Golomb, S.W. (1996) Polyominoes, Puzzeles, Patterns, Problems, and Packings. 2nd Edition, Princeton University Press, Princeton.
[2]	Hochberg, R. (2015) The Gap Number of the T-Tetromino. Discrete Mathematics, 338, 130-138. https://doi.org/10.1016/j.disc.2014.09.001
[3]	Conway, J.H. and Lagarias, J.C. (1990) Tilings with Polyominoes and Combinatorial Group Theory. Journal of Combinatorial Theory, Series A, 53, 183-208. https://doi.org/10.1016/0097-3165(90)90057-4
[4]	Pak, I. (2000) Ribbon Tile Invariants. Transactions of the American Mathematical Society, 352, 5525-5561. https://doi.org/10.1090/S0002-9947-00-02666-0
[5]	Chu, P. and Johnsonbaugh, R. (1985) Tiling Boards with Trominoes. Journal of Recreational Mathematics, 18, 188-193.
[6]	Chu, P. and Johnsonbaugh, R. (1986) Tiling Deficient Boards with Trominoes. Mathematics Magazine, 59, 34-40. https://doi.org/10.2307/2690016
[7]	Ash, J.M. and Golomb, S. (2003) Tiling Deficient Rectangles with Trominoes. Mathematics Magazine, 77, 46-55. https://doi.org/10.2307/3219230
[8]	Nitica, V. (2015) Tiling a Deficient Rectangle by L-Tetrominoes. Journal of Recreational Mathematics, 33, 259-271.
[9]	Nitica, C. and Nitica, V. (2009) Tiling a Deficient Board by P-Pentominoes. Geombinatorics, XVIII, 175-184.
[10]	Nitica, C. and Nitica, V. (2009) Tiling a Deficient Rectangle by P-Pentominoes. Geombinatorics, XIX, 18-27.
[11]	Polysolver. https://www.jaapsch.net/puzzles/polysolver.htm
[12]	Chao, M., Levenstein, D., Nitica, V. and Sharp, R. (2013) A Coloring Invariant for Ribbon L-Tetrominoes. Discrete Mathematics, 313, 611-621. https://doi.org/10.1016/j.disc.2012.12.007
[13]	Nitica, V. (2015) Every Tiling of the First Quadrant by Ribbon L n-Ominoes Follows the Rectangular Pattern. Open Journal of Discrete Mathematics, 5, 11-25. https://doi.org/10.4236/ojdm.2015.52002
[14]	Nitica, V. (2017) The Tilings of Deficient Squares by Ribbon L-Tetrominoes Are Diagonally Cracked. arXiv:1701.00419 [math.CO]