Μαθήματα Ευρετικής. Η αρχή της περιστεροφωλιάς και η Αριστοτελική οξυδέρκεια.

   

            

                                

 Ο πρώτος κανόνας διδασκαλίας είναι να γνωρίζετε αυτό που πρόκειται να διδάξετε. 

 Ο δεύτερος κανόνας είναι  να γνωρίζετε λίγο περισσότερα από αυτά που πρέπει να διδάξετε.

 Ο τρίτος κανόνας είναι να εφαρμόζετε απαρέγκλιτα τους δυο πρώτους κανόνες.

                                                                                 Ανώνυμος μαθηματικός

    Ο Polya στο κλασσικό του βιβλίο «πώς να το λύσω» ισχυρίζεται ότι η σύλληψη μιας φαεινής ιδέας είναι μια πράξη οξυδέρκειας και παραθέτει τον Αριστοτέλη :

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

 Δεν μπορώ να φανταστώ χαρακτηριστικότερο παράδειγμα απλής μα και οξυδερκούς   μαθηματικής σύλληψης από την αρχή της περιστεροφωλιάς.

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

Ας το σκεφτούμε λίγο.

                               

 Έστω ότι στο πάρτι υπάρχουν Ν καλεσμένοι.Έστω,επίσης ότι κατασκευάζουμε ταμπελακια με αρίθμηση 0,1,2,3,4,…..Ν-1, και δίνουμε σε κάθε καλεσμένο ένα ταμπελακι  στον αριθμό του οποίου  αντιστοιχίζεται ο αριθμός των γνωστών του. Παρατηρούμε ότι μόνο ένα από τα ταμπελακια με τους αριθμούς 0 και Ν-1 θα δινόταν σε καλεσμένο γιατί αποκλείεται ένας καλεσμένος να μην έχει γνωστούς και συγχρόνως ένας άλλος να τους γνωρίζει όλους στο πάρτι.Άρα έχουμε Ν-1 ταμπελακια και Ν καλεσμένους .Έχουμε δηλαδή λιγότερους αριθμούς στα ταμπελάκια από το πλήθος των καλεσμένων,μοιραία λοιπόν  δυο καλεσμένοι θα έπαιρναν ταμπελάκια με το ίδιο αριθμό,θα είχαν δηλαδή  τον ίδιο αριθμό γνωστών στην συγκέντρωση. 

    Η ιδέα που κρύβεται πίσω από αυτό το γνωστό πρόβλημα ονομάζεται αρχή των θυρίδων του  Ντιριχλετ (Dirichlet's Box Principle) ή αλλιώς αρχή της περιστεροφωλιάς (pigeonhole principle).Το θεώρημα αποδίδεται στον Γερμανό Μαθηματικό Johann Peter Gustav Lejeune Dirichlet.Από μικρό παιδί ακόμα, είχε φανεί η μεγάλη κλίση του Dirichlet στα μαθηματικά.  Συνεχίζοντας τις σπουδές του μετά το γυμνάσιο στη Γερμανία και τη Γαλλία, ο Dirichlet είχε την τύχη να διδαχθεί από τους σπουδαιότερους Μαθηματικούς εκείνης της εποχής όπως τον Οhm, τον Fourier, τον Laplace, τον Legendre και τον Poisson. Ο ίδιος υπήρξε εξαίρετος δάσκαλος που εκφραζόταν πάντα με πολύ μεγάλη σαφήνεια. Το 1855 μετά το θάνατο του  Gauss, είχε την τιμή να τον διαδεχθεί στο Gottingen.

Johann Peter Gustav Lejeune Dirichlet(1805–1859)

                                        

  Η αρχή της περιστεροφωλιάς (ή αρχή του Dirichlet) αναφέρεται πρώτη φορά στο βιβλίο του, Recherches sur les forms quadratiques à coefficients et à indéterminées complexes που εκδόθηκε το 1842.

   Η αρχή της περιστεροφωλιάς είναι ένα πολύ ισχυρό εργαλείο το όποιο χρησιμοποιείται στην συνδυαστική ανάλυση. Αλλά η βασική ιδέα είναι πολύ απλή και εξηγείται εύκολα.
Ας φανταστούμε 3 περιστέρια τα όποια πρέπει να τοποθετηθούν σε 2 περιστεροφωλιές . Μπορούμε να το κάνουμε; Φυσικά και μπορούμε αλλά είναι προφανές ότι με όποιο τρόπο και αν βάλουμε τα περιστέρια,σίγουρα ,σε μια περιστεροφωλιά θα τοποθετήσουμε τουλάχιστον δυο περιστέρια. 


                            

Μπορούμε να γενικεύσουμε για πολύ μεγαλύτερους αριθμούς .Η αρχή της περιστεροφωλιας διατυπωνεται ως εξης:

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

«Αν έχουμε κν+1 ή περισσότερα αντικείμενα  και πρέπει να κατανεμηθούν σε ν κουτιά, τότε κάποιο από τα κουτιά πρέπει να περιέχει τουλάχιστον κ+1 αντικείμενα» ή πιο συγκεκριμένα  στο προηγούμενο παράδειγμα  15=2* 7 +1 .

Είναι λογικό διότι, αν θεωρήσουμε λ₁ , λ₂ ,λ₁ ,…., λ_ν το πλήθος των αντικειμένων στο 1^ο ,2^ο ,3^ο ,…,ν-ιοστό κουτί  και υποθέσουμε ότι δεν υπάρχει κουτί  με κ+1 αντικείμενα τότε θα ισχύει:

                                                        λ₁<=κ

                                                        λ₂<=κ

                                                         λ₃<=κ

                                                             .

                                                             .

                                                        λ_ν<=κ

Προσθέτουμε κατά μέλη : λ₁ +λ₂ +λ₁ +….+λ_ν<=κν<κν+1, άτοπο.

Μερικές εφαρμογές της αρχής

1)Μεταξύ  τριών προσώπων,υπάρχουν τουλάχιστον δύο του ίδιου φύλου.Σε 3 αριθμούς (άνισους του μηδέν!) τουλάχιστον οι 2 είναι ομόσημοι.

2) Αν έχουμε 25 λέξεις  τότε σίγουρα δυο από αυτές θα αρχίζουμε τα ίδιο γράμμα.Οι  25 λέξεις (περιστέρια)  και 24 γράμματα (περιστεροφωλιες) του ελληνικού αλφάβητου.

3) Ανάμεσα σε ν διαδοχικούς αριθμούς τουλάχιστον 1 διαιρείται με τον ν  (ν-1 υπόλοιπα-φωλιές)

4)Χρωματίζουμε όλα τα σημεία του επιπέδου πράσινα ή κόκκινα (Π ή Κ). Να αποδείξετε ότι υπάρχουν τουλάχιστον 2 σημεία με το ίδιο χρώμα, τα οποία απέχουν μεταξύ τους 10 Κm. Θεωρούμε ισόπλευρο τρίγωνο ΑΒΓ με πλευρά α=10 Κm. Οι κορυφές του τριγώνου είναι 3 (περιστέρια) και τα χρώματα 2(φωλιές). Άρα με 1 χρώμα (φωλιά) θα χρωματιστούν τουλάχιστον 2 κορυφές (περιστέρια). Άρα 2 τουλάχιστον κορυφές θα έχουν το ίδιο χρώμα.

                                                    

5)Στην Αθήνα των 2.640.701 κατοίκων σίγουρα υπάρχουν τουλάχιστον 14 άνθρωποι (που δεν είναι φαλακροί) οποίοι έχουν τον ίδιο αριθμό από τρίχες στο κεφάλι τους δεδομένου ότι   κανένας άνθρωπος δεν έχει πάνω από 200.000 τρίχες στο κεφάλι του . (2.640.701=13*200.000+40.701)
 
6)Την στιγμή που γράφω αυτήν ανάρτηση σίγουρα υπάρχουν δυο αναρτήσεις με τον  ίδιο αριθμό από σχόλια στην διάρκεια ενός έτους. Δεδομένου ότι υπάρχουν πάνω από  8.2 εκατομμύρια  blogs και  για καμία ανάρτηση δεν υπάρχουν ετήσια πάνω από 8.2 εκατομμύρια σχόλια.
 

7) Αν διαλέξουμε τυχαία πέντε αριθμούς  από τους ακεραίους  από το 1 μέχρι το 8 τότε δυο από αυτούς  πρέπει να έχουν άθροισμα 9.
   Κάθε αριθμός  από το 1 μέχρι το 8 μπορεί  σαν ζευγάρι κάποιον άλλο από τους 8 να έχει άθροισμα 9 .Συνολικά είναι 4 τέτοια ζεύγη.
                                   1    με 8
                                   2    με 7
                                   3    με το 6 και τέλος  4 με 5
Ο καθένας από  5 αριθμούς πρέπει   να ανήκει σε ένα από τα  τέσσερα ζευγάρια, άρα από την αρχή της περιστεροφωλιάς ένα ζεύγος σίγουρα ανήκει στην ομάδα των 5 οπότε έχει άθροισμα 9.
 
8) (θέμα από Thaddeus Gorian college)
  Ο Παπαδόπουλος διατηρεί ένα διαδικτυακό κατάστημα και εμπορεύεται φορητούς υπολογιστές.Κοιτώντας τις πωλήσεις που έκανε στο χρονικό διάστημα από την 1^η Μαρτίου μέχρι την 16^η Μαΐου,έκανε τις εξής παρατηρήσεις : 

- Κάθε μέρα κατόρθωσε να πουλήσει  τουλάχιστον ένα υπολογιστή.

- Δεν πούλησε συνολικά παραπάνω από 132 υπολογιστές.

( για το παραπάνω χρονικό διάστημα)

  Να αποδείξετε ότι  υπάρχουν κάποιες συνεχόμενες μέρες  που ο Παπαδόπουλος πούλησε ακριβώς 21 υπολογιστές.Το κατάστημα είναι διαδικτυακό , άρα στο παραπάνω χρονικό διάστημα δεν υπάρχουν αργίες,ούτε ημέρες που το κατάστημα  δεν λειτούργησε.

Σκεφτόμαστε ως εξής:

Από την 1^η Μαρτίου μέχρι την 16^η Μαΐου έχουμε συνολικά 77 ημέρες .Έστω

Υ_i ο αριθμός των υπολογιστών που πούλησε μέχρι και την i μέρα .Έχουμε λοιπόν:

                                    1<=Υ₁< Υ₂<… <Υ₇₇<=132  προσθετουμε το 21

                                        22<= Υ₁+21< Υ₂+21<…< Υ₇₇+21<=153

  Όμως μεταξύ των παραπάνω 154 αριθμών

                                      Υ₁, Υ₂,.. ,Υ₇₇,.. Υ₁+21, Υ₂+21,…,Υ₇₇+21

από την αρχή της περιστεροφωλιάς θα υπάρχουν σίγουρα δυο ίσοι αριθμοί άρα υπάρχουν δείκτες ημερών i και j τέτοια ώστε Υ_i = Υ_j +21  έτσι ο Παπαδόπουλος θα έχει πουλήσει ακριβώς  21 υπολογιστές τις μέρες j+1,j+2,..,i.

   

9)Από τον διαγωνισμό Θαλή.

  Σε μια κατασκήνωση υπάρχουν 577 παιδιά από 9 διαφορετικές χώρες. Σε οποιαδήποτε ομάδα 9 παιδιών υπάρχουν τουλάχιστον 2 παιδιά με το ίδιο ύψος. Να αποδειχθεί ότι υπάρχει ομάδα 5 παιδιών από την ίδια χώρα, του ιδίου φύλου και του ιδίου ύψους.

 Έχουμε 577 (παιδιά)=64*9(χώρες)+1.Άρα τουλάχιστον μια χώρα θα έχει τουλάχιστον 65 παιδιά.Αφού:65=2*32+1 Σημαίνει πως 33 τουλάχιστον παιδιά είναι και  του ιδίου φύλου

Έστω τώρα πως σε αυτά τα 33 παιδιά δεν υπάρχει ομάδα 5 παιδιών του ιδίου  ύψους. Τότε θα υπάρχουν ομάδες με 4 το πολύ παιδιά του ιδίου ύψους. Επειδή  33=4*8(ομάδες)+1 θα υπάρχουν τουλάχιστον 8+1=9 ομάδες παιδιών του ιδίου  ύψους μέσα από τα 33 παιδια που αναφέραμε.Αν από καθεμία από αυτές τις 9 ομάδες πάρουμε ένα παιδί τότε θα δημιουργήσουμε μια ομάδα 9 παιδιών που  έχουν όλα διαφορετικό ύψος. Αυτό όμως είναι άτοπο διότι δίνεται ότι σε οποιαδήποτε ομάδα 9 παιδιών υπάρχουν τουλάχιστον 2 παιδιά με το ίδιο ύψος.

10) Σε ένα ελληνικό πανεπιστήμιο φοιτούν  2800  χιλιάδες φοιτητές τότε σίγουρα υπάρχουν   τουλάχιστον  54 φοιτητές θα κατάγονται από τον ίδιο νομό της Ελλάδας.(Οι νομοί της Ελλάδας είναι 51 άρα 2800/51 =54.90196078431372 ) .


Σχετική βιβλιογραφία (κλικαρετε στα link για να κατεβάσετε τα βιβλία)
A.Engel ,Problem solving strategies
D.Fomin,S.Genkin,I.Itenberg,Mathematical circles( Russian experience)
P.Zeitz, The art and craft of problem solving  
Συνδυαστική, Κοντοκώστας Δημήτρης
Barbeau Ed,Klamkin M ,Five hundred mathematical challenges
Ανδρέας Πούλος,Ο Οιδίποδας και η Σφίγγα (Αξίζει να το αγοράσετε) 
Το Φ,μαθηματικό περιοδικό,τεύχος 4 (Αξίζει επίσης να το αγοράσετε,αξίζει να αγοράσετε κάθε τεύχος του φ)

Σύνδεσμοι στο διαδίκτυο:
 https://mathhmagic.blogspot.com/search/label/%CE%A0%CF%81%CE%BF%CE%B5%CF%84%CE%BF%CE%B9%CE%BC%CE%B1%CF%83%CE%AF%CE%B1%20%CE%BC%CE%B1%CE%B8%CE%B7%CE%BC%CE%B1%CF%84%CE%B9%CE%BA%CF%8E%CE%BD%20%CE%B4%CE%B9%CE%B1%CE%B3%CF%89%CE%BD%CE%B9%CF%83%CE%BC%CF%8E%CE%BD

 http://www.cut-the-knot.org/do_you_know/pigeon.shtml
 http://www.math.ucsd.edu/~jverstra/dirichletbox.pdf
 http://www.math.ust.hk/~mabfchen/Math391I/Pigeonhole.pdf
 http://usamts.org/Solutions/Solution4_1_18.pdf
 http://www.math.ualberta.ca/pi/issue1/page19-20.pdf 
 http://www.math.illinois.edu/~hildebr/putnam/training/pigeonhole13-1.pdf
 http://www.ucd.ie/t4cms/Pigeonhole_principle.pdf

Ένα μικρό βιβλιαράκι με συναφή θεματολογία για μαθηματικούς διαγωνισμούς