A $4 \times 4$ chessboard is to be completely covered with domino tiles without gaps or overlaps (edge-to-edge). Each domino tile covers two adjacent squares. In how many ways can this be done? (We do not consider two covering patterns different if one can be transformed into the other by rotating or reflecting the board.)
I. solution. Let's call the axis of the dominoes their longer midline. First, consider the four domino tiles covering the four corner squares of the board. It is possible that all four dominoes have axes in the same direction, in which case a $90^{\circ}$ rotation - if necessary - can make them horizontal. It is also possible that the axes of three stones are parallel - we can assume they are horizontal - and the fourth one is perpendicular to them; by reflecting over the midlines - if necessary - we can achieve that the top right corner square is covered by a vertical axis domino. Finally, it is possible that the axes of two dominoes are parallel in each direction; in the latter case, the parallel axis dominoes are either adjacent along the side or cover the corner squares at the ends of a diagonal; in this case, it can be assumed that the top left corner square is covered by a horizontal domino (1st figure $A, B, C, D$ arrangement).
![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-1.jpg?height=298&width=1048&top_left_y=516&top_left_x=520)

1st figure

In the case of the $D$ arrangement, the remaining squares can only be covered in such a way that a single domino covers the outermost squares surrounded on three sides and the adjacent middle square (dashed lines). Continuing the $B$ and $C$ arrangements, the placement of only two dominoes is clear, and the remaining $2 \times 2$ squares can be covered in two ways, with horizontal or vertical axis dominoes. In the case of the $A$ arrangement, the uncovered part can cover both top corner squares with a horizontal domino, or one - for example, the left side - with a horizontal and the other with a vertical domino, or both with vertical dominoes (2nd figure, $E, F, G$).
![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-1.jpg?height=190&width=802&top_left_y=1255&top_left_x=648)

2nd figure

The first two can be completed unambiguously, the third again gives two possibilities. In them, the two ways of covering the uncovered 4 squares can be transformed into each other by a $90^{\circ}$ rotation, but this rotation does not map the covering diagram of the squares on the edge of the board onto itself, so the two coverings are not identical.

According to these, the covering can be done in 9 different ways, with obvious notation in the following ways: $A E, A F, A G_{v}, A G_{f}$, $B_{v}, B_{f}, C_{v}, C_{f}, D$

II. solution. Of the 3-3 line segments dividing the board into squares, in every covering at least 2 will be the full length boundary lines of domino tiles, i.e., they will not intersect a domino. If, in fact, a line is placed with a domino intersecting it, then in the rectangular parts of the board on either side of the line, an odd number of uncovered squares will remain, because the number of squares was originally even in each part of the rectangle. Therefore, to complete the full covering, another domino intersecting the line must be placed on the line, and if a third intersecting domino is placed on the line, it follows from the same reasoning that a fourth must also intersect the line. Thus, every intersected line is intersected by an even number of stones, and the 8 stones to be used are sufficient for the intersection of at most 4 lines, so at least 2 lines remain unintersected.

On the other hand, the number of intersected lines is at least 2, because a line can be intersected by at most 4 stones.

![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-1.jpg?height=325&width=328&top_left_y=2190&top_left_x=497)

a

![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-1.jpg?height=328&width=328&top_left_y=2189&top_left_x=888)

b

![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-1.jpg?height=369&width=314&top_left_y=2187&top_left_x=1274)

3rd figure

If there are 3 parallel - say horizontal - lines not intersected by dominoes, this divides the board into 4 rows, and each of these can only be covered by 2 adjacent dominoes (3rd figure a). If only two of the horizontal lines are not intersected by dominoes, then these lines either separate two adjacent rows or the two outermost rows from the rest of the board, and these rows can again only be covered by 2 horizontal dominoes (3rd figure b, c); therefore, only the middle vertical line can be one that is not intersected by a domino. If it is indeed, then since a horizontal line running through the still uncovered rectangle is intersected by a domino, one side - for example, the right side - of the rectangle is covered by 2 vertical dominoes (4th figure d), and the other side is covered by either 2 horizontal or 2 vertical dominoes. If the middle vertical line is intersected by a domino, this already unambiguously determines the covering of the rectangle (4th figure e).

![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-2.jpg?height=431&width=328&top_left_y=522&top_left_x=882)

4th figure

Finally, if only one horizontal and one vertical line are not intersected by a domino, these cannot both be adjacent to one of the board's sides, because then they would isolate a corner square from the rest of the board, and it could not be covered by a domino. If, for example, the top horizontal and the middle vertical lines are not intersected by a domino (5th figure f), then a domino must intersect the middle horizontal line, say on the right side of the board, and this already determines the covering of the right side, and the lower horizontal line can then only be intersected by a domino on the left side, which in turn determines the covering of the left side.
![](https://cdn.mathpix.com/cropped/2024_05_02_f2be9c91537bfab02019g-2.jpg?height=384&width=720&top_left_y=1374&top_left_x=688)

5th figure

Finally, if the two middle lines are not intersected by a domino (5th figure g), then the other lines can only be intersected by alternating horizontal and vertical dominoes covering adjacent squares.

Thus (using notation similar to the first solution), we have arrived at the following 9 coverings: $a, b d_{v}, b d_{f}, b e, c d_{v}, c d_{f}$, $c e, f, g$. (These correspond to the $A E, B_{v}, C_{v}, C_{f}, A F, A G_{f}, A G_{v}, B_{f}$, and $D$ coverings obtained in the first solution, in some cases in a different position.)

Imre Bárány (Budapest, Corvin Mátyás Gymnasium, 2nd grade)