by Norton Starr About the Puzzle History Variations References Play
| |||

To play a physical version of this puzzle, using 21 actual tromino
tiles, a single square piece, and an 8 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 2 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. HistoryThe proof that for any positive integer n, a 2 ^{n}×2^{n}
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 2^{n}×2^{n}
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 2 ^{n}×2^{n} 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. VariationsHere 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
2 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. References- J. P. D'Angelo and D. B. West,
*Mathematical Thinking: Problem-Solving and Proofs*, Second edition, Prentice Hall, Upper Saddle River, NJ, 2000.
- 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)
- I. P. Chu and R. Johnsonbaugh, "Tiling deficient boards with
trominoes,"
*Math. Mag*.,**59**(1986), 34-40. - I. P. Chu and R. Johnsonbaugh, "Tiling boards with trominoes,"
*J. Recreational Math*.,**18**(1985-86), 188-193. - S. S. Epp,
*Discrete Mathematics with Applications*, Third edition, Thomson, Belmont, CA, 2004. - 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." - 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… ." - 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."] - S. W. Golomb, "Checker Boards and Polyominoes,"
*Amer. Math. Monthly*,**61**(1954), 675-682. - S. W. Golomb, "The General Theory of Polyominoes Part I
- Dominoes, Pentominoes and Checkerboards,"
*Recreational Math. Mag*., Issue No. 4 (August, 1961), 3-12. - S. W. Golomb,
*Polyominoes*, Scribner's, New York, 1965. (Second edition:*Polyominoes, Puzzles, Patterns, Problems, and Packings*, Princeton University Press, Princeton, 1994.) - 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. - R. Honsberger,
*Mathematical Gems II*, Mathematical Association of America, Washington, DC, 1976. - R. Johnsonbaugh,
*Discrete Mathematics*, Sixth edition, Pearson Prentice Hall, Upper Saddle River, NJ, 2005. - 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].) - G. E. Martin,
*Polyominoes, A Guide to Puzzles and Problems in Tiling*, Mathematical Association of America, Washington, DC, 1991. - G. E. Martin, review of S. Golomb's
*Polyominoes*(1994 edition),*Mathematical Reviews*, MR1291821 (95k:00006), 1995. - 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) - R. B. Nelsen,
*Proofs Without Words II, More Exercises in Visual Thinking*, Mathematical Association of America, Washington, DC, 2000. - 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.) - J. N. Silva (Ed.)
*Recreational Mathematics Colloquium I*(Conference Proceedings, Apr. 29-May 2, 2009. University of Évora), Associação Ludus, Lisboa, 2010. - D. Singmaster, review of G. E. Martin's
*Polyominoes, Mathematical Reviews*, MR1140005 (93d:00006), 1993. - A. Soifer,
*Geometric Etudes in Combinatorial Mathematics*, Second Edition, Springer, New York, 2010. - N. Starr, “Tromino Tiling Deficient Cubes of Side Length
2
^{n}”,*Geombinatorics*XVIII(2) (2008), 72-87. - N. Starr, “Tromino Tiling Deficient Cubes of Any Side Length”, http://arxiv.org/abs/0806.0524 , June 3, 2008.
- D. J. Velleman,
*How To Prove It: A Structured Approach*, Second edition, Cambridge University Press, New York, 2006
© 2012 Norton Starr |