Αναζήτηση αυτού του ιστολογίου

Κυριακή 21 Φεβρουαρίου 2010

Η Αρχή της Περιστεροφωλιάς


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







Ο πολύς κόσμος έχει την αίσθηση πως τα μαθηματικά είναι η επιστήμη που ασχολείται μόνο με πολύπλοκους υπολογισμούς, αφηρημένες έννοιες, δυσνόητες πρακτικές εφαρμογές στην τεχνολογία και στις άλλες επιστήμες. Η πραγματικότητα είναι ότι ξεκίνησαν από πολύ απλές διανοητικές διαδικασίες όπως είναι η αρίθμηση, η διάταξη και η αντιστοίχηση. Ωστόσο με το πέρασμα των χρόνων όμως και με τις γνώσεις διαρκώς να συσσωρεύονται δυσκόλεψαν τόσο, που έφτασαν σήμερα να κρύβουν τις απλές δομές από τις οποίες προήλθαν. Παρόλα αυτά, ακόμα και στη σημερινή εποχή τα μαθηματικά δεν είναι μονάχα πράξεις με πολύ δύσκολους αριθμούς ούτε μόνον εφαρμογές πολύπλοκων κανόνων που ξεφεύγουν από την άμεση εμπειρία μας. Υπάρχουν θεωρίες και κανόνες και βέβαια τα αντίστοιχα προβλήματα, που μπορούν να κατανοηθούν κυριολεκτικά απ’ όλους, όσο κι αν είναι μαθηματικά «άσχετοι».

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

Ένας από τους Μεγάλους Μαθηματικούς του 19ου αιώνα ήταν και ο Dirichlet. Γεννήθηκε το 1805 στο Duren (σημερινή Γερμανία) και το πλήρες του όνομα ήταν Johann Peter Gustav Lejeune Dirichlet. Η οικογένειά του καταγόταν από την Βελγική πόλη Richelet και αυτό εξηγεί και το επίθετο που του αποδόθηκε, le jeune de Richelet, που σημαίνει ο νέος του Richelet. Από μικρό παιδί ακόμα, σε ηλικία μόλις δώδεκα χρονών, είχε φανεί η μεγάλη κλίση του στα μαθηματικά. Τόσο πολύ τον ενδιέφεραν, που ξόδευε σχεδόν ολόκληρο το χαρτζιλίκι του σε βιβλία μαθηματικών. Λέγεται ότι, η όλη παρουσία του στο γυμνάσιο ήταν τόσο εξαιρετική, που τον καθιστούσε παράδειγμα προς μίμηση για κάθε συμμαθητή του. Συνεχίζοντας τις σπουδές του μετά το γυμνάσιο στη Γερμανία και τη Γαλλία, ο Dirichlet είχε την τύχη να διδαχθεί από τους σπουδαιότερους Μαθηματικούς εκείνης της εποχής όπως τον Οhm, τον Fourier, τον Laplace, τον Legendre και τον Poisson. Ο ίδιος υπήρξε εξαίρετος δάσκαλος που εκφραζόταν πάντα με πολύ μεγάλη σαφήνεια. Το 1855 μετά το θάνατο του Gauss, είχε την τιμή να τον διαδεχθεί στο Gottingen. Στον Dirichlet οφείλουμε πολλά και σπουδαία μαθηματικά επιτεύγματα. Ένα από τα εντυπωσιακότερα (κυρίως για την απλότητα του) εργαλεία που μας κληροδότησε είναι η Αρχή της Περιστεροφωλιάς.

Η Αρχή της περιστεροφωλιάς αναφέρει πως αν ν+1 περιστέρια καθίσουν σε ν φωλιές τότε σε μία τουλάχιστον φωλιά θα καθίσουν δύο τουλάχιστον περιστέρια. Για παράδειγμα αν έχουμε 5 περιστέρια και 4 φωλιές , θα υπάρχει μία τουλάχιστον φωλιά με δύο τουλάχιστον περιστέρια!



Οι περισσότεροι άνθρωποι εκπλήσσονται από την απλότητα του κανόνα, και αμφισβητούν το μεγαλείο της ανακάλυψης και της σαφήνειας της διατύπωσης. Γεγονός όμως είναι ότι δεν φαίνεται να υπάρχει καμία αναφορά του κανόνα αυτού πουθενά στο μακραίωνο παρελθόν των μαθηματικών. Αυτό σημαίνει βέβαια πως ο κανόνας αυτός, αν δεν προέκυψε από σπουδαία μαθηματική έμπνευση προέκυψε από μεγάλη διαύγεια στη σκέψη, κι αυτό τουλάχιστον πρέπει να το πιστώσουμε στον Dirichlet. Η χρήση δε αυτής της Αρχής εκτείνεται από την Θεωρία Αριθμών μέχρι την Θεωρία Πιθανοτήτων αλλά και σε πλήθος προβλημάτων που φαίνεται να μην έχουν καμία σχέση με Μαθηματικά. Η Αρχή της περιστεροφωλιάς έχει και μια λίγο πιο δύσκολή γενίκευση με τη βοήθεια της οποίας μπορούμε να λύσουμε και άλλα εντυπωσιακά προβλήματα λογικής.



Το πρόβλημα της βιβλιοθήκης με το οποίο ξεκινήσαμε λύνεται και αυτό με την Αρχή της Περιστεροφωλιάς. Πρέπει όμως να κάνουμε την εξής λογική παραδοχή. Τα περισσότερα βιβλία έχουν από 200 μέχρι 800 σελίδες. Δεν είναι λοιπόν παράλογο να υποθέσουμε ότι δεν υπάρχουν βιβλία με περισσότερες από 10.000 σελίδες! Έτσι αν για περιστεροφωλιές βάλλουμε το πλήθος των σελίδων, αυτές θα είναι λιγότερες από 10.000. Στη συνέχεια θεωρούμε πως τα βιβλία της βιβλιοθήκης είναι τα περιστέρια. Έτσι για παράδειγμα αν κάποιο βιβλίο έχει μία σελίδα θα καθίσει στην 1η φωλιά, αν έχει δύο σελίδες στην 2η,αν έχει τριάντα σελίδες στη 30η κ.ο.κ. Όμως τα βιβλία (περιστέρια) είναι πάνω από 10.000 ενώ οι σελίδες (φωλιές) λιγότερες από 10.000 , άρα σύμφωνα με την Αρχή της Περιστεροφωλιάς δύο τουλάχιστον βιβλία (περιστέρια) θα έχουν το ίδιο πλήθος σελίδων (ίδια φωλιά).



Η συνεισφορά του Dirichlet στα μαθηματικά είναι τεράστια και οικουμενικά αναγνωρισμένη. Υπήρξε ένας από τους σπουδαιότερους της εποχής του και το όνομα του ήδη είναι γραμμένο με χρυσά γράμματα στην ιστορία των μαθηματικών. Χαρακτηριστικά είναι τα λόγια ενός μελετητή του…



« … σημαντικοί τομείς των μαθηματικών επηρεάστηκαν από τον Dirichlet. Οι αποδείξεις του ξεκινούσαν χαρακτηριστικά με εκπληκτικά απλές παρατηρήσεις, και ακολουθούσαν εξαιρετικά οξυδερκείς αναλύσεις του υπόλοιπου προβλήματος. Με τον Dirichlet άρχισε η χρυσή εποχή των μαθηματικών στο Βερολίνο!»
                                                H Koch



Ακολουθούν μερικά ακόμα απλά προβλήματα που λύνονται με παρόμοιους τρόπους

1) Μια ομάδα ποδοσφαίρου έχει 11 παίχτες. Αν ο μικρότερος είναι 21 χρονών και ο μεγαλύτερος 30, να αποδείξετε ότι δύο τουλάχιστον παίχτες έχουν την ίδια ηλικία.

2) Σ’ ένα εξεταστικό κέντρο οι δύο επιτηρητές σημειώνουν τα γραπτά με το ίδιο χρώμα στυλό, είτε και οι δύο με μπλε είτε και οι δύο με μαύρο. Αν σ’ ένα κουτί υπάρχουν 15 μπλε στυλό και 16 μαύρα, ποιος είναι ο μικρότερος αριθμός από στυλό που πρέπει να βγάλει κάποιος από το κουτί χωρίς να βλέπει, για να τους δώσει στους επιτηρητές ώστε να μπορούν να κάνουν σωστά τη δουλειά τους.

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

Μερικοί Σύνδεσμοι
 
1. Johann Peter Gustav Lejeune Dirichlet ( Πανεπιστήμιο του Αγ. Ανδρέα στη Σκοτία )
 

Τετάρτη 10 Φεβρουαρίου 2010

Το μαθηματικό δέντρο της ζωής









Έχουν κοινή ρίζα;
(Ένα μαθηματικό πρόβλημα που μπορεί να τύχει σε Ιστορικούς.)



   Σ’ ένα ιστορικό αρχείο βρέθηκαν δύο σχεδόν κατεστραμμένα γενεαλογικά δέντρα καταγεγραμμένα την ίδια χρονιά. Δυστυχώς για τους ερευνητές είχαν χαθεί πολλά στοιχεία. Το μόνο που κατάφεραν να αποσαφηνίσουν σε κάθε δέντρο ήταν η δομή του και τα ονόματα  της τελευταίας γενιάς. Τρία από τα πέντε ονόματα κάθε δέντρου είναι κοινά. Το ένα καταγράφει τέσσερις γενιές ενώ το άλλο πέντε.


Μπορούμε να καταλάβουμε αν πρόκειται για την ίδια οικογένεια ;    



  Οι περισσότεροι άνθρωποι τη μόνη σχέση της Ιστορίας με τα Μαθηματικά που κάπως έχουν ακούσει είναι η Ιστορία των Μαθηματικών.  Τη μελέτη δηλαδή της πορείας της μαθηματικής σκέψεις μέσα στους αιώνες. Από τη προϊστορική εποχή εώς τους Βαβυλώνιους και τους Αιγυπτίους, μετά στους σπουδαίους Έλληνες μαθηματικούς της αρχαιότητας, τους συστηματικούς Άραβες , τους καινοτόμους Ινδούς και τέλος στους σύγχρονους Ευρωπαίους μαθηματικούς που με τις ιδέες τους άλλαξαν κυριολεκτικά την πορεία του κόσμου. Τα τελευταία χρόνια μελετώνται και οι επιδόσεις των αρχαίων λαών της Αμερικανικής ηπείρου όπως οι Αζτέκοι και οι Ίνκας, που φαίνεται να είχαν αρκετά αναπτυγμένες μαθηματικές γνώσεις. Όμως η Ιστορία και τα Μαθηματικά σχετίζονται και με άλλο τρόπο. Δεν είναι μόνο η Ιστορία που μελετά τα Μαθηματικά αλλά καμιά φορά συμβαίνει και το αντίστροφο, δηλαδή τα Μαθηματικά μελετούν την Ιστορία. Για να είμαστε όμως πιο ακριβείς το σωστό είναι να πούμε πως τα Μαθηματικά βοηθούν στη μελέτη στοιχείων που σχετίζονται με την Ιστορία. Η λύση του προβλήματος  που δόθηκε στην αρχή θα μας δώσει μια μικρή ιδέα του πώς μπορεί να συμβεί κάτι τέτοιο, ας τη δούμε λοιπόν…

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


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


  Εκτός από την Ιστορία η χρήση των δέντρο-διαγραμμάτων με αυτό τον τρόπο, για να βρούμε δηλαδή την συμβατότητα ή όχι των στοιχείων δύο ξεχωριστών καταγραφών μπορεί να φανεί πολύ χρήσιμη στις επιστήμες της Βιολογίας, της Ζωολογίας και της  Παλαιοντολογίας.  Πολλές  ομάδες επιστημόνων και τώρα και στο παρελθόν έχουν ασχοληθεί με την ταξινόμηση των διαφόρων έμβιων οργανισμών και τα δέντρα είναι  ο συνηθέστερος τρόπος ταξινόμησης τους. Οι ταξινομήσεις  αυτές γίνονται  με στοιχεία που προκύπτουν από ευρήματα όπως τα απολιθώματα, τα καλοδιατηρημένα οστά και οι σκελετοί. Επίσης ταξινομήσεις γίνονται και με βάση στοιχεία μοριακής  βιολογίας όπως ολόκληρο το DNA ενός οργανισμού ή μόνο κάποια γονίδια που χρησιμοποιούνται ως δείκτες. Όπως είναι φυσιολογικό όμως οι ταξινομήσεις που κάνουν οι διάφορες ομάδες δεν ταυτίζονται 100%. Έτσι, μια τέτοια μέθοδος ελέγχου της συμβατότητας δύο ή περισσοτέρων δέντρο-διαγραμμάτων μπορεί να  αυξήσει  κάπως την ακρίβεια της ταξινόμησης και να εντοπίσει τις αδυναμίες ή τις ασάφειες αν υπάρχουν. Βέβαια θα πρέπει πάντα να λαμβάνονται υπ’ όψιν και άλλα επιστημονικά δεδομένα που προκύπτουν από τις ιδιαιτερότητες των συγκρινόμενων δέντρων. 

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


   Αν τελικά βρεθούν επαρκείς μέθοδοι για την δημιουργία υπέρ-δέντρων στον τομέα αυτό της φυλογένεσης, ίσος να βρεθεί κι ένας καθαρά μαθηματικός τρόπος για να ελέγξει η επιστημονική κοινότητα ακόμα περισσότερο την υπάρχουσα Θεωρία της εξέλιξης της ζωής στον πλανήτη μας. Μπορεί να βρεθεί κανόνας  υπολογισμού των χαμένων προγόνων ενός είδους ή τύπος υπολογισμού του χρόνου εξέλιξης από το ένα είδος στο άλλο. Τέτοια μαθηματικά εργαλεία, αν και φαντάζουν απρόσιτα προς το παρόν,  θα ήταν πολύ χρήσιμα στους επιστήμονες της εξέλιξης μιας και θα τους έδιναν την δυνατότητα να διαψεύσουν ή να επαληθεύσουν εικασίες που μένουν χρόνια αναπάντητες. Πάντως απ’ ότι φαίνεται, η καθαρά μαθηματική έρευνα προς  τη κατεύθυνση των υπέρ-δέντρων έχει για τα καλά ξεκινήσει κα το μόνο που μπορεί να σταματήσει την εφαρμογή των όποιων αποτελεσμάτων στα εξελικτικά ζητήματα είναι μόνο η ισχυρή αμφιβολία για την κοινή καταγωγή των έμβιων οργανισμών ή για να το πούμε αλλιώς η αναίρεση της ίδιας της θεωρίας της εξέλιξης. Κάτι τέτοιο όμως  φαίνεται μάλλον απίθανο!


Μερικοί Σύνδεσμοι


1. Το Δέντρο της Ζωής ( Wikipedia στα Αγγλικά ) 

2. Παρουσίαση Δημιουργίας Υπερδέντρου ( Πολλά και Δύσκολα Μαθηματικά στα Αγγλικά )

Δημοφιλείς αναρτήσεις

Μια ομορφιά