Corrigé Centrale 2025 Informatique MPI — Partie B, I (pavages) (Q19 à Q21) : Couvrir un terrain de voitures : parité et coloration

Les réponses ont été vérifiées par le programme de couplage maximum de Q29 (et par l'algorithme élémentaire du livre) : on obtient respectivement $17$ voitures au plus pour les $35$ cases de Q19, $16$ pour les $34$ cases et $18$ pour les $38$ cases de Q20, $2$ pour les $6$ cases de Q21, et $7$ (couverture complète) pour la figure 4.

Q19. Chaque voiture couvre exactement $2$ cases et deux voitures ne se chevauchent pas : $k$ voitures couvrent exactement $2k$ cases. Une couverture complète d'un terrain de taille $t$ impose donc $t=2k$, nombre pair. Le terrain proposé est la grille $6\times 6$ privée d'une case d'angle : $35$ cases, nombre impair ; il ne peut pas être couvert. Condition nécessaire : la taille du terrain est paire.

Q20. Terrain gauche. Il est formé de la grille $6\times 6$ privée de deux coins opposés : $34$ cases, nombre pair, la condition de Q19 ne suffit donc pas à conclure. Colorions en échiquier : la case $(i,j)$ est grise si $i+j$ est pair. Deux cases adjacentes diffèrent d'une unité sur une seule coordonnée, donc ont des couleurs différentes : toute voiture couvre une case grise et une case blanche. Une couverture complète par $k$ voitures couvrirait $k$ cases grises et $k$ cases blanches. Or la grille $6\times 6$ a $18$ cases de chaque couleur, et les deux coins retirés, $(0,0)$ et $(5,5)$, sont gris ($0+0$ et $5+5$ pairs) : il reste $16$ cases grises et $18$ blanches. Impossible.