Γρίφος... "Survivor": Οι ναύτες, οι καρύδες και ο πίθηκος

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

Στη 1:00 η ώρα τη νύχτα, ο πρώτος ναύτης ξυπνάει και, σκεπτόμενος ότι δεν μπορεί να εμπιστευτεί τους άλλους, αποφασίζει να πάρει το μερίδιό του νωρίτερα. Διαιρεί τις καρύδες σε 5 ίσα ακριβώς μερίδια, αλλά περισσεύει μία καρύδα. Δίνει την καρύδα που περισσεύει στον πίθηκο, ο οποίος την τρώει, οπότε δεν κάνει και φασαρία για να μην ξυπνήσουν οι άλλοι, κρύβει τις καρύδες του μακριά (μία από τις πέντε στοίβες) και βάζει τις υπόλοιπες καρύδες (τις άλλες 4 στοίβες) όλες μαζί σε μια νέα στοίβα κάτω από το δέντρο. Στις 2:00 η ώρα, σηκώνεται ο δεύτερος ναύτης, έχοντας τις ίδιες υποψίες. Μη γνωρίζοντας ότι ο πρώτος ναύτης είχε ήδη πάρει το μερίδιό του, διαιρεί και αυτός τις καρύδες που βρήκε σε πέντε μερίδια και περισσεύει μία καρύδα την οποία δίνει στον πίθηκο. Μετά κρύβει το μερίδιό του μακριά (μία από τις πέντε, νέες πλέον, στοίβες) και βάζει το υπόλοιπο (τις άλλες 4 στοίβες) όλες μαζί κάτω από το δέντρο.

Στις 3:00, 4:00, και 5:00 η ώρα το πρωί, ο τρίτος, τέταρτος και πέμπτος ναύτης αντίστοιχα, σηκώνεται ο καθένας και κάνει τις ίδιες ακριβώς ενέργειες.

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

 
ΤΟ ΕΡΩΤΗΜΑ:

Ποιο είναι το ελάχιστο πλήθος από καρύδες που θα μπορούσαν να υπάρχουν στην αρχική στοίβα, ώστε να μπορεί να υλοποιηθεί η παραπάνω διαδικασία;

"Τα τέσσερα χρώματα του καλοκαιριού"

 

Στη δίνη των γεγονότων του ταραγμένου εικοστού αιώνα, τρεις μεγάλοι έρωτες κι ένα "περιθωριακό" μαθηματικό πρόβλημα συνθέτουν τον καμβά του μυθιστορήματος «Τα τέσσερα χρώματα του καλοκαιριού» του Τεύκρου Μιχαηλίδη. Στο κέντρο του κύκλου, που οι ακτίνες του περνούν απ' το Παρίσι, το Γκέτινγκεν και την Αθήνα, βρίσκεται η Σέριφος: η Σέριφος των πρώτων εργατικών κινητοποιήσεων του 1916, η Σέριφος του οικονομικού μαρασμού που ακολούθησε το κλείσιμο των μεταλλείων το 1963, η Σέριφος της άλογης τουριστικής ανάπτυξης που ζούμε σήμερα. Τρεις Σερφιώτισσες, γιαγιά, μάνα και κόρη, ζουν η καθεμιά το δικό της ερωτικό δράμα με φόντο έναν μαθηματικό γρίφο που, αφού επί ένα περίπου αιώνα παίδεψε μερικές από τις λαμπρότερες μαθηματικές ιδιοφυίες, έβαλε, με τη λύση του, μια μικρή βόμβα στον τρόπο που σκεφτόμαστε τα μαθηματικά: πόσο μπορούμε να εμπιστευτούμε μια λύση που βασίζεται σε δεδομένα ηλεκτρονικού υπολογιστή τα οποία δεν μπορούμε να ελέγξουμε; Άραγε στον αιώνα της πληροφορικής "απόδειξη" σημαίνει το ίδιο που σήμαινε και την εποχή του Ευκλείδη; Κι ακόμα, πόσο μπορεί ένα μαθηματικό πρόβλημα να επηρεάσει τις συγκλίνουσες τροχιές μιας γυναίκας κι ενός άντρα που οι καρδιές τους μοιάζουν να έχουν φτιαχτεί για να χτυπούν συντονισμένα;

 

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

📚Αν δεν βρίσκετε το βιβλίο από τις εκδόσεις Πόλις, καθώς έχει εξαντληθεί από τον εκδότη, μπορείτε να αναζητήσετε μία νεότερη έκδοση του βιβλίου από τις εκδόσεις Ψυχογιός.

Γρίφος: Οι τέσσερις άγνωστοι

 

Έχω στο μυαλό μου τέσσερις διαφορετικούς φυσικούς αριθμούς, τέτοιους ώστε:

• Το άθροισμα και των τεσσάρων αριθμών είναι 31.
• Μόνο ένας από αυτούς είναι περιττός.
• Η διαφορά του μικρότερου από τον μεγαλύτερο αριθμό ισούται με 7.
• Η διαφορά των δύο μεσαίων αριθμών ισούται με 2.

Ποιοι είναι αυτοί οι αριθμοί;

"Ο αριθμός του Πλάτωνα"

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

Ο νεαρός Ελληνο-αυστραλός μαθηματικός 'Εβαν Πέτκος περιδιαβαίνει ανέμελος τις πρωτεύουσες της Ευρώπης. Λίγες ημέρες πριν επιστρέψει στην Αυστραλία, αποχωρίζεται την όμορφη Αθήνα και επιβιβάζεται σε ένα υπεραστικό λεωφορείο με προορισμό τα πατρογονικά χώματα.
Από τις πρώτες κιόλας ώρες στο χωριό, αγκιστρώνεται σε έναν ιστό από παράξενες καταστάσεις που όλες τους σχετίζονται με αριθμούς: η χωριανή που τον ξεναγεί στο σπίτι του παππού του ρυθμίζει την καθημερινότητα της σύμφωνα με την ακολουθία των αριθμών Φιμπονάτσι, ο παπάς στρατολογεί τον Έβαν και τα μαθηματικά του στον αγώνα του να γιατρέψει το αλλοπαρμένο κορίτσι που ψιθυρίζει πρώτους αριθμούς μπροστά στην Αγία Τράπεζα, ο κουτσός ακορντεονίστας, φίλος του πατέρα του, εκτελεί νοερά αδιανόητους αριθμητικούς υπολογισμούς, η γριά ψυχοκόρη του παππού του σταυροκοπιέται, με τα δάχτυλα ενωμένα σε σχήμα πενταγώνου, μπροστά στο εικόνισμα της Παρθένου...
Κι ενώ προσπαθεί να απεμπλακεί από τα μαθηματικά που στοιχειώνουν ολόκληρο το χωριό, συναντά μια Ελληνο-αμερικανίδα καθηγήτρια που παράτησε τα μαθηματικά στο Πανεπιστήμιο του Σικάγο για να εγκατασταθεί σ' αυτό το καταπράσινο μέρος της Μακεδονίας και να αφιερωθεί στη φιλοσοφία του Πλάτωνα και των πυθαγορείων. Ο Έβαν την ερωτεύεται, γοητεύεται από τα λόγια της για τα μαθηματικά της "Νέας Εποχής" και τη δύναμη του αριθμού του Πλάτωνα. Στη δίνη δραματικών εξελίξεων, ο Έβαν παραδίνεται στα θέλγητρα του μυστικού αριθμού… 

Γρίφος: Οι μοναχοί με το σημάδι του διαβόλου

 

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

Την πρώτη μέρα δεν έφυγε κανένας από το μοναστήρι.

Τη δεύτερη μέρα επίσης δεν έφυγε κανένας.

Την τρίτη μέρα έφυγε ένα πλήθος μοναχών. 

Πόσοι ήταν;

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

 

Το πρόβλημα των τεσσάρων χρωμάτων (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

"Το παράθυρο του Ευκλείδη"

Μέσα από το Παράθυρο του Ευκλείδη, ο Leonard Mlodinow μάς ταξιδεύει με τρόπο απολαυστικό διαμέσου πέντε επαναστάσεων στη γεωμετρία —από την έννοια των παράλληλων ευθειών μέχρι τις τελευταίες ιδέες για τον υπερχώρο. Εδώ έχουμε μια εντελώς νέα, φρέσκια, εναλλακτική ιστορία των Μαθηματικών, της Φυσικής και της Κοσμολογίας, η οποία αποκαλύπτει πώς απλά ερωτήματα σχετικά με το χώρο, τα οποία θα μπορούσε να θέσει ο οποιοσδήποτε, υπήρξαν η κρυφή κινητήρια δύναμη για τα υψηλότερα επιτεύγματα της επιστήμης και της τεχνολογίας.

Βασισμένο στην εκτεταμένη ιστορική έρευνα τού Mlodinow, στις μελέτες του δίπλα σε συναδέλφους (όπως ο Richard Feynman και ο Kip Thorne) και σε συνεντεύξεις με εξέχοντες φυσικούς και μαθηματικούς (όπως ο Murray Gell-Mann, ο Edward Witten και ο Brian Greene), το Παράθυρο του Ευκλείδη είναι ένα εξαιρετικό μείγμα αυστηρής, έγκυρης έρευνας και προσιτής, ευχάριστης αφήγησης, το οποίο συνιστά ένα εκπληκτικά πρωτότυπο επιχείρημα υπέρ της προτεραιότητας της γεωμετρίας. Για όσους κοιτάξουν μέσα από το παράθυρο του Ευκλείδη, κανένας χώρος, κανένα πράγμα και κανένας χρόνος δεν θα είναι πλέον ο ίδιος.

«Η πορεία της επιστήμης είναι εκείνη που χάραξαν οι Έλληνες γεωμέτρες με εργαλείο τους τα μαθηματικά. Από τους αρχαίους Έλληνες και μετά, τα μαθηματικά βρίσκονται στην καρδιά της επιστήμης και η γεωμετρία στην καρδιά των μαθηματικών. Μέσα από το παράθυρο του Ευκλείδη έχουμε ανακαλύψει πολλά, εκείνος ωστόσο δεν μπορούσε να φανταστεί πού θα μας οδηγούσαν. Το να γνωρίσουμε τα άστρα, να φανταστούμε το άτομο και να αρχίσουμε να κατανοούμε πώς αυτά τα κομμάτια τού παζλ ταιριάζουν στο κοσμικό σχέδιο, αποτελεί για το είδος μας μια ιδιαίτερη ευχαρίστηση, ίσως την υπέρτατη. […] Η έρευνά μας για βαθύτερες αλήθειες συνεχίζεται. Οφείλουμε ευγνωμοσύνη στον Ευκλείδη και στις μεγαλοφυΐες που ακολούθησαν, στον Καρτέσιο, στον Gauss στον Αϊνστάιν και —ίσως, ο χρόνος θα δείξει— στον Witten, καθώς και σε όλους εκείνους επάνω στους ώμους των οποίων αυτοί στάθηκαν. Εκείνοι δοκίμασαν τη χαρά της ανακάλυψης. Σε εμάς τους υπόλοιπους πρόσφεραν μια εξίσου σημαντική χαρά, τη χαρά της κατανόησης.»

—Από τον Επίλογο του βιβλίου.

Γρίφος: Το λιοντάρι και ο μονόκερος

Πηγή εικόνας

 

Ένα κορίτσι συναντά στο δάσος ένα λιοντάρι και έναν μονόκερο. 

Το λιοντάρι λέει ψέματα κάθε Δευτέρα, Τρίτη και Τετάρτη, ενώ τις άλλες μέρες λέει την αλήθεια.

Ο μονόκερος λέει ψέματα τις Πέμπτες, τις Παρασκευές και τα Σάββατα, ενώ τις υπόλοιπες μέρες της εβδομάδας λέει την αλήθεια.

"Χθες έλεγα ψέματα", είπε το λιοντάρι στο κορίτσι. "Κι εγώ το ίδιο", είπε ο μονόκερος. 

Τι μέρα είναι σήμερα; 

"Ο αγαπημένος μαθηματικός τύπος του καθηγητή"

 

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

Η Yoko Ogawa γι' αυτό το βιβλίο, που κυκλοφόρησε στην Ιαπωνία το 2004, τιμήθηκε με το λογοτεχνικό βραβείο Γιομιούρι, το Μεγάλο Βραβείο των Βιβλιοπωλών και, πρόσφατα, το βραβείο της Εταιρείας Μαθηματικών, επειδή αποκάλυψε στον αναγνώστη την ομορφιά αυτού του επιστημονικού κλάδου.

To 2006 το μυθιστόρημα μεταφέρθηκε στη μεγάλη οθόνη από τον Ιάπωνα σκηνοθέτη Takashi Koizumi, με τον τίτλο «The Professor and his Beloved Equation». Την ταινία αυτή, όπως και άλλες αξιόλογες ταινίες με μαθηματικό περιεχόμενο, την είχαμε αναφέρει εδώ.

Γρίφος... τετράγωνης λογικής

Βρείτε το μήκος x της πλευράς του τετραγώνου.