Domino tilings in a specific figure, math olympiad problem

367 Views Asked by At

There was a reddit post a month ago in learnmath about this question: "Prove that the number of possible domino tilings in this figure is a square number" tiling question

The last paragraph was the wrong try by this person to solve the problem (wrong because they didn't prove that you can always separate the shape in two symmetric shapes without cutting any domino piece in all the possibilities).

I'm just curious about the answer, I have thought about it from time to time and I have searched properties about domino tilings but didn't find anything that would help here. I think the question is from a previous math olympiad test, I don't know what year or even what country.

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is pretty close to correct, but you just need a bit of extra justification about how the middle section can be covered.

Give the whole board a checkerboard colouring. Now consider the left 5x5 area. Every domino covers two squares, one square of each colour. When covering the 5x5 by dominoes some will have to jut out into the middle section, and the colouring shows it can only be done in one way - one domino extending out in the middle row.

The same holds true for the other side. This leaves four uncovered squares in the middle section which must be covered by a horizontal domino at the top and the bottom. So the middle section can be tiled in only one way, symmetrically, and the result follows as before.