Lemme de Burnside : compter sans examiner tous les cas

Intervenant 10:00

Comptez jusqu'à quatre, bon, c'est un peu un jeu d'enfant. C'est l'une des toutes premières compétences intellectuelles qu'on acquiert en fait.

Intervenant 20:06

Ouais, c'est très intuitif.

Intervenant 10:08

Exactement. On compte des billes, des marches, des escaliers, des jours sur un calendrier. Mais compter des objets qui se ressemblent fortement et qui en plus peuvent pivoter dans l'espace, ça devient instantanément un cauchemar mathématique.

Intervenant 20:22

C'est clair, ça brouille complètement les pistes.

Intervenant 10:24

Bonjour et bienvenue à notre audience pour cette nouvelle exploration audio. Je suis vraiment ravie de présenter le podcast du magazine Tangente aujourd'hui avec un programme particulièrement stimulant.

Intervenant 20:35

Salut à toutes et à tous, ravi d'être là.

Intervenant 10:37

Aujourd'hui, on s'attaque au grand paradoxe du dénombrement et on va voir comment les mathématiques transforment le chaos total des symétries en une solution d'une élégance vraiment absolue.

Intervenant 20:48

Et c'est un paradoxe super fascinant, tu sais, parce que la difficulté du dénombrement, en fait, elle ne réside presque jamais dans la quantité elle-même.

Intervenant 10:57

Bah oui, c'est plutôt dans l'identité des objets qu'on manipule.

Intervenant 21:00

Voilà, c'est ça. Discerner dix cailloux tous différents, bon, c'est trivial. En revanche, manipuler des formes géométriques qui deviennent strictement identiques selon l'angle d'observation, c'est une autre paire de manches.

Intervenant 11:14

Ah oui, l'esprit humain est naturellement très vulnérable face aux doublons visuels, non ? Surtout ceux générés par des axes de symétrie.

Intervenant 21:22

Complètement. Notre cerveau a du mal à faire le tri. Et c'est pour résoudre cette vulnérabilité précise qu'un mathématicien nommé William Burnside a formulé un lème décisif au siècle dernier.

Intervenant 11:33

En s'appuyant sur la fameuse théorie des groupes, c'est ça ?

Intervenant 21:35

Absolument.

Intervenant 11:36

La théorie des groupes, c'est pour faire simple, c'est par essence le langage mathématique qui permet de codifier la symétrie.

Intervenant 21:43

C'est le meilleur outil pour ça, oui.

Intervenant 11:44

Et ce fameux lemme de Burnside, il est réputé pour être une sorte de raccourci miraculeux quand le comptage manuel devient tout simplement impossible. Quel est le principe sous-jacent en fait ?

Intervenant 21:55

Ce qui est fascinant ici, c'est l'approche presque contre-intuitive de sa

Intervenant 11:59

formule.

Intervenant 22:00

Contre-intuitive comment ?

Intervenant 12:01

Burnside démontre que pour obtenir le nombre d'objets véritablement distincts dans un ensemble en tenant compte de toutes les permutations possibles, bien sûr, il est inutile et même contre-productif d'essayer de les lister un par un pour rayer les doublons.

Intervenant 22:15

D'accord, donc on ne fait pas de liste. On fait quoi à la place ? La méthode consiste plutôt à prendre isolément chaque transformation géométrique envisageable, comme une rotation ou un effet miroir par exemple.

Intervenant 12:28

Ok, je vois.

Intervenant 22:29

Et à comptabiliser uniquement les objets qui demeurent absolument inchangés sous l'effet de cette transformation précise. Ce sont ce qu'on appelle les objets invariants.

Intervenant 12:39

D'accord, on isole ce qui ne bouge pas, c'est malin. Mais on fait quoi de ces données ensuite ?

Intervenant 22:43

C'est là que la magie opère. Une fois qu'on a récolté le nombre d'invariants pour chaque transformation du groupe, on en fait tout simplement la moyenne.

Intervenant 12:51

Attends, juste la moyenne ?

Intervenant 22:52

Juste la moyenne. La somme des invariants divisée par le nombre total de transformations. Le résultat de cette moyenne donne directement et sans la moindre marge d'erreur le nombre exact d'objets distincts.

Intervenant 13:05

Mais descendons tout de suite dans la pratique pour que l'auditoire puisse visualiser. Prenons un objet classique, par exemple un jeu de domino standard allant du double blanc au double 6.

Intervenant 23:20

Ah, c'est un terrain d'essai parfait ça. La question de base est super simple. Combien est-ce qu'on compte de dominos uniques dans un jeu complet ?

Intervenant 13:29

Alors, avec la méthode par force brute, je dirais que le calcul mental est quasi immédiat.

Intervenant 23:35

Vas-y, je t'écoute.

Intervenant 13:36

Bon, on a d'abord 7 doubles.

Intervenant 23:37

Oui.

Intervenant 13:38

Ensuite, les paires mixtes. Donc on a 6 dominos avec un blanc, 5 avec un 1, et ainsi de suite jusqu'au 5-6. On additionne simplement la suite 7 plus 6 plus 5 plus 4 plus 3 plus 2 plus 1.

Intervenant 23:53

Ce qui nous amène à ?

Intervenant 13:54

Ça donne 28 dominos ! Franchement, on n'a pas besoin de la théorie des groupes pour trouver ça.

Intervenant 23:58

Le résultat est irréprochable, je te l'accorde. Mais appliquons quand même la mécanique de Burnside pour en observer les rouages, tu veux bien ?

Intervenant 14:05

Allez, soyons fous, sortons l'artillerie lourde.

Intervenant 24:07

Considérons d'abord l'univers de tous les couples ordonnés possibles. Il y a 7 valeurs possibles pour la première moitié du domino et 7 valeurs pour la seconde.

Intervenant 14:15

Oui, de 0 à 6.

Intervenant 24:17

C'est ça. Donc, 7 multiplié par 7, on part d'un ensemble de 49 dominos théoriques.

Intervenant 14:23

Sauf que dans le monde réel, un 2-5 et un 5-2 posés sur une table, c'est la même pièce physique qu'on a juste retournée.

Intervenant 24:30

Exactement. L'ordre n'a aucune importance dans la réalité physique du domino.

Intervenant 14:34

D'accord, décortiquons tout ça. C'est précisément là qu'interviennent nos fameuses transformations géométriques, non ?

Intervenant 24:41

Tout à fait. Un rectangle comme la forme d'un domino possède deux états de symétrie qui lui permettent d'occuper la même empreinte spatiale.

Intervenant 14:48

Ok, la première transformation, j'imagine que c'est l'identité. L'action de ne faire absolument aucune manipulation.

Intervenant 24:55

C'est ça. Et la seconde, c'est une rotation de 180 degrés sur son centre. Un demi-tour, quoi.

Intervenant 15:01

Donc notre groupe de symétrie ne contient que deux opérations. L'identité et la rotation. Si on applique la règle des invariants, pour l'identité, bon, c'est trivial.

Intervenant 25:11

Parce qu'on ne touche à rien ?

Intervenant 15:12

Bah oui. Les 49 couples ordonnés restent identiques à eux-mêmes. On a donc 49 invariants.

Intervenant 25:18

Parfait. Maintenant, passons à la rotation de 180°. Que se passe-t-il si l'on prend ce fameux domino 2-5 et qu'on le fait pivoter ?

Intervenant 15:26

Il devient un 1-5-2. Il a changé d'état numérique de notre point de vue, donc ce n'est pas un invariant.

Intervenant 25:31

Du coup, lesquels survivent à cette rotation ?

Intervenant 15:33

Retourner, ça reste un bon vieux 3-3.

Intervenant 25:35

Et des doubles, on en a combien ?

Intervenant 15:37

On n'en a que 7. Donc 7 invariants pour la rotation.

Intervenant 25:40

Le calcul final se met en place. Nous avons nos invariants. 49 pour l'identité et 7 pour la rotation.

Intervenant 15:47

Et la formule exige d'en faire la moyenne sur l'ensemble des transformations qui sont au nombre de 2.

Intervenant 25:52

Exact.