Saturated Domino Coverings
by Andrew Buchanan, Tanya Khovanova, and Alex Ryba
We got this problem from Rados Radoicic:
A 7 by 7 board is covered with 38 dominoes such that each covers exactly 2 squares of the board. Prove that it is possible to remove one domino so that the remaining 37 still cover the board.
Let us call a domino covering of an n by n board saturated if the removal of any domino leaves an uncovered square. Let d(n) be the number of dominoes in the largest saturated covering of an n by n board. Rados’ problem asks us to prove that d(7) < 38.
Let’s begin with smaller boards. First we prove that d(2) = 2. Suppose that 3 dominoes are placed on a 2 × 2 board. Let us rotate the board so that at least two of the dominoes are horizontal. If they coincide, then we can remove one of them. If not, they completely cover the board and we can remove the third one. Similarly, you can check all the cases and show that d(3) = 6.
Now consider a saturated domino covering of an n × n board. We can view the dominoes as vertices of a graph, joining two if they share a cell of the board. No domino can share both cells with other dominoes, or we could remove it. Hence, each domino contains at most one shared cell. This means that all the dominoes in a connected component of the graph must overlap on a single shared cell. Hence, the only possible connected components must have the following shapes:
The largest shape in the picture is the X-pentomino. We can describe the other shapes as fragments of an X-pentomino, where the center and at least one more cell is intact. We call these shapes fragments.
A saturated covering by D dominoes corresponds to a decomposition of the n × n board into F fragments. Note that a fragment with k cells is made from k − 1 dominoes. Summing over the dominoes gives: D = n2 − F. Thus, in order to make D as large as possible, we should make F as small as possible. Let f(n) be the minimal number of fragments that are required to cover an n by n board without overlap. Then d(n) = n2 − f(n).
Consider the line graph of the n by n board. The vertices of the line graph correspond to cells in the original board and the edges connect vertices corresponding to neighboring cells. Notice that in the line graph our fragments become all star graphs formed by spokes coming out from a single central node. Thus a decomposition of a rectangular board into fragments corresponds to a covering of its line graph by star graphs. Consider an independent set in the line graph. The smallest independent set has the same number of elements as the smallest number of stars that can cover the graph. This number is called a domination number.
Now let’s present a theorem connecting domino coverings with X-pentomino coverings.
Theorem. f(n) equals the smallest number of X-pentominoes that can cover an n by n board allowing overlaps and tiles that poke outside, which is the same as the domination number of the corresponding line graph.
The proof of this theorem and the solution to the original puzzle is available in our paper: “Saturated Domino Coverings.” The paper also contains other theorems and discussions of other boards, not to mention a lot of pictures.
The practical applications of star graph coverings are well-known and widely discussed. We predict a similar future for saturated domino coverings and its practical applications, two examples of which follow:
First, imagine a party host arranging a plate of cookies. The cookies must cover the whole plate, but to prevent the kids sneaking a bite before the party, the cookies need to be placed so that removal of just one cookie is bound to expose a chink of plate. This means the cookies must form a saturated covering of the plate. Of course the generous host will want to use a maximal saturated covering.
For the second application, beam yourself to an art museum to consider the guards. Each guard sits on a chair in a doorway, from where it is possible to watch a pair of adjacent rooms. All rooms have to be observed. It would be a mistake to have a redundant guard, that is, one who can be removed without compromising any room. Such a guard might feel demotivated and then who knows what might happen. This means that a placement of guards must be a saturated domino covering of the museum. To keep the guards’ Union happy, we need to use a maximal saturated covering.
We would welcome your own ideas for applications of saturated coverings.
Share:
Sunday Links « euler cycle:
[…] Khovanova, at MIT, posted a blog about her new paper on saturated domino coverings. It doesn’t require too much math knowledge to get the blog post, and it is a pretty cool […]
26 February 2012, 7:25 pm