Dans cet article, nous allons évoquer le triangle de Sierpinski, le triangle de Pascal, un lien qui les unit, un théorème de Lucas, une démonstration due à un certain N.J. Fine ainsi qu’une illustration de tout cela dans Minecraft. Rien que ça.
Triangle de Sierpiński
Si vous êtes amateur de fractales, vous avez sans doute déjà vu un triangle de Sierpiński. Pour ceux qui ne connaîtraient pas, voici une petite explication.
Prenez un triangle équilatéral « plein » (que nous appellerons ). Ôtez-lui le petit triangle formé en joignant les milieux des trois côtés comme montré ci-dessous. On appelle
le triangle à trou obtenu :
Recommencez ce même processus avec chacun des triangles « pleins » restants:
Le triangle troué obtenu après itérations sera noté
. Par exemple, pour
, voici la figure qui apparaît:
Et lorsque vous itérez une infinité de fois ce processus, vous obtenez ce qu’on appelle le triangle de Sierpiński (du nom du mathématicien qui l’a découvert).
Triangle de Pascal
Vous avez sans doute aussi entendu parlé du triangle de Pascal. Rappelons tout de même de quoi il s’agit en introduisant quelques notations.
Si et
sont deux entiers naturels, la notation
désigne le nombre de parties à
éléments dans un ensemble à
éléments. De manière peut-être plus parlante, c’est le nombre de façons de choisir un groupe de
personnes dans un groupe de
personnes. Rappelons comment sont calculés les nombres
:
- Soit en utilisant la formule
;
- Soit par récurrence, en utilisant la formule de Pascal:
Une façon élégante de représenter ces nombres (aussi appelés coefficients binomiaux) est de les placer dans un triangle, qu’on appelle triangle de Pascal, de la manière suivante:
- Dans la première ligne, on place le nombre
- Dans le deuxième ligne, on place les nombres
et
- Dans la troisième ligne, on place les nombres
,
et
- …
- Dans la
-ème ligne, on place les nombres
,
, … ,
Tous ces nombres sont placés de façon à former un triangle. Par exemple, le triangle obtenu pour est le suivant:
Nous noterons
ce triangle. Plus généralement, le triangle de Pascal obtenu en allant jusqu’à l’entier
sera noté
. Il contient donc
lignes.
Après calculs, voilà ce que donne le triangle de Pascal :
Quand Pascal rencontre Sierpiński
Reprenons nos triangles de Sierpiński et superposons-les avec nos triangles de Pascal:
Comme on peut le voir, tous les petits triangles de sont occupés par des coefficients binomiaux impairs. Et aucun coefficient impair n’est en dehors d’un petit triangle.
Nous constatons donc que pour tout , le triangle
correspond au triangle de Pascal
dans lequel on a retiré tous les coefficients binomiaux qui sont pairs. Génial, non ? Moi, je trouve ça superbe. (Bon c’est vrai que nous ne l’avons pas prouvé mathématiquement mais nous l’admettrons ici…)
Dessinons de beaux triangles de Sierpiński…
Le constat précédent nous donne donc un moyen pratique de dessiner le triangle de Sierpiński : il suffit de découper un triangle équilatéral en de petits triangles équilatéraux ( de sorte que chaque côté du grand triangle équilatéral soit découpé en
parts égales), de superposer le triangle de Pascal
puis de noircir les petits triangles qui correspondent à des coefficients binomiaux impairs.
Voici une illustration de ceci dans Minecraft, où on a représenté le triangle à l’aide du triangle de Pascal
et d’un algorithme basé sur ce principe de parité des coefficients binomiaux:
Je n’ai pas posé moi-même ces milliers de blocs (2187 si mes calculs sont exacts), j’ai juste utilisé une petite tortue dans laquelle j’ai entré un programme puis je l’ai laissée travailler toute seule, comme une grande…
Le théorème de Lucas
Le seul souci avec cette méthode de construction des triangles de Sierpiński à l’aide des coefficients binomiaux, c’est que ces derniers peuvent être assez grands et donc difficiles à calculer. Par exemple, dans le triangle représenté dans Minecraft ci-dessus, il aurait fallu calculer à un moment qui est de l’ordre de
. Pas très pratique tout ça, surtout quand on sait que ce n’est pas le seul coefficient binomial qu’il faudrait calculer pour réaliser cette construction…
Comment remédier à ce souci ? Puisqu’il n’y a que la parité du nombre qui nous intéresse, on peut être plus astucieux et s’éviter le calcul complet de ce nombre. En fait, l’astuce vient d’un théorème qu’on doit au mathématicien français du 19ème siècle nommé Édouard Lucas:
Si et
sont les écritures de
et
en base 2 (avec éventuellement des zéros à gauche de façon à ce que ces deux écritures contiennent le même nombre
de chiffres) alors:
Donnons tout de suite un exemple pour clarifier les choses. On veut savoir si le coefficient est pair, sans avoir à le calculer.
1) On commence par déterminer la décomposition de ces deux nombres en base 2:
en base 2
en base 2
2) Puis, on fait en sorte que ces deux nombres aient le même nombre de chiffres en base 2 en rajoutant des zéros à gauche si besoin: on a donc et
.
3) On forme les coefficients binomiaux obtenus en prenant successivement chaque chiffre de et
. Par exemple, le premier chiffre de
en partant de la gauche est 1 et le premier chiffre de
est 0. On calcule donc le coefficient binomial
. On fait de même avec le deuxième chiffre de
et
: on doit donc calculer
. Les troisièmes et quatrièmes chiffres donneront respectivement les coefficients
et
. Le théorème de Lucas nous dit que
aura la même parité que le produit:
4) On calcule le produit . Or
,
,
et
(car il y a zéro façons de choisir 1 élément dans un ensemble à 0 élément !). Ainsi, le produit vaut
. D’après le théorème de Lucas,
. C’est donc un nombre pair ! (Pour vérification,
, qui est bien pair).
En fait, on remarque que dès qu’il y a un rang pour lequel le chiffre de est strictement supérieur au chiffre de
alors le coefficient
apparaîtra dans le produit, et ce produit sera donc nul. Ainsi, une façon plus commode d’utiliser le théorème de Lucas est de représenter les écritures de
et
en base 2 dans un tableau en alignant les chiffres et s’il y a une colonne où le chiffre de
est strictement supérieur au chiffre de
, alors
sera pair. Sinon, il est impair.
Par exemple, pour savoir si le coefficient est pair, on aligne les écritures de 24 et 9 en base 2:
On voit qu’il y a une colonne dans laquelle le chiffre de est strictement supérieur au chiffre de
(la dernière colonne) donc on en déduit que
est pair ! (ce qui est bel et bien vrai car
)
Everything is Fine
En fait, le théorème de Lucas est vrai même en base où
est un nombre premier. Mais nous allons le montrer uniquement pour
(la démonstration étant identique dans le cas général…). La (très élégante) démonstration que nous allons donner suit une démonstration donnée par un certain N.J. Fine en 1947. Mais avant cela, rappelons deux ou trois bricoles.
Dans toute la suite, nous allons raisonner modulo 2. Raisonner modulo 2, ça veut dire que chaque fois qu’il y a un nombre pair, on peut le remplacer par 0 et chaque fois qu’il y a un nombre impair, on peut le remplacer par 1. Hormis cela, tous les autres calculs se font de la même manière que les calculs dont vous avez l’habitude.
Commençons par une petite propriété très utile quand on raisonne modulo 2: si et
sont deux nombres entiers, alors
. Cela vient du fait que
et du fait que le terme
vaut 0 modulo 2 (car c’est un nombre pair). Dans la suite, nous nous passerons du symbole
et nous noterons
tout en se souvenant qu’on raisonne modulo 2. On en déduit facilement par récurrence, que pour tout entier naturel
,
. Bon, cela étant dit, passons aux choses (très) sérieuses.
Pour prouver le théorème de Lucas, nous allons écrire de deux façons différentes un même polynôme calculé modulo 2 puis identifier les coefficients. Ce polynôme en question, c’est .
D’une part, la formule du binôme de Newton nous donne:
D’autre part, en utilisant la décomposition de en base 2 et la petite propriété décrite plus haut, on obtient:
Ainsi, nous avons démontré l’égalité:
Maintenant, prenons un entier compris entre
et
.
- Dans le polynôme de gauche, le coefficient du terme de degré
est évidemment
.
- Dans le polynôme de droite, le coefficient de degré
est obtenu pour tous les
-uplets
tels que
. Par unicité de la décomposition d’un entier en base 2, il n’y a qu’un seul tel
-uplet, et il s’agit de
où les
sont les chiffres de
en base 2. On en déduit que le coefficient de degré
du polynôme de droite est
.
Par identification, nous en déduisons donc que l’égalité suivante est vraie modulo 2:
Voilà, nous avons bien prouvé le théorème de Lucas ! J’ai mis cette même preuve dans un pdf (car je trouve ça plus propre quand c’est dans un seul et même fichier… T.O.C.) :
Et en programme ça donne quoi ?
Disons que vous voulez savoir si est pair ou non. Voici un programme possible (en Lua) qui, après avoir entré
et
affiche 0 si le coefficient binomial est pair, et 1 sinon. (J’ai utilisé cette partie de code pour réaliser le triangle de Sierpinski dans Minecraft posté plus haut)
local parite=1 while(n>0 and k>0) do -- Si le chiffre de droite de n est plus grand ou égal -- à celui de k, on le supprime: if( (n%2)>=(k%2) ) then n = (n-n%2)/2 k = (k-k%2)/2 -- Sinon, on peut s'arrêter car -- le coefficient binomial -- sera forcément pair dans ce cas else parite=0 n=0 end end print(parite)
A vous de dessiner des triangles de Sierpinski maintenant.
Notes:
- La démonstration originale de N.J. Fine.
- Un joli site (que je viens de découvrir après l’écriture de cet article) où on peut visualiser de magnifiques triangles de Sierpinski-Pascal (et pas nécessairement modulo 2 !)
Voici un lien pour dessiner un beau triangle en LaTeX : http://www.texample.net/tikz/examples/pascals-triangle-and-sierpinski-triangle/
J’aimeJ’aime
J’avais fait ça sous Geogebra à l’époque… mais c’est tellement plus beau avec Tikz! Merci du lien 😉
J’aimeJ’aime
Ping : Triangulando: Pascal versus Sierpinski - Cuaderno de Cultura Científica