We say that a polygon is rectangular when all of its angles are $90^\circ$ or $270^\circ$. Is it true that each rectangular polygon, which sides are with length equal to odd numbers only, can't be covered with 2x1 domino tiles?
Problem
Source: VIII International Festival of Young Mathematicians Sozopol 2017, Theme for 10-12 grade
Tags: combinatorics, dominoes, Tiling
29.08.2019 13:36
See Theorem 2.1 in this paper: http://www.cccg.ca/proceedings/1999/c32.pdf
30.08.2019 22:06
The same authors had a more recent paper, see here: http://people.scs.carleton.ca/~kranakis/Papers/Domjou.pdf . They prove the original problem again, but in a nicer manner. Another interesting generalizations are also given. The method used, is an instructive one and could be used in another such tiling problems. I gave a more detailed review in my blog. Following that paper, I will provide here a short proof of the OP. Suppose our rectangular polygon $ P$ can be tiled with $ 1\times 2$ dominoes. We construct a graph $ G$, which vertices are the nodes of the tiling (where the corners of $ 1\times 2$ tiles are placed). Two vertices of $ G$ are joined whenever they lie along the long side (with length $ 2$) of some $ 1\times 2$ tile. In case they lie along the long sides of two clinging together dominoes, that edge has multiplicity $ 2$. Shortly speaking, the edges of $ G$ are the long sides of all dominoes. Now, the key observation. Every corner of $ P$ (as a vertex in $ G$) has degree $ 1$ and all the other vertices of $ G$ have even degrees (either $ 2$ or $ 4$, counted with their multiplicity). Thus, starting an Eulerian path from any corner of $ P$ (corresponding to $ v\in G$) , it will not terminate until reaching another corner of $ P$, corresponding to $ v'\in G$. We will prove there exists a corner $ v$, such that both $ v$ and $ v'$ lie on the same side of $ P$. Indeed, if it doesn't hold for some $ v,v'$ there will exist another vertex $ v_1\neq v,v'$ somewhere on the contour of the polygon $ P$, between $ v$ and $ v'$. We construct another Eulerian path $ v_1\,v'_1$ starting from $ v_1$. If that path crosses the path $ v\,v'$ we switch to the first one and may assume $ v_1'=v'$. Thus, the distance, along the contour of $P$, between $ v_1$ and $ v_1'$ is shorter than the same kind of distance between $ v$ and $ v'$ (Here, it is crucial $ P$ does not have holes). Keeping shortening that distance, we finally reach a vertex $ v_i$ such that both $ v_i$ and $ v'_i$ lie on the same side of $ P$. But then, the length of that side of the polygon would be an even number, since all the segments of the path, connecting its ends, are of even lengths and parallel to the axes. A contradiction.