Exercice 25

Numérotons les dépôts $D_{1}$, …, $D_{n}$ dans le sens de parcours, notons $d_{i}$ la quantité d'essence du dépôt $D_{i}$ et $c_{i}$ la quantité nécessaire pour aller de $D_{i}$ au dépôt suivant ($D_{1}$ après $D_{n}$). L'hypothèse s'écrit $d_{1} + \dots + d_{n} = c_{1} + \dots + c_{n}$. Montrons par récurrence sur $n \geqslant 1$ qu'un départ convenable existe, pour tout circuit à $n$ dépôts vérifiant cette hypothèse.

Initialisation : Si $n = 1$, alors $d_{1} = c_{1}$ : en partant de l'unique dépôt, on dispose exactement de l'essence nécessaire au tour.

Hérédité : Soit $n \geqslant 1$ tel que le résultat soit vrai pour $n$ dépôts, et considérons un circuit à $n + 1$ dépôts. Il existe un indice $i$ tel que $d_{i} \geqslant c_{i}$ : sinon, en sommant les inégalités $d_{i} < c_{i}$, on aurait $\sum d_{i} < \sum c_{i}$. Le dépôt $D_{i}$ permet donc d'atteindre le dépôt suivant $D_{i+1}$. Fusionnons ces deux dépôts : on vide $D_{i+1}$ dans $D_{i}$ et l'on supprime $D_{i+1}$, de sorte que le nouveau dépôt contient $d_{i} + d_{i+1}$ et qu'il faut $c_{i} + c_{i+1}$ pour aller de lui au dépôt suivant. Le nouveau circuit compte $n$ dépôts et vérifie encore l'hypothèse. Par hypothèse de récurrence, il possède un dépôt de départ convenable. Ce même dépôt convient pour le circuit initial : sur l'ancien circuit, la voiture qui arrive en $D_{i}$ y prend $d_{i} \geqslant c_{i}$, atteint donc $D_{i+1}$ et y prend $d_{i+1}$ ; elle se trouve alors exactement dans l'état où l'aurait laissée le dépôt fusionné après le trajet de $D_{i}$ à $D_{i+1}$, et la suite du parcours est identique. Si le départ convenable est le dépôt fusionné lui-même, on part de $D_{i}$, et le même argument s'applique.

Conclusion : Pour tout $n \geqslant 1$, il existe un dépôt de départ permettant de faire le tour.

On peut aussi raisonner directement : notons $S_{k} = \sum_{i=1}^{k} (d_{i} - c_{i})$ le bilan après le trajet de $D_{1}$ jusqu'à $D_{k+1}$, avec $S_{0} = 0$ et $S_{n} = 0$. Choisissons $k_{0}$ tel que $S_{k_{0}}$ soit le plus petit des réels $S_{0}$, …, $S_{n-1}$, et partons de $D_{k_{0}+1}$ : le contenu du réservoir à chaque étape est une différence $S_{k} - S_{k_{0}}$ ou $S_{k} - S_{k_{0}} + S_{n}$, toujours positive ou nulle. $$\boxed{\text{Il faut partir juste après le point où le bilan cumulé est le plus bas.}}$$