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.)
What if applet does not run? |
|Activities| |Contact| |Front page| |Contents| |Algebra|
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 90^{o} 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
(f) | f(x, y) = (1 + x + x^{2} + ... + x^{7})(1 + y + y^{2} + ... + y^{7}). |
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) | x^{a}y^{b} + x^{a+1}y^{b} + x^{a+2}y^{b} = x^{a}y^{b}(1 + x + x^{2}). |
Similarly, for a vertically placed tromino, the terms related to the covered squares are
(v) | x^{a}y^{b} + x^{a}y^{b+1} + x^{a}y^{b+2} = x^{a}y^{b}(1 + y + y^{2}). |
Any covering of the whole board with the trominos and a single monomino, splits
(1) | f(x, y) = (1 + x + x^{2})·g(x, y) + (1 + y + y^{2})·h(x, y) + x^{a}y^{b}, |
where g and h are some polynomial functions of x and y.
Let w denote one of the nonreal 3^{rd} roots of unity:
(2) | 1 + w + w^{2} = 0. |
Since w^{2} is another nonreal 3^{rd} root of unity, we also have:
(2') | 1 + w^{2} + w^{4} = 0 |
and of course w^{4} = 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) = w^{a + b}.
The two together imply that
(3) | a + b = 1 (mod 3). |
Similarly, if we evaluate f(w^{2}, 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:
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
- R. Honsberger, Mathematical Gems II, MAA, 1976, pp. 62-63
- R. Honsberger, In Pólya's Footsteps, MAA, 1997, pp. 81-84
- A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
Generating Functions
- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2017 Alexander Bogomolny
62684444 |