, 2014

Combinatorics Difficulty 8.4 Shortlist Prove it Germany

Problem:

From two $2 \times 1$ dominoes one can construct a tetromino by placing the two dominoes together along their longer sides in such a way that the midpoint of the longer side of one domino is a vertex of the other domino. This yields two types of tetrominoes that differ with respect to their orientation, which we shall call the $S$ -tetromino and the $Z$ -tetromino, respectively.

$S$ -tetrominoes:

$Z$ -tetrominoes:

A lattice polygon $P$ is a simply connected region whose boundary lines lie only on grid lines of the planar integer coordinate grid. A tiling of $P$ is a complete and non-overlapping covering of $P$ with pieces that also do not lie partially outside of $P$ .

We now assume that a lattice polygon $P$ can be tiled using only $S$ -tetrominoes. Prove that: if a tiling of $P$ with $S$ - and $Z$ -tetrominoes is also possible, then the number of $Z$ -tetrominoes used in it is always even.

Solution

Solution:

We may assume that $P$ consists of a portion of the unit squares of the integer coordinate grid, colored as shown in the figure. Under this coloring, every $S$ -tetromino covers an even number of black squares and every $Z$ -tetromino covers an odd number of them. Since $P$ can be completely tiled with $S$ -tetrominoes, it contains an even number of black squares. Thus, if a tiling with $S$ - and $Z$ -tetrominoes is possible, this even number also requires an even number of $Z$ -tetrominoes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty) added by this project.