Polyominoes: Puzzles, Patterns, Problems, and Packings

Last updated

Polyominoes: Puzzles, Patterns, Problems, and Packings is a mathematics book on polyominoes, the shapes formed by connecting some number of unit squares edge-to-edge. It was written by Solomon Golomb, and is "universally regarded as a classic in recreational mathematics". [1] The Basic Library List Committee of the Mathematical Association of America has strongly recommended its inclusion in undergraduate mathematics libraries. [2]

Contents

Publication history

The book collects together material previously published by Golomb in various articles and columns, especially in Recreational Mathematics Magazine. [3] It was originally published by Scribner's in 1965, titled simply Polyominoes, and including a plastic set of the twelve pentominoes. The book's title word "polyominoes" was invented for the subject by Golomb in 1954 [1] as a back-formation from "domino". [4] [5]

A translation into Russian by I. Yaglom, Полимино, was published by Mir in 1975; it includes also translations of two papers on polyominoes by Golomb and by David A. Klarner. [6]

A second English-language edition of the book was published by the Princeton University Press in 1994. It added to the corrected text of the original addition two more chapters on recent developments, an expanded bibliography, and two appendices, one giving an enumeration of polyominoes and a second reprinting a report by Andy Liu of the solution to all open problems proposed in an appendix to the first edition. [1]

Topics

The twelve pentominoes Pentominos 001.svg
The twelve pentominoes

After an introductory chapter that enumerates the polyominoes up to the hexominoes (made from six squares), the next two chapters of the book concern the pentominoes (made from five squares), the rectangular shapes that can be formed from them, and the subsets of an chessboard into which the twelve pentominoes can be packed. [3]

The fourth chapter discusses brute-force search methods for searching for polyomino tilings or proving their nonexistence, and the fifth introduces techniques from enumerative combinatorics including Burnside's lemma for counting polyominoes and their packings. [3] Although reviewer M. H. Greenblatt considers this more theoretical material a digression from the main topic of the book, [4] and the book itself suggests that less mathematically-inclined readers skip this material, [7] Alan Sutcliffe calls it "the heart of the book", and an essential bridge between the earlier and later chapters. [3] The question of using these methods to find a formula for the number of polyominoes with a given number of squares remains unsolved, and central to the topic. [5]

The final two chapters of the first edition concern generalizations of polyominoes to polycubes and other polyforms, [3] [4] and briefly mention the work of Edward F. Moore and Hao Wang proving the undecidability of certain tiling problems including the problem of whether a set of polyominoes can tile the plane. [3] The second edition adds a chapter on the work of David Klarner on the smallest rectangles that can be tiled by certain polyominoes, and another chapter summarizing other recent work on polyominoes and polyomino tiling, including the mutilated chessboard problem and De Bruijn's theorem that a rectangle tiled by smaller rectangles must have a side whose length is a multiple of . [8]

Audience and reception

Reviewer Elizabeth Senger writes that the book has a wide audience of "mathematicians, teachers, students, and puzzle people", and is "well written and easy to read", accessible even to high school level mathematics students. [7] Similarly, Elaine Hale writes that it should be read by "all professional mathematicians, mathematics educators, and amateurs" interested in recreational mathematics. [9] Senger adds that the second edition is especially welcome because of the difficulty of finding a copy of the out-of-print first edition. [7]

Although the book concerns recreational mathematics, reviewer M. H. Greenblatt writes that its inclusion of exercises and problems makes it feel "much more like a text book", but not in a negative way. [4] Similarly, Alan Sutcliffe writes that "an almost ideal balance has been struck between educational and recreational", [3] and Pamela Liebeck calls its coverage of the topic "fascinating and thorough". [5]

Related Research Articles

Pentomino Geometric shape formed from five squares

Derived from the Greek word for '5', and "domino", a pentomino is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.

Tetromino Shape formed from four connected squares

A tetromino is a geometric shape composed of four squares, connected orthogonally. Tetrominoes, like dominoes and pentominoes, are a particular type of polyomino. The corresponding polycube, called a tetracube, is a geometric shape composed of four cubes connected orthogonally.

Polyomino Geometric shapes formed from squares

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.

Packing problems Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

Hexomino Geometric shape formed from six squares

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.

Polyabolo Shape formed from isosceles right triangles

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.

Polycube Shape made from cubes joined together

A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.

Tromino Geometric shape formed from three squares

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.

Solomon W. Golomb American mathematician (1932–2016)

Solomon Wolf Golomb was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. Most notably, he invented Cheskers in 1948 and coined the name. He also fully described polyominoes and pentominoes in 1953. He specialized in problems of combinatorial analysis, number theory, coding theory, and communications. Pentomino boardgames, based on his work, would go on to inspire Tetris.

Heptomino Geometric shape formed from seven squares

A heptomino is a polyomino of order 7, that is, a polygon in the plane made of 7 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix hept(a)-. When rotations and reflections are not considered to be distinct shapes, there are 108 different free heptominoes. When reflections are considered distinct, there are 196 one-sided heptominoes. When rotations are also considered distinct, there are 760 fixed heptominoes.

Nonomino Geometric shape formed from nine squares

A nonomino is a polyomino of order 9, that is, a polygon in the plane made of 9 equal-sized squares connected edge-to-edge. The name of this type of figure is formed with the prefix non(a)-. When rotations and reflections are not considered to be distinct shapes, there are 1,285 different free nonominoes. When reflections are considered distinct, there are 2,500 one-sided nonominoes. When rotations are also considered distinct, there are 9,910 fixed nonominoes.

Domino tiling Geometric construct

In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

In mathematics, a domino is a polyomino of order 2, that is, a polygon in the plane made of two equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there is only one free domino.

David Anthony Klarner was an American mathematician, author, and educator. He is known for his work in combinatorial enumeration, polyominoes, and box-packing.

Proofs That Really Count: the Art of Combinatorial Proof is an undergraduate-level mathematics book on combinatorial proofs of mathematical identies. That is, it concerns equations between two integer-valued formulas, shown to be equal either by showing that both sides of the equation count the same type of mathematical objects, or by finding a one-to-one correspondence between the different types of object that they count. It was written by Arthur T. Benjamin and Jennifer Quinn, and published in 2003 by the Mathematical Association of America as volume 27 of their Dolciani Mathematical Expositions series. It won the Beckenbach Book Prize of the Mathematical Association of America.

Pearls in Graph Theory: A Comprehensive Introduction is an undergraduate-level textbook on graph theory, by Nora Hartsfield and Gerhard Ringel. It was published in 1990 by Academic Press, Inc., with a revised edition in 1994 and a paperback reprint of the revised edition by Dover Books in 2003. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

Introduction to the Theory of Error-Correcting Codes is a textbook on error-correcting codes, by Vera Pless. It was published in 1982 by John Wiley & Sons, with a second edition in 1989 and a third in 1998. The Basic Library List Committee of the Mathematical Association of America has rated the book as essential for inclusion in undergraduate mathematics libraries.

Wheels, Life and Other Mathematical Amusements is a book by Martin Gardner published in 1983. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.

Convex Polyhedra is a book on the mathematics of convex polyhedra, written by Soviet mathematician Aleksandr Danilovich Aleksandrov, and originally published in Russian in 1950, under the title Выпуклые многогранники. It was translated into German by Wilhelm Süss as Konvexe Polyeder in 1958. An updated edition, translated into English by Nurlan S. Dairbekov, Semën Samsonovich Kutateladze and Alexei B. Sossinsky, with added material by Victor Zalgaller, L. A. Shor, and Yu. A. Volkov, was published as Convex Polyhedra by Springer-Verlag in 2005.

Regular Figures is a book on polyhedra and symmetric patterns, by Hungarian geometer László Fejes Tóth. It was published in 1964 by Pergamon in London and Macmillan in New York.

References

  1. 1 2 3 Martin, George E. (1995), "Review of Polyominoes (2nd ed.)", Mathematical Reviews, MR   1291821
  2. ↑ "Polyominoes", MAA Reviews, retrieved 2020-06-19
  3. 1 2 3 4 5 6 7 Sutcliffe, Alan (November 1965), "Review of Polyominoes (1st ed.)", Mathematics Magazine, 38 (5): 313–314, doi:10.2307/2687945, JSTOR   2687945
  4. 1 2 3 4 Greenblatt, M. H. (September 1965), "Review of Polyominoes (1st ed.)", American Scientist, 53 (3): 356A–357A, JSTOR   27836143
  5. 1 2 3 Liebeck, Pamela (October 1968), "Review of Polyominoes (1st ed.)", The Mathematical Gazette, 52 (381): 306, doi:10.2307/3614210, JSTOR   3614210
  6. ↑ Stefanescu, M., "Review of Polyominoes (Russian ed.)", zbMATH, Zbl   0326.05025
  7. 1 2 3 Senger, Elizabeth (January 1997), "Review of Polyominoes (2nd ed.)", The Mathematics Teacher, 90 (1): 72, JSTOR   27970078
  8. ↑ De Clerck, Frank, "Review of Polyominoes (2nd ed.)", zbMATH, Zbl   0831.05020
  9. ↑ Hale, Elaine M. (September 1995), The Mathematics Teacher, 88 (6): 524, JSTOR   27969460 {{citation}}: CS1 maint: untitled periodical (link)
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.