Après quelques dessins, mon sentiment est qu'il y a toujours une solution. Celle-ci peut devenir extrêmement longue mais le nombre d'extrémum que nos deux alpinistes vont atteindre ne pourra jamais être plus que le carré du nombre d'extrémum sur la montagne (Et même le carré divisé par 4?).

Il y a une histoire de parité qui empoisonne l'affaire , je me demande si on n'est pas dans un problème de théorie des graphes .

Imod

Imod
Parité, théorie des graphes?
J'attends avec impatience de voir où cela va te mener...

Bonjour,
Les deux alpinistes se rapprochent horizontalement jusqu'à être au même endroit d'abscisse celle du sommet maximal puis ils montent ensemble. On peut me retorquer qu'on ne peut pas être deux au même endroit mais alors il serait possible de n'avoir qu'une seule personne au sommet.

jarod La montagne est en deux dimensions, on ne peut donc pas se déplacer horizontalement, à moins de creuser

J'ai bien une solution mais pas le temps de rédiger pour le moment .

J'avais déjà rencontré ce problème avec deux barmen évoluant sur deux escaliers parallèles . Pour rendre l'exercice plus amusant on leur avait donné des escaliers de formes différentes , collé une planche sur l'épaule et posé un verre plein sur la planche .

Je rédige la réponse dans la soirée ou demain dans la journée .

Imod

PS : Ce problème aurait pu compléter la série des escaliers , c'est une peu dommage

Je n'ai pas abandonné mais j'ai du mal à expliquer sans illustration et ça devient vite très lourd même avec seulement deux sommets . Je ne lâche pas l'affaire .

Imod

Imod toujours pas d'explication simple?
A tous Ne cherchez pas trop compliqué

 Cliquez pour afficher

On pourra procéder par récurrence

J'ai une solution complète sans récurrence mais pas le temps d'illustrer , je vais essayer d'être clair malgré tout .

 Cliquez pour afficher

On peut déjà supposer sans perdre de généralité que le chemin est une ligne brisée constituée d'une succession de pics et de creux , sans plateaux et que deux sommets ou creux  ne sont jamais à la même hauteur . On repère les extremums locaux sur un axe vertical et on place sur le trajet de l'alpiniste de gauche les points qu'il va rencontrer au franchissement des lignes horizontales repérées s'il se dirige continûment vers la droite . On considère ensuite l'ensemble des couples constitués par deux points   ( éventuellement confondus ) de même altitude et dont l'un au moins est un sommet ou un creux . Ces couples sont les sommets d'un graphe représentant en fait les deux alpinistes ( ordonnés ) . On relie ensuite ces paires si elle peuvent être jointes par les deux alpinistes en une étape . On supprime les arêtes de type qui n'ont aucun intérêt et on a notre graphe . En regardant les différents cas de figure on voit que tous les sommets du graphe sont d'ordre 2 sauf   et qui sont d'ordre 1 . Il n'y a plus qu'à considérer une chaîne maximale débutant en , elle se termine forcément sur un degré impair donc sur et c'est fini .

Oui, ça  marche comme démo, et c'est même très simple sur le principe. On peut même se passer de la théorie des graphes pour l'expliquer...
Pour les autres, d'autres tentatives d'aborder le problème? (récurrence ....)

J'avais une piste, type descente infinie ressemblant à de la récurrence :
Parcourir le chemin jusqu'au prochain minimum global atteint par au moins l'un des deux et on retrouve le problème de départ et on recommence... Il faut encore rédiger le fait qu'il soit toujours possible d'arriver au prochain minimum global

Je suppose que tu parles de minimum local...
Ne t'arrête pas sur la démonstration du cas où les chemins sont monotones pour les deux alpinistes (il suffit de dire que c'est bijectif, et donc pour la hauteur, on associe la réciproque de la pente, qui est donc une fonction continue). C'est pourquoi j'ai proposé de simplifier avec une ligne brisée... Mais tu es sur la bonne pente (sans mauvais jeu de mot )

Non, je parle bien du prochain minimum global donc sans compter le minimum actuel où se trouve les alpinistes. On peut alors avoir le même questionnement qu'au départ. Le minimum global est nécessaire pour avoir la condition : on est à l'altitude 0 et on ira pas plus bas...
J'ai remarqué que les points de passages obligés sont les minima globaux en considérant à chaque fois le sous problèmes limités aux parcours intérieurs de bornes le minimal global précèdent et son accolyte. En espérant avoir été clair

Ah oui, j'avais mal compris, alors tu es très très proche de ma démonstration, il ne te reste plus beaucoup de chemin

Oui je pense que je l'ai. Faut l'effort de rédaction avec TVI en précisant qu'il y a forcément un point plus haut que le prochain minimum global et donc que c'est possible d'y arriver...

J'ai trouvé un moment pour illustrer et ça valait le coup car on retrouve bien que la solution est unique ( si on évite les retours inutiles ) .

 Cliquez pour afficher

Pour plus de lisibilité je note les sommets et creux avec des lettres :

Il n'y a que trois chemins maximaux dans le graphe , le parcours cherché et bien sûr des cycles .

* AS-DP-BN-EK-GM-JJ-MG-KE-NB-PD-SA

* LP- CG-NR-PP-RN-PL-NN

* CG-EI-GG-IE-GC-EE

Bon, je donne ma solution, que Jarod a quasiment déjà donnée...

 Cliquez pour afficher

On prend le prochain minimum global (donc autre que les extrémités de la montagne)
N sur le schéma de Imod
On fait monter les alpinistes à cette hauteur. (Il ne pourront pas rencontrer d'extremum car sinon, il y aurait un mimimum global plus petit)
B et R sur le schéma d'Imod
Les alpinistes n'auront jamais besoin de redescendre en dessous de cette altitude.
On enlève donc les deux pentes qu'ils ont gravies et on coupe la montagne en 2 au niveau du minimum global. On se retrouve donc avec deux montagnes successives.
Les montagnes entre BN et NR
On prend le sommet de chacune de ces montagnes (J et P)
J est le sommet global. On va créer 3 nouvelles montagnes:
(BJ)(PR)
(BJ)(PN)
(BJ)(JN)
Pour les deux premières, on rajoute une pente de P à J.
Par récurrence, ces montagnes peuvent se gravir (La récurrence se finira car le nombre d'extremums diminue)
On peut donc monter jusqu'à P, puis redescendre jusqu'à N (la descente étant les étapes inverses de la montée) puis monter jusqu'à J.

Bonsoir
Il est facile d'expliquer concrètement la méthode en reprenant le croquis de Imod.
1er alpiniste   2e alpiniste
       AD                   SP
       DB                   PN
       BE                   NK
       EG                  KM
       GJ                   MJ

salut

je n'étais pas intervenu parce que j'avais trouvé comme Imod mais tout comme lui

C'est vrai que l'algorithme est assez simple et peut susciter d'autres questions  en supposant par exemple que toutes les longueurs AB,BC,...RS sont les mêmes . Quelles dispositions des sommets et creux vont générer les déplacements les plus courts , les plus longs , comment les calculer à partir du nombre de sommets ( c'était la question de LittleFox au départ ) , ...

Il y a sûrement encore à dire sur ce joli problème

Imod

il me semble que cet algorithme est "glouton" : il va donner la solution optimale  (minimale) en terme de (somme des) distances parcourues par les deux alpinistes

Oui d'accord donc , connaissant le nombre de sommets ma question est : quelles dispositions des sommets et des creux va donner le plus ou le moins d'efforts supplémentaires aux deux alpinistes par rapport à une traversée directe .

Imod

En fonction de la disposition des sommets et des creux , le nombre de tronçons varie ainsi que le trajet des deux alpinistes , la question n'est donc pas complètement ridicule

Sauf que l'algorithme glouton de carpediem ne marche pas avec une montagne comme celle-ci où à un moment les deux alpinistes sont contraints de reculer en même temps.

Je ne sais pas si c'est important mais tu as plusieurs sommets/creux à la même altitude . On peut toujours évacuer cette situation .

Imod

Ce n'est pas important pour l'algorithme de carpediem. Ce qui est important c'est qu'à un moment les deux alpinistes doivent retourner en arrière.

J'ai dessiné un graphe inspiré du graphe de Imod où tous les sommets sont des couples (extremum, segment) ou (segment, extremum). On ne peut se balader que sur les segments ce qui donne des mouvements en diagonale, verticalement avec x impair ou horizontalement avec y impair.

Mais j'ai des sommets internes du graphes qui ont un degré impair. Il faut donc trouver une autre manière de montrer que le graphe est connecté.

Peut-être que ces degrés impairs sont causés par mes points à la même altitude mais à mon avis ça ne règle pas le problème.

Le point Ajk signifie que le grimpeur de gauche est au sommet A et celui de droite sur le segment JK. Le point ABh signifie que le grimpeur de gauche est sur le segment AB et celui de droite au sommet H.

bon en fait ça ne marche effectivement pas !!! avec la figure de LittleFox ... à cause du point G et je ne vois même pas comment les deux alpinistes peuvent arriver au sommet D



les deux alpinistes vont parcourir (AG = alpiniste de gauche et AD = alpiniste de droite)

AG  AD

ab  kl
bc  lm
cn  mj
no  ji
op  ih

... mais ensuite comment AG peut revenir en A en restant à la même altitude que AD ? ... qui doit se retrouver en G !!

c'est-il qu'il n'y aurait pas de solution ?

et d'ailleurs

Je n'ai pas vérifié l'ensemble du graphe mais je pense que c'est le point G qui pose problème , d'ailleurs le résultat resterait-il vrai s'il se trouvait sous la ligne [AK] ? Il me semble que si on accepte les sommets à la même hauteur on perd le degré 2 de chaque sommet mais on conserve la parité . De toute façon on ne généralise aucunement le problème en acceptant les plateaux et/ou les sommets de même hauteur alors autant éviter ces situations .

Imod

  

@Carpediem

Nos messages se sont croisés

Pour les sommets de même altitude , si on trouve une réponse avec des altitudes différentes il suffit de garder le même schéma et adapter le relief à la situation .

Imod
  

G ne peut évidemment pas être sous AK car dans ce cas il n'y a pas d'altitude équivalente pour l'alpiniste de gauche.

Il y a bien une solution et même plusieurs. Par exemple :

AG : ABCNOPCBABCPOD
AD : KLMJIHQHGFRFED

@LittleFox

Oui , le point G pose problème , si tu pouvais hiérarchiser les différents extréma , j'aimerais bien voir le graphe associé et comment l'adapter pour une solution .

Il est vraiment amusant ce problème

Imod    

Quitte à revenir en arrière pour l'un ou pour l'autre on trouve toujours une issue.

ha oui merci à tous ... que je suis bête !!!

Du coup, s'il y a extremum à gauche du sommet et à droite, dans le graphe il y a au plus nœuds. Comme chaque nœud n'est parcouru qu'une fois c'est la limite sur le nombre d'étapes.

Donc pour extrema on arrive au sommet en moins de étapes.

Je n'ai pas beaucoup accès à internet ces derniers temps, donc désolé par avance si je ne réagis pas très vite. Dans le cas de la montagne de LittleFox, la démonstration d'Imod s'étend facilement. Tout les nœuds du graphes sont pairs, exceptés ceux correspondant aux deux alpinistes situés aux extrémités. Par le même principe que pour les cycles eulériens, il existe donc un chemin qui échange les deux alpinistes, et donc qui passe par le sommet. On n'a pas besoin que le graphe soit connexe. Il ne l'est souvent pas d'ailleurs...

J'ai n'ai pas eu le temps de regarder en détail les prolongements de LittleFox (  je ne suis pas très à l'aise avec ses notations ) . Mais il est vrai qu'en remarquant simplement  u'on ne passera jamais par le même sommet ( pic ou creux ) permet déjà de conclure et de fournir une borne au nombre de déplacements nécessaires . Il doit y avoir encore des choses à dire , je verrai ça ce week-end .

Imod