Μαθη...μαγικά : Το Θεώρημα των τεσσάρων χρωμάτων

Τετάρτη 19 Ιουλίου 2017

Το Θεώρημα των τεσσάρων χρωμάτων

Οι ηλεκτρονικοί υπολογιστές είναι άχρηστοι, μπορούν να δώσουν μόνο απαντήσεις!

Πάμπλο Πικάσο

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

Άρθουρ Σοπενχάουερ, Πάρεργα και παραλειπόμενα

Στις 23 Οκτώβριου του 1852,ο Φράνσις Γκάθρι,προπτυχιακός φοιτητής στο University College του Λονδίνου προσπάθησε να χρωματίσει τον χάρτη των περιφερειών της Αγγλίας.

Αναρωτήθηκε ποιος θα ήταν ο ελάχιστος αριθμός διαφορετικών χρωμάτων τα οποία θα χρησιμοποιούσε ώστε οι γειτονικές περιφέρειες να έχουν διαφορετικό χρώμα.Δεν κατέληξε πουθενά όποτε έθεσε στον καθηγητή Αύγουστο Ντε Μόργκαν το ερώτημα. Ο Ντε Μόργκαν ήταν ο πρώτος καθηγητής μαθηματικών του πανεπιστήμιου University College και διάσημος για τις έρευνες του πάνω στην Λογική. Όμως παρά την εξαιρετική του ευφυΐα,ο Ντε Μόργκαν δεν ήξερε την απάντηση στην ερώτηση του μαθητή του.Την ίδια μέρα έγραψε στον συνάδελφο του Χάμιλτον,τον εξυπνότερο άνθρωπο της Ιρλανδίας,στο Δουβλίνο:

Ένας μαθητής μου με, ρώτησε σήμερα να του αιτιολογήσω ένα γεγονός το όποιο αγνοούσα-και εξακολουθώ να αγνοώ- αν είναι γεγονός.Λέει ότι αν ένα σχήμα είναι χωρισμένο σε τμήματα με οποιοδήποτε τρόπο και κάθε τμήμα είναι χρωματισμένο ώστε να έχει διαφορετικό χρώμα από οποιοδήποτε άλλο με το οποίο συνορεύει-μπορεί να απαιτούνται τέσσερα χρώματα, αλλά όχι παραπάνω…Αν μου δώσεις κάποια πολύ απλή εξήγηση που θα με κάνει να νιώσω ένα αδαές ζώο, μάλλον θα ακολουθήσω το παράδειγμα της σφίγγας ….

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

Ούτε, όμως ο Χάμιλτον γνώριζε την απάντηση και μέσα σε τρεις μέρες του έγραψε:

Δεν νομίζω να ασχοληθώ σύντομα με την τετράδα των χρωμάτων σου.

Πολλοί μαθηματικοί μεγάλου βεληνεκούς δοκίμασαν την τύχη τους με το πρόβλημα,μάταια όμως.Χαρακτηριστικό παράδειγμα ο καλύτερος φίλος του Χιλμπερτ στο Γκέτιγκεν,ο Χέρμαν Μινκοφσκι.Όταν το ερώτημα τέθηκε σε κάποιο από τα μαθήματα του.Σχολίασε:«Το θεώρημα δεν έχει ακόμα αποδειχτεί, αλλά αυτό οφείλεται στο ότι ασχολήθηκαν μαζί του μόνο μαθηματικοί τρίτης κατηγορίας».

«Πιστεύω ότι μπορώ να το αποδείξω!!» Αφιέρωσε αρκετά μαθήματα, παλεύοντας με διάφορες ιδέες στον πίνακα.Τέλος,κάποιο πρωί, μπαίνοντας στην τάξη, ομολόγησε : «Οι ουρανοί εξοργίστηκαν από την αλαζονεία μου», ομολόγησε «Η απόδειξη μου παρουσιάζει προβλήματα.»

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

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

Αν και οι μαθηματικοί δεν έδιναν δεκάρα για το αν η επίλυση του προβλήματος θα βοηθούσε τους χαρτογράφους η όχι, η πρόκληση του ερωτήματος τους συνεπήρε.Για χρόνια ο Ντε Μόργκαν συνέχισε να ρωτά τους συναδέλφους του αν μπορούσαν αν βρουν μια απόδειξη μέχρι που τελικά ένας μαθηματικός ο Άλφρεντ Κεμπ δημοσίευσε μια απόδειξη. Ο Κεμπ έγινε αρκετά διάσημος ώστε τον δέχτηκαν στην Βασιλική εταιρεία και τον έχρισαν ιππότη. Φανταστείτε την αμηχανία του όταν η απόδειξη του αποδείχθηκε λανθασμένη από έναν άλλο μαθηματικό.Τον Περσι Χειγουντ.Ο Χειγουντ εργάστηκε για αρκετά χρόνια πάνω στο ίδιο πρόβλημα και κατάφερε να αποδείξει ότι η απόδειξη του Κέμπ ήταν λανθασμένη.

Ωστόσο πάλι οι μαθηματικοί δεν ήταν ικανοποιημένοι απόλυτα.Τα πέντε χρώματα πράγματι θα χρωμάτιζαν οποιοδήποτε χάρτη, αλλά τι γινόταν με τέσσερα η ακόμη και τρία; Η απόδειξη χρειάστηκε άλλα 80 χρόνια και η εκτεταμένη χρήση υπολογιστή. Η πρώτη απόδειξη ήρθε το 1976 από τους Αμερικανούς μαθηματικούς Κένεθ Άπελ (Kenneth Appel) και Γουλφανγκ Χάκεν (Wolfgang Haken), από το Πανεπιστήμιο του Ιλινόις. Για την απόδειξη απαιτήθηκε η ανάλυση 2000 ειδικών περιπτώσεων και 1000 ώρες υπολογιστικού χρόνου.

K. Appel,W.Haken

Οι μαθηματικοί αμφισβήτησαν την απόδειξη γιατί πραγματοποιήθηκε με την χρήση υπολογιστή, κανείς δεν μπορεί να επιβεβαιώσει ότι στον κώδικα του υπολογιστή δεν παραβλέφτηκε κάποια περίπτωση. Είναι πλέον διάσημο το αστείο που έκανε ο Μάρτιν Γκάρντνερ στην στήλη του με τις σπαζοκεφαλιές στο Scientific American την πρωταπριλιά του 1975(http://mathhmagic.blogspot.gr/2016/04/blog-post.html). Μόλις ένα χρόνο μετά την απόδειξη, πρότεινε ένα χάρτη 110 περιφερειών στον οποίο όπως υποστήριζε απαιτούνταν 5 χρώματα. Χρησιμοποιήθηκε όμως το πρόγραμμα mathematica και έγινε ο χρωματισμός με 4 χρώματα (δυο αποχρώσεις του γκρι, λευκό, μαύρο). Δείτε το παρακάτω σχήμα:

Το 2004, ο Τζωρτζ Γκόνθιερτων των εργαστηρίων της Microsoft στη Βρετανία και ο Μπετζαμιν Βέρνερ στο ερευνητικό κέντρο INRIA της Γαλλίας υποστηρίζουν ότι επιβεβαίωσαν την απόδειξη. Οι ερευνητές μετέγραψαν την απόδειξη στη γλώσσα υπολογιστή Coq, η οποία χρησιμοποιείται για την αναπαράσταση λογικών προτάσεων και ανέπτυξαν ένα λογισμικό ελέγχου λογικής προκειμένου να επιβεβαιώσουν ότι κάθε βήμα που οδηγεί στην απόδειξη είναι σωστό.

Δείτε και μια πλήρη εξήγηση της απόδειξης

http://www.ams.org/notices/200811/tx081101382p.pdf
Μια σχετική διπλωματική:
http://www.math.uoa.gr/me/dipl/dipl_souri.pdf

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

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

Μια μικρή πρόκληση.Ο χάρτης της Κυκλολάνδης

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