Competition problem — Combinatorics

Library / /27 of 35

Combinatorics Difficulty 6.3 National olympiad Prove it Belarus

Construct a tetramino by attaching two $2 \times 1$ dominoes along their sides such that the midpoint of the longer side of one domino is a corner of other domino. This construction yields two kinds of the tetraminoes with opposite orientations. Let us call them S- and Z-tetraminoes, respectively.

S-tetraminoes Z-tetraminoes

Assume that a lattice polygon $P$ can be tiled with S-tetraminoes.
Prove that no matter how we tile $P$ using only S- and Z-tetraminoes, we always use even number of Z-tetraminoes.

Solution

Consider the following arrangement of numbers in the cells of the lattice (see Fig.1).

It is evident that the sum of the numbers in any S-tetramino is always zero, so the sum of the numbers in all cells of the polygon $P$ from the problem condition equals zero.

Fig. 2

Fig. 3

Now we can see that the sum of the numbers in any vertical Z-tetramino (see Fig. 2) is always zero, while the sum of the numbers in any horizontal Z-tetramino (see Fig. 3) is $2$ or $-2$ . Therefore in any tiling of $P$ with tetraminoes the number of horizontal Z-tetraminoes should be even (the numbers of tetraminoes with sum $2$ equals that of with the sum $-2$ ). In the same way we can conclude that the number of vertical Z-tetraminoes is also even, which finishes the proof.

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 and solution reproduced as published; topic and difficulty added by this site.