
Problem 2. Given positive integers $m$ and $n \geq m$, determine the largest number of dominoes ( $1 \times 2$ or $2 \times 1$ rectangles) that can be placed on a rectangular board with $m$ rows and $2 n$ columns consisting of cells $(1 \times 1$ squares) so that:

(i) each domino covers exactly two adjacent cells of the board;

(ii) no two dominoes overlap;

(iii) no two form a $2 \times 2$ square; and

(iv) the bottom row of the board is completely covered by $n$ dominoes.


Solution 1. The required maximum is $m n-\lfloor m / 2\rfloor$ and is achieved by the brick-like vertically symmetric arrangement of blocks of $n$ and $n-1$ horizontal dominoes placed on alternate rows, so that the bottom row of the board is completely covered by $n$ dominoes.

To show that the number of dominoes in an arrangement satisfying the conditions in the statement does not exceed $m n-\lfloor m / 2\rfloor$, label the rows upwards $0,1, \ldots, m-1$, and, for each
$i$ in this range, draw a vertically symmetric block of $n-i$ fictitious horizontal dominoes in the $i$-th row (so the block on the $i$-th row leaves out $i$ cells on either side) - Figure 4 illustrates the case $m=n=6$. A fictitious domino is good if it is completely covered by a domino in the arrangement; otherwise, it is bad.

If the fictitious dominoes are all good, then the dominoes in the arrangement that cover no fictitious domino, if any, all lie in two triangular regions of side-length $m-1$ at the upper-left and upper-right corners of the board. Colour the cells of the board chess-like and notice that in each of the two triangular regions the number of black cells and the number of white cells differ by $\lfloor m / 2\rfloor$. Since each domino covers two cells of different colours, at least $\lfloor m / 2\rfloor$ cells are not covered in each of these regions, and the conclusion follows.

![](https://cdn.mathpix.com/cropped/2024_06_04_864907597421bc146623g-3.jpg?height=268&width=525&top_left_y=820&top_left_x=343)

Fig. 4
![](https://cdn.mathpix.com/cropped/2024_06_04_864907597421bc146623g-3.jpg?height=422&width=580&top_left_y=665&top_left_x=1069)

Fig. 5

To deal with the remaining case where bad fictitious dominoes are present, we show that an arrangement satisfying the conditions in the statement can be transformed into another such with at least as many dominoes, but fewer bad fictitious dominoes. A finite number of such transformations eventually leads to an arrangement of at least as many dominoes all of whose fictitious dominoes are good, and the conclusion follows by the preceding.

Consider the row of minimal rank containing bad fictitious dominoes - this is certainly not the bottom row - and let $D$ be one such. Let $\ell$, respectively $r$, be the left, respectively right, cell of $D$ and notice that the cell below $\ell$, respectively $r$, is the right, respectively left, cell of a domino $D_{1}$, respectively $D_{2}$, in the arrangement.

If $\ell$ is covered by a domino $D_{\ell}$ in the arrangement, since $D$ is bad and no two dominoes in the arrangement form a square, it follows that $D_{\ell}$ is vertical. If $r$ were also covered by a domino $D_{r}$ in the arrangement, then $D_{r}$ would also be vertical, and would therefore form a square with $D_{\ell}$ - a contradiction. Hence $r$ is not covered, and there is room for $D_{\ell}$ to be placed so as to cover $D$, to obtain a new arrangement satisfying the conditions in the statement; the latter has as many dominoes as the former, but fewer bad fictitious dominoes. The case where $r$ is covered is dealt with similarly.

Finally, if neither cell of $D$ is covered, addition of an extra domino to cover $D$ and, if necessary, removal of the domino above $D$ to avoid formation of a square, yields a new arrangement satisfying the conditions in the statement; the latter has at least as many dominoes as the former, but fewer bad fictitious dominoes. (Figure 5 illustrates the two cases.)
