JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Re: Η κατάλληλη διαδρομή (Λύση)



(nil): George Papargiris (gpapargi(@)hotmail.com)
Ημερομηνία: Thu 24 Apr 2003 - 17:52:09 EEST

Καλησπέρα

Ας θυμηθούμε πρώτα το πρόβλημα

4 πόλεις Α, Β, Γ και Δ σχηματίζουν ένα τυχαίο τετράπλευρο ΑΒΓΔ.
Μεταξύ τους έχουν χαραχθεί κάποιοι μη τεμνόμενοι δρόμοι οι οποίοι
φαίνονται παρακάτω:

Μεταξύ των Α & Β υπάρχουν 2 δρόμοι
Μεταξύ των Α & Δ υπάρχουν 2 δρόμοι
Μεταξύ των Γ & Β υπάρχει 1 δρόμος
Μεταξύ των Γ & Α υπάρχει 1 δρόμος
Μεταξύ των Γ & Δ υπάρχει 1 δρόμος

Μια εταιρεία θέλει να ασφαλτοστρώσει αυτούς τους δρόμους. Για να
πετύχει τη μέγιστη δυνατή οικονομία θέλει να βρει μια διαδρομή
μεταξύ των πόλεων έτσι ώστε να διασχίσει ΚΑΘΕ δρόμο μόνο ΜΙΑ φορά.
Προφανώς θα επισκευτεί κάθε πόλη περισσότερες από μια φορές. Δεν
έχει σημασία η φορά με την οποία διασχίζει ένα δρόμο.

Το ερώτημα είναι αν είναι δυνατό κάτι τέτοιο.

Όσοι απαντήσουν ΝΑΙ θα πρέπει να δώσουν τουλάχιστο μια διαδρομή.
Όσοι απαντήσουν ΟΧΙ θα πρέπει να αποδείξουν ότι τέτοια διαδρομή δεν
υπάρχει.

Και τώρα η απάντηση

Το ιστορικό αυτό πρόβλημα είναι γνωστό σαν "Οι γέφυρες του Konigsberg". Ο
ποταμός Pregel χώριζε το Konigsberg σε 4 ξηρές οι οποίες μαζί με τις
γέφυρες δημιουργούσαν στο χαρτί ένα διάγραμμα σαν και αυτό του quiz που
έστειλα. Οι κάτοικοι προβληματίζονταν για το αν μπορούν να κάνουν ένα
περίπατο έτσι ώστε να περάσουν από κάθε γέφυρα μόνο μια φορά.
Το original σχήμα μπορεί να το δει κανείς στη σελίδα

http://mathforum.org/isaac/problems/bridges2.html

Ο Leonard Euler έδειξε ότι κάτι τέτοιο δεν είναι δυνατό και μάλιστα
γενίκευσε το πρόβλημα για τυχαίο αριθμό σημείων και δρόμων.

Πριν δούμε τη γενικευμένη μορφή ας δούμε το συγκεκριμένο πρόβλημα που
λύνεται με κοινή λογική:

Μια πόλη η οποία συνδέεται με μονό αριθμό δρόμων μπορεί να είναι είτε πρώτη
είτε τελευταία στη διαδρομή. Για παραδειγμα η πόλη Γ, συνδέεται με 3 δρόμους
(ας τους πούμε 1,2,3 ανάλογα με σειρά που τους διασχίζουμε).
Αν διασχίσουμε πρώτα το δρόμο 1 βγαίνοντας από την πόλη, τότε με το δρόμο 2
θα μπούμε στην πόλη και με το δρόμο 3 θα ξαναβγούμε από την πόλη. Δεν
υπάρχει άλλος δρόμος και άρα δεν μπορούμε να ξαναμπούμε στην πόλη. Αφού δεν
υπάρχει άλλος δρόμος πριν τον 1, έτσι ώστε να έχουμε εισέλθει νωρίτερα στην
πόλη, προκυπτει ότι η πόλη Γ είναι η αρχή της διαδρομής.
Αν διασχίσουμε πρώτα το δρόμο 1 μπαίνοντας προς την πόλη, αναγκαστικά θα
βγούμε από τον 2 και θα ξαναμπούμε από τον 3. Δεν υπάρχει άλλος δρόμος και
έτσι δεν μπορούμε φύγουμε από την πόλη. Αναγκαστικά λοιπόν σε αυτή την
περίπτωση η πόλη Γ είναι το τέρμα της διαδρομής.
Με παρόμοια σκέψη καταλήγουμε στο ότι οι πόλεις που συνδέονται με μονό
αριθμό δρόμων είναι υποχρεωτικά αρχή ή τέλος διαδρομής.
Επειδή κάθε διαδρομή έχει μια αρχή και ένα τέλος, αν έχουμε παραπάνω από 2
πόλεις με μονό αριθμό δρόμων δεν υπάρχει η διαδρομή που ζητάμε.
Στο συγκεκριμένο πρόβλημα έχουμε 4 πόλεις με μονό αριθμό δρόμων και το
πρόβλημα είναι άλυτο.

Μια διαδρομή που να περνάει μια φορά από ΚΑΘΕ δρόμο λέγεται και διαδρομή
Euler. Μια διαδρομή η οποία δεν διέρχεται δεύτερη φορά από τον ίδιο δρόμο
ανεξάρτητα από το αν έχει περάσει από όλους τους δρόμους λέγεται συνεχόμενη
διαδρομή (σχεδιάζεται στο χαρτί χωρίς να σηκωθεί το μολύβι). Μια πόλη η
οποία συνδέεται με μονό αριθμό δρόμων θα την αποκαλώ για συντομία μονή πόλη.

Ο Euler γενίκευσε το πρόβλημα για τυχαίο αριθμό δρόμων και σημείων (πόλεων).
Έτσι λοιπόν:

Αν έχουμε περίσσότερες από 2 μονές πόλεις (το πλήθος τους είναι πάντα ζυγό)
δεν υπάρχει διαδρομή Euler. Το πλήθος των μονών πόλεων δια 2, είναι ίσο με
το πλήθος των ανεξάτητων συνεχόμενων διαδρομών του προβλήματος. Δηλαδή αν
έχουμε 6 μονές πόλεις έχουμε 3 συνεχόμενες διαδρομές. Για να ζωγραφίσουμε το
σχέδιο στο χαρτί πρέπει να σηκωθεί το μολύβι 2 φορές.

Αν έχουμε 2 ή 0 μονές πόλεις έχουμε τουλάχιστον μία διαδρομή Euler. Στην
περίπτωση που έχουμε 2 μονές πόλεις πάντα ξεκινάμε και τελειώνουμε με μονή
πόλη. Αν έχουμε μόνο ζυγές πόλεις σταματάμε στην πόλη που ξεκινήσαμε.

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

Με την ευκαιρία ας πούμε και 2 λόγια μόνο για τον Ελβετό μαθηματικό Leonard
Euler (1707-1783).

Πρόκυτε για τον πιο παραγωγικό μαθηματικό όλων των εποχών. Η βιβλιογραφία
μιλάει για "886 books and papers", έργο που για να συγκεντρωθεί χρειάζονται
100 μεγάλα βιβλία. Είχε σημαντική προσφορά σε όλους τους τομείς των
μαθηματικών. Στα 27 χρόνια του έχασε το ένα του μάτι. Στα τελευταία 16
χρόνια της ζωής του έμεινε τελείως τυφλός και παρόλα αυτά συνέχιζε να
παράγει μαθηματικό έργο με τον ίδιο ρυθμό.
Είχε την ικανότητα να συγκεντρώνεται ακόμα και με την παρουσία των 13
παιδιών του. Επίσης είχε τρομερή ικανότητα στο να κάνει υπολογισμούς μέσα
στο μυαλό του γεγονός που επιβεβαιώνεται και από το ότι συνέχισε να παράγει
μαθηματικό έργο ακόμα και τυφλός.
Από πολλούς θεωρήτε ο μεγαλύτερος μαθηματικός όλων των εποχών, τίτλος που
κάποιοι άλλοι αποδίδουν στον Gauss, Lagrange, Αρχιμήδη κλπ.
Προσωπικά νομίζω ότι οι Euler και Gauss είναι οι κορυφαίοι.

Σωστά απάντησαν στο πρόβλημα οι:

Βαγγέλης Καπούλας
Σάββας Δημητρίου
Δίας
Δημήτρης Σκουτέρης
Unknown Technologies
Νίκος Καραντζούλης
Γιώργος Γιαγλής
Θεοφάνης Γκούντρας
Καλδής Ιωάννης
Κώστας Τσιγαρίδης
Γιαννης Παπαγρηγοράκης
Βασίλης Παπαδόπουλος

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

Κάποιοι αναγνώρισαν ότι πρόκυτε για το πρόβλημα των γεφυρών του Konigsberg
μασκαρεμένο. Οι περισσότεροι όμως το αντιμετώπισαν ευθέως με επιτυχία.

Και κάτι ακόμα που αφορά τη δημόσια απάντηση του φίλου Βασίλη Παπαδόπουλου:
ο Βασίλης μου εξήγησε ότι το link [απάντησε σε αυτό το μήνυμα] σε συνδιασμό
με την υποσημείωση που μπαίνει πλέον αυτόματα στο τέλος κάθε μηνύματος, τον
έκανε να νομίζει ότι η εφαρμογή θα δρομολογήσει αυτόματα την απάντηση μόνο
σε αυτόν που πρέπει.
Δεκτό!
Ίσως κάτι τέτοιο να συνέβει και σε όλες τις άλλες δημόσιες απαντήσεις.
Ο Βασίλης πρότεινε να υπάρχουν 2 links. Ένα που να λεέι [απάντησε ιδωτικά]
και ένα που να λέει [απάντησε δημόσια]. Συμφωνώ μαζί του αν δε βάζει σε κόπο
το λίσταρχο.

Καλή Ανάσταση σε όλους

Γιώργος

_________________________________________________________________
Tired of spam? Get advanced junk mail protection with MSN 8.
http://join.msn.com/?page=features/junkmail

--
_______________________________________________________________
      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org
        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________

Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου