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!
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.