Combinatoire des briques LEGO

Piste bleue Le 28 mai 2016  - Ecrit par  Fabien Pazuki Voir les commentaires (1)

Empiler des briques LEGO, rien de plus simple en apparence... mais la combinatoire de ces empilements cache encore bien des mystères !

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.

Le nombre de tours symétriques de hauteur $N$.

Pour obtenir une tour symétrique de hauteur $N+1$, on doit obligatoirement partir d’une tour symétrique de hauteur $N$, et on ne peut rajouter la dernière brique que de deux manières préservant la symétrie : en croix perpendiculairement à la brique toit, ou en insérant les 8 picots sur la brique toit (donc parallèlement). Donc $s(N+1)=2s(N)$. Comme $s(1)=1$, on obtient par récurrence sur $N$ la formule $s(N)=2^{N-1}$ pour tout $N$ entier supérieur ou égal à 1, ce qui signifie que les tours symétriques de $N$ étages sont au nombre de $2^{N-1}$.

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.

Le nombre de tours asymétriques de hauteur $N$.

Prenons une tour de $N$ briques et rajoutons une brique supplémentaire au-dessus. Si la tour initiale est symétrique, la brique supplémentaire peut être placée de deux manières différentes pour conserver le caractère symétrique. Les 44 autres possibilités brisent la symétrie et donnent lieu à 22 types de tours deux à deux distinctes. Par contre si la tour initiale n’est pas symétrique, on n’obtiendra jamais de symétrie en rajoutant une brique, et le nombre de possibilités est alors 46.

On obtient ainsi les relations de récurrence suivantes :

  • s(N+1)=2s(N)
  • a(N+1)=46a(N)+22s(N) (*)
  • s(1)=1
  • a(1)=0

On injecte la formule $s(N)=2^{N-1}$ dans la relation (*) pour obtenir $a(N+1)=46a(N)+22\times 2^{N-1}$. On peut alors déduire une formule close pour $a(N)$ en fonction de $N$ en utilisant la ruse suivante. Posons $c(N)=46^{-N} a(N)$. Alors $a(N+1)=46^{N+1}c(N+1)$ et $a(N)=46^Nc(N)$, donc $a(N+1)-46a(N)=46^{N+1}(c(N+1)-c(N))$, ceci fournit donc

\[c(N+1)-c(N)=22\times 2^{N-1}/46^{N+1}=22\times 46^{-2} \times 23^{-N+1},\]

valable pour tout $N\geq 1$. On fait alors une somme télescopique, ce qui donne

\[c(N)-c(1)=\sum_{k=1}^{N-1}(c(k+1)-c(k))=22\times 46^{-2}\sum_{k=1}^{N-1}\frac{1}{23^{k-1}}\]

et comme $c(1)=a(1)=0$, on obtient

\[c(N)=22\times 46^{-2}\frac{1/23^{N-1}-1}{1/23-1}=46^{-2}(23-23^{-N+2}).\]

Ceci donne ainsi

\[a(N)=46^{N}c(N)=46^{N-2}(23-23^{-N+2})=\frac{1}{2}(46^{N-1}-2^{N-1}).\]

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 :

Théorème. Le nombre $T(N)$ de tours différentes qu’on peut construire avec $N$ briques LEGO de taille 2x4 et de hauteur $N$, où $N$ est un entier naturel supérieur ou égal à 1, est $T(N)=(46^{N-1}+2^{N-1})/2$.

Une preuve plus rapide avec des matrices.

On peut en fait obtenir le résultat de manière plus rapide en procédant comme suit : les deux suites récurrentes $a(N)$ et $s(N)$ vérifient en fait :

\[\begin{pmatrix} a(N+1) \\ s(N+1) \end{pmatrix} = \begin{pmatrix} 46 & 22 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} a(N) \\ s(N) \end{pmatrix} \]

En mettant ainsi ces relations de récurrence sous forme matricielle, la matrice décrivant le passage du cran $N$ au cran $N+1$ est triangulaire, avec sur la diagonale les valeurs propres 46 et 2. Ceci implique que $a(N)=A\times 46^{N-1} + B\times 2^{N-1}$, où $A$ et $B$ sont des constantes. Or on sait par le comptage précédent que $a(1)=0$ et $a(2)=22$, donc $A=-B$ et $A (46-2)=22$, donc $A=1/2$ et $B=-1/2$.

On conclut de la même manière en sommant $T(N)=a(N)+s(N)$.

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 ?

Post-scriptum :

Je remercie Richecoeur, Philippe Colliard, Nicolas Bedaride, Valkil07, Michaël Bages, Mélanie Guenais, Jérôme Buzzi pour leur lecture attentive et leurs nombreuses remarques, ainsi que François Brunault et toute l’équipe d’Images des Maths ! Je remercie aussi Bergfinnur Durhuus, Søren Eilers de Copenhague et Bertrand Meyer pour nos conversations sur ce thème.

Article édité par François Brunault

Notes

[1Doron Zeilberger, Automated counting of LEGO towers, Journal of Difference Equations and Applications 08/1997 ; 5(4-5). DOI : 10.1080/10236199908808194, arxiv.

[2Mikkael Abrahamsem et Søren Eilers, On the asymptotic growth of LEGO structures, Experimental Mathematics 20 (2011) 145-152.

[3Søren Eilers, Counting LEGO buildings

[6Søren Eilers, The LEGO counting problem, American Mathematical Monthly, Vol. 123, No. 5 (May 2016), pp. 415-426.

[7Bergfinnur Durhuus et Søren Eilers, « On the entropy of LEGO », Journal of Applied Mathematics and Computing 45 (2014), 433-448.

Partager cet article

Pour citer cet article :

Fabien Pazuki — «Combinatoire des briques LEGO» — Images des Mathématiques, CNRS, 2016

Crédits image :

Image à la une - Photos : Fabien Pazuki.
img_15519 - Fabien Pazuki
img_15520 - Fabien Pazuki
img_15521 - Fabien Pazuki
img_15522 - Fabien Pazuki
img_15523 - Fabien Pazuki
img_15524 - Fabien Pazuki ; LEGO ;
img_15652 - Fabien Pazuki
img_15653 - Fabien Pazuki

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM