Αρχή Dirichlet ή Περιστερώνα
- Details
- Category: Εφαρμογές μαθηματικών
- Published on Wednesday, 15 April 2015 23:35
- Written by Super User
- Hits: 4013
Αρχή Diriclet ή Περιστερώνα ή Περιστεροφωλιάς
Ένα από τα αγαπημένα παιχνίδια σε πολλές παρέες που συνδυάζει κίνηση, ευελιξία, αντανακλαστικά και σκέψη είναι οι μουσικές καρέκλες. Σε αυτό τα παιδιά που συγκροτούν την παρέα τοποθετούν καρέκλες σε κύκλο με την πλάτη προς το εσωτερικό του κύκλου. Το πλήθος τους είναι αρχικά κατά ένα μικρότερο από το πλήθος των παικτών. Οι παίκτες αρχίζουν να τρέχουν γύρω από τις καρέκλες, ακούγοντας μουσική. Κάποια στιγμή η μουσική σταματά και όλοι πρέπει να κάτσουν σε μία καρέκλα. Χάνει όποιος δεν προλάβει να καθίσει. Θα υπάρχει ηττημένος?
Στη συνέχεια του παιχνιδιού η μουσική ξαναρχίζει και οι παίκτες και πάλι αρχίζουν να τρέχουν γύρω γύρω από τις καρέκλες, οι οποίες αυτήν τη φορά έχουν μειωθεί κατά μία, ενώ και στις επόμενες φορές μειώνονται κατά μία κάθε φορά. Κερδίζει αυτός που θα προλάβει να καθίσει πρώτος στον τελευταίο γύρο του παιχνιδιού στην τελευταία καρέκλα που θα έχει απομείνει. Θα υπάρχει νικητής?
Πέρα από την εμπειρία μας, η απάντηση επιβεβαιώνεται και από μία παρατήρηση που πρώτος συστηματοποίησε και κατέγραψε αυστηρά ο P.G.L. Dirichlet περί το 1834 και έκτοτε φέρει το όνομά του.
Ο P.G.L. Dirichlet (1805-1859) υπήρξε σημαντικός Γερμανός μαθηματικός, που σπούδασε στο Παρίσι και θήτευσε ως καθηγητής και συνεχιστής του C.F. Gauss στο διάσημο Πανεπιστήμιο του G\"ottingen
Μεταξύ άλλων στο ίδιο Πανεπιστήμιο φοίτησαν ή δίδαξαν προσωπικότητες όπως οι: Arthur Schopenhauer, οι αδελφοί Grimm, Otto von Bismarck, Edmund Husserl, Max Weber, Jurgen Habermas, Gerhard Schr\"oder, Max Planck, Werner Heisenberg, J. Robert Oppenheimer, Enrico Fermi, Wolfgang Pauli και μαθηματικοί όπως οι: Carl Friedrich Gauss, Bernhard Riemann, David Hilbert, Felix Klein, Richard Courant, Emmy Noether, Constantin Carath\'eodory, John von Neumann, Bolyai, Freudenthal, Haar, Hamel, Hecke, Hurwitz, κ.ά. Έως σήμερα 45 βραβεία Nobel είχαν συμμετοχή αποφοίτων ή καθηγητών του. Τα περισσότερα από αυτά στο πρώτο μισό του 20ου αιώνα.
Είχε σημαντική συμβολή στην αναλυτική θεωρία αριθμών, στις σειρές Fourier και στην ανάλυση γενικότερα.
Αρχή Dirichlet ή Αρχή περιστεροφωλιάς
Αν n+1 περιστέρια καθίσουν σε n φωλιές, τότε σε μία τουλάχιστον φωλιά θα καθίσουν 2 περιστέρια.
Έστω ότι καμία από τις περιστεροφωλιές δεν περιέχει 2 περιστέρια ή περισσότερα. Τότε οι k περιστεροφωλιές θα περιέχουν συνολικά το πολύ k περιστέρια, το οποίο είναι άτοπο, διότι υπάρχουν τουλάχιστον k+1 περιστέρια.
Σε οποιοδήποτε κείμενο της Ελληνικής γλώσσας, σε μία σειρά από 26 λέξεις τουλάχιστον 2 αρχίζουν από το ίδιο γράμμα.
[Ισοδύναμη διατύπωση]
Έστω φυσικός αριθμός k και k+1 ή περισσότερα αντικείμενα τοποθετούνται σε k κουτιά. Τότε υπάρχει τουλάχιστον ένα κουτί, το οποίο περιέχει δύο ή περισσότερα αντικείμενα.
Σε ολόκληρη την Αττική υπάρχουν τουλάχιστον 2 άτομα που έχουν ακριβώς το ίδιο πλήθος από τρίχες στο κεφάλι τους.
Στο σχολείο μας (Γυμνάσιο και Λύκειο) υπάρχουν τουλάχιστον δύο μαθητές που έχουν την ίδια ημέρα γεννέθλια.
Αν επιλέξουμε πέντε αριθμούς από τους ακέραιους 1-8, τότε δύο από αυτούς έχουν άθροισμα 9.
Μία αντιστοίχιση των k+1 ή περισσοτέρων στοιχείων ενός συνόλου Α στα k στοιχεία ενός συνόλου Β δεν μπορεί να γίνει ένα προς ένα στοιχείο.
Για παράδειγμα όταν συγκρίνουμε δύο τρίγωνα αναζητούμε να αντιστοιχίσουμε στοιχεία ένα προς ένα και αντίστοιχα μεταξύ τους. Ας υποθέσουμε τρεις πλευρές. Αν θέλαμε να συγκρίνουμε τρίγωνο με τετράπλευρο η αντιστοίχιση των πλευρών δεν θα μπορούσε να γίνει μία προς μία.
Ας εξετάσουμε τώρα κάποιους γενικούς κανόνες που μπορούμε να συνάγουμε για τη χρήση της αρχής.
- Σε πρώτη φάση προσδιορίζουμε τους ρόλους. Δηλαδή ποια αντικείμενα έχουν το ρόλο των «περιστεριών» και ποια αντικείμενα το ρόλο της «περιστεροφωλιάς».
- Τα αντικείμενα «περιστέρια» και «φωλιές» είναι εντελώς αφηρημένα και μπορεί να αντικαθίστανται σχεδόν από οτιδήποτε βολικό.
- Φυσιολογικά φροντίζουμε ώστε οι περιστεροφωλιές να είναι λιγότερες από τα περιστέρια.
- Φτιάχνουμε έναν κανόνα τοποθέτησης των περιστεριών στις φωλιές τους.
Το συμπέρασμα της αρχής της περιστεροφωλιάς ισχύει για οποιαδήποτε τοποθέτηση περιστεριών σε φωλιές, οπότε επιλέγουμε τον κανόνα αντιστοίχισης, ώστε «αρκετά» από τα περιστέρια να βρίσκονται στην ίδια περιστεροφωλιά που δίνει τη ζητούμενη ιδιότητα.
- Εφαρμόζουμε την Α.Π.Φ. με βάση τα παραπάνω.
Ας εξετάσουμε τώρα μία λύση της άσκησης:
Θα επιλέξουμε αριθμούς μεταξύ των 1-8. Προφανώς οι 5 αριθμοί που θα επιλέξουμε θα είναι τα «περιστέρια». Οι περιστεροφωλιές θα πρέπει να είναι τέσσερεις το πολύ. Δηλαδή, θα χωρίσουμε τους αριθμούς σε ομάδες, ώστε αριθμοί από διαφορετικές ομάδες να δίνουν άθροισμα 9.
Επιλέγουμε $ \{1,2\}, \{3,4\}, \{5,6\}, \{7,8\} $ τις περιστεροφωλιές. Τότε από τους $5$ αριθμούς που επιλέχθηκαν τουλάχιστον δύο θα έχουν άθροισμα 9.
- Να αποδειχθεί ότι ανάμεσα σε 52 θετικούς ακέραιους αριθμούς υπάρχουν δύο των οποίων η διαφορά ή το άθροισμα διαιρείται με από το 100.
- Να αποδειχθεί ότι ανάμεσα σε 4 αριθμούς υπάρχουν 2, ώστε η διαφορά τους να διαιρείται από το 3.
- Να αποδειχθεί ότι ανάμεσα σε $n+1$ ακεραίους υπάρχουν δύο, των οποίων η διαφορά διαιρείται με $n$.
Γενικευμένη αρχή της περιστεροφωλιάς
Σε αρκετές περιπτώσεις η χρήση της αρχής του Dirichlet γίνεται ευκολότερα με χρήση μίας διαφορετικής διατύπωσης:
[Γενικευμένη αρχή περιστεροφωλιάς]
Αν n περιστέρια καθίσουν σε k περιστεροφωλιές, όπου n>k, τότε υπάρχει τουλάχιστον μία περιστεροφωλιά με τουλάχιστον n/k περιστέρια.
Αν για παράδειγμα υπάρχουν $5$ περιστέρια που κάθονται σε $2$ περιστεροφωλιές, τότε μία από αυτές πρέπει να έχει $\frac{5}{2} = 2,5$ περιστέρια. Προφανώς, εφόσον ο αριθμός των περιστεριών πρέπει να είναι ακέραιος, προκύπτει ότι τουλάχιστον μία θα έχει τρία περιστέρια.
Απόδειξη:
Ας υποθέσουμε ότι δεν υπάρχει περιστεροφωλιά με $\frac{n}{k}$ περιστέρια.
Τότε κάθε περιστεροφωλιά θα έχει λιγότερα από $\frac{n}{k}$ περιστέρια, οπότε ο συνολικός αριθμός περιστεριών στις $k$ περιστεροφωλιές θα είναι μικρότερος του $\frac{n}{k} \cdot k = n$ το οποίο είναι άτοπο αφού ο αριθμός των περιστεριών είναι ακριβώς $n$. Συνεπώς, υπάρχει περιστεροφωλιά με $\frac{n}{k}$ περιστέρια τουλάχιστον.
Παράδειγμα:
Ας υποθέσουμε ότι υπάρχουν $50$ καλάθια με πορτοκάλια. Αν κάθε καλάθι περιέχει το πολύ $24$ πορτοκάλια, τότε υπάρχουν $3$ τουλάχιστον καλάθια, τα οποία περιέχουν ακριβώς τον ίδιο αριθμό πορτοκαλιών.
Εδώ τα «περιστέρια» είναι τα καλάθια και τα τοποθετούμε στις $24$ «περιστεροφωλιές» ανάλογα με το πόσα πορτοκάλια περιέχει το καθένα. Έτσι ο λόγος $\frac{n}{k}$ των περιστεριών προς τις περιστεροφωλιές είναι $\frac{50}{24}=2 + \frac{2}{24}$. Οπότε από τη γενικευμένη αρχή της περιστεροφωλιάς υπάρχουν τουλάχιστον τόσα καλάθια με το ίδιο πλήθος πορτοκαλιών, δηλαδή τουλάχιστον 3 καλάθια.
Να αποδειχθεί ότι για κάθε φυσικό αριθμό $n$ υπάρχει αριθμός που αποτελείται από τα ψηφία $5$ και $0$ και διαιρείται από τον $n$.
Έστω ένα ισόπλευρο τρίγωνο με μήκος πλευράς $2$ και πέντε εσωτερικά σε αυτό σημεία. Να αποδειχθεί ότι τουλάχιστον δύο από τα σημεία έχουν απόσταση μικρότερη από $1$.
Αν επιλεχθούν $51$ ακέραιοι αριθμοί μεταξύ του $1$ και του $100$, τότε υπάρχουν τουλάχιστον δύο συνεχόμενοι. %de-D4
[Ισοδύναμη διατύπωση]
Αν περισσότερα από $n \cdot k$ αντικείμενα τοποθετηθούν σε $n$ κελιά, τότε κάποιο κελί περιέχει περισσότερα από $k$ αντικείμενα.
Διαφορετικά διατυπωμένο: Αν $nk + 1$ αντικείμενα τοποθετηθούν σε $n$ κελιά, τότε κάποιο κελί θα περιέχει $k+1$ αντικείμενα.
Σε ένα διαγωνισμό ΠΡΟΠΟ με $13$ αγώνες κάποιος θέλει να πετύχει τουλάχιστον $5$ σωστές προβλέψεις σε μία τουλάχιστον στήλη του δελτίου του. Να βρεθεί ο ελάχιστος αριθμός στηλών που πρέπει να συμπληρώσει.
Αν μία τράπουλα έχει $52$ φύλλα να βρεθεί πόσα φύλλα πρέπει να επιλεχθούν, ώστε να υπάρχουν τουλάχιστον 3 κάρτες του ίδιου συμβόλου στην επιλογή.
[Γνήσια αρχή της περιστεροφωλιάς]
Για κάθε μη κενό πεπερασμένο σύνολο αριθμών ο μεγαλύτερος είναι τουλάχιστον ίσος με τη μέση τιμή τους.
Την καθαρά Δευτέρα ο Δήμος Αθηναίων θα εορτάσει στο Ολυμπιακό Στάδιο, για το οποίο έχουν δοθεί 70.000 ατομικές προσκλήσεις. Να αποδειχθεί ότι τουλάχιστον $192$ άτομα από αυτούς που θα συμμετέχουν στη γιορτή θα έχουν γενέθλια την ίδια ημέρα.