Υπάρχουν $n$ πρατήρια καυσίμων σε έναν κυκλικό αυτοκινητόδρομο. Καθένα από τα πρατήρια έχει μια ορισμένη ποσότητα καυσίμων, ενώ όλα τα πρατήρια μαζί έχουν ακριβώς την ποσότητα καυσίμου που είναι απαραίτητη για να διανύσετε τον αυτοκινητόδρομο.
Αποδείξτε ότι είναι πάντα δυνατό να επιλέξετε τον πρώτο σταθμό ώστε ξεκινώντας από αυτόν τον σταθμό με άδειο ντεπόζιτο ένα αυτοκίνητο μπορεί να διασχίσει τον αυτοκινητόδρομο και να επιστρέψει στο αρχικό σημείο.
Απόδειξη με απλή (καταστροφική / δημιουργική) επαγωγή 😀:
ΑπάντησηΔιαγραφήΕίναι προφανώς εφικτό για 1 πρατήριο.
Υποθέτουμε ότι είναι εφικτό για n-1 πρατήρια
Απόδειξη ότι είναι εφικτό για n πρατήρια:
Είναι βέβαιο ότι υπάρχει πρατήριο Β που δίνει αρκετό καύσιμο στο αυτοκίνητο για να φτάσει μέχρι ένα γειτονικό πρατήριο Α (αν δεν υπήρχε, δεν θα αρκούσε το συνολικό καύσιμο για να διανυθεί ο κύκλος). Καταργούμε το πρατήριο Β αφού προσθέσουμε την ποσότητα του καυσίμου του στο πρατήριο Α. Πλέον έχουμε n-1 πρατήρια και, από την επαγωγική υπόθεση, έχουμε δεχθεί ότι υπάρχει πρατήριο εκκίνησης Γ που κλείνει τον κύκλο. Επαναφέρουμε τώρα το πρατήριο Β και δίνουμε πίσω το καύσιμο που είχε δοθεί στο πρατήριο Α. Δεν άλλαξε τελικά τίποτε στην ουσία, αλλά έχουμε τώρα n πρατήρια και πρατήριο εκκίνησης Γ, που κλείνει τον κύκλο, ό.έ.δ.