Dominoes on a Chessboard

Covering a chessboard with L-shaped and straight trominoes posed two different but very engaging problems. Using larger polyominoes naturally leads to a variety of problems. Perhaps unexpectedly, even the simplest of them - dominos - still afford genuine mathematical entertainment.

A domino is a 2×1 polyomino piece, i.e., a piece that consists of two adjoined squares. Obviously, any rectangular N×M chessboard can be covered with dominoes iff at least one of N and M is even. If both are odd, an empty square can be chosen arbitrarily on the board. The proof is similar to a construction used to solve another problem. So, what else the dominoes are good for? Here's one example.

The squares on an N×M chessboard, its pattern, is created by two families of evenly spaced parallel lines: (N-1) horizontal lines and (M-1) vertical lines. A domino piece that covers exactly two squares crosses one such line. Assuming the whole board is covered with dominoes, some of the lines will be crossed, but others may not be. Lets call the lines that have not be crossed fault lines. Prove that every covering of a 6×6 board with dominoes leaves at least one fault line. Give an example of a covering with exactly 1 fault.


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 http://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

An important observation is that a chessboard line on a 6×6 board can't be crossed by exactly 1 domino. For, such a line would then split the board into two parts of dimensions 6×t and 6×(6-t), each with an even number of squares of which one square is occupied with a half-domino at hand. If the line is not crossed by another domino, then each of the parts is left with an odd number of squares fully covered with dominoes. A contradiction.

Thus it takes at least two dominoes to cross a line. On a 6×6 board there are 10 lines. It takes 10·2 = 20 dominoes to cross all of them. But 20 dominoes cover 40 squares whereas a 6×6 board has only 36 of them. It follows that any covering of the 6×6 board is bound to leave some fault lines. The picture below gives an example of a covering with a single such line.

In general, an N×M board can be covered fault-free iff the following condition hold:

  1. N·M is even,

  2. N > 4 and M > 4,

  3. (N, M) (6, 6)!.

References

  1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, p. 35
  2. S. Golomb, Polyominoes, Princeton University Press; 2nd edition (March 18, 1996)
  3. A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
  4. C. W. Trigg, Mathematical Quickies, Dover, 1985, #258

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-2005 Alexander Bogomolny

     62013650

    Search by google: