Deux minutes pour le théorème de Futurama

J'avais déjà parlé des références mathématiques dans la série Futurama (là-bas), mais je n'y avais qu'à peine développé LE théorème de futurama, celui qui parle de permutation. En environ deux minutes, voilà qui est maintenant fait :

Transcription :
Le 19 août 2010, la chaîne américaine Comedy Central diffuse "Le prisonnier de Benda", dixième épisode de la sixième saison de Futurama, la deuxième série de Matt Groening après les Simpsons. L'épisode est exceptionnel puisque, pour la première fois à la télévision, une intrigue est résolue à l'aide d'un théorème avancé de la théorie des groupes. Il faut dire que le producteur de la série est David X Cohen, diplomé en informatique théorique à l'Université de Californie, et que l'épisode en question a été écrit par Ken Keeler, diplomé à Harvard en mathématiques appliqué.
Ca tombe bien, j'ai deux minutes pour en parler !
Dans cet épisode, le professeur Farnsworth met au point une machine à échanger les corps qui, comme son nom l'indique, permet d'intervertir le corps et l'esprit entre deux personnes.
Pour le premier essai, le professeur échange son corps avec celui de son étudiante Amy.
Le problème, c'est que à cause des défenses imunitaires du cerveau, l'échange ne fonctionne que dans un seul sens : le professeur et Amy ne peuvent pas faire l'échange contraire.
Pour retrouver leurs corps d'origine, leur seule solution est d'utiliser un corps de transition : ça sera celui du robot Bender !
C'est donc naturellement que'il accepte d'échanger son corps avec celui de Amy. L'esprit du professeur se retrouve alors dans le corps de Bender, l'esprit de Bender est dans le corps de Amy et l'esprit Amy est dans le corps du professeur.
Maintenant, si l'on échange les corps de Bender et du professeur, le corps de Bender possèdera l'esprit de Amy, et le corps du professeur retrouvera son corps original. Oui, mais, les corps de Amy et Bender ont déjà été intervertis, l'échange retour est donc impossible !

Mais les échanges ne s'arrêtront pas là, puisque /

• Amy, échange son corps de professeur avec celui de Leela
• Bender échange son corps de Amy avec celui du seau robotique
• Fry et Zoidberg s'échangent leur corps
• Bender échange son corps de seau avec celui de l'empereur Nikolaï de l'empire robot-hongrois
• Et enfin, Amy échange son corps de Leela avec celui de Hermès.

C'est donc une dizaine de corps et d'esprit qui sont mélangés. Comment vont-ils s'en sortir ?

Ce problème s'inscrit dans le domaine de l'algèbre appellé théorie des groupes et, plus particulièrement, dans celui des permutations.

Une permutation, c'est donc l'opération qui consiste à réarranger un certain nombre d'objets. Dans le cas présent : c'est la permutation de ces 9 corps qui nous intéresse.
Une propriété essentielle de cette théorie, c'est que n'importe quelle permutation correspond toujours à la composition de une ou plusieurs permutations circulaires disjointes. Pour le comprendre, il suffit de regarder dans quel corps se trouve chacun des espritS.
L'esprit du professeur se trouve dans le corps de Bender, l'esprit de Bender est dans le corps de Nikolaï, l'esprit de Nikolaï est dans le corps du robot de nettoyage, l'esprit de ce robot est dans le corps de Amy, l'esprit de Amy est dans le corps de Hermès, l'esprit de Hermès est dans le corps de Leela, et enfin, l'esprit de Leela est dans le corps de le corps du professeur. La boucle est bouclée. A côté de cela, il reste Fry et Zoidberg, qui ont échangé leur corps indépendament du reste du groupe.
La permutation de ces 9 personnages est donc composée de deux cycles :  un cycle de 7 personnages, appellé 7-cycle et un cycle de 2 personnages, appellé transposition.
C'est finalement une suite de transposition qui a engendré la permutation finale.
La question est donc de savoir quelle est la suite de transpositions à effectuer pour que tout rentre dans l'ordre, et le nombre minimal de corps de transition à apporter.

La réponse est donnée dans la série par Sweet Clyde et Bubble Gum Tate, deux basketteurs de l'équipe des Harlem Globtrotter. Il se trouve en effet que, dans le futur, cette équipe de basket n'est composéee que de scientifiques.
Ils démontrent donc dans l'épisode que deux corps de substitutions suffisent toujours, quel que soit la façon dont les autres membres auront été mélangés, et qu'il faudra a peu près autant d'échanges que de personnages présents. C'est ce théorème que l'on appelle aujourd'hui "théorème de Futurama", que l'on doit à Ken Keeler, le scénariste de l'épisode.

Démonstration :
Procédons dans le cas où la permutation n'est qu'un simple cycle. Pour simplifier, supposons qu'il contient 5 personnes, où l'esprit de 1 est dans le corps de 2, l'esprit de 2 est dans le corps de 3, etc., et ajoutons deux nouveaux corps X et Y, qui n'ont jamais permuté avec l'une de ces 5 personnes.
Dans un premier temps, on va permuter le corps additionnel Y avec le corps 1 et X avec le corps 2.
Dans un deuxième temps, on va remonter le corps Y jusqu'à l'esprit de X. Pour cela on échange les corps Y et 5, puis Y et 4, puis Y et 3, puis Y et 2.  
Il n'y a plus qu'à échanger les corps de X et de 1 pour que les 5 premiers esprits aient retrouvé leur corps original.
A ce point, les corps de X et Y sont échangés, il suffit d'une dernière transposition pour que tout rentre dans l'ordre.

Dans le cas général, une permutation est composée de plusieurs cycles.il suffit d'appliquer cette suite de transpositions sur chacun des cycles, et le tour est joué. CQFD

On peut maintenant appliquer le théorème à la permutation des personnages de Futurama, en ajoutant les nouveaux corps de Sweet Clyde et Bubblegum Tate.
Cette permutation est composée de deux cycles : le 2-cycle Fry-Zoidberg et le 7-cycle.
Commençons par remettre dans l'ordre Fry et Zoidberg :

• On échange Tate et Fry
• puis Clyde et Zoidberg
• puis Tate  et Zoidberg
• et enfin Clyde et Fry

Fry et Zoidberg ont retrouvé leur corps, tandis que Clyde et Tate l'ont échangé. Il n'y a plus qu'à s'occuper des 7 autres personnages :

• On échange Tate et le professeur
• puis Clyde et Bender
• puis Tate et Leela
• puis Tate et Hermès
• puis Tate et Amy
• et ainsi de suite jusqu'à l'échange entre Tate et Bender
• et enfin, on échange Clyde et le professeur

Chacun a retrouvé son corps, en seulement 11 échanges !

Le théorème donne donc la marche à suivre pour que chaque esprit retrouve son corps, bien que la solution ne soit pas forcément optimale, puisque ce problème aurait pu être résolu en seulement 7 opérations. Cependant, le théorème s'adapte à n'importe quel problème similaire, et pourrait un jour vous servir si vous échangez par mégarde votre corps avec celui d'un ami...

---

Sources :
Futurama, le prisonnier de Benda - saison 5 & 6
Keeler’s Theorem and Products of Distinct Transpositions, Ron Evans, Lihua Huang, Tuan Nguyen