If each tile consists not of a single square but of a certain number of squares joined together along their edges to form a unit, the problem of determining whether you can use such tiles to cover a rectangular floor flawlessly gets more complicated.
Indeed, mathematicians have proved that the general question of whether it's possible to cover the plane (or even a smaller region, such as a rectangle) with identical copies of a given finite set of tiles (or even a single geometric figure) is, in principle, computationally undecidable.
In other words, there's no cookbook recipe or handbook procedure that you can routinely apply to indicate whether you can fit together copies of an arbitrary shape to form a rectangle.
Mathematicians, however, have solved a variety of special cases of the tiling problem in two dimensions, particularly those that involve shapes known as polyominoes—forms that cover connected squares on a checkerboard. The term polyomino was coined in 1953 by mathematician Solomon W. Golomb.
There is only one type of monomino (the unit square by itself) and one domino (two squares stuck together along one edge). There are two distinct trominoes (three squares), five different tetrominoes (four squares), and twelve pentominoes (five squares). As the number of connected squares increases, the number of different possible configurations grows rapidly.
Simple polyominoes.
Polyominoes are the basis for thousands of mathematical puzzles. One involves proving that polyominoes of a certain shape can be laid down to form either an infinite strip or a complete rectangle.
With square or rectangular pieces, the problem is easy to solve. But a piece made up of six squares, connected so that five lie in one row with a sixth attached to a row's second square, for example, is much more difficult to deal with. So is the case of a polyomino consisting of seven squares, with five in one row, and two in the second and third places in an adjacent row.
One type of polyomino problem involves showing whether any number of tiles in the shape of a given polyomino can be fitted together to form a rectangle. Such rectangular arrangements have been found for many polyominoes, including trominoes and tetrominoes (top). Finding such an arrangement for the hexomino and heptomino shown (bottom) proved to be difficult.
For a long time, despite a great deal of effort, all anyone knew was that these two polyominoes could be used to tile a "semi-infinite" strip and that copies of each would fill a finite rectangle, except for a small square hole somewhere inside.
Examples of infinite half-strips (bottom) and rectangles with square holes (top) made from hexominoes and heptominoes.
In 1987, software engineer Karl Dahlke, combining perseverance with clever programming, managed to solve both problems (see Dahlke's "Tiling Rectangles with Polyominoes"). Dahlke, who is blind, originally heard the problem in the audio edition of a magazine. After trying out various possibilities, he decided to program his personal computer to search for an answer systematically. Dahlke's computer was equipped with a speech synthesizer that converted the computer's output into sound.
Only after adding several programming tricks designed to circumvent time-consuming situations, in which the computer was trapped in endlessly repeating patterns, could Dahlke find his solutions.
Dahlke's solutions to the problem of forming a rectangle with either hexominoes (bottom) or heptominoes (top).
It turned out that the size of the solutions was a bit beyond what one could easily do by hand, but well within the range of a personal computer.
Cristopher Moore focused on the problem of determining how many different tilings of rectangles of various widths are possible using a given type of polyomino. In one exploration, he calculated the number of ways a rectangle 4 units wide and n units long can be tiled with right trominoes.
Suppose you have a 4 x n rectangle, where n is a multiple of 3. It turns out that you need to consider only three types of interfaces when fitting right trominoes together into a strip of the required width and length.
For example, two trominoes fit together to form a 2 x 3 rectangle, and two such rectangles can be placed next to each other to produce a 4 x 3 rectangle.
There are four ways to do the stacking. These configurations all result from what Moore described as a "straight" interface for building rectangular strips.
Two other interfaces are also possible: deep jog and shallow jog.
Examples of interfaces with a deep jog (left) and a shallow jog (right).
Because the number of possible interfaces is limited to three, Moore could derive a formula that gives the number of different ways to tile rectangles of different sizes. There are four ways to produce a 4 x 3 rectangle (see above), 18 ways to produce a 4 x 6 rectangle, 88 ways to produce a 4 x 9 rectangle, and 468 ways to produce a 4 x 12 rectangle. By definition, there is only one way to build a 4 x 0 rectangle.
Technical details: The number of ways of tiling a m x n rectangle with any finite collection of shapes, where m is fixed, can be found by calculating the nth power of a matrix whose rows and columns correspond to the various interface shapes a partial tiling may have, Moore said.
For the three interfaces possible for right trominoes, Moore solved a system of linear equations to obtain the formula, or generating function, G(z) = (1 − 6z)/(1 − 10z + 22z2 + 4z3). The terms of the Taylor expansion of G give the number of ways to tile rectangles of size 4 x 0, 4 x 3, 4 x 6, and so on: 1, 4, 18, 88, 468, 2672, 16072,….
Moore also worked out formulas giving the number of different ways to tile rectangles of width 5 with right trominoes and rectangles of width 4 with L tetrominoes and T tetrominoes.
You can prove that T tetrominoes cannot tile any rectangles of width 5, 6, or 7. Indeed, a rectangle can be tiled with T tetrominoes only if its length and width are both multiples of 4.
Nonetheless, that still leaves a lot of different patterns you can try out when tiling your bathroom floor with polyominoes.
Originally posted September 27, 1999
No comments:
Post a Comment