Dans le Problème de jeep dans le désert se trouve un puzzle célèbre logique-mathématique qui nous renseigne sur l’optimisation des ressources. La situation est la suivante : une violente tempête de sable a isolé nous et les nôtres trois compagnons expédition au milieu de désert. La seule façon de se sauver est de rejoindre la ville la plus proche, en parcourant des centaines de kilomètres en voiture sans aucune possibilité de faire le plein dans une station-service en cours de route.
Le problème, cependant, c’est que les quatre jeeps qui fonctionnent encore ont unautonomie limitée: avec un réservoir plein, ils ne peuvent parcourir que la moitié de la distance nécessaire. Heureusement, les jeeps restantes sont identiques les unes aux autres, elles démarrent toutes avec un réservoir plein et peuvent se transférer du carburant les unes aux autres.
Serons-nous capables de faire entrer au moins une jeep dans la ville, mettant ainsi l’ensemble du chargement en sécurité ?
La solution au problème de la jeep
Nous savons que avec un réservoir plein chaque jeep peut voyager la moitié du voyage. Cela signifie que si nous parvenons à prendre au moins une jeep à mi-chemin avec le réservoir complètement plein, nous pourrons retourner en ville et sauver toute l’expédition. Pour ce faire, nous serons obligés de laisser quelques voitures dans le désert: la tâche des autres jeeps à notre disposition sera en effet d’accompagner la voiture principale sur une partie du parcours, transférer le propre carburant et arrête.
Quel est alors le meilleure stratégie? Quand devrons-nous nous arrêter pour transférer du carburant ? Si nous nous arrêtons trop tard, nous aurons trop consommé et il n’en restera plus assez pour faire le plein ; si nous nous arrêtons trop tôt, nous n’arriverons pas à mi-chemin avec toutes les machines dont nous avons besoin.
Puisque nous avons trois voitures « consommable », une bonne stratégie consiste à diviser la première moitié du chemin en trois parties égale et d’abandonner une machine pour chacune de ces pièces. La première étape représentera donc un sixième du voyage total, la deuxième deux sixièmes (ou un tiers), la troisième trois sixièmes (c’est-à-dire la moitié).
Pour nous assurer que cette stratégie fonctionne, nous devons comprendre la quantité de carburant que nous consommons pour chaque étape du voyage.
Nous savons que pour parcourir la moitié du chemin, il faut un réservoir plein, donc :
Pour parcourir une certaine portion du trajet, nous avons toujours besoin du doubler le carburant.
Autrement dit:
- voyager moitié tu as besoin d’un tank pour le voyage entier;
- voyager un quatrième du voyage est nécessaire moitié réservoir;
- voyager un troisième du voyage sont nécessaires deux tiers du réservoir ;
- voyager un sixième du voyage prend les deux sixièmes (c’est-à-dire un troisième) du réservoir.
À ce stade, nous pouvons partir et commencer à parcourir le premier long tronçon de route un sixième du voyage total. Après ce premier tronçon, chacune des quatre jeeps s’est usée un troisième de son propre carburant et a encore deux tiers du réservoir disponible.
Nous décidons donc de sacrifier machine numéro 4. Nous mettons un tiers de son réservoir total dans la machine 1 et un tiers dans la machine 2. De cette façon, les machines 1 et 2 ont à nouveau le réservoir plein, la machine 4 est sèche, tandis que la machine 3 a encore le réservoir aux deux tiers. Le conducteur de la voiture 4 monte dans la voiture 1 et les trois voitures restantes repartent.
Les trois voitures continuent pendant un sixième du trajet, arrivant ainsi aux deux sixièmes (ou un tiers) de la route totale. Les trois voitures ont à nouveau consommé il reste un tiers du réservoir total avec deux tiers (pour les machines 1 et 2) et un tiers pour la machine 3. La machine 3 se sacrifie donc et transfère tout le carburant gauche à la jeep 1. La jeep 1 revient ainsi à avoir un réservoir plein, tandis que la jeep 2 conserve les deux tiers du réservoir. Le conducteur de la Jeep 3 monte également à bord de la Jeep 1 et des deux jeeps restantes. ils repartent.
Pour atteindre la moitié du chemin, ils doivent encore parcourir un sixième de la distance totale. Quand ils arrivent à moitiéla jeep 1 a encore les deux tiers du réservoir, tandis que la jeep 2 a le dernier tiers du carburant. La Jeep 2 transfère ensuite tout le carburant restant à la Jeep 1, qui se retrouve avec le réservoir plein exactement à mi-chemin du parcours.
A partir de là le problème est résolu: Avec un réservoir plein et tous les explorateurs à bord, la Jeep 1 peut parcourir la seconde moitié du désert et atteindre la destination.
Ces types de problèmes et d’énigmes dans lesquels un moyen de transport doit maximiser la distance pouvant être parcourue dans des environnements hostiles, en utilisant des ressources limitées et difficiles à trouver, sont appelés « problèmes de traversée du désert« . Ils sont étudiés et appliqués dans la logistique pour optimiser les itinéraires de transport et réduire les coûts d’approvisionnement, mais aussi dans le domaine militaire pour planifier les lignes d’approvisionnement et assurer la continuité opérationnelle dans les territoires difficiles. Une idée similaire apparaît également dans la conception des lancements de fusées spatiales, où les réservoirs sont libérés au fur et à mesure qu’ils se vident, afin d’optimiser le poids de la fusée, un peu à la manière des explorateurs qui abandonnaient leurs jeeps en plein désert.