Coloriages et pavages

Domaine : Combinatoire · Niveau : débutant · Prérequis : Invariants et monovariants

L'idée

Pour montrer qu'un pavage est impossible, ou qu'un objet ne peut pas atteindre une position, on colorie les cases (ou les points) de façon astucieuse. Chaque pièce, ou chaque mouvement, couvre alors un nombre de cases de chaque couleur que l'on contrôle. Si ce décompte est incompatible avec le nombre total de cases de chaque couleur, c'est impossible.

Un coloriage est un invariant déguisé : on compte, couleur par couleur, ce que chaque pièce apporte.

Le coloriage sert aussi dans l'autre sens, pour construire : colorier les cases selon une règle simple fournit souvent la stratégie ou la configuration cherchée (par exemple « on ne joue que sur les cases blanches »).

Toute la difficulté est de choisir le coloriage : le damier est le premier réflexe, mais il ne suffit pas toujours.

Exemple résolu

Problème

Peut-on paver un échiquier \(10 \times 10\) avec des pièces droites \(1 \times 4\) ?

Étape 1 : le damier ne suffit pas. Le nombre de cases, \(100\), est divisible par \(4\). Avec le damier, chaque pièce couvre \(2\) cases blanches et \(2\) noires, et il y a \(50\) cases de chaque couleur : aucune contradiction.

Étape 2 : adapter le coloriage à la pièce. Une pièce \(1 \times 4\) couvre \(4\) cases consécutives d'une ligne ou d'une colonne. On numérote les lignes et les colonnes de \(0\) à \(9\) et l'on donne à la case \((i, j)\) la couleur \((i + j) \bmod 4\). Quatre cases consécutives, horizontales ou verticales, ont alors les quatre couleurs \(0, 1, 2, 3\), chacune une fois.

Étape 3 : compter. Un pavage utiliserait \(25\) pièces, donc couvrirait exactement \(25\) cases de chaque couleur. Mais on compte directement : la couleur \(1\) apparaît sur \(26\) cases et la couleur \(3\) sur \(24\) (la couleur \((i + j) \bmod 4\) dépend de la diagonale, et les diagonales n'ont pas toutes la même longueur).

Conclusion. Les couleurs ne sont pas équilibrées : le pavage est impossible.

Le réflexe : une pièce de longueur \(k\) appelle un coloriage modulo \(k\), construit pour que chaque position de la pièce couvre la même combinaison de couleurs.

Comment le reconnaître

• On demande si l'on peut paver une figure avec des pièces données, et la réponse attendue est non.
• Une pièce se déplace sur une grille (cavalier, roi, lapin) et l'on demande si elle peut atteindre une case.
• Des opérations modifient des cases d'une grille selon un motif fixe (retourner des pièces dans un carré \(2 \times 2\), une ligne, une diagonale).
• On cherche une stratégie ou une construction sur une grille : un coloriage régulier la suggère souvent.
• Des contraintes « deux objets voisins doivent être différents » : c'est un coloriage de graphe.

Coloriages classiques

Situation	Coloriage à essayer
Dominos \(1 \times 2\)	Le damier
Pièces droites \(1 \times k\)	\((i + j) \bmod k\), ou les colonnes modulo \(k\)
Pièces en L ou en T	Le damier, ou des bandes (colonnes alternées)
Sauts de cavalier	Le damier : chaque saut change de couleur
Opérations sur une grille selon un motif	Les coordonnées modulo \(2\) ou \(3\)
Contraintes entre voisins	Coloriage de graphe ; deux couleurs suffisent s'il n'y a pas de cycle impair

Exercices d'échauffement

1. Un cavalier part d'une case d'un échiquier et y revient après \(n\) sauts. Montrer que \(n\) est pair.
2. Peut-on paver un échiquier \(6 \times 6\) avec \(9\) pièces en forme de T (quatre cases) ? Indication : le damier, et la parité du nombre de pièces.
3. Montrer qu'un rectangle \(m \times n\) peut être pavé par des dominos si et seulement si \(mn\) est pair.
4. On colorie chaque point du plan en rouge ou en bleu. Montrer qu'il existe deux points de même couleur à distance exactement \(1\).
5. Des droites découpent le plan en régions. Montrer qu'on peut colorier les régions en deux couleurs de sorte que deux régions ayant un côté commun soient de couleurs différentes. Indication : récurrence sur le nombre de droites.

Coloriages dans la shortlist

• 2017 C1 : en coloriant en damier les cases unités, les quatre coins du rectangle ont la même couleur.
• 2018 C2 : deux cavaliers sur des cases de même couleur ne s'attaquent jamais, ce qui donne une stratégie.
• 2023 C1 : on étiquette la case \((i, j)\) par \(i + j - 2\) modulo \(3\), et chaque coup retourne exactement une pièce de chaque étiquette.
• 2022 C3 : on colorie les cases dont une coordonnée est multiple de \(3\) ; tout carré \(3 \times 3\) en contient exactement \(5\).
• 2024 C8 : un argument de parité sur les centres des opérations, pour un pavage par des L-triominos.

Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 113 à 117 (démonstrations par coloriage : tétraminos, carrelages, fourmis sur un échiquier), p. 229 à 235 (coloration des graphes), p. 257 (le problème des quatre couleurs) ; tome 3, p. 337 (le coloriage parmi les invariants classiques).

Problèmes de la shortlist

24 problèmes · difficulté moyenne : ★★★★★ (3,1) · dont 3 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 4 · 2 ★ : 6 · 3 ★ : 3 · 4 ★ : 5 · 5 ★ : 6

Problème	Difficulté	Concepts
2023 C1	★☆☆☆☆	Invariants et monovariants
2021 C2	★☆☆☆☆	Principe des tiroirs · Récurrence et constructions récursives
2018 C2 · OIM P4	★☆☆☆☆	Graphes : degrés, chemins, arbres · Jeux et stratégies gagnantes
2017 C1	★☆☆☆☆	Invariants et monovariants
2022 C3	★★☆☆☆	Jeux et stratégies gagnantes · Principe des tiroirs
2021 C3 · OIM P5	★★☆☆☆	Invariants et monovariants
2014 C4	★★☆☆☆	Invariants et monovariants
2013 C3	★★☆☆☆	Graphes : degrés, chemins, arbres · Récurrence et constructions récursives
2010 C3	★★☆☆☆	Principe des tiroirs
2007 C2	★★☆☆☆	Principe extrémal
2012 C5	★★★☆☆	Graphes : degrés, chemins, arbres · Double comptage
2009 C4	★★★☆☆	Convexité, inégalité de Jensen, lissage · Double comptage
2007 C5	★★★☆☆	Divisibilité, PGCD et algorithme d'Euclide
2023 C6	★★★★☆	Récurrence et constructions récursives
2021 C6	★★★★☆	Jeux et stratégies gagnantes
2021 C7	★★★★☆	Double comptage
2009 C6	★★★★☆	Récurrence et constructions récursives
2006 C6	★★★★☆	Récurrence et constructions récursives · Principe extrémal
2025 C8 · OIM P6	★★★★★	Principe extrémal · Double comptage · AM-GM et moyennes · Graphes : degrés, chemins, arbres
2024 C8	★★★★★	Récurrence et constructions récursives · Graphes : degrés, chemins, arbres · Principe extrémal
2018 C7	★★★★★	Graphes : degrés, chemins, arbres · Double comptage
2016 C8	★★★★★	Graphes : degrés, chemins, arbres · Principe des tiroirs
2015 C7	★★★★★	Graphes : degrés, chemins, arbres · Principe extrémal · Récurrence et constructions récursives
2011 C7	★★★★★	Double comptage · Récurrence et constructions récursives