All-Soviet-Union Mathematical Olympiad

Solution:

a.
We say a domino bridges two columns if half the domino is in each column. We show that for $0 < n < 6$ the number of dominoes bridging columns $n$ and $n+1$ must be at least $2$ and even.

Consider first $n = 1$. There cannot be $3$ dominos entirely in column $1$, or it would be separately tiled. So there must be at least one domino bridging columns $1$ and $2$. The number must be even, because it must equal the number of squares in column $1$ (even) less twice the number of dominoes (entirely) in column $1$.

Now suppose it is true for $n < 5$ and consider column $n + 1$. There must be at least one domino bridging columns $n + 1$ and $n + 2$, or columns $1$ thru $n + 1$ would be separately tiled. The number must be even, because it must equal the number of squares in column $n + 1$ (even) less the number bridging $n$ and $n + 1$ (even) less twice the number entirely in the column.

So in total there are at least $5 \times 2 = 10$ dominos bridging columns. By the same argument there are at least another $10$ bridging rows, but there are only $18$ dominoes in total.

b.
No. For example:
1 2 3 3 1 1 2 2 1 2 1 2 2 3 3 1 3 3 1 3 1 2 4 1 1 2 2 3 1 2 4 3 1 3 3 2 2 1 2 3 3 2 1 1 4 1 2 1 3 2 3 2 4 3 3 1 1 1 3 2 1 1 2 2