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


Σάββατο, 27 Ιανουαρίου 2018

Ένα θεώρημα για την φύλαξη του μουσείου και μια απόδειξη απο το βιβλίο...

O Έρντος με το βιβλίο....

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

 Μια απόδειξη από το βιβλίο
  
   Το θεώρημα φύλαξης του μουσείου (Αrt gallery problem) είναι ένα γνωστό πρόβλημα υπολογιστικής γεωμετρίας.Τέθηκε το 1973,από τον Αμερικανό μαθηματικό Victor Clee.Το απέδειξε το 1975,ο μαθηματικός Václav Chvátal.Περίπου πέντε χρόνια αργότερα  ένας άλλος μαθηματικός, ο S.Fisk επανήλθε με μια κομψή απόδειξη. 

                                                        Το πρόβλημα 

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


  Το ερώτημα: Ποιος είναι ο ελάχιστος αριθμός φυλάκων για να εποπτεύεται πλήρως η αίθουσα;

  Η αίθουσα του μουσείου έχει κάτοψη ένα απλό κλειστό πολύγωνο,με την λέξη απλό θεωρούμε ότι οι πλευρές του είναι  ευθύγραμμα τμήματα που όμως δεν τέμνονται μεταξύ τους. Επίσης,θεωρούμε ότι οι  φύλακες θα τοποθετηθούν στις κορυφές του πολυγώνου. Είναι προφανές ότι ο ελάχιστος αριθμός φυλάκων εξαρτάται από τον αριθμό ν των κορυφών του πολυγώνου.      
   Αποδεικνύεται ότι, για την πλήρη φύλαξη και επόπτευση μιας απλής κλειστής πολυγωνικής αίθουσας  με ν πλευρές (τοίχους)-ότι σχήμα και να έχει-απαιτούνται το πολύ [ν/3] φύλακες. 
 ('Οπου [x] είναι το ακέραιο μέρος του αριθμού x ,δηλαδή ο μεγαλύτερος ακέραιος που δεν υπερβαίνει τον ίδιο τον αριθμό x)
 Δηλαδή,στο παρακάτω σχήμα με 9 κορυφές,απαιτούνται το πολύ [9/3]=3  φύλακες. 


                                                       Πως αποδεικνύεται;
 

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

                                          Πως θα χωρίσουμε το πολύγωνο;

  Μια μέθοδος για να το κάνουμε είναι να το χωρίσουμε σε τρίγωνα.Φέρνουμε διαγώνιους έτσι ώστε να μην τέμνονται.Η διαδικασία ονομάζεται τριγωνοποιήση.Υπάρχουν πολλές τριγωνοποιησεις για το ίδιο σχήμα.
Δείτε το παρακάτω σχήμα.


  Προφανώς ένας φύλακας που τοποθετείται σε μια κορυφή  ενός τριγώνου μπορεί να εποπτεύσει ολόκληρο το τρίγωνο.Το τρίγωνο είναι κυρτό σχήμα δηλαδή κάθε ευθύγραμμο τμήμα που ενώνει δυο σημεία του βρίσκεται εξολοκλήρου μέσα στο τρίγωνο.Άρα,μια πρώτη σκέψη είναι ότι οι θέσεις των φυλάκων θα είναι σίγουρα σε κορυφές τρίγωνων. Επίσης,παρατηρούμε ότι όταν δυο ή περισσότερα  τρίγωνα έχουν κοινή κορυφή ο φύλακας πρέπει να τοποθετηθεί σε αυτήν για να τα εποπτεύει όλα.Πως θα γίνει η τοποθέτηση και πόσοι φύλακες θα απαιτηθούν;
   Καταφεύγουμε στην θεωρία γράφων.Χρωματίζουμε τις κορυφές των τριγώνων  με διαφορετικά χρώματα με τέτοιο τρόπο έτσι ώστε κάθε δυο γειτονικές κορυφές δεν έχουν το ίδιο χρώμα.Ποιος είναι ο ελάχιστος αριθμός διαφορετικών χρωμάτων που απαιτείται στο παραπάνω σχήμα και καλύπτει την παραπάνω προϋπόθεση;Απάντηση,μόνο 3.
   Δείτε το σχήμα.Αν θεωρήσουμε τους φύλακες στις κορυφές με κόκκινο χρώμα τότε αυτοί εποπτευουν όλη την αίθουσα,συνεπώς οι κόκκινοι φύλακες αποτελούν μια λύση του προβλήματος.Λύσεις του προβλήματος αποτελούν και οι μπλε και οι πράσινοι φύλακες.
Επιλέγουμε το χρώμα με το λιγότερο πλήθος κορυφών(εδώ τυχαίνει είναι το ίδιο πλήθος για κάθε χρώμα).
  Γενικά μετά τον χρωματισμό ενός ν-γωνου με τις παραπάνω προϋποθέσεις με τρία χρώματα το χρώμα που εμφανίζεται τις λιγότερες φορές  βρίσκεται το πολύ σε  [ν/3] κορυφές.


 Βρήκαμε λοιπον ότι χρειάζονται το πολύ 3 φύλακες για μια βέλτιστη τοποθέτηση (π.χ μπλε κορυφες)  που φαίνεται στο παρακάτω σχήμα 
  Η τριγωνοποίηση μπορεί να γίνει με πολλούς τρόπους. Όμως,αποδεικνύεται,ότι ,όπως και να χωρίσουμε το πολύγωνο σε τρίγωνα πάντα 3 χρώματα είναι αρκετά για τον χρωματισμό έτσι ώστε δυο γειτονικές κορυφές να έχουν διαφορετικά χρώματα.
  Ο Πινγκ Πονγκ το εξηγεί συνοπτικά για ένα δεξαεξαγωνικο μουσείο...



 Ένα σχετικό πρόβλημα μου έστειλε ο φίλος του ιστολογιου  Carlo De Grandi  (http://papaveri48.blogspot.gr/) και τον ευχαριστώ.




Έλεγχος των δρόμων




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


Λύση:
Θα τοποθετηθούν στις θέσεις: «B», «G», και  «H».

 



Περαιτέρω αναφορές

1.How to Guard an Art Gallery And Other Discrete Mathematical Adventures, T. S. Michael
  The Johns Hopkins University Press
2.Proofs from the book ,M Aigner,M Ziegler
3.http://mathworld.wolfram.com/ArtGalleryTheorem.html
4.http://www-users.math.umn.edu/~reiner/Talks/ArtGallery.pdf

Ένα σχετικό βίντεο:
                              
                    

4 σχόλια:

  1. Κύριε Δρούγα καλημέρα σας!!
    Ν' αντικαταστήσετε στη κατωτέρω φράση το [x] με [ν]:

    ...('Οπου [x] είναι το ακέραιο μέρος του αριθμού x ,δηλαδή ο μεγαλύτερος ακέραιος που δεν υπερβαίνει τον ίδιο τον αριθμό x)...

    Φιλικά,
    Carlo de Grandi


    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Κ.Carlo,δεν έχει νόημα να αντικατασταθεί το γράμμα , ο ορισμός του ακεραίου μέρους είναι πλήρης ,άλλωστε το ν παραπέμπει σε φυσικό και το ακέραιο μέρος ενός φυσικού είναι ο ίδιος ο αριθμός.

      Διαγραφή
  2. Κύριε Δρούγα καλημέρα σας!
    Δεν αντιλέγω σ' αυτό που γράψατε,απλώς το επεσήμανα για την ταύτηση των γραμμάτων.
    Επίσης σας υπενθυμίζω τη διόρθωση του προβλήματος Νο.430 "Νομίσματα".
    Φιλικά,
    Carlo de Grandi

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Κ.Carlo δεν πρέπει να γίνει ταύτιση των γραμμάτων,όσο για την διόρθωση,τέλος του μήνα όταν ενσωματώσω τα νέα προβλήματα.

      Διαγραφή

Related Posts Plugin for WordPress, Blogger...