The Mathematics of Dominoes

Let's define a [n-n] domino set to be all possible dominoes between [0-0] and [n-n]. The traditional Western domino sets are the [6-6] or double six set, the [9-9] or double nine set, and the [12-12] or double twelve set.

While is clear that the double six set is derived from dice, I have no idea where the larger sets started. The Eskimos and Inuit Indians of Canada have animal bone domino sets with 61 to 148 pieces in a set used for gambling games. I do not know if these are of native origin or if they might have seen Western dominoes and attempted to copy them.

Size of a Set

The number of tiles in a set of [n-n] dominoes is given by the formula ((n² + 3n + 2)/ 2). For example the number tiles in a [18-18] set is (18*18 + 3*18 + 2)/2 = 190.

Type of Set	Number of Tiles	Comment
[0-0]	1
[1-1]	3
[2-2]	6
[3-3]	10
[4-4]	15
[5-5]	21
[6-6]	28	<= most common set
[7-7]	36
[8-8]	45
[9-9]	55	<= commercially available set
[10-10]	66
[11-11]	78
[12-12]	91	<= commercially available set
[13-13]	105
[14-14]	120
[15-15]	136	<= commercially available set
[16-16]	153
[17-17]	171
[18-18]	190	<= commercially available set

Important Properties of a Set

One of the most important properties of a [n-n] set of dominoes is that any number k (where 0 <= k <= n) will appear (n+2) times on the tiles. The reason that this is important to a player is that when you want to know if you can block another player, you can quickly count the occurrences of a number in your hand and on the table. If the count is equal to (n+2), you know that no other player can match that number. Look for a double, usually played as a spinner in most games, and you will have found four of the eight occurrences immediately.

The Single Train Problem

Given a set of [n-n] dominoes, is it possible to arrange all of the tiles into a single train? A train is a line of tiles each of whose ends match the end of the tiles to their immediate left and right, with the exception of the two end tiles which match on one end only, of course.

Can you arrange a set into a single circular train? A circular train is ring of tiles laid end to end where both ends of each tile matches its left and right hand neighbors. Obviously, if a circular train exists, it can be broken apart at any point to give a single train.

By simple trial and error, the answer for the zero set is "yes" for a single train because it is a trivial train itself. The answer is "no" for a circular train because the one member of the set cannot bend around to touch itself.

The [1-1] set is made up of the tiles [0-0], [0-1] and [1-1] which is a train when played in that order, but it is not a circular train. As the value of (n) increases, answering this question by trial and error is going to get to be much harder.

Instead, let's use a different approach; graph theory. While I do not have time to go into the mathematics of graph theory in detail, I hope I can cover enough of it to explain this solution.

A graph is a mathematical modeling structure made up of nodes (dots) and edges (lines). The number of edges coming in and out of node is the degree of the node.

Let's make the nodes represent the numbers 0 to (n) and edges between them be the tiles in a [n-n] domino set. A double is shown as an arc that starts and finishes on the same node. These graphs will have the same number of edges as there are dominoes in the set they model. For example, here is the graph for a [2-2] domino set:

Now, we can transform the problem of finding a train into the problem of finding a path thru the graph of the domino set that touches all the edges. The circular train problem becomes that of finding a path thru the graph of the domino set which includes all the edges and returns to the node from which it started. Fortunately, this is a graph theory problem that has already been solved by Leonhard Euler hundreds of years ago and it is known as the "Bridges of Königsberg problem". For such a circular train to exist, either

1. Each node has an even degree, or
2. There must two and only two nodes with an odd edge.

Therefore, the [3-3] set cannot be put into a single train because its nodes have degree 5. The Double six set can be put into a train because its nodes have degree 8. Notice that the degree of the nodes of a [n-n] domino set graph will always be (n+2), so it is easy to answer the train and circular train questions. If (n) is even, then a circular train exists for that domino set. If (n) is odd, then there are (n+1)/2 trains, each ending in a digit between zero and (n).

A common question is how many different trains can build with a standard double six set. Without doing the math, the answer is 7,959,229,931,520 if you count reversals or half that amount if you do not.

Clark's Law

This is a rather interesting result that says that in a blocked game of single spinner dominoes, the sum of the four arms of the tableau must always total to an even number.

The first corollary of Clark's Law is that the sum of the four hands in a blocked game is always an even number. This is because the double six set has 168 pips in it, which is an even number and an even number minus an even number is an even number.

The second corollary of Clark's Law is that the sum of the hands of the two partnership in a blocked game must both be even or both be odd.

Clark's law derives from the facts that doubles are always even, so the spinner will have four identical halves against it. Then in each arm, the ends of the tiles must be paired, so they are even until you get to the end of an arm. If the arm ends in a double, then the exposed tile is even.

A block can be made with two arms, three arms or four arms on the tableau. This reduces further to four arms with the same number showing, which gives us an even count, or with fours with two dead numbers. The situation with three arms in a blocked game requires that they all end with the same suit as the spinner.

Dominoes and Checkerboards

The "mutilated checkerboard" is a classic demonstration of a method of setting up sets in a certain class of problems. The puzzle is to ask if you can cover a checkerboard whose opposite corners have been cut off with domino tiles which exactly cover two cells of the checkerboard.

By inspection, there are 64 - 2 = 62 cells on the mutilated checkerboard, so we will need 31 tiles, assuming a solution exists. Now look at a how a domino can sit on the board -- it either faces North-South or East-West. But no matter how it is oriented, a tile always covers one black and one white cell. The mutilated checkerboard has 32 of black cells and 30 whites cells. Therefore, you can never cover the board.

You can find other proofs in the literature. Stan Wagon published "Fourteen Proofs of a Result about tiling a Rectangle", American Mathematical Monthly, 14, 94-1987, pp. 601-617.

One would expect that if the removed squares were of different colors both the answer and solution would be quite different. Indeed, cover the whole checkerboard with domino tiles. Cut two squares from under one of the pieces. The remaining portion of the board will still be covered with the remaining domino tiles. Thus, at least, sometimes the remaining board is "coverable." As a warm-up problem you may consider this one:

Problem 1

Cover two arbitrary squares of a checkerboard with a domino tile. Is it always possible to cover the remaining portion of the board with more tiles without disturbing the original piece?

Now, you may want to go further and relax one of the conditions in Problem 1: what if the squares are not adjacent? We already have a solution if they have the same color. There remains then just one case.

Problem 2

Two arbitrary squares of different colors have been removed from a checkerboard. Is it possible to cover the remaining portion of the board with domino so that each domino tile covers exactly two squares?

Solution

Yes, it's always possible. To see this, draw two forks as shown in red on the diagram.

This splits the checkerboard into a chain of alternating squares. It takes only a little experimentation to convince oneself that the chain can be traversed by starting at any square and covering two squares at a time with a tile. This observation actually solves the problem.

What would be the next question to ask related to covering of a checkerboard with domino? My son David came up with the following question:

Problem 3

Assume at every step we remove a pair of squares of different colors. What is the maximum number of pairs that may be removed such that it's always possible to cover the remaining portion of the board with domino tiles?

An Aside

It's a very legitimate question to ask because obviously, at one extreme, when we remove all but two nonadjacent squares, the problem of covering whatever remains will be unsolvable for at least some configurations. On the other hand, as we just saw, removing only two squares we have a solvable problem. Then there must be a borderline number somewhere in between.

At first the problem may seem to be difficult to solve. But you have to start somewhere. As is often the case, experimenting with a few particular cases helps gain insight into a more general problem. So let's start with the next simplest case of four squares (2 white and 2 black) being removed. The forks that worked so well for the previous case become useless. Indeed, following the chain we can remove two consecutive white and two consecutive black squares. This would not yet prove that thus obtained configuration is unsolvable; but doubts that the problem may not have an easy solution may start creeping into your mind. At this point, it may make sense to think of the possibility of a negative result. Can we think of a counterexample? In other words, perhaps it's possible to leave "noncoverable" board by just removing two pairs of squares.

What would make the board noncoverable? Recollecting our original problem, if it were possible to isolate a region of the checkerboard that contained an odd number of squares, we would be able to claim that the solution to Problem 3 is 1, just one pair.

Solution

It's possible to remove two pairs of squares as to leave noncoverable checkerboard. Indeed, remove two white squares adjacent to a black corner. This creates a region consisting of a single (corner) square that has no adjacent white squares.

Problem 4

Assume we are allowed to remove 2 white and 2 black squares so that the board does not yet fall apart, i.e., does not split into two or more separate pieces. Is it always possible to cover whatever remains of the board with domino?

Remark

Trying to answer Problem 4 I ran into one noncoverable configuration with 3 pairs of squares removed. The diagram depicts the lower right corner.

The grey outined squares are cut off (3 black squares - the three white squares are assumed to have been removed elsewhere.) The yellow rectangle represents a domino tile in the only position where it can cover the corner square. This blocks the single white square marked with a cross to its left. Thus the configuration is indeed noncoverable. We arrive at the conclusion that a single argument is going to solve both Problem 3 (with the extra requirement that the removed squares do not disconnect the board) and Problem 4.

Problem 5

This is to check your understanding of the solution to Problem 2.

A rectangular 2nx2m board has been covered with domino tiles. Prove that there exists another cover such that no domino tile belongs to both covers.

Reference

• P.J.Davis and R.Hersh, The Mathematical Experience, Houghton Mifflin Company, Boston, 1981
• R.Honsberger, Mathematical Gems II, MAA, New Math Library, 1976
• M.Kac and S.M.Ulam, Mathematics and Logic, Dover Publications, NY, 1968.