Traversée du désert !

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

Modérateurs : JeanN, Michel Quercia

alexirom
Messages : 4
Enregistré le : lun. janv. 31, 2011 11:00 am
Classe : L3

Traversée du désert !

Message par alexirom » lun. janv. 31, 2011 11:02 am

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
Messages : 4
Enregistré le : mar. janv. 04, 2011 3:32 pm
Classe : PCSI

Re: Traversée du désert !

Message par Dreamsnet » mer. févr. 02, 2011 2:17 am

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.

Avatar du membre
Deviling
Messages : 1378
Enregistré le : ven. févr. 29, 2008 2:49 am

Re: Traversée du désert !

Message par Deviling » mer. févr. 02, 2011 5:01 pm

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.
MPSi Lakanal 2008 - 2009 ; MP*1 Saint Louis 2009 - 2010 ; Polytechnique 2010 - ...

alexirom
Messages : 4
Enregistré le : lun. janv. 31, 2011 11:00 am
Classe : L3

Re: Traversée du désert !

Message par alexirom » mer. févr. 02, 2011 5:21 pm

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
Messages : 4
Enregistré le : lun. janv. 31, 2011 11:00 am
Classe : L3

Re: Traversée du désert !

Message par alexirom » mer. févr. 02, 2011 5:32 pm

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
Messages : 173
Enregistré le : sam. sept. 15, 2007 11:12 pm

Re: Traversée du désert !

Message par nafpy » jeu. févr. 03, 2011 10:13 am

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.
Parent d'elèves ...

alexirom
Messages : 4
Enregistré le : lun. janv. 31, 2011 11:00 am
Classe : L3

Re: Traversée du désert !

Message par alexirom » jeu. févr. 03, 2011 1:57 pm

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

nafpy
Messages : 173
Enregistré le : sam. sept. 15, 2007 11:12 pm

Re: Traversée du désert !

Message par nafpy » jeu. févr. 03, 2011 3:10 pm

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".
Parent d'elèves ...

Avatar du membre
Deviling
Messages : 1378
Enregistré le : ven. févr. 29, 2008 2:49 am

Re: Traversée du désert !

Message par Deviling » jeu. févr. 03, 2011 10:02 pm

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.
MPSi Lakanal 2008 - 2009 ; MP*1 Saint Louis 2009 - 2010 ; Polytechnique 2010 - ...

Dreamsnet
Messages : 4
Enregistré le : mar. janv. 04, 2011 3:32 pm
Classe : PCSI

Re: Traversée du désert !

Message par Dreamsnet » ven. févr. 04, 2011 11:31 pm

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 =)

Avatar du membre
Deviling
Messages : 1378
Enregistré le : ven. févr. 29, 2008 2:49 am

Re: Traversée du désert !

Message par Deviling » sam. févr. 05, 2011 12:20 am

Dreamsnet a écrit :Enfin, je suis curieux de voir ton approche =)


J'ai maté la méthode rétroactive, et je m'en inspire par moment, mais sinon c'est surtout beaucoup de réflexion et de modélisation.
J'utilise un tableau à 10 colonnes et 2 lignes pour modéliser un jour de la manière suivante :

Jour X : Nb de personne au point de départ.
Case 1 = Nb de personne à 20km. // Cases 2 = Nb de personne à 40km. // ... // Case 9 = Nb de personne à 180km. // Cases 10 = Nb de personne arrivée.
Nb de litre restant.................. // Nb de litre restant................... // ... // Nb de litre restant................... // Nb de litre infini.

L'idée est simple, durant le voyage il faut minimiser le nombre de personne et maximiser le nombre de litre.
Après faut tester, et en permanence essayer d'améliorer, d'ailleurs j'y retourne.

Edit : Puis je marche aussi par séquence d'envoie.
On peut voir par exemple qu'il est impossible d'envoyer deux personnes à la fois dès le début.
On cherche donc à en envoyer 1, on trouve ce moyen ci (en remontant en fait de la fin).
5 partent du départ / 5 à 20km et 100L / 4 à 40km et 75L / 3 à 60km et 55L / 2 à 80 km et 40L / 2 à 100km et 30L / 1 à 120km et 20L / ...
Les autres partent plus tard pour récupérer ceux qui ont été abandonné avec juste 5L.

Ensuite on la peaufine, on se rend compte que ne pas utiliser les autres dès le début, c'est dommage (mais qu'il est très dur de les utiliser).
On remarque que le groupe de 4 et de 3 peuvent porter 5L supplémentaire. Donc on va initialement en envoyer 6 pour "gagner" 5L dans le raisonnement.

Etc... C'est long, c'est dur, c'est chiant.
MPSi Lakanal 2008 - 2009 ; MP*1 Saint Louis 2009 - 2010 ; Polytechnique 2010 - ...

supelecien
Messages : 148
Enregistré le : lun. nov. 23, 2009 12:03 am
Classe : 3A-Georgia Tech

Re: Traversée du désert !

Message par supelecien » sam. févr. 05, 2011 6:42 pm

Salut,
Pour ce genre d'exercice tres calculatoire il me semble qu'il faille programmer. Une methode tres bourrine est la suivante. On fait le graphe de tout les etats possibles. Ou plutot on demande a l'ordi de le faire. On considere alors si oui ou non il y a une arete entre deux etats donnes. Cela se fait en fonction des lois que l'on donne a l'ordinateur. On obtient alors une matrice symetrique. C'est notre matrice de passage: a chaque iteration du processus il suffit de multiplier le vecteur initial par cette matrice. On continue jusqu a obtenir notre vecteur final souhaite, il suffit alors de regarder quel chemin notre algorithme a parcouru. On le compare en duree a celui stocke. S il est plus court, on le garde.

Je ne suis pas sur qu il faille reflechir avec du papier et un crayon sur ce genre de probleme, on ne pourra jamais etre sur d'obtenir un resultat optimal, ni meme un resultat tout court.

Avatar du membre
Deviling
Messages : 1378
Enregistré le : ven. févr. 29, 2008 2:49 am

Re: Traversée du désert !

Message par Deviling » sam. févr. 05, 2011 7:52 pm

supelecien a écrit : Je ne suis pas sur qu il faille reflechir avec du papier et un crayon sur ce genre de probleme, on ne pourra jamais etre sur d'obtenir un resultat optimal, ni meme un resultat tout court.


Pas d'accord, si c'est résoluble par un ordinateur, c'est résoluble par un humain avec du papier et un crayon. Suffit "au pire" à réfléchir comme un ordinateur.
Personnellement, ma résolution du problème avance, et je pense que mon début est le début idéal.

Effectivement, il s'agit d'un arbre des possibilités, parfois c'est très dur on ne peut choisir entre diverses branches avant un grand nombre d'étapes, mais pas là.
Lorsque l'on compare deux (débuts de) solutions, on se rend très vite compte laquelle est la meilleure.

Edit : Ma résolution avance, au bout de 24 jours, il me reste 3 personne à faire passer (c'est la fin le plus dur !).
Edit² : Première résolution, sauf erreur, j'y arrive en 44 jours, il me reste à vérifier/améliorer.
Edit²² : Une superbe amélioration arrive, dans celle-ci, au bout de 24 jours, il n'en reste qu'un !
Edit²²² : La voilà, maintenant je le fais en 36 jours ! Je referais une vérification avant de la poster.

Voilà le fichier pdf avec ma solution : http://www.pdfhost.net/index.php?Action ... c19e7b8af2
MPSi Lakanal 2008 - 2009 ; MP*1 Saint Louis 2009 - 2010 ; Polytechnique 2010 - ...

Avatar du membre
F0U
Messages : 88
Enregistré le : lun. nov. 01, 2010 9:41 pm
Classe : 2A EPFL
Localisation : Lausanne

Re: Traversée du désert !

Message par F0U » mar. févr. 08, 2011 4:21 pm

Je suis d'accord, ta solution semble marcher,
Mais comment être sur que ta solution est optimale?
Y-a-t-il une méthode de raisonnement particulière?

C'est peut être là que l'ordinateur devient "indispensable" aux mathématiques...
Un grand débat philosophique que la valeur des démonstrations par ordinateur! :wink:

Avatar du membre
Deviling
Messages : 1378
Enregistré le : ven. févr. 29, 2008 2:49 am

Re: Traversée du désert !

Message par Deviling » mar. févr. 08, 2011 6:22 pm

F0U a écrit :Je suis d'accord, ta solution semble marcher,
Mais comment être sur que ta solution est optimale?
Y-a-t-il une méthode de raisonnement particulière?

C'est peut être là que l'ordinateur devient "indispensable" aux mathématiques...
Un grand débat philosophique que la valeur des démonstrations par ordinateur! :wink:


J'ai fait tout mon possible pour qu'elle soit optimale, à coup de rétroaction et tout.

Typiquement, au début, on regarde si on peut en envoyer 2.
Pour cela on pars du 10ème jour :
- Si 2 arrivent le 10ème jour, le 9ème ils avaient fait 180km et ils leur restaient 10L.
- Si 2 étaient à 180km avec 10L le 9ème jour, le 8ème ils avaient fait 160km et ils leur restaient 20L.
- ...
- On remonte jusqu'à 100km avec 2 types et 50L => Impossible, ils ne peuvent arriver avec 50L
Donc à 100km, ils sont 3 avec 55L (le 3ème fera demi tour avec 5L pour rejoindre d'autres qui viendront le sauver).
- Donc 3 à 80km avec 70L => Impossible, de même ils sont alors 4 avec 75L.
- Donc 4 à 60km avec 95L => Impossible, de même ils sont alors 5 avec 100L.
- Donc 5 à 40km avec 125L => Impossible, de même ils sont alors 6 avec 130L => Impossible, de même ils sont 7 avec 135L.
- Donc 7 à 20km avec 170L => Impossible, de même ils sont alors 8 avec 175L => Impossible, de même ils sont 9 avec 180L.

Ensuite dans l'autre sens, on voit qu'on en utilise que 9 donc, si on pars avec les 10 au lieu de 9, on gagne 15L
(Le 10ème consomme 5L pour faire 20km et 5L pour revenir) au bout de 20km. Il reste à voir comment les optimiser (pour cela il ne faut pas changer le nombre de gens qui bougent, juste éventuellement augmenter la quantité d'eau transportée car plus quelqu'un va loin plus il consomme d'eau "inutilement" et plus de l'eau va loin et plus elle a de la valeur pour la raison qui précède justement).

Donc on part à 10 avec 200. Puis 7 à 40km avec le maximum = 7*20 = 140. On observe qu'on gagne 5L (en fait les 10 litres doivent être ramenés par les 3 autres qui vont au départ car ils ne servent à rien). Il faut ensuite déterminer si on peut emmener ces 5L encore plus loin, la réponse est non car à 40km, ils y a 5 gars avec 100L, leur maximum (En fait il faut différencier maximum de départ = 25L et maximum d'arrivée = 25 - 5 = 20L). Dont le seul intérêt de ces 5L c'est que les 2 gars qui font demi tour de 40km à 20km arriveront avec 5L au lieu de 0L. On vient d'optimiser le trajet.

Ensuite, il faut voir si ce trajet est viable, pour cela il faut récupérer tous les mecs isolés qui ont fais demi tour et qui sont à sec. On trouve normalement que c'est impossible. Voilà, on vient de montrer que l'on ne peut pas faire passer 2 type dès le début. Il suffit de refaire tout ça avec 1, on aura optimisé le premier envois.

Ensuite le deuxième envoi, ne pars pas le 2ème, ce n'est pas viable, mais le 3ème jour comme cela on récupérer les types abandonnés lors du premier trajet. On refait la même méthode (pas besoin de tester 2, comme on récupère des gens, on consomme plus, donc au mieux on en fait passer 1) sachant que là le type arrivé peut faire demi tour avec 20L donc on gagne 20km.

Etc, c'est ce que j'ai essayé de faire à chaque fois.
Après, l'erreur est humaine, surtout sur ce genre de problème.
Mais on va dire qu'au pire, je ne me suis pas trompé de beaucoup de jour.
MPSi Lakanal 2008 - 2009 ; MP*1 Saint Louis 2009 - 2010 ; Polytechnique 2010 - ...

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 19 invités