Voici notre abeille :

Elle veut bâtir une maison de forme hexagonale et y rentrer de manière parfaite. Pour cela, elle dispose de deux types de « briques » :

Peut-elle le faire ?

Précisons le problème. La « maison » est un hexagone du type illustré ci-dessous (on suppose que tous les petits hexagones ont la même taille, égale à celle des hexagones des briques et de « l’abeille » elle-même) :

Le problème consiste alors à remplir sans superposition (le mot précis est « paver ») ces grands hexagones avec des pièces de ces deux types

tout en rajoutant une seule pièce qui représente l’abeille, donc du type

Bien sûr, on est libre de faire tourner ces pièces pour les placer de manière convenable.

Notons que la quantité totale de petits hexagones des « maisons » est égale à 19, 31 et 61 [1]. On peut donc espérer pouvoir bâtir la maison, car
\[19 = 5 \times 3 + 4, \quad 31 = 9 \times3 + 4, \quad 61 = 19\times 3 + 4. \]
D’ailleurs, ce n’est pas difficile pour l’abeille de bâtir les deux premières maisons et d’y entrer. Voici quelques possibilités :

Mais après quelques essais, on voit bien qu’il y a des problèmes pour la maison la plus grande (celle de 61 hexagones). Notre abeille n’arrive pas à bâtir une maison où elle puisse rentrer de manière parfaite.

Voici notre deuxième personnage : la chenille (à gauche). Elle veut aussi construire une maison similaire à celle de l’abeille où elle puisse rentrer. Mais on se convainc assez rapidement qu’elle ne peut pas le faire pour les deux dimensions plus petites. Faites des essais, et vous le verrez bien.

Par contre, elle peut bâtir la grande maison et y entrer, comme montré à droite !

Que se passe-t-il ?

Dans le cas général d’une maison hexagonale de taille arbitraire, sera-ce l’abeille ou plutôt la chenille (ou bien les deux, ou bien aucune des deux) qui rentrera ?

En fait, ce problème fait partie d’une infinité de problèmes autour des pavages du plan, dont il a été question dans plusieurs articles d’Images des Maths : voir ici, ici ou ici. On trouvera des discussions similaires, mais plus élaborées que celle de notre problème, dans cet article et dans cet article.

Dans notre cas, il s’agit d’un problème qui peut être résolu avec des mathématiques élémentaires. Ce type de problèmes a été étudié par l’équipe Maths à Modeler et a permis de construire des « situations de recherche pour la classe » (SIRC), comme décrit dans cet article. Notre problème est en fait inspiré de leurs travaux.

Un vieil et bel argument toujours très utile

Commençons par un problème encore plus simple et bien connu qui concerne les pavages par des carrés :

Peut-on remplir le tableau $8 \times 8$ auquel on a retiré deux cases diagonalement opposées avec des pièces de type domino ?

Après quelques essais on se convainc que c’est impossible. La preuve s’appuie sur un coloriage similaire à celui d’un plateau d’échecs. On voit bien que quelle que soit la position d’une pièce de domino sur le tableau, elle utilise une case en blanc et une case en noir. Or, puisque les deux cases retirées du tableau étaient blanches, il nous reste 30 blanches et 32 noires. L’impossibilité en découle.

On essaie maintenant d’appliquer un argument similaire pour le réseau hexagonal. On s’aperçoit cependant qu’on ne peut pas colorier les cases avec deux couleurs de manière cohérente. On est obligé de se servir de trois couleurs. On voit alors apparaître naturellement les coloriages (en blanc, gris et noir) montrés ci-dessous.

Raisonnons comme en haut. Les deux briques dont on dispose utilisent toujours une case de chaque couleur, quelle que soit leur position sur le tableau hexagonal. Voici quelques exemples :

L’abeille elle aussi utilise des cases des trois couleurs, mais bien évidemment deux des cases utilisées ont la même couleur (celles de la tête et de la queue).
Quelques exemples :

La chenille, par contre, n’utilise que des cases de deux couleurs distinctes (les cases de la tête et du corps ont une couleur, et celles du cou et de la queue une autre). Encore quelques exemples :

Regardons maintenant les maisons. La première comporte 6 cases blanches, 6 grises et 7 noires. Si l’on utilise 5 briques, chaque brique couvrirait une case de chaque couleur, donc il resterait 1 case blanche, 1 grise et 2 noires. Une telle configuration peut être couverte par l’abeille (comme montré plus haut), mais pas par la chenille. Voilà pourquoi la chenille ne rentre pas dans la première maison.

Le cas de la deuxième maison est similaire : elle comporte 12 cases blanches, 12 grises et 13 noires, et l’emploi de 11 briques nous laisse à la fin 1 case blanche, 1 grise et 2 noires, ce qui est une configuration possible pour l’abeille mais pas pour la chenille.

Le cas de la troisième maison est différent. Cette maison comporte 21 cases blanches, 21 grises et 19 noires. Si l’on emploie 19 briques, il nous reste à la fin 2 cases blanches, 2 grises et aucune noire. Il s’agit d’une configuration qui peut être remplie par la chenille (comme montré plus haut), mais jamais par l’abeille.

Nous vous laissons le soin d’étudier le « cas général » d’une maison hexagonale. Vous verrez alors que les maisons dont le côté comporte une quantité d’hexagones égale à 3, 4, 6, 7, 9, 10, 12, 13, etc. sont accessibles à l’abeille, et celles de 5, 8, 11, 14, etc. à la chenille.

Lorsque le coloriage devient inefficace

L’argument de coloriage est très simple et efficace. Cependant, il ne permet pas de régler toutes les situations, même celles dont l’énoncé est encore élémentaire, ainsi que l’ont montré John Conway et Jeffrey Lagarias dans [2], qui a ensuite été repris par William Thurston dans [3]. Voici leurs exemples.

Tout d’abord, on ne se permet d’utiliser que des briques du type ci-dessous, que l’on peut faire tourner à volonté :

L’objectif est de compléter une configuration triangulaire comme la suivante :

Essayez de le faire et vous constaterez que l’on ne le peut pas.

Voyons maintenant de plus près. La quantité d’hexagones de cette configuration est égale à $n \, (n+1) \, / \, 2$, où $n$ est la quantité d’hexagones de chaque côté. Ce nombre n’est pas un multiple de 3 pour des valeurs de $n$ égaux à 4, 7, 10, 13, etc. Pour ces valeurs, l’impossibilité du pavage devient alors évidente. Mais pour $n$ égal à 5, 6, 8, 9, 11, 12, etc, la quantité d’hexagones est bien un multiple de 3. De plus, si l’on compte le nombre de cases blanches, grises et noires qui sont dans la configuration, on verra qu’ils sont égaux !

L’argument du coloriage ne permet donc pas de prouver l’impossibilité du pavage : il faut passer à des arguments mathématiquement beaucoup plus sophistiqués. C’est ce qui a été fait par Conway et Lagarias avec la théorie combinatoire des groupes, puis repris par Thurston avec une approche plus géométrique.

Que se passe-t-il maintenant si l’on cherche à remplir la même configuration triangulaire mais avec des pièces du type ci-dessous convenablement tournées ?

De nouveau, les cas où la configuration comporte une quantité d’hexagones sur son côté égale à 4, 7, 10, 13, etc. sont rapidement écartés. Pour le reste des cas, c’est à dire 2, 3, 5, 6, 8, 9, 11, 12, etc., après quelques essais on ne trouve des configurations que pour 2, 9, 11, 12. Quelques-unes sont illustrées ci-dessous.

Plus généralement, Conway et Lagarias montrent qu’un tel pavage existe si et seulement si $n$ est congru à 0, 2, 9 ou 11 modulo 12. Il s’agit d’une très belle preuve pour laquelle nous vous renvoyons de nouveau aux articles originaux.

Pour conclure : pouvez-vous trouver d’autres configurations pour lesquelles l’existence de pavages avec différents types de pièces devient un problème intéressant ?

Pour plus d’amusements, nous vous renvoyons à ces quatre livres merveilleux titrés Winning Ways for Your Mathematical Plays de Elwyn R. Berlekamp, John H. Conway et Richard K. Guy, ainsi qu’aux travaux de l’équipe Maths à Modeler [4].