home

The Tromino Puzzle
by
Norton Starr


About the Puzzle History Variations References Play



About the Puzzle - Physical and Virtual
v-21 puzzle The basic puzzle consists of 21 right-angle shaped pieces ("tiles") of the sort shown, composed of three squares; one additional single square tile; and a plane, 8×8 square grid whose squares are the same size as those of the tiles. The tiles occupy a total of 3×21 + 1 = 63 + 1 = 64 squares, the same number of squares as on a checkerboard. In what follows, we call these angled pieces trominoes, as the simplest of several names used for them, which include L-trominoes, L-triominoes, and V-trominoes.

To play a physical version of this puzzle, using 21 actual tromino tiles, a single square piece, and an 8×8 checkerboard-like base, first position the single square tile on any one of the 64 square locations on the base. Then fill the remaining 63 squares with the trominoes so that there is no overlap and no unfilled square. Such a solution to the puzzle is called a tiling of the 8×8 square. Alternatively, start by successively placing trominoes into the checkerboard base (each such tile occupying only three squares of the grid pattern), and when all 21 are positioned, place the single square tile in the one position that remains available.

Here's the background to the commercial version of this puzzle, marketed by Kadon Enterprises. At the January, 2000 annual meeting of the Mathematical Association of America, Arthur Benjamin received the Haimo award for distinguished college teaching. In his acceptance speech he sketched his favorite proof by induction. This reasoning assures that a 2n×2n celled square (i.e. a generalized checkerboard with 2n squares along each side) with one cell occupied, can always be tiled by trominoes. Three years after hearing Benjamin's remarks I was giving a lecture on induction and recalled his favorite proof. Supplementing my prepared examples, I ad libbed this classic argument, due to Solomon Golomb. Thinking that an actual puzzle of this sort would add an element of reality and might spark interest in the method of induction, I sent a note to Kadon, a leading puzzle maker, to see if they had any I could purchase. They didn't, so I asked if they would make some to my specifications. A series of emails with Kate Jones, President of Kadon, led to a puzzle of the sort illustrated above left. She suggested using several different colors for the tromino tiles, making this a more interesting puzzle than I had originally envisioned. I opted for cooler, translucent tiles rather than bold, opaque ones, and chose blue, aqua and amethyst for the trominoes.

Kate asked if I would let Kadon add the puzzle to the array of items they sell and I readily agreed - I only wanted some for my own use. To my surprise, she declared that I would be receiving royalties. That was never my goal, and all my royalties are donated to Amherst College and the Mathematical Association of America.

Kadon brought out the puzzle under the name "Vee-21"; see www.gamepuzzles.com/polycub2.htm#V21. This commercial version, in three vivid, translucent acrylic colors, comes with a forty page brochure offering a number of enhancements to the basic puzzle. Kate contributed some extensions of the puzzle, some two-person strategy games, and the suggestion of color separation requirements for tilings one might attempt. She also discovered the aesthetic possibilities in making symmetrical patterns. Kate invited Oriel Maximé to contribute some of his maze-like challenges for tiling with the trominoes, and the brochure includes a variety of rectangular templates with strategically chosen lines of the grids darkened to serve as barriers across which trominoes may not be placed.

Two interactive computer puzzles of this sort are provided here. The 8-by-8 puzzle was developed by two of my students, while a departmental colleague contributed the M-by-N puzzle. The M-by-N puzzle (plays on most systems but may be slow to load) is somewhat more flexible, allowing the choice of any number of rows and columns between 2 and 32, inclusive. The 8-by-8 puzzle (plays best with Internet Explorer on a PC) has a different mouse action and is usefully restricted to three colors of tromino. Directions are given with each. The online and Kadon versions both have unusual breadth of appeal, intriguing for four year olds as well as seasoned puzzlers.


TOP
History
The proof that for any positive integer  n,  a 2n×2n square with one cell occupied (a "deficient" square) can always be tiled by trominoes is due to Solomon Golomb. He published it in his 1954 article [9] in the American Mathematical Monthly. As noted above, it was to illustrate Golomb's argument for 2n×2n deficient squares that the puzzle was commissioned. His same article introduced in print the term tromino and its generalization, polyomino. A polyomino is a connected array of identical squares having the property that any two squares either do not touch or else meet along an entire, common edge. The only two tromino shapes are three squares in a row and the L-shape of this puzzle, and here "tromino" only refers to the latter.

Golomb's proof is a first-rate example of mathematical induction. Beyond the sheer elegance of the argument, it's a rare instance of a nonnumerical application of the method. This stands in contrast to the examples and exercises often found in textbook treatments of induction, which typically consist of a variety of formulas for finite sums, inequalities, and the like. The proof's first appearance in a popular medium was in Joseph Madachy's Recreational Mathematics Magazine (RMM), where Golomb included it in the first of his four-part series of articles on polyominoes published in RMM [10]. In Martin Gardner's seminal May, 1957 Scientific American column introducing polyominoes to the wider public, he remarked that "a board with one square missing at any point, can be covered by 21 right trominoes" [6, p. 154]. For his first book of collected Mathematical Games columns, Gardner elaborated by remarking that "an ingenious induction argument demonstrates that 21 right trominoes and one monomino will cover the 8-by-8 board regardless of where the monomino is placed" [8, p. 126].

The tromino tiling argument for deficient checkerboards and the general 2n×2n theorem has appeared in a succession of books since the Monthly and RMM articles. It was explained in Golomb's classic Polyominoes [11, 1965, pp. 21-22] and in the second edition of that book [11, 1994, p. 5]. The second edition gives a rich history and an extensive survey of this intriguing subject, and is filled with pictures and puzzles. Its 22 pages of references, citing both books and articles, are an added bonus. The index of names lists 81 individuals, quite a few referred to more than once in the body of the book. Many of these will be recognized by game aficionados and amateur mathematicians as well as by professionals in either area. A description of the book is given in the review [17] by George Martin. In 1976, Ross Honsberger gave a lucid, detailed application of Golomb's argument to the checker board in his Mathematical Gems II [13, p. 61]. The basic idea of the proof is also mentioned in George E. Martin's book devoted to polyomino tilings [16, pp. 27-28]. David Singmaster's review [22] of this latter book is particularly interesting, for it gives a beautiful sketch of the subject and its history.

This topic also is increasingly common fare for texts and problem books. For instance, it appears in the discrete mathematics texts of Susanna Epp [5, p. 234], Richard Johnsonbaugh (who mentions tromino tilings of rectangles as arising in VLSI layout design) [14, pp. 58-59], and Kenneth Rosen [20, pp. 247-8]. Tromino tiling is also treated in Daniel Velleman's book about constructing proofs [26, pp. 271-275] and the problem books by John P. D'Angelo & Douglas B. West [1, p. 75] and by Jiří Herman, Radan Kučera & Jaromír Šimša [12, p. 271]. The most crystalline illustration of the Golomb argument is Roger Nelsen's spare "proof without words," given in his second book of that title [19, p. 123].

This area of recreational mathematics has benefited from a continuing stream of investigation and suggested problems. In 1985 and 1986, I-Ping Chu and Richard Johnsonbaugh studied the question of tiling deficient n×n boards, where  n  no longer need be a power of 2, and, more generally, deficient and non-deficient rectangular boards [3, 4]. George Martin's book included a whole chapter devoted to tromino tilings [16, pp. 23-37]. Coloration problems for tromino tiling are treated by Ilvars Mizniks, who acknowledges the Kadon Vee-21 color selection page as inspiration for his research [18]. The 2004 article [2] by J. Marshall Ash and Solomon Golomb, about tromino tiling of deficient rectangles, contains several new and basic results, one of which answers an old question of Chu and Johnsonbaugh. Ash and Golomb end with an open problem about 2-deficient rectangles (rectangles with two cells removed).

The Internet is a good source of tiling displays and information. For instance, a search on "tromino" and "tiling" turns up applets such as those by Alexander Bogomolny at www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml and Christopher Mawata at www.utc.edu/Faculty/Christopher-Mawata/trominos/, which illustrate tromino puzzles of several sizes.
TOP
Variations
Here are some extensions of the tromino puzzle which readers might consider. The first was suggested by my brother Raymond (Pete), who asked how one might arrange trominoes in the 8×8 grid so as to maximize the number of unoccupied squares. This can be elaborated upon: one route would presume the tiles and grid are velcroed so they stay in place, while alternatively one could allow the tiles to slide so as to permit squeezing in as many tiles as possible (always within grid lines). Pete was not aware that the velcro version is a variation on Golomb's pentomino positioning puzzle as described by Gardner [7, p. 128] and [8, p. 133]. Golomb extended this puzzle to a two-person pentomino game [7, p. 128] and [8, pp. 133-135], rules for which could be applied to the tromino puzzle as well. David Klarner reported on a two-person pentomino game, Pan-Kāi (developed by Alex Randolph and issued in 1961 by Phillips Publishers), which included the following constraint: “the most important rule is that it is forbidden to play a piece inside a closed region of the board if fewer than 5 cells would then remain unoccupied, unless the move exactly fills up the region.” [15, p. 8] (See [21, p. 75] for more information on Randolph and Pan-Kāi.)

Another direction is three dimensional. Consider a cube of side length 2n, containing 23n unit cells, one of which is occupied (single deficiency.) Can the remaining cells be tiled with three dimensional trominoes (three cubes in an L-shape, with two of them meeting the third on two adjacent faces of the latter)? The necessary condition that 2n = 3k + 1 turns out to be sufficient as well. [23, Chapter 6: Norton Starr’s 3-Dimensional Tromino Tiling], [24, pp. 72-87], and [25] The case of a 4×4×4 cube presents some modest challenges that may amuse young puzzlers.

Simpler problems readily suggest themselves and have been considered by numerous others. For instance, can the full 3×3 and 6×6 square arrays be tiled with trominoes? Can every deficient 5×5 and 7×7 square array be tiled? These latter two puzzles are more challenging than the full 3×3, 6×6, and deficient 8×8 cases. Going further, readers may consider tilings of various rectangular arrays - see the references below. When using a version with more than one color of tromino, such as the Kadon Vee-21, consider various color constraints. For instance, try arranging the tiles so that no two of the same color share an edge. In the opposite direction, try to group as many tiles of one color together as possible. For both these pattern types, try further to make the tiling appear symmetric about a diagonal or about a horizontal or vertical line. The opportunities for fun and discovery are numerous. Different size rectangles can be studied by clicking on the M-by-N puzzle. For color pattern experiments, the Kadon puzzle is best.


TOP
References
  1. J. P. D'Angelo and D. B. West, Mathematical Thinking: Problem-Solving and Proofs, Second edition, Prentice Hall, Upper Saddle River, NJ, 2000.
  2. J. M. Ash and S. W. Golomb, "Tiling deficient rectangles with trominoes," Math. Mag., 77 (2004), 46-55. (Available at math.depaul.edu/~mash/TileRec3b.pdf)
  3. I. P. Chu and R. Johnsonbaugh, "Tiling deficient boards with trominoes," Math. Mag., 59 (1986), 34-40.
  4. I. P. Chu and R. Johnsonbaugh, "Tiling boards with trominoes," J. Recreational Math., 18 (1985-86), 188-193.
  5. S. S. Epp, Discrete Mathematics with Applications, Third edition, Thomson, Belmont, CA, 2004.
  6. M. Gardner, "About the remarkable similarity between the Icosian Game and the Tower of Hanoi," Scientific American, 196, (May, 1957), 150-156. This column was primarily devoted to Hamilton circuits, but ends with a section on checkerboard tiling problems: Gardner states that the February column's checkerboard/domino problem "prompted Octave Levenspiel of Bucknell University to call my attention to a remarkable article by S. W. Golomb in American Mathematical Monthly for December, 1954."
  7. M. Gardner, "More about complex dominoes, plus the answers to last month's puzzles," Scientific American, 197, (December, 1957), 126-140. This Mathematical Games column starts by reporting the explosive impact of the May column's brief account of Golomb's work [6]: "In the year since this department was inaugurated, it has received more letters about one mathematical recreation than any other… the 'pentomino' problem… Hundreds of correspondents sent in widely varying solutions. Many testified to the problem's strange fascination… ."
  8. M. Gardner, The Scientific American Book of Mathematical Puzzles & Diversions, Simon and Schuster, New York, 1959. (Reprinted and updated as Hexaflexagons and Other Mathematical Diversions, University of Chicago Press, 1988.)  [Chapter 13 of this first such collection combines the tiling material of [6] and [7] and is titled "Polyominoes."]
  9. S. W. Golomb, "Checker Boards and Polyominoes," Amer. Math. Monthly, 61 (1954), 675-682.
  10. S. W. Golomb, "The General Theory of Polyominoes  Part I - Dominoes, Pentominoes and Checkerboards," Recreational Math. Mag., Issue No. 4 (August, 1961), 3-12.
  11. S. W. Golomb, Polyominoes, Scribner's, New York, 1965. (Second edition: Polyominoes, Puzzles, Patterns, Problems, and Packings, Princeton University Press, Princeton, 1994.)
  12. J. Herman, R. Kučera and J. Šimša, Counting and Configurations: Problems in Combinatorics, Arithmetic, and Geometry (Karl Dilcher, translator), Springer-Verlag, New York, 2003.
  13. R. Honsberger, Mathematical Gems II, Mathematical Association of America, Washington, DC, 1976.
  14. R. Johnsonbaugh, Discrete Mathematics, Sixth edition, Pearson Prentice Hall, Upper Saddle River, NJ, 2005.
  15. D. Klarner, Box-Packing Puzzles. Multilithed notes, University of Waterloo, Ontario, 1973-74. 42 pages + title page. (Portions of this are summarized in Chapter 8 of Honsberger [13].)
  16. G. E. Martin, Polyominoes, A Guide to Puzzles and Problems in Tiling, Mathematical Association of America, Washington, DC, 1991.
  17. G. E. Martin, review of S. Golomb's Polyominoes (1994 edition), Mathematical Reviews, MR1291821 (95k:00006), 1995.
  18. I. Mizniks, "Computer Analysis of the 3 Color Problem for V-Shapes", Acta Societatis Mathematicae Latviensis, Abstracts of the 5th Latvian Mathematical Conference, April 6-7, 2004, Daugavpils, Latvia. (Available at http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)
  19. R. B. Nelsen, Proofs Without Words II, More Exercises in Visual Thinking, Mathematical Association of America, Washington, DC, 2000.
  20. K. H. Rosen, Discrete Mathematics and Its Applications, Fifth edition, McGraw-Hill, New York, 2003. (To appear as Example 13, Section 4.1, in the sixth edition, 2007.)
  21. J. N. Silva (Ed.) Recreational Mathematics Colloquium I  (Conference Proceedings, Apr. 29-May 2, 2009. University of Évora), Associação Ludus, Lisboa, 2010.
  22. D. Singmaster, review of G. E. Martin's Polyominoes, Mathematical Reviews, MR1140005 (93d:00006), 1993.
  23. A. Soifer, Geometric Etudes in Combinatorial Mathematics, Second Edition, Springer, New York, 2010.
  24. N. Starr, “Tromino Tiling Deficient Cubes of Side Length 2n”, Geombinatorics XVIII(2) (2008), 72-87.
  25. N. Starr, “Tromino Tiling Deficient Cubes of Any Side Length”, http://arxiv.org/abs/0806.0524 , June 3, 2008.
  26. D. J. Velleman, How To Prove It: A Structured Approach, Second edition, Cambridge University Press, New York, 2006

© 2012 Norton Starr