«Ο Αρχιμήδης θα μνημονευθεί όταν ο Αισχύλος θα έχει λησμονηθεί, διότι οι γλώσσες πεθαίνουν, μα οι μαθηματικές ιδέες όχι.» G.Hardy


Τετάρτη, 16 Απριλίου 2014

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

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


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


    Ο 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.

Peter Gustav Lejeune Dirichlet.jpg
Johann Peter Gustav Lejeune Dirichlet(1805–1859)
                                        

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



                           File:TooManyPigeons.jpg 

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

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

  Σε μια διαφορετική διατύπωση:


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

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

                                                        λ1<=κ

                                                        λ2<=κ

                                                         λ3<=κ

                                                             .

                                                             .

                                                        λν<=κ

Προσθέτουμε κατά μέλη : λ1 21 +….+λν<=κν<κν+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 κατοίκων σίγουρα υπάρχουν τουλάχιστον 13 άνθρωποι (που δεν είναι φαλακροί) οποίοι έχουν τον ίδιο αριθμό από τρίχες στο κεφάλι τους δεδομένου ότι   κανένας άνθρωπος δεν έχει πάνω από 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<=Υ1< Υ2<… <Υ77<=132  προσθετουμε το 21

                                        22<= Υ1+21< Υ2+21<…< Υ77+21<=153

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

                                      Υ1, Υ2,.. ,Υ77,.. Υ1+21, Υ2+21,…,Υ77+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 (Αξίζει επίσης να το αγοράσετε,αξίζει να αγοράσετε κάθε τεύχος του φ)

Σύνδεσμοι στο διαδίκτυο:



15 σχόλια:

  1. Κύριε Δρούγα καλημέρα σας,
    Φρονώ ότι στο κατωτέρω κείμενο ο αριθμός 25, που γράφθηκε εκ παραδρομής, πρένει να γραφεί 15.
    **********************************************************************************************
    Υπάρχει και μια άλλη εκδοχή της αρχής η οποία ισχυρίζεται ότι η μεγίστη τιμή ενός μη κενού συνόλου πραγματικών αριθμών είναι ιση η μεγαλύτερη από την μέση τιμή των αριθμών.Μην σας τρομάζει η διατύπωση,η ιδέα προσεγγίζεται πολύ εύκολα διαισθητικά. Αν έχουμε 15 ανθρώπους τότε τουλάχιστον δυο από αυτούς γεννήθηκαν την ιδία μέρα της εβδομάδας,25 /7 =2,1 άνθρωποι ανά ημέρα της εβδομάδας .
    Σε μια διαφορετική διατύπωση:
    «αν έχουμε κν+1 ή περισσότερα αντικείμενα και πρέπει να κατανεμηθούν σε ν κουτιά, τότε κάποιο από τα κουτιά πρέπει να περιέχει τουλάχιστον κ+1 αντικείμενα» ή πιο συγκεκριμένα στο προηγούμενο παράδειγμα 25=2* 7 +1
    **************************************************************************************************
    Σας εύχομαι Καλή Ανάσταση και Καλό Πάσχα!
    Φιλικά,
    Carlo de Grandi
    .

    ΑπάντησηΔιαγραφή
  2. Έχετε δίκιο ,ευχαριστώ για την διόρθωση ,Καλό Πάσχα

    ΑπάντησηΔιαγραφή
  3. Στο ίδιο κείμενο αναφερόταν δύο φορές το λάθος. Πρέπει να διορθώσετε και το δεύτερο 25 σε 15:
    ... Σε μια διαφορετική διατύπωση:
    «αν έχουμε κν+1 ή περισσότερα αντικείμενα και πρέπει να κατανεμηθούν σε ν κουτιά, τότε κάποιο από τα κουτιά πρέπει να περιέχει τουλάχιστον κ+1 αντικείμενα» ή πιο συγκεκριμένα στο προηγούμενο παράδειγμα 25=2* 7 +1
    **************************************************************************************************

    ΑπάντησηΔιαγραφή
  4. Είναι σωστό να δίνετε link για κατέβασμα των βιβλίων;

    ΑπάντησηΔιαγραφή
  5. Να προσθέσω στο ωραίο κείμενο πως η αρχική ορολογία του Ντίριχλετ για την αρχή του περιστερώνα ήταν "αρχή του συρταριού" (Schubfachprinzip (Σούμπφαχπριντσίπ) στα γεμανικά. Ορολογία που ακόμη χρησιμοποιείται από τους γερμανόφωνους.
    Πολύ δυνατή Αρχή ! Kαι, κάτι πολύ σημαντικό, ισχύει ακόμη και για συνεχείς ποσότητες ,κι όχι μόνο για διακριτές. Aυτό ξεφεύγει μερικές φορές (μαζί με την ευκαιρία ωραίων και απλών (όχι απλοϊκών!)) λύσεων.

    ΑπάντησηΔιαγραφή
  6. Δεν ανέβασα εγώ τα βιβλία ,τα link δίνω,τώρα τι είναι σωστό και τι είναι λάθος ο καθένας έχει τις απόψεις του.

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

    ΑπάντησηΔιαγραφή
  8. Οι συγγραφείς; τα δικαιώματα κ.Δρούγα;

    ΑπάντησηΔιαγραφή
  9. Καλό θα ήταν να σχολιάζετε επώνυμα, όσο για τους συγγραφείς ο ένας υπήρξε προπονητής της ολυμπιακής ομάδας της Γερμανίας , ο άλλος της Αμερικής ,άνθρωποι με πάθος για τα μαθηματικά , νομίζετε ότι θα έφερναν αντίρρηση να κατεβάσει ένα παιδί ή οποιοσδήποτε άλλος με αγάπη στο αντικείμενο τα βιβλία τους την στιγμή που βεβαιωμένα δεν διαθέτει 100 και πλέον ευρώ για τα αγοράσει, και επαναλαμβάνω δεν ανέβασα εγώ τα βιβλία.

    ΑπάντησηΔιαγραφή
  10. άλλα λέγατε ,εδώ :
    http://mathhmagic.blogspot.gr/2013/08/blog-post.html

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

    ΑπάντησηΔιαγραφή
  12. Κύριε Δρούγα,
    Έχετε απόλυτο δίκιο.Το να επιμένει κάποιος για ένα θέμα προφανές, και δη ανώνυμα, είναι κάπως γελοίο, εφόσον αποδεδειγμένα φαίνεται ότι αναρτήθηκαν από τους ίδιους τους συγγραφείς για ευνόητους λόγους, όπως ανάφερετε.
    Μακάρι όλοι συγγραφείς να έκαναν το ίδιο.
    Φιλικά,
    Carlo de Grandi

    ΑπάντησηΔιαγραφή
  13. Συμφωνούμε,κ.de grandi ο καθένας δικαιούται να έχει αποψη , δεν είμαστε όμως υποχρεωμένοι να την δεχτούμε.

    ΑπάντησηΔιαγραφή

Related Posts Plugin for WordPress, Blogger...