Every Tiling of the First Quadrant by Ribbon L n-Ominoes Follows the Rectangular Pattern
Abstract: Let and let be the set of four ribbon L-shaped n-ominoes. We study tiling problems for regions in a square lattice by . Our main result shows a remarkable property of this set of tiles: any tiling of the first quadrant by , n even, reduces to a tiling by and rectangles, each rectangle being covered by two ribbon L-shaped n-ominoes. An application of our result is the characterization of all rectangles that can be tiled by , n even: a rectangle can be tiled by , n even, if and only if both of its sides are even and at least one side is divisible by n. Another application is the existence of the local move property for an infinite family of sets of tiles: , n even, has the local move property for the class of rectangular regions with respect to the local moves that interchange a tiling of an square by n/2 vertical rectangles, with a tiling by n/2 horizontal rectangles, each vertical/horizontal rectangle being covered by two ribbon L-shaped n-ominoes. We show that none of these results are valid for any odd n. The rectangular pattern of a tiling of the first quadrant persists if we add an extra tile to , n even. A rectangle can be tiled by the larger set of tiles if and only if it has both sides even. We also show that our main result implies that a skewed L-shaped n-omino, n even, is not a replicating tile of order k2 for any odd k.
Cite this paper: 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. doi: 10.4236/ojdm.2015.52002.
References

[1]   Golomb, S.W. (1954) Checker Boards and Polyominoes. The American Mathematical Monthly, 61, 675-682.
http://dx.doi.org/10.2307/2307321

[2]   Golomb, S.W. (1994) Polyominoes, Puzzles, Patterns, Problems, and Packings. 2nd Edition, Princeton University Press, Princeton.

[3]   Pak, I. (2000) Ribbon Tile Invariants. Transactions of the American Mathematical Society, 352, 5525-5561.
http://dx.doi.org/10.1090/S0002-9947-00-02666-0

[4]   Chao, M., Levenstein, D., Nitica, V. and Sharp, R. (2013) A Coloring Invariant for Ribbon L-Tetrominoes. Discrete Mathematics, 313, 611-621.
http://dx.doi.org/10.1016/j.disc.2012.12.007

[5]   Golomb, S.W. (1964) Replicating Figures in the Plane. The Mathematical Gazette, 48, 403-412.
http://dx.doi.org/10.2307/3611700

[6]   Gardner, M. (1963) On “Rep-Tiles”, Polygons That Can Make Larger and Smaller Copies of Themselves. Scientific American, 208, 154-157.
http://dx.doi.org/10.1038/scientificamerican0563-154

[7]   Nitica, V. (2003) Rep-Tiles Revisited, in the Volume MASS Selecta: Teaching and Learning Advanced Undergraduate Mathematics, American Mathematical Society, Providence.

[8]   de Brujin, N.G. (1969) Filling Boxes with Bricks. The American Mathematical Monthly, 76, 37-40.
http://dx.doi.org/10.2307/2316785

[9]   Nitica, V. (2004-2005) Tiling a Deficient Rectangle by L-Tetrominoes. Journal of Recreational Mathematics, 33, 259-271.

[10]   Reid, M. (2014) Many L-Shaped Polyominoes Have Odd Rectangular Packings. Annals of Combinatorics, 18, 341-357.
http://dx.doi.org/10.1007/s00026-014-0226-9

[11]   Thurston, W. (1990) Conway’s Tiling Groups. The American Mathematical Monthly, 97, 757-773.
http://dx.doi.org/10.2307/2324578

[12]   Conway, J.H. and Lagarias, J.C. (1990) Tilings with Polyominoes and Combinatorial Group Theory. Journal Combinatorial Theory, Series A, 53, 183-208.
http://dx.doi.org/10.1016/0097-3165(90)90057-4

[13]   Kenyon, C. and Kenyon, R. (1992) Tiling a Polygon with Rectangles. Proceedings of 33rd Annual Symposium on Foundations of Computer Science (FOCS), Pittsburgh, 24-27 October 1992, 610-619.

[14]   Calderon, A., Fairchild, S., Nitica, V. and Simon, S. (2015) Tilings of Quadrants by L-Ominoes and Notched Rectangles. Topics in Recreational Mathematics, 5.

Top