Coureur solitaire et forêts impénétrables

Piste rouge Le 28 janvier 2017  - Ecrit par  Pierre-Antoine Guihéneuf Voir les commentaires (1)

Après avoir carrelé de manière originale, on continue d’explorer les comportements bizarres des cubes en grandes dimensions, à travers la conjecture du coureur solitaire.

Bob est coureur de fond. Tous les soirs, il règle son réveil pour pouvoir, le lendemain à l’aube, effectuer pendant cinquante cinq minutes les cinq mille foulées qui lui fournissent sa dose de dopamine quotidienne : comme beaucoup d’autres, Bob est devenu accro à la course à pied. Tous les matins, il parcourt consciencieusement douze tours d’un circuit d’exactement 1 km. Ça lui laisse le temps de penser à beaucoup de choses, parfois à rien. D’observer les autres fanatiques de l’aérobie qui, comme lui, occupent quasiment un vingt-quatrième de leur temps à tourner en rond.

À force de ne penser à rien trois mille trois cents secondes par jour, le mardi sept mai à sept heures vingt huit, au moment de boucler son premier tour de piste, Bob se rend soudainement compte qu’au cours de son parcours il y a toujours un moment où les autres coureurs sont tous loin de lui. Et il se demande bien pourquoi.

Bob commence par essayer de se faire une image simple de la situation. Il y a $n$ coureurs sur la piste, circulaire et longue de 1 km. Bon, et disons qu’ils font une course : au top départ, les coureurs, Bob y compris, partent tous du même endroit de la piste, et chacun se met à courir à vitesse constante. Pour faire simple, imaginons que ces coureurs ne s’arrêtent jamais, ils peuvent bien faire un petit effort pour que Bob ait la réponse à sa question. Est-ce que forcément, à un moment, Bob se retrouve éloigné de tous les autres coureurs ?

Non, il faut ajouter au moins une condition : si un coureur va exactement à la même vitesse que Bob, alors ils resteront côte-à-côte pour toujours. Bob suppose donc que les vitesses des coureurs sont toutes différentes.

Au troisième tour de sa séance du mardi sept mai, après avoir doublé et salué à contrecœur son voisin de palier promenant son affreux schnauzer, Bob réalise que ce qui est important, ce n’est pas vraiment la vitesse absolue des coureurs, mais leur vitesse relative par rapport à lui : si chaque coureur décide de courir 1 km/h plus vite, cela ne changera pas leurs positions les uns par rapport aux autres . Cela revient à faire comme si Bob restait immobile au niveau de la ligne de départ et chacun des autres coureurs courait à leur vitesse à laquelle on aurait retranché la vitesse de Bob. Bob trouve étrange l’idée de courir indéfiniment en faisant du sur-place, mais comme ça simplifie pas mal les choses, il se dit qu’il vaut mieux désormais supposer qu’il reste immobile sur la ligne de départ.

Bob n’a pas fini son cinquième tour de piste qu’il s’imagine la situation où il est immobile sur la ligne de départ, et où le coureur au dossard numéro $i$ court à une vitesse de $i$ km/h. Puisqu’il y a $n$ coureurs (Bob compris), et puisque la piste circulaire fait $1$ km de long, à tout moment il y a au moins deux coureurs qui sont à distance inférieure à $1/n$ km l’un de l’autre [1]. Disons que ces deux coureurs ont les dossards $i$ et $j$ (et que $i$ est plus rapide que $j$). Mais dans ce cas précis, la distance entre les dossards $i$ et $j$ est identique à celle entre Bob et le dossard numéro $i-j$, justement parce que la vitesse du dossard $i$ par rapport au dossard $j$ est $i-j$ km/h et que celle du dossard $i-j$ par rapport à Bob (qui est immobile) est $i-j$ km/h. Donc le coureur au dossard $i-j$ (avec $i-j$ qui est plus petit que $n-1$) est à distance au plus $1/n$ de Bob.

La partie rouge correspond aux endroits de la piste qui sont à moins de $1/n$ km de Bob, et le coureur au dossard numéro $i$ court à la vitesse $i$ km/h, les dossards allant de $0$ à $n$. On voit qu’il y a toujours au moins un coureur (différent de Bob) dans la partie rouge.

Bob en conclut que dans cette situation, il n’est jamais énormément éloigné des autres coureurs ; plus précisément, il y a toujours au moins un coureur à moins de $1/n$ km de lui. Mais est-ce qu’il y a d’autres situations où on peut faire mieux que ces $1/n$ km ? Si la réponse est non, ça voudra dire qu’il y a toujours un moment où Bob est relativement loin de tous les autres coureurs, et ça confirmera l’intuition qu’il avait eue à la fin de son premier tour. Bob reformule cette question de la manière suivante :

Si $n-1$ coureurs, en plus de Bob, courent indéfiniment sur une piste circulaire, chacun à vitesse constante, est-ce qu’il existe un moment où chaque coureur est à au moins $1/n$ km de Bob ?

Bob ne le découvrira qu’une heure plus tard, en consultant la version française de Wikipedia, après s’être débarrassé de sa sueur à grands jets d’eau courante et de sa faim en ingurgitant deux œufs et un grand bol où il aura mélangé lait écrémé, raisins secs, banane et avoine hyperprotéinée : cette question résiste encore et toujours aux mathématiciens. Elle est communément appelée conjecture du coureur solitaire.

Par exemple, s’il y a 2 coureurs au départ (y compris Bob, qui reste sur la ligne de départ, courant en sur-place pendant toute la course à durée infinie), la conjecture dit qu’à un certain moment, tous les coureurs seront à au moins 1/2 km=500 m de Bob. De même, la conjecture prévoit que s’il y a 10 coureurs au départ — Bob compris —, alors à un moment, tous les coureurs seront à au moins 1/10 km=100 m de Bob.

Bob se rend compte très vite, dès le début de son sixième tour, que cette conjecture est vraie s’il y a seulement un coureur en plus de lui (autrement dit $n=2$) : il y a forcément un moment où ce coureur se trouve à l’opposé de Bob sur la piste ; autrement dit, où il est à 500 m de Bob. Et 500 m, c’est bien $1/n=1/2$ km : la conjecture fonctionne dans ce cas.

L’étape suivante est de regarder ce qui se passe lorsqu’il y a $n=3$ coureurs. Il y a donc Bob, immobile sur la ligne de départ, et deux autres coureurs, aux dossards numéros 1 et 2. La conjecture prévoit que dans ce cas, il y aura un moment où ces deux coureurs seront à au moins à 1/3 km de Bob (soit environ 333 m).

Bob ne commence à réfléchir à cette situation qu’au milieu de son septième tour. Pendant un kilomètre, son attention a été détournée par les figures produites par l’alignement des troncs de la forêt, plantée méthodiquement vingt ans plus tôt, selon un réseau à domaine carré, par un agent zélé de l’office national des forêts, géomètre à ses heures perdues.

Libéré de son état quasi hypnotique par une racine qui a failli le faire plonger dans une des flaques produites par les six millimètres de pluie tombés la veille, Bob retourne à ses considérations mathématiques. Il se représente la distance parcourue par les coureurs de la manière suivante. Le coureur 1 court à une vitesse $v_1$, donc la distance qu’il a parcourue au temps $t$ est $v_1\times t$. Idem pour le coureur 2, la distance qu’il a parcourue au temps $t$ est $v_2\times t$. À chaque temps $t$, Bob trace mentalement dans le plan le point dont les coordonnées sont les distances parcourues par les dossards 1 et 2, donc le point de coordonnées $(v_1\times t, v_2\times t)$. Cela lui donne une demi-droite du plan, de pente $v_1/v_2$, que Bob décide de se représenter en bleu :

Notons que cette demi-droite bleue n’est ni horizontale, ni verticale, car les vitesses $v_1$ et $v_2$ ne sont pas nulles (sinon il y aurait un coureur différent de Bob qui ferait lui aussi du sur-place).

Quand est-ce que Bob est éloigné d’au moins $x$ kilomètres des deux autres concurrents ? Eh bien pour cela, il faut et il suffit que chacun des autres coureurs soit dans la partie jaune de la piste sur le dessin suivant.

Un coureur est dans la partie jaune si et seulement si la distance qu’il a parcourue depuis le dernier passage à la ligne de départ est comprise entre $x$ et $1-x$. Sur le dessin suivant, les bandes verticales jaunes correspondent aux endroits où le coureur numéro 1 est éloigné d’au moins $x$ km de Bob (autrement dit est dans la partie jaune du dessin précédent) ; de même les bandes horizontales jaunes correspondent aux endroits où le coureur numéro 2 est éloigné d’au moins $x$ km de Bob. Par conséquent, les intersections de ces bandes — qui sont les carrés jaune foncé sur le dessin — sont exactement les endroits où les coureurs 1 et 2 sont chacun à distance au moins $x$ km de Bob.

Bob en déduit que les deux coureurs sont éloignés de lui d’au moins $x$ km si et seulement si le point de coordonnées $(v_1\times t, v_2\times t)$ appartient à la collection de carrés jaune foncé. Bob vient de reformuler son problème de manière géométrique :

Il y a toujours un moment où chaque coureur est à au moins $x$ km de Bob si et seulement si n’importe quelle droite passant par l’origine, et qui n’est ni horizontale ni verticale, rencontre au moins un carré du dessin suivant. Sur ce dessin, les carrés ont leurs côtés de longueur $1-2x$ et sont centrés en des points dont les coordonnées sont des nombres entiers plus $0,5$ (par exemple $(3,5\ ;\ 4,5)$, mais pas $(2\ ;\ 4,5)$).

Bob réalise tout de suite que ce dessin correspond trait pour trait à ce qui l’avait détourné de ses pensées sur les coureurs solitaires un tour plus tôt : le dessin précédent peut représenter la carte d’une forêt plantée, dont les troncs sont à base carrée. S’il se trouve au beau milieu de cette forêt, et si la taille des troncs est suffisamment grande par rapport à l’espacement des troncs, alors Bob ne pourra voir le bout de la forêt que dans 2 directions, celles qui sont verticale et horizontale sur la carte. La conjecture du coureur solitaire dit justement que cela est vrai si et seulement si le rapport entre la taille des troncs et leur espacement est supérieur à $1/3$.

Une fois rentré chez lui, rituellement douché, rassasié et informé de l’éventuel email qu’il aura reçu pendant une heure de déconnexion technologique, cela ne prendra pas plus de cinq minutes à Bob, armé d’un papier et d’un crayon, pour vérifier que ça fonctionne bien : si ce rapport est inférieur à 1/3, alors en regardant dans la direction du coin de l’arbre le plus proche, on arrive à voir l’horizon (et cette direction n’est ni horizontale, ni verticale). En revanche, si ce rapport est supérieur à 1/3, alors dans n’importe quelle direction qui n’est ni verticale ni horizontale, on ne voit pas le bout de la forêt. Bob a donc démontré que la conjecture est vraie pour $n=3$.

Les carrés sont des coupes de troncs, la croix est l’origine (donc le point de coordonnées $(0,0)$). Si, comme sur ce dessin, les carrés ont leurs côtés de longueur $x$ inférieure à $1/3$, alors il existe une demi-droite bleue qui ne rencontre aucun tronc : on voit l’horizon dans une direction qui n’est ni horizontale, ni verticale. Et donc à tout moment, il y a un coureur à distance inférieure à $x$ de Bob.


Si $x$ est supérieur à $1/3$, alors toute demi-droite passant par l’origine et qui n’est ni verticale, ni horizontale, doit forcément rencontrer un des carrés à un moment. Autrement dit, un observateur placé sur la croix ne verra l’horizon que dans deux directions, celle verticale et celle horizontale sur ce plan. Dans ce cas, il y a forcément un moment où chaque coureur est à plus de $x$ km de Bob.


Le cas limite est celui où le côté des carrés $x$ vaut $1/3$. Il y a alors une seule demi-droite qui ne rencontre aucun carré, et qui n’est ni horizontale ni verticale.

Onzième tour. Le Soleil commence à sécher la piste, et il semble que toute l’humidité suée par la forêt depuis l’aube s’est maintenant condensée sur le corps de Bob. Bob ne s’en rend pas compte : il pense toujours à son problème de coureurs. Et s’il y en a plus que 4 (Bob compris), disons qu’il y en a $n$, est-ce que la conjecture du coureur solitaire est vraie ? Bob réalise qu’on peut toujours faire le même raisonnement que pour deux coureurs, et transformer ce problème en termes de forêts impénétrables, mais en dimension plus grande : dans l’espace de dimension $n-1$ (voir l’encadré de cet article), on place un cube dont le côté est de longueur $1-x$ centré en chaque point dont les coordonnées sont des nombres entiers plus $0,5$. La question est de savoir si lorsque $x$ est supérieur à $1/n$, un observateur placé sur le point de coordonnées $(0,0,\dots,0)$ verra l’horizon dans une direction différente des directions évidentes [2].

Fin de l’entraînement pour Bob. Bob sèche. Pas étonnant : même si ce problème de visibilité de l’horizon dans des forêts supradimensionnelles semble à première vue assez simple, on ne sait toujours pas si la conjecture est vraie ou pas dans le cas général. Tout juste les mathématiciens ont-ils des preuves pour un petit nombre de coureurs $n$. Pour l’instant, on sait faire jusqu’à 7 coureurs, mais les les démonstrations sont loin d’être simples : par exemple, il a fallu attendre 1972 pour une résolution du problème dans le cas de 4 coureurs !

Ce qui se passe en dimension 3, extrait d’un article de survol de Clayton Barnes II.

Pour continuer à courir un peu

  • Bob n’a pas expliqué sa démonstration de la conjecture pour $n=3$ à l’aide de la méthode géométrique qu’il a imaginée. Les lecteurs marathoniens pourront essayer de la retrouver !
  • L’article de survol de Clayton Barnes II sur la conjecture (en anglais), qui explique en particulier la connexion entre la conjecture et les problèmes de visibilité qu’on a abordé dans notre article, la théorie des approximations diophantiennes, et la théorie des billards dans des tables carrées.
  • La page Wikipédia, recensant entres autres les résultats partiels connus à ce jour.
  • Si on veut mesurer la densité de notre forêt, on utilisera un relascope.
Post-scriptum :

Les animations de cet article ont été crées avec le logiciel Geogebra.

Un grand merci aux relecteurs de cet article : l’éditeur Frédéric Le Roux (qui a eu raison de m’embêter pour que je fasse des animations), Simon Billouet, Mateo_13, Clement_M, Adriano Marmora, Clément Caubel et myg204.

Article édité par Frédéric Le Roux

Notes

[1Autrement dit, si on divise la piste de $1$ km en les $n$ intervalles entre deux coureurs consécutifs, au moins l’un de ces intervalles est de longueur supérieure à $1/n$ km.

[2C’est-à-dire les demi-droites dont tout les points ont leur $i^{\text{ème}}$ coordonnée nulle, pour un certain $i$ entre 1 et $n-1$.

Partager cet article

Pour citer cet article :

Pierre-Antoine Guihéneuf — «Coureur solitaire et forêts impénétrables» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - https://commons.wikimedia.org/wiki/File:Pinus_taeda_plantation.jpg
img_16431 - https://commons.wikimedia.org/wiki/File:PixAile14.jpg
img_16438 - https://commons.wikimedia.org/wiki/File:Bendtrup_Skov.jpg

Commentaire sur l'article

  • Coureur solitaire et forêts impénétrables

    le 31 janvier à 18:05, par ROUX

    Superbe article dans lequel je dois encore revenir voyager pour me convaincre que j’ai bel et bien à peu près tout compris.
    Passer du coureur solitaire au rangement d’hyper-arbres, c’est très stimulant :-) !!!

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM