__The chessboard covered with dominoes__

We consider a partitioning of the squares of the 8×8 chessboard into 32 pairs of adjacent squares and call a pair of squares in the same row (column) “a horizontal (vertical) domino”. Then the number of horizontal dominoes with a black left square equals that of those with a white left square. [Corollary: the number of horizontal dominoes is even.]

__Proof__ Consider for a given partitioning one of the seven lines that separate two adjacent columns; it divides the board into a left and a right part. We observe that (i) because the column length is even, each column, and hence the left part consists of equal numbers of black and white squares, and (ii) because domino consists of a black and a white square, the dominoes entirely to the left of the line comprise equal numbers of black and of white squares. Combining the two observations, we conclude about the horizontal dominoes crossed by the line —i.e., the dominoes with 1 square at either side of the line— that there are as many with a black left square as with a white one. Since each horizontal domino is crossed by exactly one of the seven lines, we now can conclude by summation that the total number of horizontal dominoes with a black left square equals the total number of those with a white left square.

(End of Proof)

Note that of the chessboard dimensions, we only used that the height is even.

__Acknowledgement__ I owe thanks to Jayadev Misra who inspired me to write this down and to Jan L.A. van de Snepscheut, who contributed part of the argument.

Austin, 5 February 2001

prof. dr. Edsger W. Dijkstra

Department of computer Sciences

The University of Texas at Austin

Austin, TX 78712–1188

USA

Transcription by Xiaozhou (Steve) Li.

Last revision: