On the road again - partie 2 (assez difficile)

Cet article est la suite d'un article du même nom publié le 21 mars 2022. 

https://olivierlamy.blogspot.com/2022/03/on-road-again-facile-quoi-que.html

Il est destiné à "poser le problème" pour pouvoir l'étudier.

Rappelons le :

Vous êtes sur une route. Il existe un point de secours sur cette route mais vous ne savez pas dans quelle direction ni à quelle distance.Vous devez y parvenir rapidement et à coup sûr.

Une première idée peut être de partir vers la droite et d’avancer indéfiniment. Si vous avez de la chance, vous parviendrez au poste de secours. Pour les chanceux, c’est la technique la plus directe. Mais pour les chanceux uniquement...

Pour les autres, il faut penser autrement.

Fixons-nous une distance d₁. Si, au bout de cette distance sur la droite, nous ne parvenons pas au poste de secours, opérons un demi-tour, revenons au point de départ, fixons-nous alors une autre distance g₁ et partons sur la gauche.

Là encore, si nous ne parvenons pas au poste de secours, revenons vers le point de départ.

Et ainsi de suite, avec des distances à droite d₁, d₂, d₃…, et à gauche g₁, g₂, g₃…

On ne considérera que des distances croissantes, bien entendu, car il ne sert à rien d’opérer un demi-tour au sein d’une partie déjà explorée.

Au fur et à mesure des déplacements, on découvre de nouvelles parties de la route, mais aussi on repasse sur des parties déjà connues.

Pour chaque point de la route, quelle est la distance à parcourir pour l’atteindre la première fois ? Si le poste de secours y est présent, c’est la distance nécessaire pour y parvenir. Appelons-la "D"

Voici un graphe qui indique la distance D à parcourir pour une première découverte du point x.

 

Dans cet exemple, on a 

d₁ = g₁ = 100 m, d₂ = g₂ = 200 m, d₃ = g₃ = 400 m

Les parties en diagonale correspondent au parcours de parties inexplorées.

Les parties verticales sont des trajets en terre déjà connue.

A droite, au niveau des d_i, il y a un sursaut vertical de 2d_i+2g_i.

Il correspond à

    - un trajet vers la gauche, sur les x positifs, vers le point de départ : d_i

    - un trajet vers la gauche, sur les x négatifs : g_i

    - un trajet vers la droite, sur les x négatifs, vers le point de départ : g_i

    - un trajet vers la droite, sur les x positifs : d_i

De même, à gauche au niveau des g_i, il y a un sursaut de 2g_i+2d_i+1

Il correspond à .

    - un trajet vers la droite, sur les x négatifs, vers le point de départ : g_i

    - un trajet vers la droite, sur les x positifs : d_i+1

    - un trajet vers la gauche, sur les x positifs, vers le point de départ : d_i+1

    - un trajet vers la gauche, sur les x négatifs : g_i

Le sursaut à gauche de 0 est dû au fait qu’on commence l'exploration par la droite. Pour uniformiser l’approche, on peut considérer qu’il y a eu des premiers « déplacements » d₀ = g₀ = 0 et le sursaut en 0 à gauche rentre bien dans le cadre d’une taille de 2g_i+2d_i+1.

Finalement, on a posé le problème :

• on s’est donné deux suites positives et croissantes, g et d, telles que g₀ = d₀ = 0
  
• qui permettent de construire une courbe D ainsi :
• D(0) = 0
• pas de sursaut à droite de 0
• une partie verticale à gauche de 0 de hauteur 2d₁
• des pentes 1 (respectivement -1) entre les d_i (respect. -g_i),
• des parties verticales de longueur 2d_i+2g_i ( respect. 2g_i+2d_i+1) au niveau des d_i (respect. -g_i).

Avec ce système, on est certain de trouver à coup sûr le poste de secours, mais le trouver « rapidement » suppose que D(x)/|x| est (le plus) faible (possible).

Nous allons nous y attacher dans un prochain article.

Je vous laisse méditer là-dessus...