Introduction

LEGO. Voilà plus de 80 ans que les enfants (et leurs parents...) du monde entier s’amusent à empiler des briques de LEGO. L’origine de ces jouets remonte en effet aux années 30 et aux idées de Ole Kirk Christiansen, charpentier danois basé dans le Jutland, qui réalise des jouets démontables en bois. Petit à petit l’idée des briques fait son chemin et des briques de plastique sont testées dès la fin des années 40. Les premières figurines voient le jour quant à elles à la fin des années 70.

Un classique dans l’univers des jouets depuis lors, dont le nom est la contraction de lege godt, littéralement du danois bien jouer. On aurait également pu employer spille godt dans cette langue scandinave, ce qui aurait donc donné « Spigo », mais l’histoire en a décidé autrement.

Outre le plaisir de manipuler ces petits objets de couleur et de construire des châteaux en les empilant convenablement, ces fameuses briques posent des défis mathématiques de taille. L’objectif de ce texte est d’en présenter un en particulier, bien simple à énoncer : combien d’empilements différents peut-on créer avec $N$ briques similaires ?

Cette question de combinatoire doit être rapprochée d’une famille célèbre de problèmes ouverts, systématiquement étudiés depuis Golomb, et portant sur le dénombrement de structures baptisées polyominos (une généralisation des dominos). On pourra consulter à ce sujet Wikipedia et Quelques questions ouvertes sur les polyominos, ainsi qu’un lien explicite donné dans [1].

Les problèmes de décomptes d’empilements LEGO ont fait l’objet de plusieurs autres publications relativement récentes et le lecteur intéressé trouvera des éléments complémentaires notamment dans les références [2], [3], [4], [5].

Notons qu’un logiciel de simulation de constructions LEGO est disponible en ligne à cette adresse http://ldd.lego.com/fr-fr/.

L’idée de cet article a germé lors d’une conversation avec Søren Eilers à Copenhague. Je me suis étonné d’apprendre que ces questions de comptages en apparence élémentaires résistent encore. Ajoutez à cela le fait que la conversation ait lieu au Danemark, à propos de ces jouets qui ont occupé une bonne partie de mon temps de jeu pendant l’enfance, cela m’a donné l’envie de partager cette question !

Une tour de briques

Nous allons débuter avec des configurations particulières appelées « tours ». Une brique de base sera ici un parallélépipède rectangle de dimension 2 x 4, de couleur bleu, portant les 8 picots sur le dessus. Voici donc le héros de cette histoire :

La règle d’empilement que nous allons utiliser est la suivante : deux telles briques sont empilées si et seulement si :

• Les picots sont orientés dans la même direction (disons « vers le haut »).
• Les briques sont soit parallèles, soit perpendiculaires.
• Une brique est au-dessus de l’autre.
• Au moins un picot de la brique du dessous est inséré dans la brique du dessus.

Voici deux briques empilées de manière parallèle,

et deux briques empilées de manière perpendiculaire,

par contre les trois briques figurant sur l’image suivante ne vérifient pas les critères de notre définition d’empilement (car elles ne sont ni parallèles, ni perpendiculaires, mais obliques) ce type de configuration ne sera donc pas considéré dans la suite.

Par définition, une tour de hauteur 1 est simplement une brique isolée.
En appliquant la règle d’empilement à $N$ briques l’une après l’autre, où $N$ est un entier naturel supérieur ou égal à 2, on obtiendra alors une tour de briques de hauteur $N$. À chaque étage ne figure qu’une seule brique. Il y a une brique « socle » tout en bas. Il y a une brique « toit » tout en haut. Chaque brique de la tour qui n’est ni socle ni toit est donc attachée exactement à une brique en dessous et à une brique au-dessus. On considère que deux tours sont différentes si on ne peut pas les déduire l’une de l’autre par une rotation. Si on fixe le socle dans la même direction pour toutes les tours, alors la seule rotation possible pour passer d’un empilement à un autre sera un demi-tour. Voici un exemple de tour de 6 briques :

On se concentre sur la question suivante : combien y-a-t-il de telles tours de briques différentes en fonctions du nombre de briques $N$ ?

Baptisons $T(N)$ le nombre de tours différentes qu’il est possible de construire avec $N$ briques et commençons l’étude !

Le premier cas

Tout d’abord, si $N=1$, on a une seule brique, donc une seule tour et $T(1)=1$.

Si $N=2$, nous allons compter petit à petit (ne pas hésiter à prendre deux briques en main pour essayer). Une première remarque : le nombre de picots insérés peut être 1, 2, 3, 4, 6 ou 8, mais jamais 5, et jamais 7. Une deuxième remarque : il y a des symétries qui apparaissent. Nous allons distinguer deux types de tours. Celles dites symétriques sont les tours qui restent invariantes par rotation d’axe vertical et d’angle 180 degrés (un demi-tour). Les deux tours symétriques obtenues avec deux briques empilées sont les suivantes (à gauche 8 picots insérés, à droite 4 picots insérés) :

Les autres tours sont dites asymétriques. Voici un exemple de deux configurations asymétriques (obtenues avec deux briques, et deux picots insérés) qui sont images l’une de l’autre par une rotation de 180 degrés :

Nous conviendrons que les tours images l’une de l’autre par demi-tour représentent le même modèle de tour : on ne les comptera pas deux fois. On analyse alors au cas par cas :

Si les briques sont parallèles et ont 1 picot inséré : 4 possibilités qui donnent 2 tours différentes.

Si les briques sont perpendiculaires et ont 1 picot inséré : 4 possibilités qui donnent 2 tours différentes.

Si les briques sont parallèles et ont 2 picots insérés : 6 possibilités qui donnent 3 tours différentes.

Si les briques sont perpendiculaires et ont 2 picots insérés : 12 possibilités qui donnent 6 tours différentes.

Si les briques sont parallèles et ont 3 picots insérés : 4 possibilités qui donnent 2 tours différentes.

Si les briques sont perpendiculaires et ont 3 picots insérés : 0 possibilité qui donne 0 tour.

Si les briques sont parallèles et ont 4 picots insérés : 4 possibilités qui donnent 2 tours différentes.

Si les briques sont perpendiculaires et ont 4 picots insérés : 9 possibilités qui donnent 5 tours différentes, donc une est symétrique (en forme de croix).

Si les briques sont parallèles et ont 6 picots insérés : 2 possibilités qui donnent 1 tour.

Si les briques sont perpendiculaires et ont 6 picots insérés : 0 possibilité qui donne 0 tour.

Si les briques sont parallèles et ont 8 picots insérés : 1 possibilité qui donne 1 tour, laquelle est symétrique.

Si les briques sont perpendiculaires et ont 8 picots insérés : 0 possibilité qui donne 0 tour.

On dénombre donc 46 possibilités d’imbrications qui donnent lieu à 24 tours deux à deux différentes. Donc $T(2)=24$.

Le cas général

Il est possible de prouver une formule générale pour $T(N)$. On vient de voir que lorsqu’on prend deux briques de base et qu’on les empile, parmi les 46 configurations obtenues, 2 sont symétriques et les 44 autres vont par paires de configurations images l’une de l’autre par une rotation de 180 degrés.

Pour obtenir une formule générale, il sera utile de distinguer les configurations symétriques et les configurations asymétriques. Nous allons obtenir le résultat en décomposant $T(N)=s(N)+a(N)$, où $s(N)$ est le nombre de tours symétriques obtenues avec exactement $N$ briques, et $a(N)$ est le nombre de tours asymétriques obtenues avec exactement $N$ briques, à une rotation près. Pour les calculs de $s(N)$ et $a(N)$, on cherche à déduire le nombre de tours (symétriques, respectivement asymétriques) de hauteur $N$ à partir du nombre de tours de hauteur $N-1$ (on cherche une formule de récurrence).

Les tours symétriques de hauteur $N$ sont au nombre de $s(N)=2^{N-1}$ pour tout $N\geq 1$, voir le détail ci-après.

Pour les tours asymétriques, il faut travailler un peu plus pour trouver la formule $a(N)=(46^{N-1}-2^{N-1})/2$. On trouvera une preuve détaillée ci-après.

Au final on obtient donc $T(N)=a(N)+s(N)=1/2(46^{N-1}-2^{N-1})+2^{N-1}=(46^{N-1}+2^{N-1} )/2$. C’est gagné, on a trouvé le nombre de tours distinctes de hauteur $N$ ! On peut donc énoncer le théorème suivant :

Ce résultat était vraisemblablement déjà connu (dans une forme équivalente) de J. K. Kristensen, un ingénieur chimiste, petit-fils du fondateur de LEGO. Kristensen publie la formule dans deux notes internes à l’entreprise en 1973 et 1974, voir à ce sujet l’introduction de l’article « The LEGO Counting Problem » de S. Eilers [6].

Et les pyramides ?

Que se passe-t-il si on ne se restreint pas aux tours, mais qu’on autorise plusieurs briques sur un même étage dans nos empilements ? Baptisons $P(N)$ le nombre de structures différentes obtenues avec $N$ briques.

Il n’existe pas à ce jour d’expression simple pour le nombre de pyramides $P(N)$ en fonction de $N$. On sait tout de même les choses suivantes :

• $P(N)>T(N)$ dès que $N>2$. Bien sûr, si on s’autorise plusieurs briques au même étage, on a strictement plus d’empilements possibles !

• La croissance de $P(N)$ fonction de $N$ est une fonction à croissance au plus exponentielle en $N$, c’est-à-dire qu’elle ne grandit pas plus vite qu’une fonction du type $c^N$, où $c>2$ est indépendant de $N$.

• On a l’encadrement $78^{N-1}\leq P(N)\leq 192^{N-1}$ pour tout entier $N$ strictement positif. Cet encadrement est un peu plus difficile à démontrer et dépasse le cadre de notre présentation. Le lecteur intéressé pourra consulter les références.

Les deux derniers points ont été démontrés par Bergfinnur Durhuus et Søren Eilers dans l’article [7].

On est encore loin d’une formule exacte. Il reste donc du travail !

Une dernière question

Combien faut-il de briques pour construire un empilement du type suivant ?