Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Romania

A domino is a rectangle formed by two unit squares that share a common side. A number of 1818 dominoes fit together to tile a 6×66 \times 6 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 [0,6]×[0,6][0, 6] \times [0, 6]. We first show that either some grid-vertical x=ix = i, i=1,2,3,4,5i = 1, 2, 3, 4, 5, or some grid-horizontal y=jy = j, j=1,2,3,4,5j = 1, 2, 3, 4, 5, crosses no tile. Let mim_i and njn_j be the number of tiles crossed by the grid-vertical x=ix = i and the grid-horizontal y=jy = j, 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 m1+m2+m3+m4+m5m_1 + m_2 + m_3 + m_4 + m_5. Similarly, the number of vertical tiles is n1+n2+n3+n4+n5n_1 + n_2 + n_3 + n_4 + n_5. Hence the number of tiles is m1+m2+m3+m4+m5+n1+n2+n3+n4+n5=18m_1 + m_2 + m_3 + m_4 + m_5 + n_1 + n_2 + n_3 + n_4 + n_5 = 18. Consequently, either some mi1m_i \le 1, i=1,2,3,4,5i = 1, 2, 3, 4, 5, or some nj1n_j \le 1, j=1,2,3,4,5j = 1, 2, 3, 4, 5.

Now, for each positive integer i5i \le 5, the rectangle [0,i]×[0,6][0, i] \times [0, 6] consists of a certain number of tiles and mim_i unit cells, the left halves of the horizontal tiles the grid-vertical x=ix = i crosses. Since the area of each [0,i]×[0,6][0, i] \times [0, 6] and the area of each tile are both even, so is each mim_i. Similarly, each njn_j is even.

Finally, by the conclusion of the preceding paragraph, either some mi=0m_i = 0, i=1,2,3,4,5i = 1, 2, 3, 4, 5, in which case the corresponding grid-vertical x=ix = i crosses no tile; or some nj=0n_j = 0, j=1,2,3,4,5j = 1, 2, 3, 4, 5, in which case the corresponding grid-horizontal y=jy = j 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 mim_i and the five njn_j are all positive even integers, i.e., they are all at least 22. Consequently, the ten add up to at least 20>1820 > 18 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 [0,6]×[0,6][0, 6] \times [0, 6] with a single separating line, i.e., one crossing no tile. Clearly, grid-lines alone are to be considered.

Begin by tiling the rectangle [0,3]×[0,6][0, 3] \times [0, 6] by four horizontal dominoes, namely,
[0,2]×[0,1],[0,2]×[3,4],[1,3]×[4,5],[1,3]×[5,6], [0, 2] \times [0, 1], \quad [0, 2] \times [3, 4], \quad [1, 3] \times [4, 5], \quad [1, 3] \times [5, 6],
and five vertical dominoes, namely,
[2,3]×[0,2],[0,1]×[1,3],[1,2]×[1,3],[2,3]×[2,4],[0,1]×[4,6]. [2, 3] \times [0, 2], \quad [0, 1] \times [1, 3], \quad [1, 2] \times [1, 3], \quad [2, 3] \times [2, 4], \quad [0, 1] \times [4, 6].

Notice that the grid–horizontal y=4y = 4 is the single separating line of this tiling.

Next, tile the rectangle [3,6]×[0,6][3, 6] \times [0, 6] by a copy of the reflection of the above tiling in the grid–horizontal y=3y = 3, to make the grid–horizontal y=2y = 2 its single separating line. Explicitly, the four horizontal tiles are
[4,6]×[0,1],[4,6]×[1,2],[3,5]×[2,3],[3,5]×[5,6], [4, 6] \times [0, 1], \quad [4, 6] \times [1, 2], \quad [3, 5] \times [2, 3], \quad [3, 5] \times [5, 6],
and the five vertical tiles are
[3,4]×[0,2],[5,6]×[2,4],[3,4]×[3,5],[4,5]×[3,5],[5,6]×[4,6]. [3, 4] \times [0, 2], \quad [5, 6] \times [2, 4], \quad [3, 4] \times [3, 5], \quad [4, 5] \times [3, 5], \quad [5, 6] \times [4, 6].
The grid–horizontal y=2y = 2 is clearly the single separating line of this tiling.

Finally, the two tilings fit together along the grid–vertical x=3x = 3 to form an overall tiling of the square [0,6]×[0,6][0, 6] \times [0, 6] with a single separating line — the grid–vertical x=3x = 3, of course.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.