Petites enigmes > Réponse Sciences sujet

La récurrence s'intéresse juste à réduire le nombre de station pour revenir à un cas connu dont on sait que la solution marche.

On va prendre le cas suivant avec tous les points avec 10 d'écart.

A-B-C-D-E-F-A

On a un total de carburant de 60.
A a 11
B a 10
C a 9
D a 9
E a 11
F a 10

On fait le cas n = 6
De A, j'arrive à B. On réduit alors le cas à n = 5. Avec le cas suivant:
A-C-D-E-F-A
Toutes les distances valent 10 sauf A-C qui vaut 20
Et la station A a maintenant le carburant de A et B soit 21

On est dans le cas n = 5 (dont on a déjà déterminé que c'était bon - principe de la récurrence)
En continuant, de A on arrive a C.
On a donc plus que A-D-E-F-A.
Avec d(AD) = 30, Carburant(A) = 11 + 10 + 9 = 30

Sur ce nouveau cas, de A on arrive a D. On réduit donc
A-E-F-A
Avec d(AE) = 40, Carburant(A) = 11 + 10 + 9 + 9 = 39

Sur ce nouveau cas, de E on arrive à F. On réduit donc:
A-E-A
Avec d(EA) = 20, Carburant(E) = 11 + 10 = 21

On est donc au cas a 2 points, de E on peut arriver à A et comme la somme de l'essence est suffisante pour faire le tour et qu'on est aller à toutes les stations, on a fait le tour en partant de E.

A partir du moment ou tu supprimes une station en la considérant absorbée par la station précédente qui parvient à l'atteindre, tu passes au cas n-1 que dont tu as déjà démontré que c'était réalisable car n=1 et n=2 sont trivial pour démarrer la récurrence.