Théorie > Combinatoire > Pavages
Coloriage
Voici un exemple classique de problème de pavage.
La première attitude face à un tel problème est évidemment d'essayer d'effectuer un tel pavage. On se rend cependant vite compte que cela n'est pas possible, et vient alors le moment de le prouver. Un élève n'ayant jamais rencontré de problèmes similaires sera peut-être tenté de discuter différents cas : "Si je place un pavé dans le sens horizontal dans ce coin, alors je dois en placer un autre dans ce sens...". Un tel raisonnement n'a cependant aucune chance d'aboutir dans ce cas vu le grand nombre de pavés qui doivent être placés.
Une méthode évidente pour prouver qu'un pavage est impossible est simplement de voir si l'aire d'un pavé divise l'aire de la surface totale. Ici, la surface totale est constituée de $62$ petits carrés, alors qu'un pavé permet de recouvrir $2$ petits carrés. On ne trouve donc pas dans ce cas d'absurdité, mais on sait déjà que, si un pavage existe, alors il est constitué de $\frac{62}{2} = 31$ pavés.
Une autre méthode plus prometteuse pour ce genre de problème est le coloriage. Elle consiste à colorier les différentes cases de la surface à paver de manière astucieuse, de sorte à prouver la non-existence d'un pavage. Pour notre exemple, le coloriage est en fait même suggéré par l'énoncé puisqu'un échiquier possède un coloriage naturel :
Ce coloriage peut sembler bien anodin, mais il permet en fait de résoudre directement le problème ! En effet, ce coloriage a de particulier que n'importe quel pavé $1 \times 2$ recouvre exactement un petit carré noir et un petit carré blanc. Or, on constate que la surface contient $32$ carrés blancs pour $30$ carrés noirs : il est donc clairement impossible d'effectuer un pavage correct !
Un simple coloriage permet donc de prouver très facilement qu'un pavage est impossible, alors qu'il semble difficile de conclure sans utiliser cette astuce. Le coloriage "en échiquier" est souvent performant, mais il faut parfois adapter le coloriage selon la surface et le type de pavé. Il n'est notamment pas interdit d'utiliser plus de deux couleurs, comme nous le verrons par la suite...
Problème
Est-il possible de paver (entièrement et sans recouvrement) un échiquier $8 \times 8$ dont deux coins opposés ont été retirés à l'aide de pavés de la forme $1 \times 2$ (dont les côtés doivent être parallèles aux côtés de l'échiquier) ?
La première attitude face à un tel problème est évidemment d'essayer d'effectuer un tel pavage. On se rend cependant vite compte que cela n'est pas possible, et vient alors le moment de le prouver. Un élève n'ayant jamais rencontré de problèmes similaires sera peut-être tenté de discuter différents cas : "Si je place un pavé dans le sens horizontal dans ce coin, alors je dois en placer un autre dans ce sens...". Un tel raisonnement n'a cependant aucune chance d'aboutir dans ce cas vu le grand nombre de pavés qui doivent être placés.
Une méthode évidente pour prouver qu'un pavage est impossible est simplement de voir si l'aire d'un pavé divise l'aire de la surface totale. Ici, la surface totale est constituée de $62$ petits carrés, alors qu'un pavé permet de recouvrir $2$ petits carrés. On ne trouve donc pas dans ce cas d'absurdité, mais on sait déjà que, si un pavage existe, alors il est constitué de $\frac{62}{2} = 31$ pavés.
Une autre méthode plus prometteuse pour ce genre de problème est le coloriage. Elle consiste à colorier les différentes cases de la surface à paver de manière astucieuse, de sorte à prouver la non-existence d'un pavage. Pour notre exemple, le coloriage est en fait même suggéré par l'énoncé puisqu'un échiquier possède un coloriage naturel :
Ce coloriage peut sembler bien anodin, mais il permet en fait de résoudre directement le problème ! En effet, ce coloriage a de particulier que n'importe quel pavé $1 \times 2$ recouvre exactement un petit carré noir et un petit carré blanc. Or, on constate que la surface contient $32$ carrés blancs pour $30$ carrés noirs : il est donc clairement impossible d'effectuer un pavage correct !
Un simple coloriage permet donc de prouver très facilement qu'un pavage est impossible, alors qu'il semble difficile de conclure sans utiliser cette astuce. Le coloriage "en échiquier" est souvent performant, mais il faut parfois adapter le coloriage selon la surface et le type de pavé. Il n'est notamment pas interdit d'utiliser plus de deux couleurs, comme nous le verrons par la suite...