Προβλήματα Μαθηματικών

Μαρτίου 25, 2008

Περιφερειακός

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 4:13 μμ

Πάνω σε έναν κυκλικό αυτοκινητόδρομο υπάρχουν n σταθμοί ανεφοδιασμού.
Η συνολική ποσότητα βενζίνης που έχουν οι n σταθμοί είναι αρκετή ώστε ένα
αυτοκίνητο να μπορεί να διαγράψει όλη την διαδρομή (δηλαδή έναν πλήρη κύκλο)
με αυτήν. Θεωρούμε οτι το αυτοκίνητο μπορεί να αποθηκεύσει απεριόριστη
ποσότητα βενζίνης. Δείξτε οτι υπάρχει κάποιος από τους n σταθμούς
ανεφοδιασμού, τέτοιος ώστε αν το αυτοκίνητο ξεκινήσει από αυτόν θα μπορεί να
επιστρέψει σε αυτόν (κινούμενο πάντα προς την ίδια κατεύθυνση).

Advertisements

2 Σχόλια »

  1. Πολύ ενδιαφέροντα τα προβλήματα 🙂

    Ας δείξουμε αρχικά πως υπάρχει τουλάχιστον ένας σταθμός με αρκετή ποσότητα βενζίνης, τέτοια ώστε ένα αυτοκίνητο που ξεκινά από αυτόν, να μπορεί να φτάσει στον επόμενο.

    Αυτό είναι εύκολο να δειχτεί: Αν δεν υπάρχει τέτοιος σταθμός, τότε η συνολική ποσότητα βενζίνης δεν επαρκει ωστε να είναι δυνατή η διαγραφή ενός πλήρη κύκλου με το αυτοκίνητο, γεγονός που βρίσκεται σε αντίθεση με τα δεδομένα του προβλήματος.

    Υπάρχει λοιπόν τέτοιος σταθμός i, με ποσότητα βενζίνης που επαρκεί μεχρι τον i+1.

    Ας θεωρήσουμε τους δύο αυτούς διαδοχικούς σταθμούς ως έναν «σταθμό», που βρίσκεται στη θέση του i και που εχει αποθηκευμένη βενζίνη ίση με το αθροισμα της βενζίνης και των δύο. Θέτουμε το ίδιο ερώτημα: Υπάρχει σταθμός με αρκετή βενζίνη ωστε ενα αυτοκίνητο που ξεκινά απο αυτόν να φτάσει στον επόμενο;

    Το ερώτημα αναφέρεται σε ίδιο με το αρχικό πρόβλημα αλλα με εναν σταθμό ανεφοδιασμου λιγότερο (λόγω της συγχώνευσης των i και i+1). Τα δεδομένα δεν έχουν αλλάξει και η απάντηση είναι θετική, για τον ίδιο λόγο.

    Συγχωνεύουμε τον νέο σταθμό που απαντά θετικά στο ερώτημά μας με τον επόμενο και συνεχίζουμε την ίδια διαδικασία έχοντας πια ανάγει το αρχικό πρόβλημα των n σταθμών σε πρόβλημα n-2 σταθμών.

    Με τον τρόπο αυτό και επανάληψη της ίδιας συλλογιστικής καταλήγουμε τελικά σε δύο «σταθμούς» Α και Β προερχόμενους απο διαδοχικές συγχωνεύσεις. Ακολουθώντας το ίδιο επιχειρημα, ένας απο τους δύο, εστω ο Α, πρέπει να έχει αρκετή βενζίνη για να φτάσει ενα αυτοκίνητο στον Β. Και ο Β πρέπει να εχει ικανό απόθεμα βενζίνης ωστε μαζί με όση περίσσεψε, να επιστρέψει το αυτοκίνητο, διαγράφοντας πλήρως τον κύκλο, στον Α.

    Υπάρχει λοιπον σταθμος τέτοιος όπως τον ζητάει το πρόβλημα και είναι αυτός που βρίσκεται στη θέση του «σταθμού» Α.

    Μου αρέσει!

    Σχόλιο από yioryos — Μαρτίου 27, 2008 @ 12:10 πμ

  2. Πολύ ωραία λύση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 27, 2008 @ 8:18 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: