XXIX Rioplatense Mathematical Olympiad

Suppose the board is colored like a chessboard. First let's establish a bit of notation. A cycle is a sequence of cells $c_1,\dots ,c_k$ such that for all $i$ we have that $c_i$ and $c_{i+1}$ share one side (where $c_{k+1}=c_1$). There are two possible covers of a cycle by dominoes, one that joins each black square to the next square and one that joins each black square to the previous square. Let's say that the tiles of the first cover are inverse to those of the second one.

Lemma. Given a covering $T$ of a $2m\times (2n+1)$ board, each square in the $(n+1{)}^{\text{st}}$ column is contained in a single symmetrical cycle with respect to it and covered by the pieces of $T$ in one of the two ways described above.

Proof. Consider the cover symmetric to $T$ with respect to column $n+1$ and imagine the two covers overlapping, one on top of the other. Each square on the board is covered by two tiles so that the entire board is divided into several cycles. Since everything is symmetric about column $n+1$, particularly if a cycle is formed by the overlapping, its symmetric too, whereby the cycles that contain cells in column $n+1$ must coincide with their symmetric ones. In other words, they must be symmetrical. $\square$

Let's take a cell in column $n+1$ and look at the cycle whose existence is guaranteed by the above lemma. The cycle must be symmetrical with respect to column $n+1$ from which it follows that it must intersect it in exactly two cells, furthermore, these must be of different colors. Otherwise, the cycle would encircle an odd number of cells, which is impossible (since these can be covered by dominoes).

Let us call special squares of a covering $T$ those black squares of the column $n+1$ that share a domino with a square of the column. It follows from the above that the cycles corresponding to special squares are all disjoint.

Now, given a covering $T$, we are going to replace it by another $T^{\ast }$ as follows: for each special square of $T$ let's take the cycle guaranteed by the lemma and let's change the $T$ tiles that cover it for their inverses. Since the cycles in question are all disjoint, then they do not interfere with each other and the covering $T^{\ast }$ is well defined, which we will call the normal form of $T$.

The covering $T^{\ast }$ cannot have horizontal pieces between a white square of the $n^{\text{th}}$ column and a black one of the $(n+1{)}^{\text{st}}$ (because when we went from $T$ to $T^{\ast }$, what we did was turning over all those $T$ pieces). But then you can't have any horizontal dominoes between a black square on the $n^{\text{th}}$ column and a white one on the $(n+1{)}^{\text{st}}$ column, as this would unbalance the number of white and black squares on the left side of the board. In conclusion, all the squares of the central column must be covered by a $T^{\ast }$ domino tile that joins it to a square in the $(n+2{)}^{\text{nd}}$ column.

We have then proved that the normal form $T^{\ast }$ of $T$ breaks into a $2m\times n$ board cover, $2m$ horizontal tiles covering the $n+1$ and $n+2$ columns and a $2m\times (n-1)$ board cover. It follows from the above that there are $N(2m,n)N(2m,n-1)$ possible normal forms.

How to recover $T$ from its normal $T^{\ast }$ form? To do this, it is enough to consider the cycles of $T^{\ast }$ that contain the special squares of $T$ that guarantees the lemma and "invert them". That is, we must know not only $T^{\ast }$ but also the subset of special cells of $T$. There are $m$ black cells in the middle column, giving $2^m$ possible sets of special cells. That is, each normal form $T^{\ast }$ comes from two possible coverages. In short, with all of the above it is obtained that $N^{\ast }(2m,2n+1)=2^{m}N(2m,n)N(2m,n-1)$ as we wanted to show.