Longues suites : pourquoi un ordre devient-il inévitable ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente.

Intervenant 20:02

Salut Sam.

Intervenant 10:03

Aujourd'hui, on a une mission vraiment fascinante. On va parler de l'ordre, mais de l'ordre dans le désordre.

Intervenant 20:10

VASP Programme.

Intervenant 10:11

Ouais. Posons la prémisse, tu veux bien. Si on génère une suite de nombres dans le chaos le plus absolu, le hasard pur, sans aucune règle, est-ce qu'il est possible d'y trouver une séquence parfaitement ordonnée ?

Intervenant 20:23

L'intuition nous hurle que non, en général.

Intervenant 10:26

Bah oui, l'esprit humain déteste le chaos, on cherche des motifs partout, mais on se dit que, face au hasard total, la logique finit par s'effondrer quoi.

Intervenant 20:34

Eh bien, les mathématiques prouvent très exactement le contraire.

Intervenant 10:37

C'est ça qui est dingue.

Intervenant 20:38

Ouais, c'est un paradoxe fondamental. Peu importe les efforts colossaux qu'on déploie pour créer le désordre le plus total, l'ordre parfait est littéralement inévitable, du moins pour peu qu'on observe un échantillon suffisamment grand.

Intervenant 10:54

Et c'est précisément ce qu'on va décortiquer dans cette plongée au cœur des articles du magazine Tangente. Comment les mathématiques nous garantissent que le chaos absolu n'est en fait qu'une illusion.

Intervenant 21:05

Exactement.

Intervenant 11:06

Pour ancrer ce concept qui peut paraître abstrait, commençons par une image de notre source. Une image très familière, les frères Dalton.

Intervenant 21:14

Ah oui, l'univers de Lucky Luke, c'est un excellent point de départ pour ça. Prenons les quatre frères, qu'on numérote par ordre de taille tout simplement.

Intervenant 11:21

D'accord, donc Joe est le numéro 1, le plus petit.

Intervenant 21:24

C'est ça. William et Jack sont les deux et trois. Et Averell, le plus grand, c'est le numéro 4.

Intervenant 11:29

Logique.

Intervenant 21:29

La question de l'ordre est assez triviale si on prend seulement deux frères au hasard. On aura forcément le plus petit d'abord ou le plus grand d'abord.

Intervenant 11:37

Donc soit une suite croissante, soit décroissante.

Intervenant 21:40

Voilà, ça monte ou ça descend. Mais là où ça se corse, et c'est notre vraie question de départ, c'est que se passe-t-il si on veut extraire trois Dalton de notre groupe de quatre ?

Intervenant 11:50

Et exiger qu'il soit parfaitement classé, tous les trois.

Intervenant 21:53

Tout à fait. L'intuition pourrait suggérer que sur quatre éléments, on a de la marge pour en trouver trois bien alignés.

Intervenant 12:00

On se dit qu'il y a forcément une combinaison qui marche.

Intervenant 22:02

Eh bien, c'est impossible à garantir. Il suffit de construire le bon contre-exemple. Analysons la suite donnée par l'article. Le 3, puis le 4, puis le 1 et enfin le 2.

Intervenant 12:13

Attends, je vais prendre le temps de visualiser cette suite. 3, 4, 1, 2. C'est-à-dire Jack, Avril, Joe, William.

Intervenant 22:22

C'est ça.

Intervenant 12:23

Mon but, c'est d'en extraire 3 qui soient dans l'ordre. Bon, je teste. Si j'enlève le 3 initial, il me reste 4, 1, 2.

Intervenant 22:32

Et donc ?

Intervenant 12:32

Ça descend violemment de 4 à 1, puis ça remonte à 2. Pas d'ordre.

Intervenant 22:38

Exact, pas monotone. Essaye la suite.

Intervenant 12:40

Si j'enlève le 4, j'ai 3, 1, 2. Même problème, ça descend, puis ça monte. Si j'enlève le 1, ça donne 3, 4, 2. Ça monte, puis ça chute. C'est ça. Et enfin, si j'enlève le dernier, le 2, j'obtiens 3, 4, 1. Mais c'est fou ! Absolument aucune de ces combinaisons n'est bonne.

Intervenant 22:59

Le constat est sans appel, oui.

Intervenant 13:01

C'est presque frustrant en fait. Aucune n'est dans un ordre purement croissant ou décroissant. L'ordre monotone, comme on dit. Ici, le chaos semble avoir gagné la manche.

Intervenant 23:10

C'est vrai. Avec quatre éléments, le désordre peut temporairement triompher. Mais c'est ici que les lois de l'univers mathématique basculent, tu vois ?

Intervenant 13:18

Hein ? Le retournement de situation.

Intervenant 23:21

Puisque quatre éléments garantissent rien du tout, introduisons une seule variable en plus. Imaginons l'arrivée d'un mystérieux cinquième Dalton. Les nombres de 1 à 5.

Intervenant 13:31

Donc juste un seul élément de plus et la règle change complètement.

Intervenant 23:36

Radicalement. C'est la première grande révélation de ce domaine. Avec une suite de cinq éléments, il y a 120 permutations possibles.

Intervenant 13:44

120 façons de les mélanger, ok.

Intervenant 23:46

Eh bien les mathématiques démontrent qu'on pourra toujours, sans la moindre exception, extraire une sous-suite monotone de longueur 3. Le chaos total est définitivement vaincu dès l'instant où le cinquième élément entre en scène.

Intervenant 13:59

C'est fascinant de voir qu'un système passe de l'incertitude totale à la certitude absolue juste par l'ajout d'une unité quoi.

Intervenant 24:06

C'est la beauté de ces théorèmes.

Intervenant 14:07

Mais du coup, poussons le raisonnement un peu plus loin. On a garanti un ordre de longueur 3. Et si on est un peu plus exigeant ?

Intervenant 24:14

C'est-à-dire ?

Intervenant 14:15

Si on cherche à extraire une suite ordonnée de 5 éléments, pas juste 3, mais 5, comment on fait pour éviter cet ordre le plus longtemps possible et construire la pire suite, la plus chaotique ?

Intervenant 24:26

Ah ! Pour esquiver une sous-suite monotone de longueur 5, l'ingénierie mathématique demande beaucoup plus de matériel,

Intervenant 14:32

en fait. Il nous faut combien de Dalton pour fuir l'ordre de longueur 5 ?

Intervenant 24:36

Plus précisément, on va devoir utiliser 16 éléments. Les nombres de 1 à 16. Et pour organiser ce chaos maximal, on ne va pas les placer n'importe comment.

Intervenant 14:47

Bah oui, comment on les dispose intérieurement ? On ne va pas juste les jeter au hasard. Il doit y avoir une structure derrière cette fuite de l'ordre.

Intervenant 24:54

Une marche.

Intervenant 14:55

Ok, un escalier.

Intervenant 24:56

Sur chaque marche, on va placer quatre nombres. Mais la subtilité, c'est que chaque marche fonctionne comme un petit toboggan qui nous fait glisser vers l'arrière.

Intervenant 15:05

Un escalier avec des toboggans. Ok, je visualise. Donc sur la première marche tout en bas, on met les nombres de 1 à 4, mais on les fait glisser à l'envers.

Intervenant 25:15

Exactement. Le premier bloc de nombres, ce sera 4, 3, 2, 1.

Intervenant 15:20

D'accord.

Intervenant 25:21

Ensuite, on monte sur la deuxième marche et on fait pareil avec les quatre nombres suivants. Donc 8, 7, 6, 5. Ah

Intervenant 15:28

ouais. La troisième marche, ça serait 12, 11, 10, 9.

Intervenant 25:33

C'est ça. Et la dernière marche, tout en haut, 16, 15, 14, 13.

Intervenant 15:38

Je vois parfaitement la forme que ça prend. Du coup, si on lit la suite d'un bout à l'autre, on a une ligne qui descend de 4 à 1, puis qui fait un bond énorme vers le haut pour atterrir à 8, qui redescend jusqu'à 5, qui rebondit à 12. C'est une structure en dents de scie super agressive. Et dans ces 16 nombres, tu me dis qu'aucune suite de 5 ne s'aligne.

Intervenant 25:58

Aucune. Et la preuve repose sur un outil fondamental en mathématiques qu'on appelle le principe des tiroirs.

Intervenant 16:04

Ah, le fameux principe des tiroirs.

Intervenant 26:06

L'idée de base est super simple.