Straight Tromino on a Chessboard

A straight tromino is a piece consisting of three equal squares in a linear pattern. If the constituent squares have the size of a square on a chessboard, a straight tromino may cover three contiguous squares lying in a column or a row of the board. A monomino is a piece that consists of a single square.

The task of covering (without overlap) an 8×8 board with 21 straight trominos and 1 monomino, has been discussed on several occasions, in particular twice by Ross Honsberger: in Mathematical Gems II and In Pólya's Footsteps. The question is, where can the monomino be placed?

(For the case of the L-shaped tromino, the monomino can be placed anywhere on the board. The case of the straight tromino is more involved.)

The applet below let's you experiment with the problem. To place a tromino, click on a free square, move the cursor to another free square two squares away, click there too. Provided, the two squares can be covered by a single tromino without creating an overlap with existing pieces, these steps will add a tromino to the board. You can remove it by clicking the "Remove last" button. As a matter of course, the applet affords boards of different dimensions: from 3×3 to 20×20. (When the side length is divisible by 3, the board can be covered by trominos in a trivial manner. This case is not interesting.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

Discussion


|Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

There are two approaches to the problem. The original one by Solomon Golomb (Am Math Monthlyv. 61 (1954), pp. 675-682) and a later one by by Joe Roberts (Math Gazette 1989, pp. 210-211). Both solutions are intended for the standard 8×8 board. We'll see about generalizations later on.

Solution 1 (Golomb)

Color the 8×8 board in three colors red, white and black as shown below

Note that however you place a straight tromino on the board, it always covers cells of all three colors. It follows that when all the trominos have been placed on the standard board, they cover exactly 21 red, 21 white and 21 black squares. By direct verification, the board has 21 squares of each red and black and 22 white squares. Therefore, the monomino may only be placed on a white square. However, not every white square will do. Observe that, with the pieces in place, the board (i.e. the grid together with the pieces, not the coloring) can be reflected in its horizontal and vertical axes of symmetry and rotated 90o and its multiples. Thus obtained covering also solve the problem. Hence, after the transformations, the monomino has to be located again in a white square. The white squares that do not map on the white squares under these transformations do not fit the bill. There are only 4 that do. These are c3, c6, f3, f6. It is easy to find coverings with straight trominos that leave out either of the four squares.

Solution 2 (Roberts)

We are going to assign to each square of the board a pair of integers coordinates (i, j), both i and j varying from 0 to 7. The first coordinate increase left to right, the second from the bottom upwards. With each square (a, b) we shall further associate the term xayb of the function

(f) f(x, y) = (1 + x + x2 + ... + x7)(1 + y + y2 + ... + y7).

The function f has exactly 64 terms, one per square, and may be considered the generating function of the board.

A straight tromino if placed horizontally on the board will cover three successive squares related to three terms of f:

(h) xayb + xa+1yb + xa+2yb = xayb(1 + x + x2).

Similarly, for a vertically placed tromino, the terms related to the covered squares are

(v) xayb + xayb+1 + xayb+2 = xayb(1 + y + y2).

Any covering of the whole board with the trominos and a single monomino, splits f(x, y) into a sum of terms (h) and (v) and a single xayb:

(1) f(x, y) = (1 + x + x2)·g(x, y) + (1 + y + y2)·h(x, y) + xayb,

where g and h are some polynomial functions of x and y.

Let w denote one of the nonreal 3rd roots of unity:

(2) 1 + w + w2 = 0.

Since w2 is another nonreal 3rd root of unity, we also have:

(2') 1 + w2 + w4 = 0

and of course w4 = w. Substituting w into (f) we see that

f(w, w) = (1 + w)(1 + w) = w.

On the other hand, from (1)

f(w, w) = wa + b.

The two together imply that

(3) a + b = 1 (mod 3).

Similarly, if we evaluate f(w2, w) in two ways, we'll get

(3') 2a + b = 0 (mod 3).

Combining (3) and (3'), we are led to

a = -1 = 2 (mod 3).

So that a could only be 2 or 5, and the same is true for b. Thus we have 4 possible locations for the single monomino: (2, 2), (2, 5), (5, 2), and (5, 5). The same as above.

As an exercise, one can establish that on a 7×7 board there are 9 possible locations for the monomino, both a and b satisfy

a, b = 0 (mod 3),

i.e., a, b = 0, 3, 6.

The applet allows choosing independent vertical (N) and horizontal (M) dimensions. The implied novelty is that now the number of squares N×M may have the remainder 2 modulo 3. So that 2 monominos become necessary. Their locations could be found by the above methods with a little more effort than before. They could not be placed arbitrarily, but there is much freedom in choosing their locations.

References

  1. R. Honsberger, Mathematical Gems II, MAA, 1976, pp. 62-63
  2. R. Honsberger, In Pólya's Footsteps, MAA, 1997, pp. 81-84
  3. A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)

Generating Functions


Related material
Read more...

  • Covering A Chessboard With Domino
  • Tiling a Chessboard with Dominoes
  • Straight Tromino on a Chessboard
  • Golomb's inductive proof of a tromino theorem
  • Tromino Puzzle: Interactive Illustration of Golomb's Theorem
  • Tromino as a Rep-tile
  • Tiling Rectangles with L-Trominoes
  • Squares and Straight Tetrominoes
  • Covering a Chessboard with a Hole with L-Trominoes
  • Tromino Puzzle: Deficient Squares
  • Tiling a Square with Tetrominoes Fault-Free
  • Tiling a Square with T-, L-, and a Square Tetrominoes
  • Tiling a Rectangle with L-tetrominoes
  • Tiling a 12x12 Square with Straight Trominoes
  • Bicubal Domino

  • |Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62338264

    Search by google: