Problem:
We define a chessboard polygon to be a polygon whose edges are situated along lines of the form or , where and are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
- Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.
- Prove that such a tasteful tiling is unique.
Solution:
- We prove the first part by induction on the number of dominoes in the tiling. The claim is clearly true for . So suppose we have a chessboard polygon that can be tiled by dominoes. Of all the leftmost squares in the polygon, select the lowest one and label it ; assume for sake of argument that square is black. In the given tiling, remove the domino covering , leaving a polygon which may be tiled with dominoes. By the induction hypothesis, this chessboard polygon can be tastefully tiled.
Now replace the domino that was removed. If this domino is horizontal, then we are guaranteed that the augmented tiling is still tasteful, since square is black and there are no squares below it. If the domino is vertical the augmented tiling may still be tasteful, but if not the trouble can only arise because there is another vertical domino directly to its right. In this case rotate the offending pair of dominoes to get two horizontal dominoes. We are not done yet, but if we now repeat this process-removing the horizontal domino covering , tiling the remainder, and replacing the domino - then we will obtain a tasteful tiling.
If square is white we may obtain a tasteful tiling by performing a similar process. This time we only encounter difficulty if the domino covering in the original tiling is horizontal, in which case there must be another horizontal domino directly above it. We rotate this pair, remove the now vertical domino covering , tile the remainder tastefully using the induction hypothesis, and restore the vertical domino to finish.
- Suppose now that there are two tasteful tilings of a given chessboard polygon. By overlaying these two tilings we obtain chains of overlapping dominos, since every square\
is part of one domino from each tiling. For example, a chain of length one indicates a domino common to both tilings. A chain of length two cannot occur, since these arise when a block is covered by horizontal dominos in one tiling and vertical dominos in the other, and one of these configurations will be distasteful.
Since the tilings are distinct a chain of length three or more must occur; let be the region consisting of such a chain along with its interior, if any. (It is possible that such a chain may completely occupy a region, so that only some of the dominoes in the chain adjoin squares outside of .) Note that the chain must include a horizontal domino along its lowermost row. If there are two or more overlapping horizontal dominos, then one of them will be a WB domino, i.e. have a white square on the left. Otherwise there are two adjacent vertical dominos that overlap with the single horizontal domino; since they are part of a tasteful tiling we again must have a WB domino. We will now focus on the tiling that includes this WB domino.
The two squares above the WB domino must be part of region . Furthermore, a single horizontal domino cannot cover them both, nor can a pair of vertical dominos. (Both cases yield distasteful configurations.) Hence a horizontal domino must cover at least one of these squares, extending past the given WB domino either to the left or right. Hence we can deduce the existence of a horizontal WB domino on the next row up. We may repeat this argument until we reach a horizontal WB domino in region for which the two squares immediately above it are not both in region . Hence this domino must be part of the chain that defined .
Now imagine walking along the chain, starting on the white square of the WB domino that exists along the lowest row of region and taking the first step towards the black square of the same domino. Draw an arrow along each domino in the direction of travel all the way around the chain. Since the squares must alternate white and black, these arrows will always point from a white square to a black square. Furthermore, since the interior of the region was initially to our left when we began the loop, it will always be to our left whenever the chain follows the boundary of .
But we now reach a contradiction. We earlier deduced the existence of a horizontal WB domino that was part of the chain and was adjacent to the boundary of , having a square above it that was not part of . Hence this domino must be traversed from right to left, since we leave the interior of to our left as we traverse the loop. Hence it must contain an arrow pointing to the left, implying that it must be a BW domino instead. This contradiction completes the proof.
This problem was suggested by Sam Vandervelde.
The problems on this page are the property of the MAA's American Mathematics Competitions