Το Διαπλανητικό Πρόβλημα Χρωματισμού Χαρτών

Ίσως να έχεις ακούσει για το περίφημο Θεώρημα των Τεσσάρων Χρωμάτων — μια από τις πιο γνωστές προτάσεις της μαθηματικής τοπολογίας. Το πρόβλημα ξεκινά απλά: πόσα χρώματα χρειάζονται ώστε κάθε χώρα σε έναν χάρτη να έχει διαφορετικό χρώμα από τις γειτονικές της;

Αν και για δεκαετίες πιστευόταν ότι μπορεί να χρειάζονται πέντε, αποδείχθηκε τελικά (το 1976, από τους Appel και Haken) ότι τέσσερα χρώματα είναι πάντα αρκετά — και ποτέ δεν χρειάζονται περισσότερα.

Το διαπλανητικό βήμα

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

1. Δύο χώρες που έχουν κοινό σύνορο στον ίδιο πλανήτη να έχουν διαφορετικό χρώμα.
2. Κάθε έθνος να έχει το ίδιο χρώμα και στους δύο πλανήτες.

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

Τα ερωτήματα

• Μπορείς να βρεις ένα ζεύγος χαρτών που απαιτεί οκτώ χρώματα;
• Και (πιο δύσκολο) — υπάρχει παράδειγμα που απαιτεί εννέα;

Αυτό το πρόβλημα είναι γνωστό ως Interplanetary Map-Colouring Problem, και συνδυάζει τη γεωμετρία, τη θεωρία γράφων και τη λογική. Η απλότητά του κρύβει τη βαθιά δυσκολία του: πώς δύο συνδεδεμένα «σύμπαντα» περιορισμών μπορούν να χρωματιστούν με τον ελάχιστο δυνατό αριθμό αποχρώσεων;

Από τη Γη στο Διάστημα

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

Μερικά μαθηματικά προβλήματα μοιάζουν απλά — μέχρι να τα δεις από δύο πλανήτες ταυτόχρονα.