Futurama

Guego · September 2010

Bonjour,

L'épisode 10 de la dernière saison de futurama soulève un problème mathématique. Pour ceux qui suivent la série, attention, ce qui suit révèle une partie de l'épisode !

Je détaille. Le professeur invente une machine qui permet à un couple d'échanger leur corps (mettre l'esprit de l'un dans le corps de l'autre et vice-versa). Mais cet échange est irréversible : un couple "qui a été échangé" ne peut plus réutiliser la machine (éventuellement, chacun peut ensuite s'échanger avec une tierce personne, mais le couple lui-même ne peut plus). Ensuite, je ne détaille pas l'épisode, mais bien sûr, tout le monde s'échange dans tous les sens.
Problème : Comment revenir à la situation de départ ?
Ils réfléchissent et concluent qu'avec l'aide de 2 personnes auxiliaires, c'est possible, ce qu'ils mettent en oeuvre et à la fin, chacun a retrouvé sa peau (y compris les 2 personnes auxiliaires).

Question : comment ont-ils trouvé ce "2" ? Y a-t-il un algorithme qui permette (sachant les échanges déjà effectués, et en utilisant des personnes auxiliaires) de revenir à la situation de départ ?

Formulé mathématiquement : on part d'une permutation écrite comme produit de transpositions. Comment écrire l'inverse comme produit de transpositions (éventuellement en rajoutant des personnes à permuter) avec la condition qu'on ne doit pas utiliser 2 fois la même transposition, ni une transposition utilisée "dans le sens aller" ?

chris93 · September 2010

Rhoooooooooooooo les copieurs, il y a la même situation dans un épisode de Stargate...Et, effectivement, ils utilisent deux autres personnes pour retrouver leurs corps respectifs...

Parcontre, je ne sais pas répondre à ta question 8-)

Lucas · September 2010

Tout ça fait une raison de plus de regarder cette géniale série qui est absolument délirante!

(Il y a souvent des références à stargate, c'est peut-être pas vraiment du plagiat mais un hommage)

Molinier · September 2010

Il me semble qu'il vaut mieux décomposer ta permutation en cycles disjoints. On commence par traiter le cas des transpositions, si l'on note A et B les deux éléments qu'on ajoute on voit que sans échanger A et B on peut inverser la transpositions, ce qui nous permets déjà d'inverser toutes les transpositions de la décomposition (puisqu'on n'utilise pas de transposition entre A et

.
Pour les k cycles, on peut se ramener aux transpositions. En effet, on passe de l'état (1,...,k) en échangeant 1 avec 2, puis 3 etc... (c'est là justement que tu te trompais en utilisant des décompositions en permutations sans support disjoints)
puis on recommence en échangeant 2 avec 3, 4 jusqu'à k-1 etc... jusqu'à obtenir (k,k-1,...1)

Futurama

Réponses

Bonjour!

Catégories

In this Discussion