Covering a chess board with $2$ missing places with $31$ dominoes

Question

I am reading a book that is intended to a wide audience (and not just mathematicians etc'), the book is, of course, about mathematics (Its still not clear about what exactly, I am only in page $2$).

The author gives the following riddle:

Take an $8\times8$ bored, and remove the bottom right piece and the upper left one, can you cover it with $31$ dominoes ?

The answer is given - it is no. The author explains that if we were to paint the board as a chess board then the removed pieces are of the same color, but since each domino will cover exactly one black piece and one white piece then we can't cover the $30$ white pieces and $32$ black pieces.

Then the author poses an exercise:

Prove that this can be done if the removed pieces are of different color

I don't know how to start with this, I can look at a given board and try to cover it, but I can't give a methodology or a proof for this.

Can someone please hint me in the right direction ?

Answer 1

Draw a hamiltonian cycle on the chessboard. Any cycle will do, and the following one suffices:

Pick (any) one square and call it $s_0$. Number the following squares in the hamiltonian cycle $s_1, s_2,\ldots s_{63}$:

Note that the even $s_i$ are all one color (say pink) and the odd $s_i$ are the other color (say brown). So far this is all very easy.

Now suppose two squares of the opposite colors have been deleted; for example:

The cycle has been cut into two paths, both of which have even length. Such a path is easily covered with dominoes: say one path is $s_k, s_{k+1}, \ldots, s_{k+2j+1}$, where the subscripts are understood mod 64. Then the dominoes easily go onto $(s_k, s_{k+1}), (s_{k+2}, s_{k+3}), \ldots (s_{k+2j}, s_{k+2j+1})$. Similarly the other path is tiled by $(s_{k+2j+3}, s_{k+2j+4}), \ldots, (s_{k-3}, s_{k-2})$.

This theorem and the proof I have given appear on pages 111–112 of Solomon W. Golomb Polyominoes (revised ed.), Princeton University Press, 1994. The proof is attributed to Ralph Gomory.

Answer 2

If they are of different colors then you start covering the board, row after row, until you get to a row that has an empty square. Next to it you lay the domino piece horizontally and you keep compensating until you get to the next row that has the missing square.

You now need to take care of the missing pieces being on the last row and you do that by turning the board around.

Answer 3

Consider the rectangle with the two removed squares at diagonally opposite corners. Show that this has one side of even length and the other of odd length. Find a standard pattern for tiling such rectangles with diagonally opposite corners missing.

Then show that you can tile the remainder of the board outside the rectangle. You might want to consider cases for the parity of the row/column of the position of one of the corners of the rectangle and again show that the outside can be tiled using one of a small number of standard patterns depending on the parity.

Answer 4

Not a full proof, but essentially those are the steps:

• Check, that the corresponding grid graph of the chess board is Hamiltonian. (In layman's terms: Taking only horizontal and vertical steps you can pass all the $64$ squares exactly once and finish where you started.)

• If two pieces are removed, then the circle is split into two paths, whose lengths are both even, if the removed pieces have different colors.

• Since the length is even and the paths take only horizontal and vertical steps, you can cover both paths with dominoes.

Answer 5

This may be a different way to go from the existing answers. You're looking for a perfect matching on the grid graph which corresponds to the mutilated chessboard. This graph is bipartite, and so Hall's Theorem gives a necessary and sufficient condition for the existence of a matching. That condition in this context would be that for every subset $S$ of black squares, if $|S|\leq |N(S)|$ where $N(S)$ is the set of adjacent white squares to all of the black squares in $S$, and vice versa. I believe this can be proven without too much difficulty by induction.

Answer 6

By rotating the board if necessary, we may assume that the white and black gap are not in the same row. The gaps part their rows into an odd and an even part. Fill the even parts in the obvious manner. Also fill the (even) rows below the lower and above the upper gap in straightforward manner.

The remaining part can be filled in a zig-zag manner - but why? Whether the odd part in a gappy row is on the left or right changes with the colour of the gap and also with the parity of the row number. Therefore, if the gaps are in consecutive rows, the odd parts are in the same direction and things work out fine. If they have one row inbetween, the odd parts are in opposite direction and that matches the zig-zag well. And so on with more intermediate rows.