Shortlist 2014, C4

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Hungary

Concepts : Coloriages et pavages · Invariants et monovariants

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 32 (page 33 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

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

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

Indices : les idées clés

• Coloriage (solution 1) : un coloriage bien choisi fait couvrir à tout S-tétromino un nombre pair de cases noires, et à tout Z-tétromino un nombre impair.
• Invariant de parité : \(P\), pavable par des S seuls, contient un nombre pair de cases noires, donc le nombre de Z est pair.
• Poids (solution 2) : on écrit \(3^i (-3)^j\) dans la case \((i, j)\) ; les sommes couvertes par les S sont divisibles par \(32\), celles des Z valent \(0\) ou \(16\) fois un nombre impair.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (deux solutions et trois remarques).

Solution 1

On peut supposer que le polygone \(P\) est une réunion de cases d'un échiquier infini. Colorions les cases de l'échiquier en deux couleurs comme sur la figure.

Quel que soit le pavage de \(P\), tout S-tétromino couvre un nombre pair de cases noires, tandis que tout Z-tétromino en couvre un nombre impair. Comme \(P\) peut être pavé uniquement par des S-tétrominos, il contient un nombre pair de cases noires. Mais si des S-tétrominos et des Z-tétrominos couvrent un nombre pair de cases noires, le nombre de Z-tétrominos est pair. \(\blacksquare\)

Remarque. Une autre approche utilise les deux coloriages suivants, peut-être plus naturels.

Soient \(s_1\) et \(s_2\) les nombres de S-tétrominos du premier et du second type (comme sur la figure de l'énoncé) utilisés dans un pavage de \(P\), et de même \(z_1\) et \(z_2\) pour les Z-tétrominos. Le premier coloriage montre que \(s_1 + z_2\) est invariant modulo \(2\), le second que \(s_1 + z_1\) l'est. En additionnant, \(z_1 + z_2\) est invariant modulo \(2\), ce qu'il fallait démontrer. En fait, la somme des deux coloriages (blanc valant \(0\) et noir \(1\), addition modulo \(2\)) est le coloriage de la solution.

Solution 2

Repérons les cases de l'échiquier infini par des coordonnées, de sorte que les cases de \(P\) aient des coordonnées positives ou nulles, la première coordonnée augmentant vers la droite et la seconde vers le haut. Écrivons l'entier \(3^i \cdot (-3)^j\) dans la case de coordonnées \((i, j)\), comme sur la figure.

La somme des nombres de quatre cases que peut couvrir un S-tétromino est soit de la forme

\[3^i \cdot (-3)^j \cdot \big(1 + 3 + 3 \cdot (-3) + 3^2 \cdot (-3)\big) = -32 \cdot 3^i \cdot (-3)^j\]

(pour le premier type de S-tétromino), soit de la forme

\[3^i \cdot (-3)^j \cdot \big(3 + 3 \cdot (-3) + (-3) + (-3)^2\big) = 0,\]

donc toujours divisible par \(32\). Ainsi la somme des nombres écrits dans les cases de \(P\), et donc aussi la somme des nombres couverts par les Z-tétrominos dans le second pavage, est divisible par \(32\). Or la somme couverte par un Z-tétromino est soit de la forme

\[3^i \cdot (-3)^j \cdot \big(3 + 3^2 + (-3) + 3 \cdot (-3)\big) = 0\]

(pour le premier type de Z-tétromino), soit de la forme

\[3^i \cdot (-3)^j \cdot \big(1 + (-3) + 3 \cdot (-3) + 3 \cdot (-3)^2\big) = 16 \cdot 3^i \cdot (-3)^j,\]

c'est-à-dire \(16\) fois un nombre impair. Pour obtenir un total divisible par \(32\), il faut donc utiliser un nombre pair de Z-tétrominos du second type. En tournant tout de \(90^\circ\), on voit que le nombre de Z-tétrominos du premier type est pair lui aussi. On a donc même prouvé un peu plus que nécessaire. \(\blacksquare\)

Remarques

Remarque 1. Dans la seconde solution, on peut remplacer \(3\) et \(-3\) par d'autres valeurs. Par exemple, pour tout entier \(a > 0\) tel que \(a \equiv 3 \pmod 4\), on peut écrire \(a^i \cdot (-a)^j\) dans la case \((i, j)\) et appliquer le même argument.

Remarque 2. Comme le montre la seconde solution, on a même un résultat plus fort : dans un pavage de \(P\) par des S- et des Z-tétrominos, la parité du nombre de pièces de chacun des quatre types est un invariant de \(P\). C'est encore vrai s'il n'existe aucun pavage de \(P\) par des S-tétrominos seuls.