Comptes Rendus MATh.en.JEANS 03-05

Enseignants : Didier MISSENARD.

Chercheur : Romain DUJARDIN (doctorant moniteur, Univ. Paris Sud, Orsay), Pierre PANSU (prof. Univ. Paris Sud, Orsay), Lionel PAUMOND (doctorant moniteur, Univ. Paris Sud, Orsay).

Atelier MATh.en.JEANS du Lycée Blaise Pascal d'Orsay (91). Atelier de Pratique Scientifique, année scolaire 2002-2003.

---

[Article en cours d'analyse et de vérification : les passages entre crochets sont des éditeurs]

Plan

1- Présentation du problème.
2- Premières conditions (A. La parité B. Le coloriage).
3- Dallages convexes (A. Définitions préliminaires B. Théorème et démonstration)
4- Fonction de hauteur.

1. Présentation du problème

Tout commence lorsqu'on demanda à un carreleur de paver la pièce suivante, formée d'un assemblage de triangles équilatéraux unité - on appellera un tel assemblage un « dallage » - , avec des dalles en forme de losange, formés de deux triangles équilatéraux accolés, les dalles devant recouvrir tout le dallage et ne devant pas se chevaucher :

Rapidement, il trouve une solution :

Le client, ravi, demande alors au carreleur de paver une autre pièce, avec des identiques :

Mais le carreleur s'aperçoit très vite que la pièce ne peut pas être pavée. En effet, si elle pouvait l'être, le triangle « isolé » dans le coin en haut à gauche devrait être obligatoirement relié à l'unique triangle adjacent, ce qui crée un autre triangle « isolé » dans un coin, et ainsi de suite, ce qui force le placement de cinq dalles (en couleur) et laisse un unique triangle isolé qui ne peut être relié à aucun triangle adjacent encore libre :

Ainsi, se dit le carreleur, il existe deux catégories de dallages : ceux qui peuvent être pavés - les dallages « pavables » - et ceux qui ne peuvent pas l'être. Nous allons étudier comment savoir si un dallage est pavable ou ne l'est pas.

2. Premières conditions

2A. La parité

Une première condition nécessaire pour qu'un dallage soit pavable repose sur la parité du nombre de triangles composant le dallage : chaque losange recouvrant deux triangles, un nombre quelconque de losanges recouvrera toujours un nombre pair de triangles. Ainsi, un dallage « impair », c'est à dire composé d'un nombre impair de triangles, ne pourra jamais être pavé. C'est le cas du dallage ci-dessous, composé de neuf triangles :

Mais cette condition n'est pas suffisante. Le dallage ci-dessous, bien que composé de dix triangles et donc pair, est toutefois non pavable : le triangle tout en haut est nécessairement relié au triangle juste en dessous, ce qui force le placement du losange rouge, puis celui du losange jaune, puis celui du vert, ce qui laisse le triangle marqué d'un cercle bleu sans triangle adjacent.

C'est pourquoi nous allons rechercher d'autres conditions nécessaires.

2B. Le coloriage

Reprenons le dallage pair mais non pavable présenté ci-dessus, et colorions ses triangles en blanc et en noir, de manière à ce que tout triangle noir ne soit adjacent qu'à des triangles blancs, et vice-versa :

On remarque qu'il y a dix triangles d'une couleur et six de l'autre. Or, le coloriage est tel que tout losange recouvre obligatoirement un triangle noir et un blanc, puisqu'il recouvre deux triangles adjacents. Ce raisonnement nous permet donc de prouver que ce dallage n'est pas pavable, et de trouver une autre condition nécessaire : il faut que le dallage considéré, une fois colorié en noir et blanc, possède autant de triangles blancs que de triangles noirs. On dira dans ce cas que le dallage est « bien colorié ».

Mais cette condition n'est pas suffisante, elle non plus. Considérons le dallage ci-dessous :

On vérifie aisément qu'il est pair (28 triangles) et bien colorié (14 noirs, 14 blancs). Et pourtant, il n'est pas pavable. Pour le montrer, il suffit de remarquer que si le triangle marqué d'un cercle rouge est relié au triangle à sa droite, celui à sa gauche sera obligatoirement seul, et que s'il est relié à celui à sa gauche, ce sera celui à sa droite qui sera seul.

Ainsi, bien que nécessaires, les conditions de parité et de coloriage ne sont pas suffisantes. Avant de chercher une condition nécessaire et suffisante, nous allons à présent étudier un cas plus simple, celui des dallages « convexes ».

3. Dallages convexes

3a. Définitions préliminaires

Dallage convexe. Un dallage est dit convexe si, quelque soient deux points à l'intérieur du dallage, le segment qui les relie est entièrement à l'intérieur du dallage.

En pratique, un dallage convexe est un dallage qui a la forme d'un hexagone convexe avec éventuellement des côtés de longueur nulle (c'est à dire qu'un dallage convexe est un dallage qui a la forme d'un polygone convexe à 6 côtés ou moins [au plus], sans trou.

Exemple : le dallage de gauche est convexe, celui de droite ne l'est pas (le segment rouge relie deux points à l'intérieur du dallage mais passe à l'extérieur de celui-ci).

Dallage symétrique. Un dallage convexe est dit symétrique si toute paire de côtés parallèles du dallage est constitué de côtés de longueurs égales.

Exemple : Le dallage ci-dessous est symétrique.

3b. Théorème et démonstration

Il existe une condition simple pour savoir si un dallage convexe est pavable.

Théorème 1. Un dallage convexe est pavable si, et seulement si il est bien colorié, et si, et seulement si il est symétrique.

Voici la démonstration de ce théorème (dans ce qui suit, sauf indication contraire, les dallages sont supposés symétriques) :

• Montrons :  (i) le dallage est symétrique  le dallage est pavable

  (i) est évident pour les dallages en forme de parallélogramme : il suffit de commencer à paver le dallage par les extrémités « pointues » du dallage, puis de revenir vers le centre.

  

  Si le dallage symétrique considéré n'est pas un parallélogramme, on le sépare en deux parties : la couronne, constituée de tous les triangles du dallage ayant au moins un sommet sur le bord du dallage, toujours pavable (aisément vérifié [on peut voir par exemple la couronne comme une réunion de parallélogrammes]), et un intérieur, également symétrique, et strictement plus petit que le dallage initial. En réitérant le raisonnement sur le dallage intérieur, on finit par aboutir à un découpage du dallage initial en une série de couronnes successives pavables et un intérieur symétrique avec des côtés nuls, c'est à dire un parallélogramme (ou rien du tout, si tous les côtés de ce parallélogramme sont nuls, c'est à dire de longueur nulle). Sur l'exemple ci-dessous, les couronnes successives ont été coloriées.

On a ainsi montré par récurrence que tout dallage symétrique est pavable (et donné un algorithme pour le paver).

• [L'implication :] (ii) Le dallage est pavable le dallage est bien colorié  est évidente.
  
• Pour montrer : (iii) le dallage est bien colorié le dallage est symétrique , et ainsi terminer la démonstration du théorème, nous allons montrer un lemme valable pour tous les dallages.
  Lemme (3.1) Un dallage est bien colorié si, et seulement si lorsqu'on parcourt le bord du dallage dans un sens arbitraire, pour une direction choisie, on parcourt autant d'arêtes (de triangles-unités) de cette direction dans un sens que dans l'autre.

  Sur le dallage ci-dessous, le lemme permet d'affirmer que, comme le dallage est bien colorié, quand on parcourt le bord du dallage, on va autant de fois vers la droite que vers la gauche, soit que

  

  [Démonstration du lemme 3.1] Pour démontrer ce lemme, notons n (resp. b) le nombre de triangles noirs (resp. blancs) du dallage et N (resp. B) le nombre d'arêtes du bord du dallage étant des [qui sont] les arêtes d'un triangle noir (resp. blanc).

  Considérons une direction arbitraire, et notons  (resp. ) le nombre d'arêtes de cette direction parcourues dans un sens (resp. dans l'autre). On démontre aisément par récurrence sur le nombre de triangles que

  

  [Indications sur le démonstration :] cette propriété est vraie pour un triangle et on vérifie aisément que si elle est vraie pour n triangles, elle reste vraie en ajoutant un triangle quelque soit son emplacement. Lors du raisonnement, il suffit discuter sur le nombre de triangles déjà placés et adjacents au nouveau triangle.

  On a donc  ; reste à montrer  . Pour cela, nous allons montrer le résultat plus fort :

  (iv)   

  Ce résultat se montre également par récurrence sur le nombre de triangles : (iv) est clairement vraie pour un triangle unique. Supposons qu'elle soit vraie pour n triangles, et ajoutons un n+1^ième triangle. S'il est blanc (resp. noir), b-n augmente (resp. diminue) de 1 et on vérifie que B-N augmente (resp. diminue) de 3 quelque soit le nombre de triangles déjà placés et adjacents au n+1^ième triangle. Dans les deux cas (blanc ou noir), cela permet de montrer que (iv) reste vrai. (iv) est donc vrai pour tout dallage, ce qui permet de finir la démonstration du lemme (3.2)

  Dans un dallage convexe, il n'existe pas trois côtés parallèles distincts deux à deux. Si on choisit une direction, on a donc seulement deux côtés du dallage de cette direction. Comme les arêtes d'un même côté sont toutes parcourues dans le même sens, et celles de côtés opposés dans des sens opposés, le lemme permet d'affirmer que si le dallage est bien colorié, les deux côtés parallèles choisis ont donc même longueur. En refaisant ce raisonnement pour les deux autres paires de côtés parallèles, on en déduit que le dallage est symétrique, ce qui montre (iii).

Ainsi, (i), (ii) et (iii) étant montrés, on a :

• le dallage est symétrique le dallage est pavable
• le dallage est pavable le dallage est bien colorié
• le dallage est bien colorié le dallage est symétrique

C.Q.F.D.

Le cas des dallages convexes ayant été résolu, il ne reste plus qu'à étudier le cas général, ce qui sera fait en introduisant une nouvelle notion, celle de la fonction de hauteur.

4. Fonction de hauteur

Ainsi, nous n'avons vu pour l'instant que des conditions nécessaires mais non suffisantes. Nous allons donc essayer d'en trouver une.

Pour cela, considérons un pavage déjà vu :

Nous savons aussi que ce dallage est pavable :

L'idée consiste à voir ce dallage comme une représentation en 3 dimensions d'un empilement de cubes, ou plus simplement comme un objet en 3D.

Pour cela, pavons notre dallage d'une façon assez spéciale:

En effet, nous avons colorié tous les losanges orientés vers le haut en gris, tous les losanges orientés vers la droite en blanc et tous les losanges orientés vers la gauche en noir :

On remarque qu'on obtient une sorte d'escalier, dont la partie formée de losanges blanc à droite est le premier étage et la deuxième partie formée de losanges blancs le deuxième étage. Nous avons donc bien obtenu un objet en 3D.

Nous pouvons alors nous intéresser à l'altitude des sommets en 3D. Choisissons une origine, c'est-à-dire un sommet dont l'altitude sera 0: dans notre exemple, nous choisirons arbitrairement le sommet en bas à droite (mais on pourrait aussi bien en choisir un autre).

On choisit également une direction et un sens qui correspondront à la verticale ascendante, les deux autres directions étant horizontales. Choisissons le sens le plus naturel, celui indiqué par la flèche (à nouveau, ce choix est arbitraire) :

Calculons l'altitude sur le bord :

Comme nous l'avons déjà dit, si le sommet se trouve sur le sol alors il a une altitude nulle. Ensuite, on parcours le bord en partant du sommet d'altitude 0 (que l'on a nous-même choisi).

Si, pendant notre parcours, nous allons dans le sens indiqué, cela veut dire que nous montons. Ainsi le sommet d'arrivée aura une altitude supérieure de 1 à celle du sommet de départ.

Au contraire, si nous nous dirigeons dans le sens contraire, cela veut dire que ne descendons. Ainsi le sommet d'arrivée aura une altitude inférieure de 1 à celle du sommet de départ.

Si nous nous dirigeons dans l'une des deux autres directions, nous restons sur la même altitude.

On s'est restreint ici à représenter l'altitude sur le bord. Il va de soi qu'elle est définie partout, mais c'est uniquement les valeurs qu'elle prendra sur le bord qui nous intéresseront.

Résumons. Nous avions un dallage pavable. Nous avons réussi à le voir comme une représentation d'un objet en 3D d'un objet (un escalier). De ce fait, nous avons calculé l'altitude de chaque sommet, en fixant une altitude 0 et un sens dans lequel monter. En particulier, cela a permis de définir une fonction sur le bord du pavage, qu'on nommera , plutôt qu'altitude, fonction de hauteur.

On peut montrer aisément que cela se généralise :

Tout dallage pavable admet une représentation en 3D et donc que sa fonction de hauteur est réelle et qu'elle est définie partout sur le bord.

Cette propriété permet de montrer que certains dallages ne sont pas pavables : on peut en effet définir une fonction de hauteur sur le bord d'un dallage en se donnant une origine et un sens, et ce indépendemment de toute représentation 3D, que le dallage soit pavable ou non. Si cette fonction de hauteur ne peut correspondre à une altitude réelle, cela signifie que le dallage de départ ne pouvait être pavable.

[Exemple] Prenons d'abord un des dallages les plus simples, le triangle équilatéral de côté 3.

Comme précédemment, on choisit sommet en bas a gauche comme sommet d'altitude nulle, et on décide qu'on monte vers la droite. On essaye ensuite de calculer la hauteur sur tous les sommets du bord. On obtient :

Mais le sommet en bas à gauche a 2 hauteurs: 0 et 3 ! Mais [Or] dans une représentation en 3D, un sommet ne peut avoir qu'une seule altitude ! La fonction de hauteur ne peut donc correspondre à une altitude : le dallage considéré ne peut être la représentation d'un objet en 3D : il n'est pas pavable.
Ce n'est cependant pas une surprise, car on savait qu'il était impair.

On peut même montrer que le fait qu'un point possède plusieurs hauteurs est équivalent au mauvais coloriage du dallage (démonstration par récurrence).

Nous allons maintenant voir une autre contradiction possible, plus subtile. Pour cela, considérons un dallage déjà étudié, qui n'est pas pavable:

[Exemple]

Comme précédemment, choisissons le sommet en bas a gauche comme origine, et décidons qu'on monte vers la droite.

On essaye ensuite de calculer la hauteur sur tous les sommets du bord. On obtient :

A la différence de l'exemple précédent, il n'y a pas de contradiction apparente (cela est du au fait que ce dallage est bien colorié). Cependant, regardons les deux valeurs de la hauteur au niveau du rétrécissement : l'une est de 0, l'autre de 6. C'est justement cela qui constitue notre contradiction:

         Supposons que ce dallage soit la représentation d'un objet 3D. Alors ces deux points ont une différence d'altitude de 6. Cependant, sur le dallage, ils sont reliés par 4 segments, qui correspondraient à 4 arêtes de longueur 1 en 3D. Il est cependant clair, par une inégalité triangulaire, que deux points de différence d'altitude de 6, et donc à distance supérieure à 6 l'un de l'autre, ne peuvent être reliés par une ligne polygonale de longueur 4. C'est ce qui constitue notre contradiction.

Finalement, notre conjecture est :

Conjecture. Un dallage est pavable si, et seulement si la fonction de hauteur telle qu'on l'a définie ne possède pas l'une des contradictions présentées ci-dessus, et ce quelque soit le sens choisi comme sens de montée.

Ce dernier détail ["quelque soit le sens choisi"] est important car si dans la figure précédente on avait choisi l'un des 2 autres sens, on aurait pas vu de contradiction semblable.

Par exemple, dans ce dallage :

La fonction de hauteur n'est contradictoire pour aucun des sens choisis. Notre dallage est donc pavable !

[5. Un invariant]

[Depuis leur présentation au congrès de Bordeaux, l'atelier MATh.en.JEANS du Lycée Blaise Pascal a obtenu un nouveau résultat sur les carrelages par losanges : les nombres de losanges placés dans chacune des 3 directions possibles ne dépendent que de la forme du dallage et non de la manière de carreler ¡ voir le texte ]

1. Article reçu le 20 Octobre 2003.

retour à l'appel de cette note

PAVAGE LOSANGE TRIANGLE HEXAGONE CONVEXE PARITÉ RECURRENCE CONDITIONS NECESSAIRES ET SUFFISANTES