Τα 5 πιο περίεργα μαθηματικά μοντέλα

 

Γράφει ο Θανάσης Κοπάδης, Μαθηματικός – Συγγραφέας

 

 

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

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

 Τα μαθηματικά μοντέλα χρησιμοποιούνται σε πολλές επιστήμες όπως στη φυσική, στις οικονομικές επιστήμες, αλλά και στη βιολογία. Στην τελευταία ανήκουν και τα μοντέλα επιδημιών  που εύκολα αντιλαμβάνεται κανείς την σημαντικότητά τους, αφού ο στόχος τους είναι η πρόβλεψη της χρονικής εξέλιξης ασθενειών-επιδημιών. Σήμερα, περισσότερο από ποτέ, βλέπουμε πόσο σπουδαίο εργαλείο αποτελούν αυτά τα μοντέλα αφού ουσιαστικά κατευθύνουν την πολιτεία για τις απαραίτητες ενέργειες που πρέπει να πάρει προκειμένου να έχουμε μείωση στη μετάδοση του κορωνοϊού.

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

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

1️⃣ Μαθηματικό μοντέλο για τα mosh pits

Δύο καθηγητές σε πανεπιστήμιο της Νέας Υόρκης κατάφεραν να φτιάξουν το μαθηματικό μοντέλο που περιγράφει τις κινήσεις των ανθρώπων σε ένα mosh pit.

Πριν λίγα χρόνια ο ένας από αυτούς πήγε σε μια συναυλία με την κοπέλα του. «Υπό άλλες συνθήκες θα πηδούσα μέσα στο mosh pit. Αλλά εκείνη τη φορά ήθελα να την έχω σε ασφαλές σημείο οπότε κάτσαμε στην άκρη και παρακολουθούσαμε τα πράγματα από εκεί». Καθώς παρατηρούσε τα άτομα συνειδητοποίησε ότι η κίνησή τους έμοιαζε με αυτή των μορίων ενός αερίου.

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

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

Δείτε την προσομοίωση του παραπάνω μοντέλου:

http://mattbierbaum.github.io/moshpits.js/ 

2️⃣ Μαθηματικό μοντέλο για το top10

Πρόκειται για ένα μαθηματικό μοντέλο που έχει να κάνει με την δημιουργία ενός αλγορίθμου που φτιάχνει μουσικά "σουξέ".

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

Το ποσοστό επιτυχίας των αλγόριθμων αυξομειώνεται ανάλογα με την εποχή. Όταν όμως πρόκειται για μουσική από τέλη της δεκαετίας του 1990 έως σήμερα, οι αλγόριθμοι προβλέπουν με ακρίβεια 60% το εάν ένα τραγούδι θα καταφέρει να μπει στο Top5.

Όπως εξήγησαν οι ερευνητές σε Διεθνές Συνέδριο Μηχανικής Μάθησης και Μουσικής οι αλγόριθμοι εξέτασαν τα στοιχεία του επίσημου βρετανικού Top40 των singles για τα τελευταία 50 χρόνια.

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

Τα μοντέλα δίνουν ένα «δυναμικό επιτυχίας», ενδεικτικό της προοπτικής να γίνει ένα τραγούδι σουξέ.

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

3️⃣ Μαθηματικό μοντέλο είχε προβλέψει την κρυψώνα του Mπιν Λάντεν

Έρευνα που δημοσιεύτηκε το 2009 προέβλεπε με ακρίβεια 80,9% ότι ο Οσάμα Μπιν Λάντεν κρυβόταν σε έπαυλη της πόλης Αμποταμπάντ του Πακιστάν. Η μελέτη, βασισμένη σε ένα μοντέλο πιθανοτήτων που χρησιμοποιείται στην οικολογία των απειλούμενων ειδών, είχε τραβήξει τότε την προσοχή αμερικανικών ΜΜΕ, όχι όμως και των μυστικών υπηρεσιών.

Όπως αναφέρει ο δικτυακός τόπος του περιοδικού Science, οι ερευνητές του Πανεπιστημίου της Καλιφόρνια στο Λος Άντζελες τροφοδότησαν το μαθηματικό μοντέλο με δορυφορικά δεδομένα και με πληροφορίες για τις φημολογούμενες μετακινήσεις του Μπιν Λάντεν τα τελευταία χρόνια.

Η ερευνητική προσπάθεια ξεκίνησε σχεδόν ως αστείο σε μια ομάδα προπτυχιακών φοιτητών. Υπεύθυνοι της ομάδας ήταν δύο γεωγράφοι οικοσυστημάτων.

Η ειδικότητα των δύο ερευνητών είναι η μελέτη απειλούμενων οικοσυστημάτων με τη χρήση δεδομένων τηλεπισκόπησης από δορυφόρους και άλλα συστήματα. Η πρόβλεψη για τη θέση του τρομοκράτη βασίστηκε στη θεωρία της «βιογεωγραφίας νήσων». Στη βάση της, η θεωρία προβλέπει ότι, έπειτα από μια μεγάλη φυσική καταστροφή, τα είδη που ζουν σε μικρά νησιά είναι πιθανότερο να εξαφανιστούν, σε σχέση με τα είδη που ζουν σε μεγάλα νησιά.

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

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

Το γεγονός ότι ο καταζητούμενος δεν κρυβόταν σε κάποια απομονωμένη τοποθεσία, αλλά σε μια σχετικά μεγάλη πόλη, δεν είναι καθόλου περίεργο: "Υποθέσαμε ότι (ο Μπιν Λάντεν) δεν θα βρισκόταν σε μια μικρή κωμόπολη, όπου οι κάτοικοι θα ανέφεραν ότι τον είδαν".

Αναμενόμενο για τον ερευνητή ήταν και το γεγονός ότι ο Μπιν Λάντεν δεν κρυβόταν σε κάποια σπηλιά, όπως πολλοί πίστευαν: "Οι σπηλιές είναι κρύες, και δεν μπορείς να διακρίνεις τον κόσμο που μπαίνει μέσα" εξηγεί.

Τελικά, η ερευνητική ομάδα κατέληξε ότι η πιθανότερη τοποθεσία ήταν το Αμποταμπάντ, το οποίο μεταξύ άλλων προσφέρει εύκολη πρόσβαση σε νοσοκομεία (η υγεία του Μπιν Λάντεν είναι γνωστό ότι ήταν εύθραυστη).

Μάλιστα το μαθηματικό μοντέλο προέβλεψε με επιτυχία και το συγκεκριμένο κτίριο όπου μπορεί να κρυβόταν ο Μπιν Λάντεν. Αυτό βασίστηκε βέβαια σε υποθέσεις, όπως το ότι ο τρομοκράτης ήταν ψηλός και θα χρειαζόταν ένα ψηλοτάβανο χρήστη, όπως επίσης θα χρειαζόταν φράκτη και ασφάλεια.

Η έρευνα δημοσιεύτηκε το 2009 σε μια σχετικά μικρή επιθεώρηση, το MIT International Review. Τράβηξε τότε την προσοχή διαφόρων αμερικανικών μέσων, μεταξύ άλλων της μεγάλης εφημερίδας USA Today.

Περιέργως, οι αμερικανικές Αρχές είτε δεν έμαθαν για την έρευνα είτε δεν την θεώρησαν αρκετά αξιόπιστη.

4️⃣ Μαθηματικό μοντέλο για την εκλογή βουλευτών

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

 Τι εννοούν με τον όρο «αποτελεσματικότητα»; Ότι οι αποφάσεις θα ήταν προς το καλό του κοινωνικού συνόλου (κατ' αντιδιαστολή με το προσωπικό όφελος των εκλεγμένων αντιπροσώπων μας).

 Οι Ιταλοί ερευνητές δημοσίευσαν τη μελέτη τους στον διαδικτυακό τόπο του Πανεπιστημίου τους. Tο άρθρο τους αρχίζει θυμίζοντας μας ότι «Στην αρχαία Ελλάδα, στο λίκνο της δημοκρατίας, κυβερνητικά σώματα επιλέγονταν εν πολλοίς με κλήρωση».

Για τη μοντελοποίηση της ιδέας τους οι Ιταλοί επιστήμονες εμπνεύστηκαν από τον ιστορικό της Οικονομίας στο Πανεπιστήμιο του Μπέρκλεϊ και συμπατριώτη τους Carlo Maria Cipolla (1922-2000). Στη διάσημη χιουμοριστική μονογραφία του «The basic laws of human stupidity» (οι βασικοί νόμοι της ανθρώπινης ηλιθιότητας) ο Cipolla χωρίζει τους ανθρώπους σε τέσσερις κατηγορίες οι οποίες προκύπτουν από τη θέση (διασπορά) τους σε έναν καρτεσιανό άξονα συντεταγμένων.

Πηγή εικόνας: Μαθηματικές ιστορίες για όλους

Έτσι, με τον άξονα των χ να αντιπροσωπεύει το προσωπικό όφελος και τον άξονα των ψ το κοινό όφελος, τα άτομα που εμπίπτουν στο πάνω δεξιά τεταρτημόριο (δικό τους όφελος και κοινό όφελος) είναι τα έξυπνα άτομα, τα άτομα που εμπίπτουν στο πάνω αριστερά τεταρτημόριο (δικό τους κακό, κοινή ωφέλεια) είναι τα αφελή άτομα, τα άτομα που εμπίπτουν στο κάτω δεξιά τεταρτημόριο (δικό τους καλό, κοινό κακό) είναι οι ληστές και, τέλος, εκείνα που εμπίπτουν στο κάτω αριστερό τεταρτημόριο είναι οι ηλίθιοι (κακό δικό τους και του κοινού).

Βάσει αυτής της κατηγοριοποίησης ο Cipolla δίνει τον ορισμό του ηλιθίου: «ένα άτομο είναι ηλίθιο αν μπορεί να προκαλέσει βλάβη σε ένα άλλο άτομο ή ομάδα ατόμων χωρίς να έχει κανένα προσωπικό όφελος ή ακόμη χειρότερα, να προκαλέσει και δική του βλάβη κατά τη διαδικασία».

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

5️⃣ Μαθηματικό μοντέλο για το Αλτσχάιμερ

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

Το ερευνητικό έργο της ομάδας ξεκίνησε πριν από 10 χρόνια και κατάφερε να μοντελοποιήσει τις λειτουργίες ενός αρχικού κυττάρου του εγκεφάλου - μιτοχονδρίου - και να τις προσομοιώσει στον υπολογιστή.

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

Όπως χαρακτηριστικά ανέφερε ο επίκουρος καθηγητής του τμήματος Πληροφορικής του Ιόνιου Πανεπιστημίου Παναγιώτης Βλάμος, η «ηλεκτρική θρόμβωση» αποτελεί τη βασική αιτιολόγηση των δυσλειτουργιών των μιτοχονδρίων, καθώς απ' αυτήν προκαλούνται ηλεκτρικά σύμπλοκα και δυσμορφίες στο εσωτερικό της μεμβράνης τους.

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

«Όταν η διαδικασία της συγχώνευσης και της διάσπασης γίνονται με λανθασμένο τρόπο, επέρχεται ηλεκτρική θρόμβωση, που οδηγεί στα ηλεκτρικά σύμπλοκα στην εσωτερική μεμβράνη του μιτοχονδρίου. Μ' αυτό τον τρόπο, η ‘υπεραγωγιμότητα’ της μεμβράνης διακόπτεται, οδηγώντας με τη σειρά της στη μείωση της παραγωγής ενέργειας», εξήγησε.

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

 

 

Πηγή: Alfavita

Τα "Πανταζάρια": Πώς να κερδίζετε πάντα στα ζάρια!

Σας αρέσει ο τζόγος; Με τα "Πανταζάρια-6" θα τρελάνετε τον συμπαίκτη σας...

 

Τα "Πανταζάρια-6" από το Μουσείο Γρίφων Μεγίστης

Τα "Πανταζάρια-6" είναι ιδιαίτερα. Πρόκειται για μη μεταβατικά ζάρια, μια εφαρμογή της Θεωρίας Πιθανοτήτων. Τα μη μεταβατικά ζάρια είναι γνωστά στο χώρο των ψυχαγωγικών μαθηματικών για το ιδιαίτερο χαρακτηριστικό τους, ότι δεν είναι "δίκαια"... Χρησιμοποιήθηκαν για πρώτη φορά από τον Μπράντλεϋ Έφρον (1970) με τέσσερα ζάρια, ενώ πρόσφατα ακολούθησαν άλλες εκδόσεις με διαφορετικό αριθμό ζαριών.  Περιέργως, κάνεις δεν χρησιμοποίησε έξι ζάρια που είναι πιο αποτελεσματικά και τα οποία, σε μια ριξιά, δίνουν μέσο όρο πιθανότητας νίκης πάνω από 74%. Έτσι, τα δημιούργησε ο κ. Πανταζής Χούλης στο Μουσείο Γρίφων Μεγίστης...

Στο παρακάτω βίντεο εξηγείται η ιδέα των μη μεταβατικών ζαριών:

Το πρόβλημα των τεσσάρων χρωμάτων

 

Το πρόβλημα των τεσσάρων χρωμάτων (four-color problem), είναι ένα "πολύχρωμο" πρόβλημα, που είναι πολύ εύκολο να εξηγηθεί και να κατανοηθεί, αλλά η πολύπλοκη απόδειξή του, που συνάρπαζε και απογοήτευε γενιές μαθηματικών, εξακολουθεί να προκαλεί τη μαθηματική κοινότητα, καθώς είναι το πρώτο θεώρημα στην ιστορία που αποδείχτηκε με χρήση ηλεκτρονικού υπολογιστή. Σε αυτή την ανάρτηση θα μάθουμε περί τίνος πρόκειται...

Παράδειγμα χάρτη χρωματισμένου με τέσσερα χρώματα

Ένα από τα μεγάλα επεισόδια στην ιστορία των μαθηματικών ξεκίνησε στις 23 Οκτωβρίου 1852. Σε μια επιστολή του προς τον Sir William Rowan Hamilton, ο Augustus De Morgan έγραψε: «Ένας μαθητής μου ζήτησε σήμερα να του εξηγήσω ένα γεγονός που δεν ήξερα ότι ήταν γεγονός -και δεν το ξέρω ακόμα».

Μέχρι σήμερα, αυτό το "γεγονός" συνεχίζει να συναρπάζει και να προκαλεί τους μελετητές. Ο φοιτητής ήταν ο Frederick Guthrie και το εν λόγω "γεγονός" προερχόταν αρχικά από τον αδελφό του, Francis. Αφού εξέτασε έναν χάρτη των βρετανικών κομητειών, αναρωτήθηκε αν ήταν πάντα δυνατό να χρωματιστεί ένας χάρτης χρησιμοποιώντας 4 ή λιγότερα χρώματα, διασφαλίζοντας ταυτόχρονα ότι οι περιοχές που έχουν κοινά σύνορα (περισσότερα από ένα γωνιακό σημείο) έχουν διαφορετικά χρώματα.

Φαινόταν ότι αυτό θα έπρεπε να είναι πάντα εφικτό. «Όσο περισσότερο το σκέφτομαι τόσο πιο προφανές φαίνεται», έγραψε ο De Morgan. Παρόλα αυτά, το πρόβλημα δεν ενθουσίασε τον Hamilton και οι προσπάθειες του De Morgan να προσελκύσει το ενδιαφέρον άλλων ερευνητών απέτυχαν επίσης.

Σύμφωνα με το Θεώρημα των τεσσάρων χρωμάτων, απαιτούνται τέσσερα χρώματα για να χρωματίσετε τη Δυτική Βιρτζίνια, την Πενσυλβάνια, το Οχάιο, το Κεντάκι, τη Βιρτζίνια και το Μέριλαντ -τρία για τους γείτονες της Δυτικής Βιρτζίνια και ένα τέταρτο για την ίδια τη Δυτική Βιρτζίνια.

Το πρόβλημα έμεινε σε αδράνεια μέχρι το 1878, όταν ο Arthur Cayley ρώτησε τα μέλη της Μαθηματικής Εταιρείας του Λονδίνου αν κάποιος είχε βρει μια απόδειξη. Αμέσως μετά, άρχισαν να εμφανίζονται αποδείξεις. Η πρώτη, του δικηγόρου Alfred Kempe το 1879, ήταν αυτή που αποδείχθηκε η πιο σημαντική. Η απόδειξη ήταν πειστική και έγινε αποδεκτή ως σωστή για πάνω από μια δεκαετία. Δυστυχώς, η απόδειξη του Kempe -όπως και όλες οι άλλες που θα εμφανίζονταν τον επόμενο αιώνα- ήταν λανθασμένη. Ωστόσο, ήταν έξυπνη και περιείχε βασικές ιδέες που θα εμφανίζονταν στην τελική απόδειξη.

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

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

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

Ένα πρόβλημα χρωματισμού χαρτών μπορεί να μετατραπεί σε πρόβλημα χρωματισμού γραφημάτων.

Μπορούμε τώρα να επαναδιατυπώσουμε το πρόβλημα του Francis Guthrie: Αποδείξτε ότι ο χρωματικός αριθμός κάθε απλού επίπεδου γραφήματος είναι το πολύ 4. Ακολουθεί ένα περίγραμμα του επιχειρήματος του Kempe, που περιγράφεται με σύγχρονους όρους χρησιμοποιώντας γραφήματα αντί για χάρτες. Ξεκίνησε παρατηρώντας ότι ένα γράφημα με μία κορυφή -ίσως ο χάρτης να είναι ένα μοναχικό νησί- απαιτεί μόνο ένα χρώμα. Στη συνέχεια χρησιμοποίησε ένα έξυπνο επιχείρημα για να χτίσει από εκεί και πέρα προς τα πάνω, υποστηρίζοντας ότι είναι δυνατόν να χρησιμοποιηθούν το πολύ τέσσερα χρώματα για να χρωματιστεί ένα γράφημα με δύο κορυφές, μετά τρεις κορυφές και ούτω καθεξής. Ορίστε πώς: Ας υποθέσουμε ότι μπορούμε να χρωματίσουμε όλα τα απλά επίπεδα γραφήματα με n κορυφές με το πολύ τέσσερα χρώματα —αυτό είναι ασήμαντο για n μικρότερο από 5— και τότε μας δίνεται ένα γράφημα με n+1 κορυφές. Πώς μπορούμε να δείξουμε ότι και αυτό θα χρωματίζεται το πολύ με τέσσερα χρώματα;

Αρχικά, ο Kempe έδειξε, χρησιμοποιώντας ένα προσεκτικό επιχείρημα καταμέτρησης, ότι κάθε απλό επίπεδο γράφημα έχει κάτι κοινό: πρέπει να περιέχει τουλάχιστον μία κορυφή με το πολύ 5 γείτονες. Λαμβάνοντας υπόψη όλες τις επιλογές, αυτό σημαίνει ότι κάθε πιθανό γράφημα που βασίζεται σε έναν χάρτη περιέχει μία από έξι ειδικές διαμορφώσεις κορυφών.

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

Εάν αφαιρέσουμε αυτήν την κορυφή και όλες τις άκρες που συνδέονται με αυτήν, αφήνουμε πίσω μας ένα γράφημα με n κορυφές —το οποίο ήδη γνωρίζουμε ότι μπορεί να χρωματιστεί χρησιμοποιώντας 4 χρώματα. Στην πραγματικότητα το κάνουμε ως το επόμενο βήμα. Τώρα, κοιτάξτε τις κορυφές δίπλα στην κορυφή που αφαιρέσατε. Εάν εμφανίζουν 3 ή λιγότερα χρώματα, μπορούμε να χρωματίσουμε την κορυφή που αφαιρέθηκε με ένα από τα υπόλοιπα χρώματα και τελειώσαμε: Μόλις δείξαμε ότι το γράφημα με n+1 κορυφές μπορεί να χρωματιστεί με 4 χρώματα. Και αν οι γειτονικές κορυφές περιλαμβάνουν και τα 4 χρώματα, ο Kempe επινόησε μια έξυπνη μέθοδο επαναχρωματισμού ορισμένων κορυφών για να ελευθερώσει ένα χρώμα για την κορυφή που αφαιρέθηκε, δείχνοντας πάλι ότι το γράφημα με n+1 κορυφές χρειάζεται μόνο 4 χρώματα.

Το 1890, ο μαθηματικός Percy Heawood εντόπισε το λάθος του Kempe. Υπήρχε μια ειδική περίπτωση στην οποία η έξυπνη μέθοδος του Kempe απέτυχε. Ο Heawood παρατήρησε ότι, αν και η δική του εργασία φαινόταν " μάλλον καταστροφική παρά εποικοδομητική", έδειξε ότι η τεχνική του Kempe μπορούσε να αποδείξει ότι κάθε χάρτης μπορεί να χρωματιστεί με 5 ή λιγότερα χρώματα - όχι όπως ακριβώς ο αρχικός στόχος, αλλά και πάλι εντυπωσιακός.

Ο Heawood διερεύνησε επίσης χάρτες που σχεδιάστηκαν σε πιο περίπλοκες επιφάνειες. Απέδειξε ότι ένας χάρτης σε ένα ντόνατ με g τρύπες μπορεί να χρειαστεί \( \frac{1}{2} \big( 7+\sqrt{1+48g} \big) \)   χρώματα (όπου αυτή η τιμή στρογγυλοποιείται στον πλησιέστερο ακέραιο). Όμως, σύμφωνα με αυτό που είχε αρχίσει να γίνεται συνήθεια, η απόδειξή του για τις γενικές επιφάνειες ήταν ελλιπής, και δεν είχαμε μια πλήρη απόδειξη μέχρι το 1968.

Για αυτόν τον χάρτη σε ένα ντόνατ, που φαίνεται και από τις δύο πλευρές, κάθε μία από τις επτά περιοχές συνορεύει με τις άλλες έξι περιοχές, οπότε απαιτούνται επτά χρώματα.

Αλλά ακόμη και όταν αποδείχθηκε το θεώρημα του Heawood για γενικές επιφάνειες, το πρόβλημα των τεσσάρων χρωμάτων παρέμεινε άλυτο. Χάρη σε δεκαετίες σκληρής δουλειάς, όμως, η απόδειξη ήταν ορατή. Σε ένα συνέδριο το 1976, 124 χρόνια αφότου ο Guthrie έθεσε το πρόβλημα, ο Wolfgang Haken ανακοίνωσε μια απόδειξη σε συνεργασία με τον Kenneth Appel και με τη βοήθεια του μεταπτυχιακού φοιτητή John Koch. Οι αντιδράσεις ήταν ανάμεικτες. "Περίμενα ότι το ακροατήριο θα ξεσπούσε σε ένα μεγάλο χειροκρότημα", έγραψε ο Don Albers, ο οποίος ήταν παρών στην ομιλία. "Αντίθετα, απάντησαν με ευγενικό χειροκρότημα!" Αυτό συνέβη επειδή η ομάδα, αντί να παράγει ένα επιχείρημα με μολύβι και χαρτί, βασίστηκε σε μεγάλο βαθμό σε έναν υπολογιστή.

Δεν έβαλαν μια μηχανή να απαντήσει άμεσα στο ερώτημα, καθώς είναι δυνατά άπειρα επίπεδα γραφήματα και ένας υπολογιστής δεν μπορεί να τα ελέγξει όλα. Ωστόσο, όπως ο Kempe απέδειξε ότι κάθε γράφημα περιέχει μία από έξι ειδικές διαμορφώσεις κορυφών, οι Appel και Haken έδειξαν ότι κάθε γράφημα πρέπει να έχει μία από 1.936 ειδικές διαμορφώσεις. Η απόδειξη του θεωρήματος ισοδυναμεί με το να δείξουμε ότι χρειαζόμαστε μόνο τέσσερα χρώματα για να χρωματίσουμε οποιοδήποτε γράφημα που περιέχει αυτούς τους υπογράφους. Η διάσπαση των έξι ειδικών περιπτώσεων του Kempe σε 1.936 υποπεριπτώσεις τους έδωσε πιο λεπτομερή έλεγχο και έκανε κάθε περίπτωση ευκολότερο να ελεγχθεί -αν και ο συνολικός αριθμός ήταν πλέον πολύ μεγάλος για να μπορέσει ένας άνθρωπος να τον ελέγξει χωρίς βοήθεια. Στην πραγματικότητα, η ολοκλήρωση των υπολογισμών απαιτούσε πάνω από 1.000 ώρες εργασίας στον υπολογιστή.

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

Η απόδειξη του προβλήματος των τεσσάρων χρωμάτων ήταν, φυσικά, μόνο η αρχή της επανάστασης των υπολογιστών στα μαθηματικά. Το 1998 ο Thomas Hales χρησιμοποίησε έναν υπολογιστή για να αποδείξει την περίφημη εικασία του Johannes Kepler ότι ο πιο αποτελεσματικός τρόπος για να στοιβάζονται σφαίρες είναι αυτός που χρησιμοποιείται συνήθως για να στοιβάζονται πορτοκάλια σε ένα παντοπωλείο. Και πρόσφατα οι υπολογιστές βοήθησαν να βρεθεί ο "αριθμός του Θεού" - ο μέγιστος αριθμός στροφών που απαιτούνται για να λυθεί ένας κύβος του Ρούμπικ (20 στροφές ή 26 αν οι μισές στροφές μετράνε ως δύο). Αν και το πρόβλημα των τεσσάρων χρωμάτων για τους χάρτες έχει διευθετηθεί, πολλά βασικά ερωτήματα σχετικά με το χρωματισμό γραφημάτων παραμένουν αναπάντητα ή μόλις τώρα επιλύονται.

Η εργασία του Heawood με τις επιφάνειες έδειξε ότι μπορούμε να θέσουμε ερωτήματα χρωματικότητας για μη επίπεδα γραφήματα. Και στην πραγματικότητα, ο χρωματικός αριθμός ενός συγκεκριμένου γραφήματος δεν εξαρτάται από την επιφάνεια στην οποία σχεδιάζεται ο ισοδύναμος χάρτης. Για παράδειγμα, ένα γράφημα στον οποίο κάθε κορυφή συνδέεται με κάθε άλλη κορυφή ονομάζεται πλήρες γράφημα και ο χρωματικός αριθμός ενός πλήρους γραφήματος με n κορυφές είναι n. Έτσι, αν ένας μεγάλος γράφος (γράφημα) περιέχει έναν πλήρη γράφο με n κορυφές, τότε γνωρίζουμε ότι ο χρωματικός αριθμός του μεγάλου γραφήματος είναι τουλάχιστον n.

Ένα πλήρες γράφημα με n κορυφές έχει χρωματικό αριθμό n.

Η παρατήρηση αυτή δεν συνεπάγεται ότι αν ο χρωματικός αριθμός ενός γραφήματος είναι n, τότε περιέχει ένα πλήρες γράφημα με n κορυφές. Αλλά το 1943, ο Hugo Hadwiger υπέθεσε κάτι πολύ παρόμοιο. Πίστευε ότι αν ένα γράφημα χωρίς βρόχους έχει χρωματικό αριθμό n, τότε έχει μια διάταξη κορυφών που ονομάζεται K_n, όπου η διαγραφή ορισμένων κορυφών και ακμών και η ομαδοποίηση άλλων οδηγεί σε ένα πλήρες γράφημα με n κορυφές. Αναδιατυπωμένη, αυτή η εικασία δηλώνει ότι αν ένα γράφημα δεν έχει ένα δευτερεύον K_n, τότε μπορεί να χρωματιστεί με λιγότερα από n χρώματα. Η εικασία του Hadwiger, ένα από τα σημαντικότερα ανοιχτά προβλήματα στη θεωρία γραφημάτων, γενικεύει το θεώρημα των τεσσάρων χρωμάτων, καθώς ένα επίπεδο γράφημα δεν μπορεί να περιέχει έναK₅ minor.

Αν και ο χρωματισμός γραφημάτων ξεκίνησε με ένα ερώτημα στη χαρτογραφία, προβλήματα που δεν έχουν καμία σχέση με χάρτες ή χρώματα μπορούν επίσης να ενταχθούν στο πλαίσιο του χρωματισμού γραφημάτων. Για παράδειγμα, το sudoku είναι ένα πρόβλημα χρωματισμού γραφήματος μεταμφιεσμένο. Δείτε κάθε κελί ως κορυφή και τα εννέα ψηφία ως χρώματα. Κάθε κορυφή έχει 20 ακμές που βγαίνουν από αυτήν -μία προς κάθε κελί στη σειρά, στη στήλη και στο υποτετράγωνο 3x3. Αυτός ο γράφος με 81 κορυφές και 810 ακμές ξεκινά με έναν μερικό χρωματισμό (τις δεδομένες ενδείξεις). Το αντικείμενο του παιχνιδιού είναι να χρωματίσετε τις υπόλοιπες κορυφές.

Το Sudoku μπορεί να θεωρηθεί ως ένα πρόβλημα χρωματισμού γραφημάτων.

Παρ' όλη την προσοχή που έχουν λάβει αυτά τα προβλήματα χρωματισμού, δεν έχουμε ακόμα μια απόδειξη του αρχικού θεωρήματος των τεσσάρων χρωμάτων που να μπορεί να διαβάσει ένας άνθρωπος. Αυτό δεν οφείλεται στην έλλειψη προσπάθειας. Ακόμη και σήμερα, νέες αποδείξεις εμφανίζονται, προκαλούν κάποιο ενθουσιασμό και, όπως η απόδειξη του Kempe, αποδεικνύεται ότι περιέχουν λάθη.

Ο μαθηματικός Paul Erdös συνήθιζε να μιλάει για το "The Book" -έναν φανταστικό τόμο που περιέχει τις πιο κομψές αποδείξεις κάθε θεωρήματος. Αναρωτιέται κανείς αν το "The Book" περιέχει μια αναγνώσιμη από τον άνθρωπο απόδειξη του θεωρήματος των τεσσάρων χρωμάτων, και αν ναι, αν θα τη δούμε ποτέ...

 

Πηγή: Quanta Magazine

Η εξίσωση του... Batman

Σύμφωνα με το Wolfram MathWorld, η "εξίσωση του Batman" ή "καμπύλη του Batman", που αναπαριστά το λογότυπο του αγαπημένου από πολλούς σούπερ ήρωα, είναι μια καμπύλη αποτελούμενη από επιμέρους τμήματα, καθένα από τα οποία είναι γράφημα κάποιας συνάρτησης. Πρωτοδημοσιεύτηκε στο Reddit τον Ιούλιο του 2011.

Τσεκάρετε έναν άλλο τρόπο αναπαράστασης του λογότυπου του Batman, στο Wolfram Alpha, γράφοντας "batman logo"!