Self-tiling tile set

Last updated
Figure 1: A 'perfect' self-tiling tile set of order 4 A perfect self-tiling tile set of order 4.png
Figure 1:   A 'perfect' self-tiling tile set of order 4

A self-tiling tile set, or setiset, of order n is a set of n shapes or pieces, usually planar, each of which can be tiled with smaller replicas of the complete set of n shapes. That is, the n shapes can be assembled in n different ways so as to create larger copies of themselves, where the increase in scale is the same in each case. Figure 1 shows an example for n = 4 using distinctly shaped decominoes. The concept can be extended to include pieces of higher dimension. The name setisets was coined by Lee Sallows in 2012, [1] [2] but the problem of finding such sets for n = 4 was asked decades previously by C. Dudley Langford, and examples for polyaboloes (discovered by Martin Gardner, Wade E. Philpott and others) and polyominoes (discovered by Maurice J. Povah) were previously published by Gardner. [3]

Lee Sallows English recreational mathematician

Lee Cecil Fletcher Sallows is a British electronics engineer known for his contributions to recreational mathematics. He is particularly noted as the inventor of golygons, self-enumerating sentences, and geomagic squares.

Polyabolo

In recreational mathematics, a polyabolo is a shape formed by gluing isosceles right triangles edge-to-edge, making a polyform with the isosceles right triangle as the base form. Polyaboloes were introduced by Martin Gardner in his June 1967 "Mathematical Games column" in Scientific American.

Martin Gardner recreational mathematician and philosopher

Martin Gardner was an American popular mathematics and popular science writer, with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literature—especially the writings of Lewis Carroll, L. Frank Baum, and G. K. Chesterton. He is recognized as a leading authority on Lewis Carroll. The Annotated Alice, which incorporated the text of Carroll's two Alice books, was his most successful work and sold over a million copies. He had a lifelong interest in magic and illusion and was regarded as one of the most important magicians of the twentieth century. He was considered the doyen of American puzzlers. He was a prolific and versatile author, publishing more than 100 books.

Contents

Examples and definitions

Figure 2: A setiset with duplicated piece. A setiset with duplicated piece.png
Figure 2:   A setiset with duplicated piece.

From the above definition it follows that a setiset composed of n identical pieces is the same thing as a 'self-replicating tile' or rep-tile, of which setisets are therefore a generalization. [4] Setisets using n distinct shapes, such as Figure 1, are called perfect. Figure 2 shows an example for n = 4 which is imperfect because two of the component shapes are the same.

Rep-tile a tiling of the plane in which a prototile is recursively subdivided into copies of itself

In the geometry of tessellations, a rep-tile or reptile is a shape that can be dissected into smaller copies of the same shape. The term was coined as a pun on animal reptiles by recreational mathematician Solomon W. Golomb and popularized by Martin Gardner in his "Mathematical Games" column in the May 1963 issue of Scientific American. In 2012 a generalization of rep-tiles called self-tiling tile sets was introduced by Lee Sallows in Mathematics Magazine.

The shapes employed in a setiset need not be connected regions. Disjoint pieces composed of two or more separated islands are also permitted. Such pieces are described as disconnected, or weakly-connected (when islands join only at a point), as seen in the setiset shown in Figure 3.

The fewest pieces in a setiset is two. Figure 4 encapsulates an infinite family of order 2 setisets each composed of two triangles, P and Q. As shown, the latter can be hinged together to produce a compound triangle that has the same shape as P or Q, depending upon whether the hinge is fully open or fully closed. This unusual specimen thus provides an example of a hinged dissection.

Hinged dissection

A hinged dissection, also known as a swing-hinged dissection or Dudeney dissection, is a kind of geometric dissection in which all of the pieces are connected into a chain by "hinged" points, such that the rearrangement from one figure to another can be carried out by swinging the chain continuously, without severing any of the connections. Typically, it is assumed that the pieces are allowed to overlap in the folding and unfolding process; this is sometimes called the "wobbly-hinged" model of hinged dissection.

Figure 3: A setiset showing weakly-connected pieces. A setiset showing weakly-connected pieces.png
Figure 3:   A setiset showing weakly-connected pieces.
Figure 4: An infinite family of order 2 setisets. An infinite family of order 2 setisets.png
Figure 4:   An infinite family of order 2 setisets.

Inflation and deflation

Figure 5: A setiset of order 4 using octominoes. Two stages of inflation are shown. A setiset of order 4 showing two stages of inflation.png
Figure 5:   A setiset of order 4 using octominoes. Two stages of inflation are shown.

The properties of setisets mean that their pieces form substitution tilings, or tessellations in which the prototiles can be dissected or combined so as to yield smaller or larger duplicates of themselves. Clearly, the twin actions of forming still larger and larger copies (known as inflation), or still smaller and smaller dissections (deflation), can be repeated indefinitely. In this way, setisets can produce non-periodic tilings. However, none of the non-periodic tilings thus far discovered qualify as aperiodic, because the prototiles can always be rearranged so as to yield a periodic tiling. Figure 5 shows the first two stages of inflation of an order 4 set leading to a non-periodic tiling.

In geometry, a tile substitution is a method for constructing highly ordered tilings. Most importantly, some tile substitutions generate aperiodic tilings, which are tilings whose prototiles do not admit any tiling with translational symmetry. The most famous of these are the Penrose tilings. Substitution tilings are special cases of finite subdivision rules, which do not require the tiles to be geometrically rigid.

Prototile the shape of a tile within a tessellation

In the mathematical theory of tessellations, a prototile is one of the shapes of a tile in a tessellation.

Aperiodic tiling non-periodic tiling with the additional property that it does not contain arbitrarily large periodic patches

An aperiodic tiling is a non-periodic tiling with the additional property that it does not contain arbitrarily large periodic patches. A set of tile-types is aperiodic if copies of these tiles can form only non-periodic tilings. The Penrose tilings are the best-known examples of aperiodic tilings.

Loops

Figure 6: A loop of length 2 using decominoes. A loop of length 2 using decominoes.png
Figure 6:   A loop of length 2 using decominoes.

Besides self-tiling tile sets, which can be interpreted as loops of length 1, there exist longer loops, or closed chains of sets, in which every set tiles its successor. [5] Figure 6 shows a pair of mutually tiling sets of decominoes, in other words, a loop of length 2. Sallows and Schotel did an exhaustive search of order 4 sets that are composed of octominoes. In addition to seven ordinary setisets (i.e., loops of length 1) they found a bewildering variety of loops of every length up to a maximum of 14. The total number of loops identified was nearly one and a half million. More research in this area remains to be done, but it seems safe to suppose that other shapes may also entail loops. [6]

Methods of construction

To date, two methods have been used for producing setisets. In the case of sets composed of shapes such as polyominoes, which entail integral piece sizes, a brute force search by computer is possible, so long as n, the number of pieces involved, is not prohibitive. It is easily shown that n must then be a perfect square. [4] Figures 1,2,3,5 and 6 are all examples found by this method.

Polyomino plane geometric figure formed by joining one or more equal squares edge to edge

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling

In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it can be written as 3 × 3.

Alternatively, there exists a method whereby multiple copies of a rep-tile can be dissected in certain ways so as to yield shapes that create setisets. Figures 7 and 8 show setisets produced by this means, in which each piece is the union of 2 and 3 rep-tiles, respectively. In Figure 8 can be seen how the 9 pieces above together tile the 3 rep-tile shapes below, while each of the 9 pieces is itself formed by the union of 3 such rep-tile shapes. Hence each shape can be tiled with smaller duplicates of the entire set of 9. [4]

Figure 7: A rep-tile-based setiset of order 4. A rep-tile-based setiset of order 4.png
Figure 7:   A rep-tile-based setiset of order 4.
Figure 8: A rep-tile-based setiset of order 9. A rep-tile-based setiset of order 9.png
Figure 8:   A rep-tile-based setiset of order 9.

Related Research Articles

Pentomino polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge

Pentomino tiling puzzles and games are popular in recreational mathematics. Usually, video games such as Tetris imitations and Rampart consider mirror reflections to be distinct, and thus use the full set of 18 one-sided pentominoes.

Self-replication creation of copies

Self-replication is any behavior of a dynamical system that yields construction of an identical copy of itself. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction. Biological viruses can replicate, but only by commandeering the reproductive machinery of cells through a process of infection. Harmful prion proteins can replicate by converting normal proteins into rogue forms. Computer viruses reproduce using the hardware and software already present on computers. Self-replication in robotics has been an area of research and a subject of interest in science fiction. Any self-replicating mechanism which does not make a perfect copy (mutation) will experience genetic variation and will create variants of itself. These variants will be subject to natural selection, since some will be better at surviving in their current environment than others and will out-breed them.

Rectangle Quadrilateral with four right angles

In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as an equiangular quadrilateral, since equiangular means that all of its angles are equal. It can also be defined as a parallelogram containing a right angle. A rectangle with four sides of equal length is a square. The term oblong is occasionally used to refer to a non-square rectangle. A rectangle with vertices ABCD would be denoted as  ABCD.

Tessellation Tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps

A tessellation of a flat surface is the tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellations can be generalized to higher dimensions and a variety of geometries.

A hexomino is a polyomino of order 6, that is, a polygon in the plane made of 6 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix hex(a)-. When rotations and reflections are not considered to be distinct shapes, there are 35 different free hexominoes. When reflections are considered distinct, there are 60 one-sided hexominoes. When rotations are also considered distinct, there are 216 fixed hexominoes.

Tromino polyomino of order 3; polygon in the plane made of three equal-sized squares connected edge-to-edge

A tromino is a polyomino of order 3, that is, a polygon in the plane made of three equal-sized squares connected edge-to-edge.

A dissection puzzle, also called a transformation puzzle or Richter Puzzle, is a tiling puzzle where a set of pieces can be assembled in different ways to produce two or more distinct geometric shapes. The creation of new dissection puzzles is also considered to be a type of dissection puzzle. Puzzles may include various restraints, such as hinged pieces, pieces that can fold, or pieces that can twist. Creators of new dissection puzzles emphasize using a minimum number of pieces, or creating novel situations, such as ensuring that every piece connects to another with a hinge.

Penrose tiling non-periodic tiling of the plane

A Penrose tiling is an example of non-periodic tiling generated by an aperiodic set of prototiles. Penrose tilings are named after mathematician and physicist Roger Penrose, who investigated these sets in the 1970s. The aperiodicity of prototiles implies that a shifted copy of a tiling will never match the original. A Penrose tiling may be constructed so as to exhibit both reflection symmetry and fivefold rotational symmetry, as in the diagram at the right.

Pseudo-polyomino

A pseudo-polyomino, also called a polyking, polyplet or hinged polyomino, is a plane geometric figure formed by joining one or more equal squares edge to edge or corner to corner at 90°. It is a polyform with square cells. The polyominoes are a subset of the polykings.

Pythagorean tiling

A Pythagorean tiling or two squares tessellation is a tiling of a Euclidean plane by squares of two different sizes, in which each square touches four squares of the other size on its four sides. Many proofs of the Pythagorean theorem are based on it, explaining its name. It is commonly used as a pattern for floor tiles. When used for this, it is also known as a hopscotch pattern or pinwheel pattern, but it should not be confused with the mathematical pinwheel tiling, an unrelated pattern.

Geometric magic square

A geometric magic square, often abbreviated to geomagic square, is a generalization of magic squares invented by Lee Sallows in 2001. A traditional magic square is a square array of numbers whose sum taken in any row, any column, or in either diagonal is the same target number. A geomagic square, on the other hand, is a square array of geometrical shapes in which those appearing in each row, column, or diagonal can be fitted together to create an identical shape called the target shape. As with numerical types, it is required that the entries in a geomagic square be distinct. Similarly, the eight trivial variants of any square resulting from its rotation and/or reflection, are all counted as the same square. By the dimension of a geomagic square is meant the dimension of the pieces it uses. Hitherto interest has focused mainly on 2D squares using planar pieces, but pieces of any dimension are permitted.

Aperiodic set of prototiles

A set of prototiles is aperiodic if copies of the prototiles can be assembled to create tilings, such that all possible tessellation patterns are non-periodic. The aperiodicity referred to is a property of the particular set of prototiles; the various resulting tilings themselves are just non-periodic.

Conway criterion

In the mathematical theory of tessellations, the Conway criterion, named for the English mathematician John Horton Conway, describes rules for when a prototile will tile the plane; it consists of the following requirements: The tile must be a closed topological disk with six consecutive points A, B, C, D, E, and F on the boundary such that:

In plane geometry, the einstein problem asks about the existence of a single prototile that by itself forms an aperiodic set of prototiles, that is, a shape that can tessellate space, but only in a nonperiodic way. Such a shape is called an "einstein", a play on the German words ein Stein, meaning one tile. Depending on the particular definitions of nonperiodicity and the specifications of what sets may qualify as tiles and what types of matching rules are permitted, the problem is either open or solved. The einstein problem can be seen as a natural extension of the second part of Hilbert's eighteenth problem, which asks for a single polyhedron that tiles Euclidean 3-space, but such that no tessellation by this polyhedron is isohedral. Such anisohedral tiles were found by Karl Reinhardt in 1928, but these anisohedral tiles all tile space periodically.

References

  1. ↑ Sallows, Lee (December 2012). "On Self-Tiling Tile Sets". Mathematics Magazine . 85 (5): 323–333. doi:10.4169/math.mag.85.5.323.
  2. ↑ Alejandro Erickson on Self-tiling tile sets
  3. ↑ Polyhexes and Polyaboloes in Mathematical Magic Show, by Martin Gardner, Knopf, 1977, pp 146-159
  4. 1 2 3 Sallows, Lee (April 2014). "More On Self-Tiling Tile Sets". Mathematics Magazine. 87 (2): 100–112. doi:10.4169/math.mag.87.2.100.
  5. ↑ Geometric Hidden Gems by Jean-Paul Delahaye in Scilogs, April 07, 2013
  6. ↑ Self-Tiling Tile Sets website
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.