Superpermutations

En 2006 est diffusé pour la première fois à la télévision japonaise l’adaptation du roman : Suzumiya Haruhi no Yûutsu. Cette diffusion a cela de particulier que les quatorze épisodes qui constituent la série sont diffusés dans le désordre. Elle provoque ainsi un engouement à l’échelle nationale et internationale si bien qu’une grande communauté de fans se constitue autour de cette série. En 2018, sur l’un des forums internet fréquenté par ces fans, l’un d’eux pose la question suivante :

« Est-il possible de regarder les épisodes de la série dans tous les ordres possibles ? »

Le nombre d’épisode étant fini, c’est naturellement possible, mais, plus pertinent : est-ce possible en temps raisonnable ? Il s’agit ainsi de regarder chacune des 14! permutations des 14 épisodes de la série. Un épisode faisant environ 20 minutes, on trouve une durée de

    \[ 14\times 14!\times 20 = 464\,420 \text{ si\`ecles.} \]

À titre indicatif, il s’agit approximativement de la durée qui nous sépare de l’apparition des premiers primates sur Terre.

On pourrait conclure sur l’impossibilité de regarder les épisodes de la série dans tous les ordres possibles, mais ce serait sans compter sur l’ingéniosité de certains internautes qui ont l’idée suivante. Simplifions d’abord le problème, et supposons que la série ne compte que deux épisodes : 1 et 2. Plutôt que de regarder d’abord les épisodes dans l’ordre 12, puis dans l’ordre 21 (on a donc regardé quatre épisodes), regardons-les dans l’ordre 121 ! De cette manière, on aura regardé les épisodes dans tous les ordres possibles, mais en s’économisant un épisode.

De même, pour une série de trois épisodes : 1, 2 et 3, plutôt que de regarder chacune des permutations :

    \[123.132.213.231.312.321\quad \text{(18 \'episodes)}.\]

Regardons-les d’un coup dans l’ordre suivant :

    \[ 123121321\quad \text{ (9 \'episodes).}\]

On peut vérifier aisément que toutes les permutations des 3 épisodes sont contenues dans le mot ci-dessus. Ces mots, qui contiennent toutes les permutations sur un alphabet de n symboles ont un nom en mathématique : il s’agit de superpermutations, et l’on peut réécrire notre problème : « Quelle est la plus petite superpermutation sur un alphabet de n symboles ? » Dans notre exemple, n = 14.

Plan

  1. Définitions & Propriétés
  2. Superpermutation Minimale
  3. La théorie des graphes à la rescousse
1 Cliquer pour recommander cet article