[MATHS] Résolution du problème d'Haruhi

Le problème d'Haruhi est un problème combinatoire qui demande la plus courte suite d'épisodes d'un anime à regarder pour avoir toutes les combinaisons de celui ci (sans répétition sinon on aurait le même épisode à l'infini) :

Exemple : avec les épisodes A, B et C.
La suite A,B,C,A,B,A,C,B,A est une suite valide car elle contient tous les arrangement possibles, à savoir :
ABC, ACB, BAC, BCA, CAB et CBA.

C'est la plus courte série possible (source : croyez moi, la démonstration va arriver plus tard, je suis à la gare, j'ai pas le temps de le démontrer là, mais vous pouvez brute force et vous verrez que c'est vrai)

Bref, pour 3 épisodes on a la série la plus courte qui est composée de 9 éléments.

Pour 3 épisodes, c'est 9.
Pour 2 épisodes, c'est évidement 3 : A,B,A.
Pour 1 épisode, c'est encore plus évident que c'est 1 : A.

On a la suite 1, 3, 9. Il serait très tentant de dire que le prochain est 27 Mais en fait non, c'est 33 pour 4 épisodes :
ABCDABCADBCABDCABACDBACBDACBADCBA

Bref, la formule donnant la suite la plus courte est assez simple mais longue à démontrer.
Pour 2 épisodes c'est :
2×(1!) + 1×(2!-1!) = 2+1 = 3
Pour 3 épisodes c'est :
3×(1!) + 2×(2!-1!) + 1×(3!-2!) = 3+2+4 = 9
Pour 4 épisodes c'est :
4×(1!) + 3×(2!-1!) + 2×(3!-2!) + 1×(4!-3!) = 4+3+8+18 = 33

Pour 14 épisodes comme pour le problème d'Haruhi, c'est simplement la même chose que plus haut.

C'est la somme de n = 2 à 14 de : (15-n) × (n! - (n-1)!). à quoi on ajoute 14 car on a commencé par n=2 pour éviter d'avoir (1!-0!) en facteur

Pour 14 on a : 93 928 268 313
https://image.noelshack.com/fichiers/2021/42/1/1634569874-screenshot-20211018-170949-chrome.png

Un mec sur 4chan a trouvé les encadrements de ce nombre mais sans le trouver exactement. Perso je l'ai trouvé exactement + j'ai la démonstration mais j'ai pas le temps de la poster là, peut être ce soir ou demain matin
Vous pouvez vous amuser à vérifier que c'est correct si vous voulez. Voici ce que le gars de 4chan avait trouvé :
https://mathsci.fandom.com/wiki/The_Haruhi_Problem
Sinon sur Google : 4chan anime maths

Je up

Suffit de skip les endless eight, c'est plus simplehttps://image.noelshack.com/fichiers/2021/41/7/1634499431-kuu-sore.png

Je up une seconde fois
Et j'invoque les mathématiciens du forom, montrons à 4chan qu'on est aussi intelligents qu'eux en plus d'avoir une meilleure interface

Tu penses vraiment qu'on en a qqch à foutre?

Attend, y'a un animé qu'il faut regarder dans le désordre chronologique pour comprendre le fil de l'histoire ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

[17:30:19] <je_vi_je_visser>
Attend, y'a un animé qu'il faut regarder dans le désordre chronologique pour comprendre le fil de l'histoire ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

Oui, tu peux quand même essayer de le regarder en fonction de l'ordre chronologique de diffusion mais tu vas être larguéhttps://image.noelshack.com/fichiers/2021/41/7/1634499509-hina-confuse.png

Le 18 octobre 2021 à 17:25:17 :
Tu penses vraiment qu'on en a qqch à foutre?

Ahi, je m'attendais à au moins une personne intéressée par un problème qui est vieux de presque 30 ans et qui n'a pas été résolu

Le 18 octobre 2021 à 17:31:44 :

[17:30:19] <je_vi_je_visser>
Attend, y'a un animé qu'il faut regarder dans le désordre chronologique pour comprendre le fil de l'histoire ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

Oui, tu peux quand même essayer de le regarder en fonction de l'ordre chronologique de diffusion mais tu vas être larguéhttps://image.noelshack.com/fichiers/2021/41/7/1634499509-hina-confuse.png

Seulement si tu as 50 de qi.

Oui c'était grâce à 4chan, ils ont cité "anonymous" dans le papier de recherche

Le 18 octobre 2021 à 17:32:30 :
Oui c'était grâce à 4chan, ils ont cité "anonymous" dans le papier de recherche

Justement, le papier ne donnait qu'un intervalle

https://www.numerama.com/sciences/435102-un-anonyme-de-4chan-a-une-solution-a-un-probleme-de-math-et-la-science-ne-sait-pas-comment-lutiliser.html

Apparemment le gars l'a déjà résolu du coup non ? : (

Et j'ai eu du mal à comprendre le problème, mais je crois avoir compris : En gros pour regarder 3 épisodes dans tous les ordres possibles, il faudrait théoriquement 3!=1*2*3=6 mais l'idée du truc c'est de réduire ce nombre en écrivant des permutations possibles à la suite c'est ça ? Genre au lieu de devoir regarder A,B,C puis C,A,B tu peux direct faire A,B,C,A,B de sorte à que les deux permutations se retrouvent dans ta série c'est ça ? C'est intéressant

Du coup pour 14 épisodes, pour regarder tous les épisodes dans tous les ordres possibles il faudrait donc regarder 93 928 268 313 épisodes
au minimum c'est ça ?

C'est plus grand que 14! = 87 178 291 200 donc ça n'a pas de sens non ? Ça devrait être plus petit non ?

Le 18 octobre 2021 à 17:40:29 :
https://www.numerama.com/sciences/435102-un-anonyme-de-4chan-a-une-solution-a-un-probleme-de-math-et-la-science-ne-sait-pas-comment-lutiliser.html

Apparemment le gars l'a déjà résolu du coup non ? : (

Et j'ai eu du mal à comprendre le problème, mais je crois avoir compris : En gros pour regarder 3 épisodes dans tous les ordres possibles, il faudrait théoriquement 3!=1*2*3=6 mais l'idée du truc c'est de réduire ce nombre en écrivant des permutations possibles à la suite c'est ça ? Genre au lieu de devoir regarder A,B,C puis C,A,B tu peux direct faire A,B,C,A,B de sorte à que les deux permutations se retrouvent dans ta série c'est ça ? C'est intéressant

Le gars n'a su donner qu'un intervalle. Même numberphile ou Matt Parker n'ont pas semblé avoir trouvé

Mais sinon oui, tu as bien compris le but du calcul, j'aurais dû mieux expliquer

Vidéos de Numberphile et Matt Parker :
https://youtu.be/OZzIvl1tbPo
https://youtu.be/wJGE4aEWc28&t=3m38s

On voit dans la dernière vidéo que ma formule marche pour les nombres de 1 à 5 déjà. Je vais poster la démonstration plus tard, le temps de bien l'écrire

Le 18 octobre 2021 à 17:31:44 :

[17:30:19] <je_vi_je_visser>
Attend, y'a un animé qu'il faut regarder dans le désordre chronologique pour comprendre le fil de l'histoire ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

Oui, tu peux quand même essayer de le regarder en fonction de l'ordre chronologique de diffusion mais tu vas être larguéhttps://image.noelshack.com/fichiers/2021/41/7/1634499509-hina-confuse.png

Ça parle de quoi ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

Le 18 octobre 2021 à 17:43:25 :
Du coup pour 14 épisodes, pour regarder tous les épisodes dans tous les ordres possibles il faudrait donc regarder 93 928 268 313 épisodes
au minimum c'est ça ?

C'est plus grand que 14! = 87 178 291 200 donc ça n'a pas de sens non ? Ça devrait être plus petit non ?

Bah pour 3 épisodes, tu as 9 épisodes à regarder, ce qui est plus grand que 3!=6.
On a 6 combinaisons de 3 épisodes, il faut donc multiplier 3 par 6, ce qui donne 18 épisodes pour tout faire. Tu dois donc multiplier 14 par 14!, ce qui est beaucoup plus grand que 14! tout seul ou que 93kMd

Le 18 octobre 2021 à 17:45:44 :

Le 18 octobre 2021 à 17:40:29 :
https://www.numerama.com/sciences/435102-un-anonyme-de-4chan-a-une-solution-a-un-probleme-de-math-et-la-science-ne-sait-pas-comment-lutiliser.html

Apparemment le gars l'a déjà résolu du coup non ? : (

Et j'ai eu du mal à comprendre le problème, mais je crois avoir compris : En gros pour regarder 3 épisodes dans tous les ordres possibles, il faudrait théoriquement 3!=1*2*3=6 mais l'idée du truc c'est de réduire ce nombre en écrivant des permutations possibles à la suite c'est ça ? Genre au lieu de devoir regarder A,B,C puis C,A,B tu peux direct faire A,B,C,A,B de sorte à que les deux permutations se retrouvent dans ta série c'est ça ? C'est intéressant

Le gars n'a su donner qu'un intervalle. Même numberphile ou Matt Parker n'ont pas semblé avoir trouvé

Mais sinon oui, tu as bien compris le but du calcul, j'aurais dû mieux expliquer

Vidéos de Numberphile et Matt Parker :
https://youtu.be/OZzIvl1tbPo
https://youtu.be/wJGE4aEWc28&t=3m38s

On voit dans la dernière vidéo que ma formule marche pour les nombres de 1 à 5 déjà. Je vais poster la démonstration plus tard, le temps de bien l'écrire

Super intéressant clé, je vais jeter un oeil à ta formule et aux vidéos quand j'aurais le temps, gros GG à toi si tu as trouvé une bonne formule avec démonstration Je suis en L1 Maths et tu éveilles ma curiosité

Le 18 octobre 2021 à 17:49:00 :

Le 18 octobre 2021 à 17:43:25 :
Du coup pour 14 épisodes, pour regarder tous les épisodes dans tous les ordres possibles il faudrait donc regarder 93 928 268 313 épisodes
au minimum c'est ça ?

C'est plus grand que 14! = 87 178 291 200 donc ça n'a pas de sens non ? Ça devrait être plus petit non ?

Bah pour 3 épisodes, tu as 9 épisodes à regarder, ce qui est plus grand que 3!=6.
On a 6 combinaisons de 3 épisodes, il faut donc multiplier 3 par 6, ce qui donne 18 épisodes pour tout faire. Tu dois donc multiplier 14 par 14!, ce qui est beaucoup plus grand que 14! tout seul ou que 93kMd

Oui j'ai EDIT mon message après effectivemment j'avais pas compris que 14! était le nombre de combinaisons et pas d'épisode Bien vu clé

[17:46:30] <je_vi_je_visser>

Le 18 octobre 2021 à 17:31:44 :

[17:30:19] <je_vi_je_visser>
Attend, y'a un animé qu'il faut regarder dans le désordre chronologique pour comprendre le fil de l'histoire ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

Oui, tu peux quand même essayer de le regarder en fonction de l'ordre chronologique de diffusion mais tu vas être larguéhttps://image.noelshack.com/fichiers/2021/41/7/1634499509-hina-confuse.png

Ça parle de quoi ?https://image.noelshack.com/fichiers/2017/29/6/1500743424-kageyama.png

C'est l'histoire du personnage principal, Kyon, qui entre au lycée et fait la connaissance d'une fille, Suzumiya Haruhi, la protagoniste, qui possède des pouvoirs surnaturels et est capable de manipuler l'espace-temps. Il rejoint alors un club appelé la Brigade SOS avec Haruhi et d'autres membres ayant des pouvoirs spéciaux. C'est un style Slice of Life/comédie, c'est vraiment pas mal et le film est incroyablehttps://image.noelshack.com/fichiers/2021/41/7/1634499043-hina-contente.png

Le 18 octobre 2021 à 17:49:15 :

Le 18 octobre 2021 à 17:45:44 :

Le 18 octobre 2021 à 17:40:29 :
https://www.numerama.com/sciences/435102-un-anonyme-de-4chan-a-une-solution-a-un-probleme-de-math-et-la-science-ne-sait-pas-comment-lutiliser.html

Apparemment le gars l'a déjà résolu du coup non ? : (

Et j'ai eu du mal à comprendre le problème, mais je crois avoir compris : En gros pour regarder 3 épisodes dans tous les ordres possibles, il faudrait théoriquement 3!=1*2*3=6 mais l'idée du truc c'est de réduire ce nombre en écrivant des permutations possibles à la suite c'est ça ? Genre au lieu de devoir regarder A,B,C puis C,A,B tu peux direct faire A,B,C,A,B de sorte à que les deux permutations se retrouvent dans ta série c'est ça ? C'est intéressant

Le gars n'a su donner qu'un intervalle. Même numberphile ou Matt Parker n'ont pas semblé avoir trouvé

Mais sinon oui, tu as bien compris le but du calcul, j'aurais dû mieux expliquer

Vidéos de Numberphile et Matt Parker :
https://youtu.be/OZzIvl1tbPo
https://youtu.be/wJGE4aEWc28&t=3m38s

On voit dans la dernière vidéo que ma formule marche pour les nombres de 1 à 5 déjà. Je vais poster la démonstration plus tard, le temps de bien l'écrire

Super intéressant clé, je vais jeter un oeil à ta formule et aux vidéos quand j'aurais le temps, gros GG à toi si tu as trouvé une bonne formule avec démonstration Je suis en L1 Maths et tu éveilles ma curiosité

Ah bah au plaisir, je vais essayer de prendre en photo mes notes ce soir pour que vous voyiez un peu le raisonnement