From: George Papargiris (gpapargi(@)hotmail.com)
Date: Πεμ 24 Απρ 2003 - 17:52:09 EEST

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]

Καλησπέρα

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

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. Ένα που να λεέ [απάντησε ιδωτκά] και ένα που να λέει [απάντησε δημόσια]. Συμφωνώ μαζί του αν δε βάζει σε κόπο το λίσταρχο.

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

Γιώργος

--



_______________________________________________________________

      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org

        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________

• Next message: George Papargiris: "Re: Ένα περίρεγο τοίχημα (Απάντηση)"
• Previous message: Vassilios Papadopoulos: "Re: Η κατάλληλη διαδρομή"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]