A domino is a rectangle formed by two unit squares that share a common side. A number of dominoes fit together to tile a square. Show that some line crossing the interior of the square crosses the interior of no domino. Is it possible that such a line be unique?
Solution
Let the square be . We first show that either some grid-vertical , , or some grid-horizontal , , crosses no tile. Let and be the number of tiles crossed by the grid-vertical and the grid-horizontal , respectively. Clearly, a grid-vertical crosses only horizontal tiles, and a grid-horizontal crosses only vertical tiles.
Since every horizontal tile is crossed by a single grid-vertical, the number of horizontal tiles is . Similarly, the number of vertical tiles is . Hence the number of tiles is . Consequently, either some , , or some , .
Now, for each positive integer , the rectangle consists of a certain number of tiles and unit cells, the left halves of the horizontal tiles the grid-vertical crosses. Since the area of each and the area of each tile are both even, so is each . Similarly, each is even.
Finally, by the conclusion of the preceding paragraph, either some , , in which case the corresponding grid-vertical crosses no tile; or some , , in which case the corresponding grid-horizontal crosses no tile.
Alternative solution.
Suppose, in the above setting, that every grid-line, whether vertical or horizontal, crosses at least one tile. Then the five and the five are all positive even integers, i.e., they are all at least . Consequently, the ten add up to at least which is a contradiction. This establishes the first part.
The answer to the second part is in the affirmative. To prove this, we exhibit a domino tiling of the square with a single separating line, i.e., one crossing no tile. Clearly, grid-lines alone are to be considered.
Begin by tiling the rectangle by four horizontal dominoes, namely,
and five vertical dominoes, namely,
Notice that the grid–horizontal is the single separating line of this tiling.
Next, tile the rectangle by a copy of the reflection of the above tiling in the grid–horizontal , to make the grid–horizontal its single separating line. Explicitly, the four horizontal tiles are
and the five vertical tiles are
The grid–horizontal is clearly the single separating line of this tiling.
Finally, the two tilings fit together along the grid–vertical to form an overall tiling of the square with a single separating line — the grid–vertical , of course.