Sur le carré dessiné ci-dessous, nous avons placé au hasard 50 points — qui peuvent par exemple représenter des villes sur une carte — et relié certains d’entre eux (marqués en rouge) de façon à ce que le chemin obtenu se dirige toujours vers le nord-est.

Le chemin que nous avons tracé relie 9 villes. Aurait-on pu trouver un autre chemin qui en relie davantage? Il se trouve que non, comme on peut s’en convaincre après une longue recherche exhaustive (qu’il est préférable de confier à un ordinateur) [1].

Bien sûr, si les points avaient été disposés de manière différente, il aurait été possible de trouver un chemin passant par plus de villes: voyez, par exemple, le carré représenté ci-dessous où on a pu exhiber un parcours en reliant 14!

Quelques statistiques

Nous pouvons maintenant tenter et retenter l’expérience un grand nombre de fois et faire des statistiques. Voici un diagramme en bâtons qui indique combien de fois chaque «nombre maximal de villes visitées par un chemin nord-est» a été obtenu pour un total de 1000 expériences.

Nous constatons que ce nombre reste concentré autour de sa valeur moyenne qui est entre 11 et 12. Ce diagramme nous apprend encore plus précisément qu’il serait très étonnant d’obtenir, de façon aléatoire, une configuration pour laquelle le plus long chemin nord-est passe par un nombre de villes qui n’est pas compris entre 9 et 14. Notez bien cependant que cela n’est pas impossible: il se peut même, à vrai dire, qu’il existe un chemin nord-est passant par toutes les villes dans le cas où celles-ci seraient alignées sur la diagonale sud-ouest / nord-est du carré. De même, il ne pourrait exister aucun chemin nord-est reliant deux villes si toutes les villes étaient alignés sur l’autre diagonale. De telles configurations sont toutefois extrêmement peu probables.

Sur la dépendance par rapport au nombre de villes

Que se passe-t-il à présent si nous ne partons pas de 50 villes, mais de 100 ou encore davantage? Bien entendu, il sera alors logiquement possible de trouver un chemin «nord-est» passant par plus de villes. Mais dans quelles proportions cette augmentation aura-t-elle lieu? Voici un tableau qui fait apparaître la moyenne de nombre maximal de villes visitées par un chemin nord-est en fonction du nombre de villes total.

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Nombre de villes} & 100 & 200 & 300 & 400 & 500 & 600 & 700 & 800 & 900 \\ \hline \begin{array}{c}\text{Nombre maximal de villes} \\ \text{visitées par un chemin nord-est}\end{array} & 16,\!7 & 24,\!5 & 30,\!6 & 35,\!7 & 40,\!3 & 44,\!2 & 48,\!2 & 51,\!8 & 55,\!0 \\ \hline \end{array}\]

Nous remarquons que, certes, la deuxième ligne croît en même temps que la première mais elle le fait à une allure moindre. Lorsque l’on passe par exemple de 200 à 800 villes, le nombre de villes est multiplié par 4 alors que le nombre correspondant sur la seconde ligne du tableau est seulement multiplié par 2 environ. De même, lorsque l’on passe de 100 à 900 villes, le nombre de villes est multiplé par 9 et celui de la seconde ligne par 3 environ.

En fait, il se trouve qu’en moyenne, le nombre maximal de villes visitées par un chemin nord-est varie proportionnellement non pas au nombre de villes mais à sa racine carrée! Ceci est cohérent avec les observations qui ont été faites: en effet, la racine carrée de 4 (qui est le facteur multiplicatif lorsqu’on passe de 200 à 800 villes) est 2 (qui est le facteur multiplicatif correspondant sur la seconde ligne du tableau) et, de même, celle de 9 est 3. Par ailleurs, remarquons que ce comportement n’est en réalité pas surprenant car, comme on le voit sur la vignette de cet article, lorsque le nombre de villes est grand, un chemin nord-est optimal aura tendance à suivre la diagonale autour de laquelle se trouve un nombre de villes proportionnel à la racine carrée du nombre total de villes (la diagonale est de dimension 1, alors que le carré lui-même est de dimension 2).

L’exposé de Valentin Feray

Dans son exposé au séminaire Mathematic Park, Valentin Feray aborde ces questions et donne plusieurs éléments qui mettent en avant la dépendance en la racine carrée que nous venons d’évoquer. Attention, dans son exposé, Valentin adopte une présentation différente du problème (tri d’un jeu de cartes) et n’explique le rapport avec «le plus long chemin nord-est» qu’après une heure d’exposé environ. Mais, ne vous inquiétez pas, il traite bien, dès le début, la même question.

Visionnez-le ci-dessous. Attention, certains passages de cet exposé sont classés hors-piste.