Stap 1: Met één station
kan het overduidelijk
Stap 2: (inductieaanname) Stel dat het voor elke verdeling
met n - 1 stations kan.
Neem nu n stations.
Op minstens één van de stations moet genoeg benzine zijn om
het volgende station te bereiken. Noem dit station S1
en het volgende S2. Haal in gedachten het gas
van station S2 weg, en voeg dat toe aan de
hoeveelheid bij S1.
Dan zijn er nog maar n - 1 stations en dan
zegt de inductieaanname dat een rondgang mogelijk is.
Maar omdat er in S1 genoeg was om S2 te
bereiken is dezelfde rondgang met n stations wéér
mogelijk!
Daarmee is de inductiestap bewezen en het bewijs klaar! |