Polyominoes: Puzzles, Patterns, Problems, and Packings

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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]

Publication history[edit]

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[edit]

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[edit]

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]

References[edit]

  1. ^ a b c Martin, George E. (1995), "Review of Polyominoes (2nd ed.)", Mathematical Reviews, MR 1291821
  2. ^ "Polyominoes", MAA Reviews, retrieved 2020-06-19
  3. ^ a b c d e f g Sutcliffe, Alan (November 1965), "Review of Polyominoes (1st ed.)", Mathematics Magazine, 38 (5): 313–314, doi:10.2307/2687945, JSTOR 2687945
  4. ^ a b c d Greenblatt, M. H. (September 1965), "Review of Polyominoes (1st ed.)", American Scientist, 53 (3): 356A–357A, JSTOR 27836143
  5. ^ a b c 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. ^ a b c 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)

External links[edit]