🖼️ Ένα κομψό ερώτημα
Το Θεώρημα της Πινακοθήκης (Art Gallery Theorem) αναφέρει ότι, αν διαχειρίζεστε μια πινακοθήκη με n γωνίες, θα χρειαστείτε το πολύ ⌊n/3⌋ φύλακες για να παρακολουθείτε ολόκληρο τον χώρο — ανεξάρτητα από το πόσο περίπλοκο ή ακανόνιστο είναι το σχήμα της.
Το ερώτημα τέθηκε πρώτα το 1973, από τον μαθηματικό Victor Klee, ο οποίος το έθεσε ο ίδιος στον νεαρό τότε μαθηματικό Václav Chvátal, σε ένα συνέδριο. Ο Chvátal το απέδειξε σχεδόν αμέσως, το 1975 — αν και η αρχική του απόδειξη ήταν αρκετά περίπλοκη, με πολλαπλές ειδικές περιπτώσεις.
🚌 Μια απόδειξη που γεννήθηκε σε λεωφορείο
Τρία χρόνια αργότερα, το 1978, ο μαθηματικός Steve Fisk βρήκε μια εντελώς διαφορετική, εξαιρετικά κομψή απόδειξη — και το έκανε, σύμφωνα με τη δική του αφήγηση, ενώ αποκοιμιόταν σε ένα λεωφορείο κάπου στο Αφγανιστάν.
Η ιδέα του ήταν εντυπωσιακά απλή: τριγωνοποιήστε την πινακοθήκη (χωρίστε την σε τρίγωνα με διαγώνιες), και μετά χρωματίστε τις κορυφές του σχήματος με μόνο τρία χρώματα, έτσι ώστε κάθε τρίγωνο να έχει και τα τρία χρώματα στις γωνίες του — κάτι που είναι πάντα εφικτό.
Τοποθετώντας φύλακες σε όλες τις κορυφές του λιγότερο συχνού χρώματος, κάθε τρίγωνο —άρα και ολόκληρη η πινακοθήκη— είναι εγγυημένα ορατό, με το πολύ ⌊n/3⌋ φύλακες συνολικά.
Η απόδειξη του Fisk θεωρείται τόσο όμορφη, που συμπεριλήφθηκε στο θρυλικό βιβλίο Proofs from THE BOOK — μια συλλογή αποδείξεων που, κατά την έκφραση του μεγάλου μαθηματικού Paul Erdős, θα μπορούσαν να προέρχονται από ένα φανταστικό «Βιβλίο» όπου ο Θεός κρατά τις τελειότερες δυνατές αποδείξεις κάθε μαθηματικής αλήθειας.
🦷 Γιατί το όριο είναι σφιχτό
Το φράγμα ⌊n/3⌋ δεν είναι απλώς μια ασφαλής υπερεκτίμηση — υπάρχουν πινακοθήκες που πράγματι χρειάζονται ακριβώς τόσους φύλακες. Το κλασικό παράδειγμα είναι μια πινακοθήκη σε σχήμα «χτένας», με πολλά μυτερά «δόντια»: κάθε δόντι είναι ορατό μόνο από μια μικρή, απομονωμένη περιοχή, οπότε απαιτεί τον δικό του, ξεχωριστό φύλακα.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου