Writings of E. W. Dijkstra

The University of Texas hosts an archive of the writings of the late Professor Dijkstra. This is a treasure trove of musings by one of the greatest minds in all of Computer Science. You could do much worse with your time than to spend it poking around the archive. Today, for example, I read this gem:

Consider the plane figure Q, defined as the 8 by 8 square from which, at two opposite corners, two 1 by 1 squares have been removed. The area of Q is 62, which equals the combined area of 31 dominos of 1 by 2. The theorem is that the figure Q cannot be covered by 31 of such dominos.

Another way of stating the theorem is that if you start with squared paper and begin covering this by placing each next domino on two new adjacent squares, no placement of 31 dominos will yield the figure Q.

So, a possible way of proving the theorem is by generating all possible placements of dominos and verifying for each placement that it does not yield the figure Q: a tremendously laborious job.

The simple argument, however is as follows. Colour the squares of the squared paper as on a chess board. Each domino, covering two adjacent squares, covers 1 white and 1 black square, and, hence, each placement covers as many white squares as it covers black squares. In the figure Q, however, the number of white squares and the number of black squares differ by 2 –opposite corners lying on the same diagonal– and hence no placement of dominos yields figure Q.

(Credit to Bheeshmar for leading me to EWB1036)

Advertisements


%d bloggers like this: