Un problème de maths vieux de 25 ans résolu sur 4chan

Mathieu Grumiaux

26 octobre 2018 à 06h31

Sans le savoir, un utilisateur cherchant le meilleur ordre pour regarder un anime japonais a résolu un problème mathématique insoluble depuis 25 ans.

Comment un anime japonais peut mener à la résolution d'un problème mathématique vieux de 25 ans? C'est une question que se posent aujourd'hui les chercheurs à la lecture de ce message posté sur le site 4chan.

A partir d'un anime, une formule mathématique complexe

Un utilisateur anonyme essayait de trouver le meilleur ordre pour regarder les 14 épisodes d'un animé intitulé Haruhi. La particularité de cette œuvre est que chaque épisode se déroule dans des époques différentes. Sa diffusion de l'époque avait été non-linéaires et les aficionados de l'anime tentent depuis des années de trouver l'ordre le plus efficace et logique narrativement pour regarder la saison.

Sans le savoir, cet utilisateur a trouvé la réponse à un problème mathématique appelé «superpermutations ». En mathématiques, une permutation est l'ordre d'un ensemble de nombres. En termes d'anime, une des permutations de Haruhi serait de regarder les 14 épisodes dans l'ordre de leur diffusion selon The Verge.

La méthodologie donnée par le contributeur anonyme de 4chan a été ensuite traduite par Jay Pantone, un mathématicien à l'Université de Marquette dans une forme plus générale et compréhensible par des mathématiciens. Et pour lui, le raisonnement tient la route.

Prises sous un angle précis, tout le monde peut faire des maths

Robin Houston, informaticien et mathématicien, a été le premier a repéré le post et à le partager sur Twitter. Il explique qu'avec le problème Haruhi, les gens recherchaient la superpermutation la plus courte possible pour l'ensemble des 14 épisodes. Mais personne n'a trouvé de formule permettant de résoudre ce problème. Les travaux de 1993 suggéraient une partie de cette solution. Mais en 2014, il a découvert que les calculs utilisés dans le problème de 1993 ne fonctionnaient pas pour les ensembles contenant plus de six nombres.

Le contributeur anonyme apporte lui une solution pour trouver le plus petit nombre afin d'arriver à la solution. Selon les deux chercheurs, il faut regarder au moins 93 884 313 611 épisodes pour pouvoir regarder la saison dans n'importe quel ordre possible. À partir de ce chiffre insensé, il faudra encore de nombreuses recherches afin de trouver l'ordre le plus juste pour regarder Haruhi dans le futur. Mais cet exemple que les maths, sous un angle plus ludique, sont accessibles à tous.

Mathieu Grumiaux

Grand maître des aspirateurs robots et de la domotique qui vit dans une "maison du futur". J'aime aussi parler films et séries sur les internets. Éternel padawan, curieux de tout ce qui concerne les n...

Lire d'autres articles

Commentaires (21)

gvia66

J’avais bien aimer, mais finalement c’est quoi l’ordre des 14 épisodes ?

GBAR4

" Selon les deux chercheurs, il faut regarder au moins 93 884 313 611 épisodes pour pouvoir regarder la saison dans n’importe quel ordre possible" Comment arrivent-ils à cette conclusion ? pour moi 14! = 87 178 291 200 Cela fait beaucoup (!!!) moins non ?

Nehi

“d’un animé intitulé Haruhi” intitulé La mélancolie de Suzumiya Haruhi.

Rambo_z_a_Clown

La conclusion est ahurissante à mes yeux !

chabgyver

J’ai rien compris. Dans science et avenirs, ils seront peut-être plus clairs

Alexol

Je pense que c’est parce que quand tu fais une série tu enchaines les séries. Je ne suis pas clair je m’explique, par ex avec 3 épisodes tu peux faire : 1 2 3 1 3 2 Là ou tu penses que tu enchaines 2 séries de chiffres en fait je vois quatre séries 123 , 231, 313, 132 donc en fait on a plus en moins d’itérations que les 14! ? Ici on a 4 séries différentes dont 1 à rejeter (313 n’étant pas utile).

Alexol

Pardonne moi j’ai encore moins bien lu ton commentaire. En effet je ne sais pas comment ils ont fait pour trouver plus ^^ que les 14!

la_girafe1

L’article est soit trop précis, soit pas assez. Personnellement, je n’ai pas compris quel était le problème mathématique vieux de 25 ans, ni comment il l’avait résolu. Même si c’est très technique, je pense qu’il y a moyen de vulgariser ça.

Keorl

Alexol, tu as oublié que les 93 milliars ne sont pas un nombre de permutations mais un nombre d’épisodes. Dans ton exemple avec 1 2 3, tu as 6 permutations (3!). Toutes les regarder indépendamment ferait regarder 18 épisodes (6x3), mais comme tu l’as fait remarquer il doit exister un ordre qui contient toutes les permutations plus rapidement (le tien contient 123 231 132 mais aussi 312, donc tu as regardé 4 ordres sur les 6 ordres … en “seulement” 6 épisodes mais bel et bien plus que 4). Il doit y avoir une combinaison optimisée pour regarder un minimum d’épisodes et avoir vu tous les ordres. C’est ce qu’on a avec les 93 milliards pour 14 épisodes.

LeToi

+10000…

radiusMini

C’est parce que 14! c’est le nombre de combinaison possible, mais dans chaque combinaison tu regarde 14 épisodes, donc sans “optimization”, il faut regarder 14 x 14! épisode, et non pas 14! autrement, si il y a 2 épisodes: 2! combinaison= 2 combinaison: 1 puis 2 ou 2 puis 1 donc 4 épisode à regarder le 1 puis le 2 (1ere combi) puis le 2 puis le 1 (2eme combi) En resolvant le problème mathematique (bien trivial ici avec 2 épisodes), on regarde 1 puis 2 puis 1 et on a vu toutes les combinaisons possible en regardant que 3 épisodes

radiusMini

sauf que 14! c’est le nombre de combinaison et que chaque combinaison à 14 épisodes, donc la réponse “naive” est 14 x 14! et pas juste 14! Dans ton example, tu as 3 épisodes, ce qui fait 3! combinaison possible (donc 6), donc tu dois regarder 6 fois 3 épisodes = 18. Evidement comme tu l’explique si on enchaine 1 2 3 puis 3 1 2, on va pas regarder deux fois de suite le ‘3’ et donc on regarde que 5 épisode (1, 2, 3, 1, 2) au final pour une serie de 3 épisodes il n’y a que 9 épisode à echainer pour avoir vu tout les combinaison possible

radiusMini

J’essaye de vulgariser: Tu as une serie de 2 épisodes, tu veux regarder tout les épisodes dans tout les ordres possible. Tu peux regarder le 1 puis le 2 ou le 2 puis le 1 Donc tu regardes 1, 2, 2 ,1. Comme on le voit ici, on regarde 2 fois de suite l’épisode 2, ce qui n’a pas de sens, on va donc voir 1, 2, 1 et on aura vu tout les ordres possibles (1 puis 2 et 2 puis 1). Il y a donc ici 3 épisodes à regarder pour voir les épisodes dans tout les ordres possible. La question mathématique qui se pose est comment trouver mathématiquement que la réponse est 3. Ici avec 2 épisodes c’est bien trivial à trouver “à la main” mais avec 3 épisodes c’est déjà plus compliqué, il y a 6 combinaisons possible (1, 2, 3 | 1, 3, 2 | 2, 1, 3 | 2, 3, 1 | 3, 1, 2 | 3, 2, 1) Si tu regardes naivement chaque combinaisons, tu va regarder 18 épisodes ( 3 épisode x 6 combinaison) Alors que “optimisé” tu peux regarder que 9 épisodes: 1 3 2 1 3 1 2 3 1 1 3 2 1 peux se redecomposer en (1 3 2) et (3 2 1) (meme principe de précedement mais ici il y l’enchainement des épisode 3 puis 2 qu’on ne regarde pas “en double”. La decomposition total de 1 3 2 1 3 1 2 3 1 est : (1 3 2) (3 2 1) (2 1 3) (3 1 2) (1 2 3) (2 3 1). Donc la question mathématique: comment passer de (1, 2, 3 | 1, 3, 2 | 2, 1, 3 | 2, 3, 1 | 3, 1, 2 | 3, 2, 1) à 1 3 2 1 3 1 2 3 1

cityhunter67

Après avoir lu les coms j’ai juste envie de dire : Vous vous foutez de notre gueule ?

mecatroid

Ah ben voilà, comme ça c’est enfin clair. Merci RadiusMini, +1

wartillo

Pourtant trouver le nombre de d’ordre possible est relativement simple. Considérant que chaque épisode est écouté une seule fois, cela ne serait pas plus simple de revenir au probabilité : 141312111098765432*1. Àprès chaque épisode il y à une de moins à regarder. Toutefois je ne crois pas que les maths vont aider à connaitre l’ordre précis à regarder la série. Après quelques visionnements de la série il est possible de déduire l’ordre logique par l’histoire.

Rapidkiller

Attention Clubic … Résolu par un chercheur américain Jay Pantone) après s’être inspiré d’un commentaire d’un membre 4Chan … ce n’est pas un membre 4Chan qui a apporté la réponse mathématique à la question : « Vous avez n épisodes d’une série TV. Vous voulez regarder les épisodes dans chaque ordre possible. Quel est le plus petit nombre d’épisodes que vous auriez à regarder pour y arriver ? Ceci inclut de pouvoir regarder plusieurs fois un même épisode, et que leur ordre soit continu. » Quant à la réponse, elle est donnée dans l’article mais irréalisable Il faudrait regarder au moins 93 884 313 611 épisodes pour être sûr d’avoir toutes les combinaisons possibles (bon courage !!)

fennecpoilu

Numérama: “Voici donc la question à l’origine du sujet de discussion de 4chan, publié le 17 septembre 2011 : « Vous avez n épisodes d’une série TV. Vous voulez regarder les épisodes dans chaque ordre possible. Quel est le plus petit nombre d’épisodes que vous auriez à regarder pour y arriver ? Ceci inclut de pouvoir regarder plusieurs fois un même épisode, et que leur ordre soit continu. »” IL FAUDRAIT REGARDER AU MOINS 93 884 313 611 ÉPISODES POUR ÊTRE SÛR D’AVOIR TOUTES LES COMBINAISONS POSSIBLES

fennecpoilu

2011 quand même

wannted

j’ai rien compris

Voir tous les messages sur le forum

Un problème de maths vieux de 25 ans résolu sur 4chan

A partir d'un anime, une formule mathématique complexe

Prises sous un angle précis, tout le monde peut faire des maths

A découvrir en vidéo

Commentaires (21)

Top app & logiciels

Sur le même sujet