Traversée du désert !

Un problème, une question, un nouveau théorème ?
alexirom

Traversée du désert !

Message par alexirom » 31 janv. 2011 10:02

Voilà cela fait quelques jours que je bloque sur le problème suivant. Il semblerait que le plus difficile soit de le modéliser : 10 personnes sont conviées à traverser un désert de 200 km. On estime que chaque personne peut parcourir 20 km par jour et a un besoin journalier de 5 litres d'eau par jour. Or chacun ne peut emporter que 25 litres d'eau. On ne peut donc compter que sur la solidarités des uns avec les autres pour réussir une telle mission. Autre donnée, il y a une réserve infinie d'eau au départ et à l'arrivée. Le but du jeu est donc de connaitre le nombre de jours minimum nécessaires pour réaliser ce challenge... Je dois avouer que je sèche un peu. Vous êtes peut être plus imaginatifs que moi !

Dreamsnet

Re: Traversée du désert !

Message par Dreamsnet » 02 févr. 2011 01:17

Hum, à vue de nez, avec un rapide croquis sans doute mal optimisé, je dirais 30 jours (vraiment à vue de nez, je me suis perdu dans mon calcul et j'ai un peu du mal a reprendre le fil, je le referai au calme demain).

Voici le principe qui me semble marcher (même si je doute fortement que ce soit LE principe attendu ^^'):

On suppose que chaque participant fait 10 km en une demi-journée (puisque 20 en une journée).
Découpons le trajet en tranches de 10 kilomètres :

Départ (kilomètre 0) / Km10 / km20 / km30 / km 40/ ... / km 190/ km 200 : Arrivée

On numérote les participants arbitrairement de 1 à 10 : les 5 premiers se placent respectivement aux kilomètres 10, puis 20, 30, 40, et 50.

-Le participant 1 (P1) fera donc 1 trajet "Départ=>km10, km10=>Départ" par jour. A chaque passage au départ, il remplit son "bidon" de 25 litres. Sachant qu'il consomme 5 litres par jour, donc 2,5 par demi-journée, il fait la chose suivante :

Mettons, à midi (c'est plus simple comme ça =P), il part du départ, il arrive à minuit au km10. Il a consommé 2,5 litres. Il pose 20 litres au km 10, puis garde 2,5 pour revenir au départ.

-Le participant 2 (P2), qui a bu 5 litres pour arriver au km 20, consomme 2,5 L supplémentaires pour revenir au km 10. Il a donc dans son bidon 25-7,5=17,5 L. Il prend 7,5 L des 20 L laissés au km 10 par P1 afin de remplir entièrement son bidon de 25 litres. Il se dirige vers le km 20 (où est "sa place"), pour y déposer 20 litres d'eau des 25 dispos dans son bidon (puisque lui aussi aura besoin de 5 litres pour faire l'aller retour "km20=>km10, km10>km20").

-Le participant 3 (P3), qui a bu 7,5 L pour arriver au km 30, consomme 2,5 L supplémentaires pour revenir au km 20. Il a donc dans son bidon 25-10= 15 litres. Il prend 10 litres des 20 laissés au km 20 par P2 afin de remplir entièrement son bidon de 25 litres. Il se dirige vers le km 30 (où est "sa place"), pour y déposer 20 litres d'eau des 25 dispos dans son bidon (puisque lui aussi aura besoin de 5 litres pour faire l'aller retour "km30=>km20, km20>km30").

-Le participant 4 (P4), qui a bu 10 L pour arriver au km 40, consomme 2,5 L supplémentaires pour revenir au km 30. Il a donc dans son bidon 25-12,5= 12,5 litres. Il prend 12,5 litres des 20 laissés au km 30 par P3 afin de remplir entièrement son bidon de 25 litres. Il se dirige vers le km 40 (où est "sa place"), pour y déposer 20 litres d'eau des 25 dispos dans son bidon (puisque lui aussi aura besoin de 5 litres pour faire l'aller retour "km40=>km30, km30>km40").

-Enfin, le participant 5 (P4), qui a bu 12,5 L pour arriver au km 50, consomme 2,5 L supplémentaires pour revenir au km 40. Il a donc dans son bidon 25-15= 10 litres. Il prend 15 litres des 20 laissés au km 40 par P4 afin de remplir entièrement son bidon de 25 litres. Il se dirige vers le km 50 (où est "sa place"), pour y déposer 20 litres d'eau des 25 dispos dans son bidon (puisque lui aussi aura besoin de 5 litres pour faire l'aller retour "km50=>km40, km40=>km50").



Voilà voilà. A ce stade, il y a en théorie à tout temps (20+ n modulo[20]) litres d'eau au km 50.

Je me rends compte qu'il y a encore pas mal de choses à retranscrire.... Bon, pour faire simple, le participant 6 (P6) sera le "passeur" : son cycle à lui sera de faire le trajet "départ => km 100" aller puis retour, en piochant tous les 10 km 2,5 litres d'eau jusqu'au km 50 inclus (2,5 au km10, 2,5 au km20 ...), de façon à avoir 25 litres d'eau dans son bidon au km 60. Du km 60 au km 100 inclus, il laisse une bouteille de 2,5 L d'eau tous les 10 km. Ainsi, si quelqu'un m'a suivi jusque là (et si je ne me suis pas trompé dans les calculs), arrivé au km 100, il devrait avoir 12,5 L d'eau dans son bidon.

Une fois au km 100, il revient au départ en 2 temps : jusqu'au km 50 il épuise l'eau de son bidon puis, à partir de là, il pioche dans les réserves remplies régulièrement par (P1 à 5) pour arriver au départ.

-Le chemin jusqu'au km 100 "balisé" d'eau, le participant (P7) va faire le chemin jusqu'à l'arrivée en 2 temps : son principe sera d'avoir son bidon rempli à 25L tout le long du chemin, jusqu'au km100 (grâce aux réserves et bouteilles laissées précédemment). Au km 100, il a, en théorie, 25L d'eau : ainsi, il pourra aisément rejoindre l'arrivée (km200).


-On répète 3 fois le "balisage" par le "passeur", pour faire passer respectivement (P8),(P9) et (P10).

-Ensuite, ce sera au tour de (P1), qui est au km 10 : le "passeur" "balise" le chemin à nouveau, (P1) retourne au départ, suit le passeur avec un décalage d'une demi-journée, puis arrive au km 200.

- Idem pour (P2) qui était au km 20.

-Si vous avez bien compté, il ne reste plus que (P3), (P4), (P5) et le passeur, (P6) : Il y a donc 6 personnes à l'arrivée.

Ces 6 personnes à l'arrivée vont reproduire le même schéma type sus-expliqué ("en miroir", par une réflexion d'axe km 100). Du coup, les 4 restants vont tour à tour (à quelques journées d'intervalle, histoire de laisser le nouveau passeur baliser le chemin) aller jusqu'au km 100 avec leurs propres réserves, puis du km 100 à l'arrivée à l'aide des bouteilles laissées par le passeur, de manière analogue à la méthode vue plus haut.


Voilà voilà voilà, grosso modo le cycle entier doit durer aux alentours de 30 jours, pour un chiffre précis néanmoins, il faudra attendre demain ^^'.

En espérant n'avoir rien omis d'important,

Bonne soirée.

Deviling

Re: Traversée du désert !

Message par Deviling » 02 févr. 2011 16:01

Oula, les hypothèses ont l'air très fortes.
Moi, j'ai supposé que leur action était déterminée pour la journée (20km en avant, 20km en arrière ou rien) et que l'on ne pouvait pas laisser d'eau.
Peut-être étais-je dans l'erreur.

En tout cas, j'aime bien ce problème, je vais m'y replonger.

alexirom

Re: Traversée du désert !

Message par alexirom » 02 févr. 2011 16:21

Oui effectivement, nous sommes des écolos et nous ne laisserons rien trainer dans la nature. Blague à part, J'ai réfléchi au problème à ta manière. Rien ne sert de rajouter des hypothèses et d'utiliser des huitièmes de bouteille. Bref, ce problème occupe pas mal mon esprit en ce moment. Disons que j'ai tenté plusieurs simulations en optimisant au maximum l'utilisation de l'eau, à savoir on ne laisse avancer la personne que si cette personne a fait le plein, autrement dit 25 L. Maintenant, d'un point de vu mathématiques, c'est bcp moins évident puisqu'il s'agit a priori d'un problème linéaire à valeurs entières, seulement impossible de mettre le doigt sur l'équation objective...

alexirom

Re: Traversée du désert !

Message par alexirom » 02 févr. 2011 16:32

D'ailleurs, dans un premier temps, j'ai trouvé une solution réalisable en 27 jours mais il se trouve que j'avais bêtement oublié un intervalle si bien que ma simulation reposait sur une distance de 180 et non 200...

nafpy

Re: Traversée du désert !

Message par nafpy » 03 févr. 2011 09:13

Je dirais à vue de nez que la traversée du desert prendra 10 jours. Ce genre de Pb est classique en gestion de projet et se resoud allègrement à l'aide du diagramme de PERT.
Indication: Commencez par la fin, sous l'hypothèse qu'un seul candidat arrive à l'etape finale, avec 0l d'eau.
L'etape precédente peut être facilement identifiée avec les données suivantes.
Pour la réussite du projet le candidat P10 devrait au 5e jour J5, se trouver à l'etape E5=100Kms, disposer de 25L d'eau, P10=25L, et c'est grace à P9 qui lui a cédé 5L, P9 devrait garder 5L pour rejoindre l'etape antérieure E4.
En résumé: D10={J10; E10=0Kms; P10=0L} ... D5={J5; E5=100; P10=25; P9=5} ... Et à chaque remontée d'etape on rajoute un relais Pi chargé d'alimenter ceux qui poursuivent le trajet, Pi garderait en reserve 5L pour retourner à l'etape précedente.
Les premiers relais seront chargés de revenir au départ afin de reaprovisionner. Bien entendu le graphe serait parallelisable en certains endroits... A suivre :arrow:
Et surtout la solution n'est pas unique.

alexirom

Re: Traversée du désert !

Message par alexirom » 03 févr. 2011 12:57

10 jours :shock: !!! Wahou mais dis moi, tu pars du principe qu'on peut vivre trois jours sans eau ? :lol:

nafpy

Re: Traversée du désert !

Message par nafpy » 03 févr. 2011 14:10

alexirom a écrit :10 jours :shock: !!! Wahou mais dis moi, tu pars du principe qu'on peut vivre trois jours sans eau ? :lol:
Oui, 10 jours (j'ai donné l'idée de départ) ça se resoud facilement à l'aide du diagramme PERT.
P10 au bout du 5e jours peut poursuivre sa route jusqu'au but. P9 avec les 5 L, revient à l'etape précedente ou il trouvera P8 qui lui fournira 5L (au moins pour revenir aux autres étapes et ainsi de suite.
Il faut faire un diagramme. Ceux qui font de la gestion de Projet sont familiers avec ce genre de Pb.
Faut voir les détails peut être dans la "Programmation Concurente".

Deviling

Re: Traversée du désert !

Message par Deviling » 03 févr. 2011 21:02

nafpy a écrit :
alexirom a écrit :10 jours :shock: !!! Wahou mais dis moi, tu pars du principe qu'on peut vivre trois jours sans eau ? :lol:
Oui, 10 jours (j'ai donné l'idée de départ) ça se resoud facilement à l'aide du diagramme PERT.
P10 au bout du 5e jours peut poursuivre sa route jusqu'au but. P9 avec les 5 L, revient à l'etape précedente ou il trouvera P8 qui lui fournira 5L (au moins pour revenir aux autres étapes et ainsi de suite.
Il faut faire un diagramme. Ceux qui font de la gestion de Projet sont familiers avec ce genre de Pb.
Faut voir les détails peut être dans la "Programmation Concurente".
Il faut 10 jours à une personne pour traverser le désert.
Or elle ne peut transporter que la moitié de l'eau qui lui est nécessaire.
Donc non, tu ne feras pas traverser les 10 personnes en 10 jours.

Edit : Je crois que je suis sur une piste.
Edit² : Par contre, cela prend un temps fou. Au moins 30 jours.

Dreamsnet

Re: Traversée du désert !

Message par Dreamsnet » 04 févr. 2011 22:31

Oui donc, Deviling, intrinsèquement, cela rejoint l'idée postée par mes soins, non ? (et qui n'est de ce fait pas si capilo-tractée que ça, même si je ne maîtrise aucunement la PLNE)

Enfin, je suis curieux de voir ton approche =)

Répondre