Problème du "poste de secours"

poumpampim
Modifié (January 2023) dans Mathématiques et Société

Bonjour à tous.
Avant tout, si je ne poste pas au bon endroit, n’hésitez pas à déplacer cette discussion, voire à la supprimer si elle ne respecte pas, bien malgré moi, l’esprit du forum.
Voici un problème que je me pose depuis quelques années. Je n’y ai pas trouvé de solution satisfaisante. À dire vrai, je n’ai pas réussi à le poser clairement. Je sollicite votre attention et votre aide bienveillante.
Je l’illustre à partir d’une mise en situation.

Une personne se réveille sur une route droite qui s’étend à l’infini d’un côté et de l’autre (on va dire à droite et à gauche pour fixer les idées).
Un panneau indicateur, à côté de la personne, mentionne qu’il existe un poste de secours sur la route, au niveau duquel on peut demander de l’aide. Mais il n'indique pas sa direction ni sa distance. La personne a simplement la certitude de son existence.
Je précise que la personne est éternelle, dispose de ressources physiques inépuisables, mais qu'elle ne peut pas se déplacer à une vitesse supérieure à un maximum fixé.
La question est :

existe-t-il une stratégie optimale pour atteindre le poste de secours ? Si oui, laquelle ?

Voici quelques unes de mes réflexions.
Intuitivement, on envie de faire des oscillations de plus en plus grandes à droite et à gauche. Mais quel serait le coefficient d’augmentation à retenir pour chaque amplitude d’une oscillation par rapport à la précédente ?
Doit-on aller aussi loin à droite qu’à gauche quand on oscille ? La situation n’est pas symétrique car il faut bien choisir un côté au départ.
On se dit qu’une fois qu’on a fait la 2e oscillation, on peut grosso modo se ramener à la situation de la fin de la 1re oscillation par une homothétie réductrice. Mais cela ne fournit pas de stratégie.

Le bon critère à minimiser est-il bien
  Max[longueur (« partie explorée ») / longueur(« chemin parcouru »)]

où la réunion des « parties explorées » est l'ensemble de la droite ?

J’ai étudié des formes d’oscillations possibles et certaines sont meilleures que d’autres.
Les meilleures semblent celles où la dernière oscillation est tellement plus grande que la précédente, que les allers retours précédents deviennent négligeables devant elle.
Le fait de se dire que le poste de secours peut être n’importe où est difficile à gérer car on ne peut pas considérer une probabilité équirépartie sur les points d’une droite infinie. Mais,... allez dire ça au naufragé qui cherche la bonne stratégie au bord de la route…
Bref… Je suis assez convaincu qu’il n’existe pas de stratégie optimale. Mais simplement des stratégies meilleures que d’autres.
Je suis preneur de vos réflexions, de votre aptitude à poser un problème.
Et je vous souhaite une belle année 2023.
Olivier.

Réponses

  • Le problème, c'est qu'on n'a aucune dimension. Et donc le problème est insoluble.

    Tu proposes des oscillations. Le premier demi-tour sera fat quand le naufragé aura parcouru une distance de 1. Mais 1 quoi ? 1kilomètre, 1 hectomètre ? 1 année-lumière ?
    On n'a strictement aucun argument pour dire : là, il est temps de faire demi-tour.
    Dès qu'il y aura un pseudo-indice dans l'énoncé de l'exercice pour répondre à cette première question, alors la suite devrait pouvoir (soyons optimiste) se dérouler plus ou moins bien.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • poumpampim
    Modifié (January 2023)
    Oui, Lourran, tu as raison : on n'a aucune dimension. Cela est dû au fait qu'on ne sait rien sur la distance du poste de secours.
    Toutefois, le critère que je propose de minimiser est sans dimension et permet de hiérarchiser des stratégies.
    Ainsi, il existe des stratégies meilleures que d'autres selon ce critère.
    La stratégie qui consiste à ne pas bouger est bien évidemment l'une des pires car elle ne couvre pas la droite.
    Celle qui consiste à partir indéfiniment dans une direction donnée fournit une chance sur deux. Ce n'est pas ce qu'on demande.
    Enfin celle qui consiste à doubler l'amplitude à chaque oscillation semble meilleure que celle qui consiste à rajouter une distance fixe donnée.
    Et toi que ferais-tu à la place du naufragé ?
    En ce qui me concerne, je choisirais un coefficient c>1 et j'oscillerais de 1, puis c puis c^2 etc.
    Mais, là, ce n'est plus de la mathématique mais de la psychologie :-)
  • poumpampim
    Modifié (January 2023)
    Je complète ma réponse précédente. En fait si, on dispose d'une dimension unité si on le souhaite : l'enjambée du naufragé. On peut tout mesurer en nombre de pas qu'il fait. Mais, évidemment, ce qui est compliqué, c'est qu'on ne connaît pas à quel nombre de pas est le poste de secours ni même une distribution de probabilité qui viendrait qualifier cette position...
  • Pomme de terre
    Modifié (January 2023)
    Salut poumpampim, je tente une formalisation.
    Disons que la vitesse maximale du marcheur est $1$. Une stratégie est une fonction $1$-lipschitzienne et surjective de $\R_+$ dans $\R$ telle que $x(0) = 0$.
    Pour toute position $p \in \R$ du poste de secours, le temps d'atteinte de $p$ par la stratégie $x$ est le réel $T(x, p) = \inf\{t \in \R_+ \mid x(t) = p\}$.
    Une stratégie $x$ est optimale lorsque : pour toute stratégie $y$, pour tout réel $p$ : $T(x,p) \leq T(y,p)$.
    Soit $x$ une stratégie quelconque. Montrons qu'elle n'est pas optimale.
    On considère l'image de $[0,1]$ par $x$. C'est un segment $[a,b]$ de $\R$ de largeur $b - a \leq 1$ (d'après la condition de vitesse). Il existe donc $c \in \{1,-1\}$ tel que $c \notin [a,b]$. Mais alors $T(x, c) > 1$. Pourtant, il existe clairement une stratégie $y$ telle que $T(y,c) = 1$.
  • Ici, à tout instant, on a l'option de continuer tout droit, ou de faire demi-tour. Si on fait demi-tour, on a la certitude de ne pas voir ce poste de secours sur plusieurs kilomètres, alors qu'en continuant tout droit, on a l'espoir de tomber dessus à la prochaine enjambée.  
    Donc toujours tout droit.

    Mais tout ça, c'est parce que : on ne connaît pas à quel nombre de pas est le poste de secours ni même une distribution de probabilité qui viendrait qualifier cette position.

    Cette question tient plus du test de psychologie  digne de figurer dans Télé-7-jours que de l'exercice de maths.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • @lourran, tu es un peu sévère : le problème peut être précisé à loisir ! On peut par exemple (changer le problème et) supposer que la sortie est aléatoire (gaussienne, pourquoi pas ?) et calculer, pour une stratégie donnée, le temps moyen de sortie !
  • gerard0
    Modifié (January 2023)
    Georges,
    tu dis essentiellement la même chose que Lourrran. Avec un autre énoncé, on pourrait avoir un problème mathématique.
    Mais il faut reconnaître qu'un énoncé aussi minime manque de sérieux.
    Problème analogue : choisir un nombre.
    Tous les probabilistes savent que ça n'a pas de sens. On prouve d'ailleurs que certaines acceptions ne sont même pas possibles, alors que ce sont les plus évidentes.
    Cordialement.
  • Bonjour

    tu parles d'oscillations (comme pour le pendule de Foucault !)
    il s'agit plutôt ici d'allers-retours tantôt à droite, tantôt à gauche

    il ne s'agit pas ici d'un sujet mathématique mais d'un problème psychologique de survie
    dont raffolent les scouts et qui concernent les pompiers en exercice en milieu hostile

    la solution instinctive et de bon sens pour le naufragé consistera
    à faire 10 pas à droite puis revenir à son point de départ
    enchaîner 20 pas à gauche puis revenir à son point de départ
    puis 40 pas à droite et revenir à son point de départ etc.

    et continuer ainsi les allers-retours tantôt à droite, tantôt à gauche
    avec des distances qui suivent une progression géométrique de raison 2
    il sera certain d'atteindre le poste de secours mais dans quel état physique !
    même s'il est supposé éternel...

    Cordialement
  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    Bonjour Pomme de Terre
    D'abord merci d'avoir "tenté une formalisation".
    Je ne suis pas en accord avec ta définition de stratégie optimale.

    Tu indiques ceci.
    Une stratégie x est optimale lorsque : quel que soit y dans S (l'ensemble des stratégies), quel que soit p dans R, T(x, p) inférieur ou égal à T(y, p)

    Selon moi, on ne peut pas imposer à une stratégie optimale d'être meilleure que toute autre stratégie partout.
    Soit x une stratégie. Forcément, quelque part, elle propose un demi-tour et donc il existe un p, au-delà du demi tour, tel que T(x, p) > p puisque pour atteindre p avec x, il a fallu parcourir plus que la distance p.
    Or la stratégie y qui consiste à aller directement vers p vérifie T(y, p) = p. Elle est donc "meilleure" au niveau de p.
    Donc, si on adopte la définition de "meilleure partout", une stratégie optimale  candidate est battue dès son premier demi-tour par une stratégie directe.
    À mon sens il faut plutôt minimiser (max(T(x, p) / p, où p parcourt toutes les positions) où x parcourt l'ensemble S des stratégies).
    Ceci dit, il semble que, même avec cette définition, il n'existe pas de stratégie optimale mais seulement un classement des stratégies (mais cela reste à prouver).
    Le naufragé serait donc dans une situation délicate : quelle que soit la stratégie de survie qu'il adopte (et il en existe comme celle des oscillations en progression géométrique de raison 2), il semble qu'il existe une stratégie meilleure.
    Je pose donc plusieurs questions.

    Question 1.
    La définition de stratégie optimale y suivante est-elle la bonne ?
    "stratégie y qui atteint min(max(T(x, p) / p, où p réel), où x parcourt l'ensemble S des stratégies)"

    est-elle la bonne ?

    Question 2.
    Est-il vrai que ce minimum n'existe pas et qu'il n'existe pas de stratégie optimale ?

    Question 3.
    Peut-on néanmoins hiérarchiser les stratégies ?

    Question 4.
    Que devient le problème si on dispose d'une distribution de probabilité de présence du poste de secours ?

    Remarque.
    Il n'est pas évident pour moi de lire ta publication car elle apparaît sur mon écran avec des symboles parasites tels que $, \, leq...
    J'ai donc fait une "traduction" et le texte devient ceci (j'ai aussi ajouté quelques éléments de ma compréhension).

    ******************
    Disons que la vitesse maximale du marcheur est 1. Une stratégie est une fonction x, 1-lipschitzienne et surjective de R+ dans R telle que x(0) = 0.
    [ajouté par moi]
    L’ensemble de départ, R+, représente le temps passé (ou la distance parcourue si la vitesse est constante).
    L’ensemble d’arrivée, R, représente les positions atteintes.
    On appelle S l'ensemble des stratégies.
    [/ajouté par moi]
    Pour toute position p dans R du poste de secours, le temps d'atteinte de p par la stratégie x est le réel T(x, p) = inf(t dans R+ | x(t) = p)
    Une stratégie x est optimale lorsque : quel que soit y dans S, quel que soit p dans R, T(x, p) inférieur ou égal à T(y, p)
    Soit x une stratégie quelconque. Montrons qu'elle n'est pas optimale.
    On considère l'image de [0,1] par x. C'est un segment [a, b] de R de largeur b - a, inférieure à 1 (d'après la condition de vitesse). Il existe donc c qui vaut 1 ou -1 tel que c ne soit pas dans [a,b]. Mais alors T(x, c) > 1. Pourtant, il existe clairement une stratégie y telle que T(y,c) = 1.

    *****************

  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    Il se trouve que, avec ma compagne, nous sommes l'un des auteurs des énigmes logiques (intégrammes) qui sont dans Télé 7 jeux :-)
    Nous sommes aussi les uniques auteurs des revues "Enquêtes logiques" publiées par la société "Sport Cérébral" que l'on trouve dans tous les kiosques à journaux.
    Que tu compares mon questionnement et ma demande à ces revues est un honneur pour moi :-)
  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    Merci Georges :
    Effectivement, ce problème ne demande qu'à être précisé et enrichi. J'ai posé de nouvelles questions dans une publication précédente.
    J'ai proposé par exemple de supposer l'existence d'une probabilité de présence du poste de secours.
    Je me suis aussi demandé s'il était possible de hiérarchiser toutes les stratégies et selon quel critère ?
  • @gerard0 : Woa, comme tu y vas, "manque de sérieux" ! Ici, "formaliser le problème" est analogue à "trouver une modélisation probabiliste pour telle histoire parlant d'urnes et de boules". Parfois, on ne sait pas exactement quel problème précis poser, et en discuter aide à trouver des problèmes intéressants !
  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    Bonjour Gérard
    Le manque de sérieux, ce n'est pas un défaut.
    Je n'attends pas de toi d'être un consommateur de mes énoncés supposés parfaits.
    Il est loin, pour moi, le temps de l'agrégation où tout était parfaitement formalisé et où il fallait simplement résoudre.
    J'espère au contraire que tu m'aides à formaliser et enrichir.
    Je ne pense pas que ce problème n'ait pas de sens du tout. En tout cas, ce n'est pas la réponse qu'aimerait entendre le naufragé :-)
    En tout cas, j'ai proposé ce matin de nouvelles questions qui précisent le problème.
    J'aimerais que tu les considères mais rien ne t'y oblige :-)
  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier l’avant dernier message. Un lien suffit. AD]
    Merci Georges :-)
  • poumpampim
    Modifié (January 2023)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    Bonjour Jean
    Il y a effectivement un aspect psychologique important car il semble qu'il n'existe pas de stratégie optimale.
    Toutefois, on peut se demander
      - s'il est possible de définir un critère indiquant si une stratégie est meilleure qu'une autre (j'en ai proposé un plus haut)
      - si ce critère définit un ordre total des stratégies
      - s'il est possible de définir des familles de stratégies (spontanément on pense aux oscillations en progression géométrique ou arithmétique) et de hiérarchiser ces familles.
      - si une stratégie optimale existe si on sait quelque chose sur le poste de secours (comme une densité de probabilité de présence)
    Ceci dit, pour revenir à l'aspect psy, je choisirais la même stratégie que toi !
  • Wilfrid
    Modifié (January 2023)

    La longueur des oscillations dépend avant tout de la distance de l'horizon (jusqu'auquel on pourrait apercevoir le poste de secours). Si l'homme en question fait 1,80 m, l'horizon se trouve pour lui à 5 km ; c'est la distance minimale du premier parcourt dans une direction choisie au hasard. Il serait idiot de faire demi-tour avant d'avoir parcouru cette distance pour explorer la direction opposée. Dans ce cas, la longueur de chaque oscillation doit être un multiple de 5 km : 5, 10, 15, 20, etc. Mais l'homme va devoir repasser un nombre incalculable de fois par les mêmes portions de route, ce qui représente une perte de temps et de ressources colossale.

    Si la route ne se trouve pas sur Terre mais dans l'espace au milieu de nulle part, alors la distance minimale à parcourir la première fois dépend des capacités visuelles de l'homme.

    La meilleure solution serait de considérer que le panneau indiquant un poste de secours à proximité ne doit pas se trouver à plus de 10 km de celui-ci (sur une autoroute c'est la première mention d'une aire de repos) : on parcourt 10 km dans un sens, et si on ne trouve rien on parcourt 20 km dans l'autre sens. C'est le parcours total le plus court.

    Je comprends que ce n'est pas le sens de la question initiale, mais c'est la seule réaliste.

    PS : et je ne parle même pas de la position du panneau indicateur, qui se trouve du côté de la route correspondant au sens de la circulation, ce qui indique la direction du poste de secours.

  • poumpampim
    Modifié (January 2023)
    Bonjour Wilfrid
    Si la géométrie de l'espace est sphérique et que la route est un grand cercle, à mon avis, le naufragé peut partir dans un sens donné jusqu'à atteindre le poste de secours sans avoir à osciller. Au pire, il parcourt 40 000 km dans le cas terrestre... Je t'accorde toutefois que ce serait une mauvaise publicité pour les sociétés d'autoroute.
    Si la géométrie est hyperbolique, et que la route est infinie (une branche d'hyperbole, par ex), le problème se pose de nouveau.
    Mais, ceci dit, si l'on suppose, comme tu le fais, que l'homme peut "sortir" de l'espace, de par sa taille, alors il verra le poste de secours et se dirigera dans la bonne direction dans le cas d'une géométrie plate ou d'une branche d'hyperbole (à condition d'être bien du côté extérieur de l'hyperboloïde). Après tout, on peut supposer qu'il a une vision infinie, vu qu'il est déjà éternel...
    Dans le cas de la géométrie sphérique, il aura bien sûr intérêt à jeter un œil des deux côtés avant d'en choisir un. Ou alors il est à l'intérieur d'une sphère creuse et il verra aussi le poste de secours...
  • Et ça répond à ta question initiale ?

  • La question initiale est un cadre au sein duquel j'essaie de réfléchir et que j'essaie de préciser.
    Tu étoffes ce cadre en évoquant la géométrie de l'espace. Donc, oui, pour moi, ça participe à une réponse :-)
    Merci à toi
  • Bibix
    Modifié (January 2023)
    Bonjour,
    Je propose de formaliser le critère de lourrran qui me paraît être le plus pertinent, à savoir minimiser la distance inutilement parcourue. Sans perte de généralité, on peut supposer dans le cas 1D que le naufragé est placé en $x = 0$, et le poste de secours serait situé par une v.a. $X$. L'ensemble des stratégies admissibles est donné par $S = \{s \in (\mathbb{R} \cup \{\pm \infty\})^{\mathbb{N}} : \forall i \in \mathbb{N}, s_i s_{i+1} < 0, |s_{i}| < |s_{i+2}|, \underset{n \to +\infty}{\lim} |s_n| = +\infty\}$. On cherche alors à minimiser l'espérance de la distance inutilement parcourue, donc à résoudre le problème (avec la convention $s_{-1} = 0$)
    $$\min_{s \in S} \sum_{i = 1}^{+\infty} P(i) \sum_{k = 0}^{i-1} |s_k| \mathbb{1}_{s_k \in \mathbb{R}},$$
    où $P(2i) = \mathbb{P}(s_{2i-2} < X \leqslant s_{2i})$ et $P(2i+1) = \mathbb{P}(s_{2i+1} \leqslant X < s_{2i-1})$. Dans le cas borné 1D (une ligne droite $[a,b]$) avec probas uniforme (celui qui me paraît le plus vraisemblable), on peut remplacer la condition $\underset{n \to +\infty}{\lim} |s_n| = +\infty$ par $\exists N, s_N \in \{b,a\}, s_{k} = a + b - s_N \, \forall k > N$. Alors une solution optimale est d'aller vers une borne parmi les plus proches puis de rebrousser chemin.

    Edit : Au passage, si l'on ne connait rien sur la position du poste de secours (pas même une distribution de probabilité qu'on pourrait induire à mesure qu'on parcourt la route), alors il est assez évident qu'on ne peut absolument pas trouver de critère satisfaisant. En effet, supposons que $y_1$ (resp. $y_2$) soit une stratégie qui mène à la position $p$ avec une distance parcourue $d_1$ (resp. $d_2 > d_1$) et à la position $p'$ avec une distance parcourue $d_1'$ (resp. $d_2' < d_1'$). Si le poste de secours se trouve en $p$, la meilleure stratégie est clairement $y_1$. En revanche, si le poste de secours se trouve en $p'$, la meilleure stratégie est $y_2$.
  • Ma question portait sur ton avant-dernière réponse : "est-ce que le concept de géométrie de l'espace, qu'il soit sphérique ou hyperbolique, constitue une réponse à ta question initiale ?". C'était de l'ironie.
  • poumpampim
    Modifié (January 2023)
    Merci pour ta réponse, Bibix.
    Pas le temps de la regarder à mon grand regret : je serai éloigné de l'Internet pendant plusieurs jours.
    Retour semaine prochaine.
    J'espère que des esprits bienveillants, curieux et intelligents la regarderont dans cet intervalle.
    J'espère qu'ils feront aussi avancer la réflexion. Mais si ce n'est pas le cas, ce n'est pas bien grave.
  • P.2
    P.2
    Modifié (January 2023)
    Il a eu une thèse de troisième cycle sur ce sujet exactement faite à l’Université Paul Sabatier a Toulouse, laboratoire de Probabilités et Statistique, dans les années 1980 par El Rayes. Il faudrait contacter la bibliothèque de Mathématiques pour obtenir une photocopie. Si on se donne une loi pour la position $X$ aléatoire du poste de secours, plusieurs problèmes d'optimisation  au sujet de $T_X$ le temps d'atteinte de $X$ suivant différentes stratégies, comme minimiser $E(T_X)$ ou $ \Pr(T_X>a)$ avec $a$ fixe, y sont bien étudiés.
  • Dans certaines situations il n'y a pas de minimax on appelle ça le https://fr.wikipedia.org/wiki/Jeu_de_cons
    Suivant les usages des visas de censure au cinéma

    Tout rapport avec un ballon chinois survolant le territoire étazunien ou un comédien conduisant sous l'effet de stupéfiants est sans rapport avec le film.

Connectez-vous ou Inscrivez-vous pour répondre.