Tromino Puzzle: Deficient Squares

S. Golomb gave an inductive proof to the following fact: any 2n×2n board with one square removed can be tiled by right (or L-) trominoes - a piece formed by three adjacent squares in the shape of an L. Golomb's proof of the theorem became a model of elegance in elementary mathematics.

I-Ping Chu and Richard Johnsonbaugh extended Golomb's result to squares with sides not necessarily a power of 2. More accurately:

Theorem

If n ≠ 5, then a deficient n×n board can be tiled with L-trominoes if and only if n is not a multiple of 3.

(The board is deficient if one of the small unit squares is missing.)

Some 5×5 deficient boards can be tiled, others cannot. Although 5 appears as an exceptional case in the theorem, the 5×5 board with a removed corner can be tiled and plays an important role in the proof. The proof does exploits other special cases.

The applet below helps you test your understanding of the theorem by tiling the board manually. It takes three clicks to place a tromino piece on the board: click on three adjacent squares in sequence. (Do not drag the mouse.)


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?

Note that for small (2×2 and 4×4) boards the solution is unique and follows Golomb's proof. For larger boards, viz. starting with 8×8, this is no longer true: there is a good deal of solutions. However, some thinking is still required to tile the board and, more often than not, careless tiling will produce 1 and 2 squares pockets.

Another applet provides additional insight into the tiling with L-trominoes.

Interstingly, we run into an entirely different situation if we try to cover the chessboard with straight trominos. Now, we'll have to consider very carefully which single square may or may not be removed!

References

  1. I-Ping Chu, Richard Johnsonbaugh, Tiling Deficient Boards with Trominoes, Mathematics Magazine, Vol. 59, No. 1 (Feb., 1986), pp. 34-40

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny

Theorem

If n ≠ 5, then a deficient n×n board can be tiled with L-trominoes if and only if n is not a multiple of 3.

The proof is a consequences of several partial results.

Proposition 1

A 5×5 board with one corner square removed can be tiled

The proof is by inspection:

right tromino tiling of a deficient 5x5 board

Observe that the board with any of the squares next to a corner one removed could not be tiled with L-trominoes.

Proposition 2

A (2i)×(3j) board, i, j > 1, can be tiled.

Such a board could be tiled by 2×3 rectangles each composed of 2 trominoes:

2 right tromino make a 2x3 board

More general rectangles can be tiled with L-trominoes, but the above is the only case used below.

Proposition 3

Every deficient 7×7 board can be tiled.

The proof is again by inspection. There are just a few cases to consider. Enumerate squares starting in the upper left corner of the board with two integers (row, column). Because of the symmetry, we only have to check the cases of missing squares for 1 ≤ row ≤ column ≤ 4.

a deficient 7x7 board with (3, 3) removed

The untiled portion of the board is the deficient 5×5 board from Proposition 1 and can be tiled. If we enumerate squares starting in the upper left corner of the board with two integers (row, column), the diagram tells us that the 7×7 board with the (3, 3) removed could be tiled. With a slight modification it also shows how to tile the board with squares (2, 2), (3, 2), (2, 3) removed.

a deficient 7x7 board with (1,1) removed

This diagram serves to show tilings with one of the squares - (1, 1), (1, 2), (2, 2), (2, 1) - removed.

a deficient 7x7 board with (1,3) removed

This diagram serves to show tilings with one of squares - (1, 3), (2, 3), (1, 4), (2, 4) - removed.

Two additional tilings (without (4, 4) and (3, 4) squares) complete the proof:

a deficient 7x7 board with (4, 4) removed
a deficient 7x7 board with (3, 4) removed

Proposition 4

Any deficient n×n board, with n is odd, n > 5, and not divisible by 3, can be tiled by L-trominoes.

First, we examine a deficient 11×11 board. As the diagram suggests, the board can be split into the a 7×7 piece (that is assumed to contain the missing square), two 4×6 pieces, and one 5×5 piece, with one corner square removed.

a deficient 11x11 board

As it was already shown, all four can be tiled with L-trominoes.

From here we proceed by induction. Assume that n is odd, not divisible by 3, and greater than 11. For the inductive step, assume that the statement holds for all smaller odd n not divisible by 3.

Split the board as shown below. The (n - 6)×(n - 6) pieces is assumed to contain the missing square.

a deficient odd x odd board

If n is odd and not divisible by 3, so is (n - 6), making the (n - 6)×(n - 6) tilable by the inductive assumption. On the other hand, for n odd, n - 7 is even, so that the (n - 7) & times; 6 pieces can be tiled by Proposition 2. The deficient 7×7 pieces can, in turn, be tiled due to Proposition 3.

Proposition 5

Any deficient n×n board, with n even, greater than 1 and not divisible by 3 can be tiled with L-trominoes.

We start the induction with the observation that the 2×2, 4×4, and 8×8 deficient boards can be tiled (either by inspection or from Golomb's theorem).

Assume n is even, greater than 8, and is not divisible by 3. Suppose also that all smaller boards with such n can be tiled. Split the board into 4 pieces as shown:

a deficient even x even board

We assume that the missing square is located in the (n - 3)×(n - 3) piece. If n is even and not divisible by 3, then (n - 3) is odd and not divisible by 3. Given that n > 8, n - 3 > 5 so that Proposition 4 applies. The (n - 4)×3 pieces can be tiled by Proposition 2. So the whole board can be tiled and we are done.

A combination of the 5 propositions proves the theorem:

If n ≠ 5, then a deficient n×n board can be tiled with L-trominoes if and only if n is not a multiple of 3.

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]