Dominoroto-toto

Question

Consider a domino tiling of a plane rectangle of size $n \times m$. (Obviously, at least one of $m$ and $n$ has to be even for that to be possible.) I personally hate those because they tend to look terribly untidy. In fact, whenever I see one I can't help rearranging it into a nice regular pattern where either all dominos are horizontal or all dominos are vertical.

But currently, with social distancing rules in place, I'm not allowed to handle more than two dominos at the same time. All others must stay put meanwhile. This means the only change I can make is finding a $2 \times 2$ square which happens to have two dominos in it and rotate them by 90$°$.

My question (and I don't know the answer): using only rotations of the kind I have described can I always bring all dominos to the same orientation?

Example

╔═══╦═╦═══╦═╗
╠═╦═╣ ╠═══╣ ║
║ ║ ╠═╩═╦═╩═╣
╚═╩═╩═══╩═══╝

╔═══╦═╦═╦═╦═╗
╠═╦═╣ ║ ║ ║ ║
║ ║ ╠═╩═╬═╩═╣
╚═╩═╩═══╩═══╝
╔═══╦═╦═╦═══╗
╠═╦═╣ ║ ╠═══╣
║ ║ ╠═╩═╬═══╣
╚═╩═╩═══╩═══╝
╔═══╦═╦═╦═══╗
╠═══╣ ║ ╠═══╣
╠═══╬═╩═╬═══╣
╚═══╩═══╩═══╝

╔═══╦═══╦═══╗
╠═══╬═══╬═══╣
╠═══╬═══╬═══╣
╚═══╩═══╩═══╝

Answer 1

Answer

Without loss of generality assume the board has 7 rows and 8 columns. Clearly we want all dominoes to be horizontal. Let us say that a state P is optimal if it is not possible to reduce the number of vertical dominoes with legal moves. Clearly the desired end state has zero vertical dominoes and is hence optimal. Suppose P is optimal but has at least one vertical domino. A simple parity argument shows there must be two vertical dominoes covering the same two rows and (this is most important) separated by an even number of columns. Let us call these dominoes a “vertical pair”.

Now we ask ourselves how to cover the A-B squares with dominoes? There are 4 options

(1) All dominoes are horizontal

(2) There is at least one A-B domino

(3) There are two vertical A-x dominoes separated by an even number of columns, where x is any square other than A or B.

(4) There are two vertical B-x dominoes separated by an even number of columns, where x is any square other than A or B.

In the first case we can change the red dominoes to horizontal, contradicting the optimality of P. In all other cases we get a new vertical pair separated by a smaller number of even columns. In this case we simply repeat the same argument, forcing the same contradiction. Therefore the only optimal state has all horizontal dominoes. QED.

Answer 2

First, let us define some things:

• For simplicity, for partial boards presented (with ...), let's consider that the width is equals to or larger than the height. If not, you can just rotate everything 90° to get a board that is like this.
• Unsolvable board (UB) - One that no matter what you rotates, it is impossible to have all the dominoes with the same orientation.
• Smallest unsolvable dimension (SUD) - The smallest number possible as the dimension of an UB.
• Minimal unsolvable board (MUB) - An UB that has one of its dimension sized the SUD and the other dimension as smallest as possible for it being an UB.
• Impossible board (IB) - A board that can't be filled with dominoes. Like one that has an odd number of tiles.

Lemma 1. An UB exists if, and only if, a MUB exists.

If there is an UB (or a lot of them), there is at least one that is also a MUB. Trivially, if there is a MUB, so there is some UB because every MUB is also an UB.

This also means that if no MUB exist, so no UB exist either. If no UB exist, there can't be a MUB also.

Lemma 2. A solvable board that have both dimensions even can be solved with either orientation.

Proof: Solve the board with any orientation. Split it into many $2 \times 2$ subblocks and rotate all of them. The result is a board solved to the other orientation.

Lemma 3. A solvable board that have an odd dimension must be solved with the dominoes oriented along the other dimension.

Proof: By being odd, you can't fill it with dominoes that are even-sized along this dimension.

Lemma 4. A MUB can't be splitted in two rectangular subboards along either dimension.

Let's suppose we have a MUB that is splittable in subboards like this:

╔═══...═══╗ ╔═...═╦═...═╗
║         ║ ║     ║     ║
...     ... ║     ║     ║
║         ║ ║     ║     ║
╠═══...═══╣ ...  ...  ...
║         ║ ║     ║     ║
...     ... ║     ║     ║
║         ║ ║     ║     ║
╚═══...═══╝ ╚═...═╩═...═╝

If one of the subboards is unsolvable, then the big board was not a MUB. If any subboard is an IB, so is the big board, so it is not a MUB either. So, both subboards must be solvable.

However, if both subboards are solvable, then if solved in the same orientation, the great board would also be solvable, hence not a MUB.

So, we have that the solvable subboards must be solvable in different orientations. Considering lemma 2, one of them must have $odd \times even$ and the other $even \times odd$ dimensions. There is no way to divide the big board to have this result because the length in which it is divided can't be odd and even at the same time.

The conclusion is that a MUB can't be divided in two rectangular subboards in any way. This lead us to the following lemma:

Lemma 5. A MUB necessarily features for every pair of neighboring rows and every pair of neighboring columns, at least one domino spanning such a pair.

Because if it isn't, we will violate lemma 4.

In fact, we will not use this lemma. But I will keep it here anyway because I think it is beautiful.

Lemma 6. With one dimension sized 2, it is always solvable.

Proof: Let's start filling the top-left corner of the MUB with a SUD = 2. The only two possibilities of starting are those:

╔═══╦═    ╔═╦═   
╠═══╣ ... ║ ║ ...
╚═══╩═    ╚═╩═   

By invoking lemma 4, those aren't MUBs. By invoking lemma 1, if there isn't a MUB, so there is not UB also. So, with dimension 2, it is always solvable.

Lemma 7. With one dimension sized 3, it is always solvable.

Proof: Let's start filling the top-left corner of a MUB with one dimension sized 3. The only possibilities are those:

╔═══╦═    ╔═╦═╦═    ╔═══╦═    ╔═╦═══╦═══    ╔═══╦═══╦═
╠═══╣ ... ║ ║ ║ ... ╠═╦═╣ ... ║ ╠═══╣   ... ╠═╦═╩═╦═╝ ...
╠═══╣     ╠═╩═╣     ║ ║ ║     ╠═╩═╦═╩═╗     ║ ╠═══╣
╚═══╩═    ╚═══╩═    ╚═╩═╩═    ╚═══╩═══╩═    ╚═╩═══╩═══
  A         B         C           D             E

Considering lemma 4, $A$, $B$ and $C$ aren't MUBs. In $D$ and $E$, with a single rotation, we will also violate that lemma. So, this is no way unsolvable.

Hence, there is no MUB with a dimension sized 3, so $SUD > 3$.

Lemma 8. With one dimension sized 4, it is always solvable.

Filling the left side of a MUB:

╔═╦═    ╔═══╦═    ╔═╦═╦═    ╔═══╦═    ╔═╦═══╦═    ╔═══╦═══    ╔═══╦═    ╔═══╦═══
║ ║     ╠═══╣     ║ ║ ║     ╠═══╣     ║ ╠═══╣     ╠═══╣       ╠═╦═╣     ╠═╦═╩═╗
╠═╣ ... ╠═══╣ ... ╠═╩═╣ ... ╠═╦═╣ ... ╠═╩═╦═╝ ... ╠═╦═╩═╗ ... ║ ║ ║ ... ║ ╠═══╣ ...
║ ║     ╠═══╣     ╠═══╣     ║ ║ ║     ╠═══╣       ║ ╠═══╣     ╠═╩═╣     ╠═╩═╦═╝  
╚═╩═    ╚═══╩═    ╚═══╩═    ╚═╩═╩═    ╚═══╩═══    ╚═╩═══╩═    ╚═══╩═    ╚═══╩═══
  A       B         C         D         E           F           G         H

Well, $A$, $B$, $C$, $D$ and $G$ violates lemma 4 (we can split the first two columns off the rest of the board), so they aren't MUBs.

For $E$, $F$ and $H$, we can rotate the two horizontally-oriented dominoes on the right to the vertically-oriented. Thus, once again violating lemma 4.

Lemma 9. If there is no two neighboring dominoes forming a $4 \times 1$ or $1 \times 4$ area alongside any of the four borders, it is not a MUB.

In fact, lemmas 6, 7 and 8 are here just for the show for it being easier to understand what is going on. We could just proceed from lemma 4 directly to this lemma instead.

Let's try to fill the left side of an arbitrarily-lengthed side of the board (here it is 7):

╔═══╦═
╠═══╣
╠═╦═╝
║ ║  
╠═╩═╗ ...
╠═╦═╝
║ ║  
╚═╩═══

If we fill the gaps with vertically-oriented dominoes, we will violate lemma 4. Putting two horizontally-oriented dominoes in each gap, we will be able to rotate each of them, also leading to a violation of lemma 4.

So, any MUB must have at least two neighboring dominoes forming a $4 \times 1$ block. Since this is equally valid for all the borders, all the borders must follow this rule in order to a MUB be constructed.

Lemma 10. If there is no three neighboring dominoes forming a $6 \times 1$ or $1 \times 6$ area alongside any of the four borders, it is not a MUB.

From lemma 9, let's try to fill the left side of a MUB with a $4 \times 1$ block:

╔═══╦═
╠═══╣
╠═╦═╝
║ ║  
╠═╣   ...
║ ║  
╠═╩═╗
╚═══╩═

The only way to fill the gap without falling to the lemma 4 is starting with this:

╔═══╦═       ╔═══╦══
╠═══╣        ╠═══╣
╠═╦═╝        ╠═╦═╩═╗
║ ╠═╗        ║ ╠═╦═╝
╠═╣ ║ ... -> ╠═╣ ║   ...
║ ╠═╝        ║ ╠═╩═╗
╠═╩═╗        ╠═╩═╦═╝
╚═══╩═       ╚═══╩══

We can then proceed with either of this:

╔═══╦══     ╔═══╦════
╠═══╣       ╠═══╣
╠═╦═╩═╗     ╠═╦═╩═╗
║ ╠═╦═╣     ║ ╠═╦═╩═╗ 
╠═╣ ║ ║ ... ╠═╣ ╠═══╣ ...
║ ╠═╩═╣     ║ ╠═╩═╦═╝
╠═╩═╦═╝     ╠═╩═╦═╝
╚═══╩══     ╚═══╩════
   A           B

However, $B$ can be rotated into $A$. From $A$, we proceed with those rotations:

╔═══╦══        ╔═══╦══        ╔═══╦══
╠═══╣          ╠═══╣          ╠═══╣  
╠═╦═╩═╗        ╠═╦═╩═╗        ╠═╦═╬═╗
║ ╠═╦═╣        ║ ╠═══╣        ║ ║ ║ ║
╠═╣ ║ ║ ... -> ╠═╬═══╣ ... -> ╠═╬═╬═╣
║ ╠═╩═╣        ║ ╠═══╣        ║ ║ ║ ║
╠═╩═╦═╝        ╠═╩═╦═╝        ╠═╩═╬═╝
╚═══╩══        ╚═══╩══        ╚═══╩══

And we've violated lemma 4 again because we can split the first two columns off the rest of the board.

So, a $4 \times 1$ block isn't enough. Hence, we will need at least a $6 \times 1$ block.

Lemma 11. A triangular "staircase" corner can't be filled.

Let's look to these areas:

╔═╗     ╔═╗     
║ ╚═╗   ║ ╚═╗   
║   ╚═╗ ║   ╚═╗ 
╚═════╝ ║     ╚═╗
        ╚═══════╝

Even if the areas have an even number of tiles, they are impossible to fill. The reason is because if we fill the diagonal with vertically-oriented dominoes, the bottom-most one would not be possible to be filled. If we use horizontally-oriented dominoes, we won't be able to fill the topmost. Trying to use some combination of vertically and horizontally oriented dominoes will leave at least one gap in the middle. So, this is impossible.

This can also be easily proved with a checker board coloring. The number of black and white squares won't match (there would be a difference of 2) and each domino must necessarily fill one black and one white square.

Lemma 12. It is always solvable.

Let's do an induction on lemmas 9 and 10.

First, let's get a left side filled with a lot of vertical blocks without violating lemma 4:

╔═══╦═
╠═╦═╝
║ ║  
╠═╣
║ ║
╠═╣
║ ║   ...
╠═╣
║ ║
╠═╣
║ ║  
╠═╩═╗
╚═══╩═

Filling it in any way that follows the lines dividing the vertically-oriented block will lead us to eventually violate lemma 4. So, in order to avoid that, we will eventually build a pyramid:

╔═══╦═════════
╠═╦═╩═╗
║ ╠═╦═╩═╗
╠═╣ ╠═╦═╩═╗
║ ╠═╣ ╠═╦═╩═╗
╠═╣ ╠═╣ ╠═╦═╝
║ ╠═╣ ╠═╣ ║   ...
╠═╣ ╠═╣ ╠═╩═╗
║ ╠═╣ ╠═╩═╦═╝
╠═╣ ╠═╩═╦═╝
║ ╠═╩═╦═╝
╠═╩═╦═╝
╚═══╩═════════

Filling the top of it in either way:

╔═══╦═════════    ╔═══╦═══════════
╠═╦═╩═╗           ╠═╦═╩═╗
║ ╠═╦═╩═╗         ║ ╠═╦═╩═╗
╠═╣ ╠═╦═╩═╗       ╠═╣ ╠═╦═╩═╗
║ ╠═╣ ╠═╦═╩═╗     ║ ╠═╣ ╠═╦═╩═╗
╠═╣ ╠═╣ ╠═╦═╣     ╠═╣ ╠═╣ ╠═╦═╩═╗
║ ╠═╣ ╠═╣ ║ ║ ... ║ ╠═╣ ╠═╣ ╠═══╣ ...
╠═╣ ╠═╣ ╠═╩═╣     ╠═╣ ╠═╣ ╠═╩═╦═╝
║ ╠═╣ ╠═╩═╦═╝     ║ ╠═╣ ╠═╩═╦═╝
╠═╣ ╠═╩═╦═╝       ╠═╣ ╠═╩═╦═╝
║ ╠═╩═╦═╝         ║ ╠═╩═╦═╝
╠═╩═╦═╝           ╠═╩═╦═╝
╚═══╩═════════    ╚═══╩═══════════
       A                   B

Once again, $B$ can be rotated into $A$. So we proceed from $A$ to rotate the horizontally-oriented dominoes into the base of the pyramid:

╔═══╦═════════    ╔═══╦═════════    ╔═══╦═════════    ╔═══╦═════════
╠═╦═╩═╗           ╠═╦═╩═╗           ╠═╦═╩═╗           ╠═╦═╩═╗       
║ ╠═╦═╩═╗         ║ ╠═╦═╩═╗         ║ ╠═╦═╩═╗         ║ ╠═╦═╩═╗     
╠═╣ ╠═╦═╩═╗       ╠═╣ ╠═╦═╩═╗       ╠═╣ ╠═╦═╩═╗       ╠═╣ ╠═╦═╬═╗   
║ ╠═╣ ╠═╦═╩═╗     ║ ╠═╣ ╠═╦═╬═╗     ║ ╠═╣ ╠═══╬═╗     ║ ╠═╣ ║ ║ ╠═╗ 
╠═╣ ╠═╣ ╠═══╣     ╠═╣ ╠═╣ ║ ║ ║     ╠═╣ ╠═╬═══╣ ║     ╠═╣ ╠═╬═╬═╣ ║ 
║ ╠═╣ ╠═╬═══╣ ... ║ ╠═╣ ╠═╬═╬═╣ ... ║ ╠═╣ ╠═══╬═╣ ... ║ ╠═╣ ║ ║ ╠═╣ ...
╠═╣ ╠═╣ ╠═══╣     ╠═╣ ╠═╣ ║ ║ ║     ╠═╣ ╠═╬═══╣ ║     ╠═╣ ╠═╬═╬═╣ ║ 
║ ╠═╣ ╠═╩═╦═╝     ║ ╠═╣ ╠═╩═╬═╝     ║ ╠═╣ ╠═══╬═╝     ║ ╠═╣ ║ ║ ╠═╝ 
╠═╣ ╠═╩═╦═╝       ╠═╣ ╠═╩═╦═╝       ╠═╣ ╠═╩═╦═╝       ╠═╣ ╠═╩═╬═╝   
║ ╠═╩═╦═╝         ║ ╠═╩═╦═╝         ║ ╠═╩═╦═╝         ║ ╠═╩═╦═╝     
╠═╩═╦═╝           ╠═╩═╦═╝           ╠═╩═╦═╝           ╠═╩═╦═╝       
╚═══╩═════════    ╚═══╩═════════    ╚═══╩═════════    ╚═══╩═════════

╔═══╦═════════    ╔═══╦═════════    ╔═══╦═════════    ╔═══╦═════════
╠═╦═╩═╗           ╠═╦═╩═╗           ╠═╦═╩═╗           ╠═╦═╬═╗       
║ ╠═╦═╩═╗         ║ ╠═╦═╬═╗         ║ ╠═══╬═╗         ║ ║ ║ ╠═╗     
╠═╣ ╠═══╬═╗       ╠═╣ ║ ║ ╠═╗       ╠═╬═══╣ ╠═╗       ╠═╬═╬═╣ ╠═╗   
║ ╠═╬═══╣ ╠═╗     ║ ╠═╬═╬═╣ ╠═╗     ║ ╠═══╬═╣ ╠═╗     ║ ║ ║ ╠═╣ ╠═╗ 
╠═╣ ╠═══╬═╣ ║     ╠═╣ ║ ║ ╠═╣ ║     ╠═╬═══╣ ╠═╣ ║     ╠═╬═╬═╣ ╠═╣ ║ 
║ ╠═╬═══╣ ╠═╣ ... ║ ╠═╬═╬═╣ ╠═╣ ... ║ ╠═══╬═╣ ╠═╣ ... ║ ║ ║ ╠═╣ ╠═╣ ...
╠═╣ ╠═══╬═╣ ║     ╠═╣ ║ ║ ╠═╣ ║     ╠═╬═══╣ ╠═╣ ║     ╠═╬═╬═╣ ╠═╣ ║ 
║ ╠═╬═══╣ ╠═╝     ║ ╠═╬═╬═╣ ╠═╝     ║ ╠═══╬═╣ ╠═╝     ║ ║ ║ ╠═╣ ╠═╝ 
╠═╣ ╠═══╬═╝       ╠═╣ ║ ║ ╠═╝       ╠═╬═══╣ ╠═╝       ╠═╬═╬═╣ ╠═╝   
║ ╠═╩═╦═╝         ║ ╠═╩═╬═╝         ║ ╠═══╬═╝         ║ ║ ║ ╠═╝     
╠═╩═╦═╝           ╠═╩═╦═╝           ╠═╩═╦═╝           ╠═╩═╬═╝       
╚═══╩═════════    ╚═══╩═════════    ╚═══╩═════════    ╚═══╩═════════   

And, after a lot of rotations, lemma 4 is violated once again.

Let us go back to this:

╔═══╦═
╠═╦═╝
║ ║  
╠═╣
║ ║
╠═╣
║ ║   ...
╠═╣
║ ║
╠═╣
║ ║  
╠═╩═╗
╚═══╩═

Trying to not build a pyramid, would mean adding an horizontally-oriented domino somewhere in the middle. Something like this:

╔═══╦═
╠═╦═╝
║ ║
╠═╣
║ ║
╠═╬═══╗
║ ╠═══╝  ...
╠═╣
║ ║
╠═╣
║ ║
╠═╩═╗
╚═══╩═

But this would just result in building a smaller pyramid in the even-sized gap or to fill it up nicely leading to us closer to violating lemma 4 or any combination of that. In the odd-sized gap, we will need at least one other horizontally-oriented domino which will either leave another even-sized gap to build a pyramid or will subdivide the gap in two even-sized smaller gaps which will see the same fate.

And what if the pyramid grows to reach the other side of the board before its top?

╔═══╦═════╗
╠═╦═╩═╗   ║
║ ╠═╦═╩═╗ ║
╠═╣ ╠═╦═╩═╣
║ ╠═╣ ╠═╦═╣
╠═╣ ╠═╣ ║ ║
║ ╠═╣ ╠═╬═╣
╠═╣ ╠═╣ ║ ║
║ ╠═╣ ╠═╬═╣
╠═╣ ╠═╣ ║ ║
║ ╠═╣ ╠═╩═╣
╠═╣ ╠═╩═╦═╣
║ ╠═╩═╦═╝ ║
╠═╩═╦═╝   ║
╚═══╩═════╝

In this case, it would fail lemma 11 (the triangular staircases in the right corners). Even if you manage to dodge lemma 11 somehow, this still does not prevent the horizontally-oriented dominoes to be rotated to the base of the pyramid leading to a violation of lemma 4.

So, no $2k \times 1$ blocks along the border is enough to prevent lemma 4 be violated. Hence, it is impossible to build an UB, so there is no MUB either (lemma 1) and all the possible boards are solvable.