Ανοίξτε οποιονδήποτε χάρτη — της Ευρώπης, της Ελλάδας, του κόσμου. Κάθε χώρα (ή νομός, ή περιοχή) έχει ένα χρώμα, και γειτονικές περιοχές δεν μοιράζονται ποτέ το ίδιο. Πόσα χρώματα χρειάζονται; Η απάντηση είναι εκπληκτικά μικρή: τέσσερα. Πάντα. Για κάθε χάρτη που υπήρξε, υπάρχει ή θα υπάρξει. Αυτό είναι το Θεώρημα Τεσσάρων Χρωμάτων.
Το πρόβλημα
Αρκούν 4 χρώματα. Δεν είναι πάντα αναγκαία τα 4 — πολλοί απλοί χάρτες χρωματίζονται με 2 ή 3. Αλλά ποτέ, σε κανέναν χάρτη, δεν θα χρειαστεί πέμπτο. Φαίνεται προφανές; Κάθε χαρτογράφος το «ήξερε» από τη μεσαιωνική εποχή. Αλλά η απόδειξη αυτού του «προφανούς» απαίτησε 124 χρόνια μαθηματικής προσπάθειας — και τελικά έναν υπολογιστή.
Γιατί όχι 3;
Φτιάξτε νοερά 4 περιοχές, κάθε μία γειτονική με τις άλλες 3 — σαν πίτα κομμένη σε 4 κομμάτια με ένα κέντρο. Κάθε κομμάτι ακουμπά τα δύο διπλανά του και το κέντρο. Χρειάζονται ακριβώς 4 χρώματα. Με 3 δεν γίνεται.
Αντίστροφα, 5 χρώματα εξασφαλίζονται πάντα και αποδεικνύεται σχετικά εύκολα (θεώρημα πέντε χρωμάτων, Heawood, 1890). Η πραγματική πρόκληση ήταν η απόδειξη ότι 4 αρκούν — και σ’ αυτό κρύβεται μια από τις πιο δραματικές ιστορίες στην ιστορία των μαθηματικών.
Η ιστορία: 124 χρόνια μέχρι την απόδειξη
Πώς δουλεύει (η ιδέα)
Η στρατηγική Appel–Haken βασίζεται σε δύο πυλώνες. Πρώτον, δείχνουν ότι κάθε χάρτης περιέχει αναγκαστικά τουλάχιστον μία «αναπόφευκτη» γεωμετρική δομή — δηλαδή ένα σύνολο μοτίβων τέτοιο ώστε κάθε χάρτης να περιέχει τουλάχιστον ένα. Δεύτερον, δείχνουν ότι κάθε τέτοιο μοτίβο είναι «αναγώγιμο» — αν ο μεγαλύτερος χάρτης δεν χρωματίζεται με 4, τότε ούτε ένας μικρότερος, κάτι που οδηγεί σε αντίφαση.
Ο ρόλος του υπολογιστή ήταν η εξακρίβωση κάθε μίας από τις ειδικές περιπτώσεις. Κανένας άνθρωπος δεν μπορούσε να ελέγξει χιλιάδες διατάξεις χειρωνακτικά χωρίς λάθος — αλλά ένας υπολογιστής μπορεί.
Η μεγάλη διαμάχη: είναι αυτή «απόδειξη»;
Η απόδειξη του 1976 ήταν η πρώτη σημαντική μαθηματική απόδειξη που βασίστηκε ουσιωδώς σε υπολογιστή. Κανένας άνθρωπος δεν μπορεί να την «διαβάσει» ολόκληρη. Αυτό προκάλεσε θεμελιώδη συζήτηση: αν μια απόδειξη δεν μπορεί να επαληθευτεί από ανθρώπινο νου, μετράει;
Πολλοί μαθηματικοί ένιωσαν δυσφορία. Ο φιλόσοφος Thomas Tymoczko υποστήριξε ότι αυτό αλλάζει ριζικά τη φύση της μαθηματικής γνώσης. Άλλοι, πρακτικότεροι, επεσήμαναν ότι η τυπική επαλήθευση (Coq, 2005) εξαλείφει κάθε αμφιβολία. Σήμερα, η πλειοψηφία αποδέχεται την απόδειξη — αλλά η αναζήτηση μιας «ανθρώπινης» απόδειξης παραμένει ανοιχτό πρόβλημα.
Πού εφαρμόζεται σήμερα
Το πρόβλημα του χρωματισμού γράφων — η μαθηματική γενίκευση του χρωματισμού χαρτών — εμφανίζεται παντού στη σύγχρονη ζωή. Στην κατανομή ραδιοφωνικών συχνοτήτων (γειτονικοί σταθμοί δεν πρέπει να χρησιμοποιούν την ίδια συχνότητα), στον χρονοπρογραμματισμό εξετάσεων (δύο μαθήματα με κοινούς φοιτητές δεν γίνεται να εξετάζονται ταυτόχρονα), στην κατανομή μνήμης σε μεταγλωττιστές, ακόμα και στη λύση Sudoku — ένα Sudoku είναι στην ουσία ένα πρόβλημα χρωματισμού γράφου με 9 «χρώματα».
Πάρε τον χάρτη της Ελλάδας κατά περιφέρειες ή νομούς. Δοκίμασε να τον χρωματίσεις με μόνο 4 χρώματα, ώστε γειτονικοί νομοί να έχουν διαφορετικό. Θα ανακαλύψεις ότι πάντα βρίσκεται λύση — και ότι η πρόκληση δεν είναι αν γίνεται, αλλά πώς.
Τι μας διδάσκει
Το Θεώρημα Τεσσάρων Χρωμάτων μας δείχνει κάτι βαθύ για τα μαθηματικά: ότι ακόμα και ερωτήματα που μπορεί να κατανοήσει ένα παιδί μπορεί να κρύβουν θεμελιώδεις δυσκολίες. Μας δείχνει επίσης ότι τα μαθηματικά εξελίσσονται — η σχέση ανθρώπου και υπολογιστή στην απόδειξη θεωρημάτων δεν είναι πια επιστημονική φαντασία, αλλά ζωντανή πραγματικότητα. Και τέλος, μας θυμίζει ότι ένα «απλό» ερώτημα ενός φοιτητή μπορεί να απασχολήσει τους κορυφαίους μαθηματικούς για πάνω από έναν αιώνα.
• Wilson, R. (2002). Four Colors Suffice: How the Map Problem Was Solved, Princeton UP.
• Appel, K. & Haken, W. (1977). “Every planar map is four colorable”. Illinois J. Math., 21(3), 429–567.
• Gonthier, G. (2008). “Formal proof — The Four-Color Theorem”. Notices of the AMS, 55(11), 1382–1393.
• Wikipedia: Four color theorem
Καθηγητής Μαθηματικών — Εκπαιδευτικός Αναλυτής
Δημιουργός site PaideiaNet.com