From: George Papargiris (gpapargi(@)hotmail.com)
Date: Δευ 05 Μαΐ 2003 - 13:06:50 EEST

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]

Καλημέρα και χρόνια πολλά σε όλους.

Καταρχήν ας θυμηθούμε το πρόβλημα που όπως είπα και στην εκφώνηση μου έστειλε ο φίλος μου Θεοφάνης Γκούντρας:

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

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

Ποιος από τους 2 έχει δίκιο και γιατί;

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

Απάντηση

Έψαξα κάμποσο και είδα ότι πρόκυτε για υποπερίπτωση ενός γνωστού (στην επιστημονική κοινότητα) προβλήματος. Το 1949 ο Edward Nelson έθεσε το ακόλουθο ερώτημα: "Αν θέλουμε να χρωματίσουμε ένα επίπεδο έτσι ώστε 2 σημεία που απέχουν μεταξύ τους δεδομένη απόσταση d (έστω d=1) να μην έχουν το ίδιο χρώμα, ποιος είναι ο ελάχιστος αριθμός χρωμάτων που χρειαζόμαστε;"

Ο Martin Gardner, γνωστός από την ενασχόλησή του με τα ψυχαγωγικά μαθηματικά και συγγραφέας βιβλίων σε αυτό το αντικείμενο, έκανε ευρέως γνωστό το πρόβλημα από τη στήλη του στο Scientific american. Ο διάσημος μαθηματικός Paul Erdos (1913-1996) το ανέφερε σε αρκετές από τις διαλέξεις του (ήταν ένα από τα αγαπημένα του προβλήματα).

Ας δούμε λοιπόν τι πρόοδος έχει γίνει μέχρι στιγμής: Αποδεικνύεται ότι 7 χρώματα είναι αρκετά για τον ζητούμενο χρωματισμό (χρησιμοποιώντας εξάγωνους σχηματισμούς). Επίσης αποδεικνύεται ότι 3 χρώματα δεν είναι αρκετά. Αυτό ήταν και το ζητούμενο στο συγκεκριμένο quiz. Καταλήγουμε δηλαδή στο ότι το "chromatic number of plane", όπως αναφέρεται, είναι 4,5,6 ή 7. Μέχρι εδώ έχουμε φτάσει. Όχι και πολύ σημαντικη πρόοδος... Το να βρεθεί ο ελάχιστος αριθμός χρωματων είναι ένα πρόβλημα που διατυπώνεται εύκολα αλλά λύνεται πολύ δύσκολα. Ίσως και να μη λύνεται.

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

Ας δούμε αυτή την απόδειξη.

Έστω 1,2 και 3 τα χρώματα που έχουμε στη διάθεσή μας. Έστω Α, Β και Γ ένα ισόπλευρο τρίγωνο με πλευρά d. Άν το Α έχει το χρώμα 1, τότε υποχρεωτικά τα Β και Γ έχουν τα χρώματα 2 και 3. Ας πούμε ότι το Β έχει το χρώμα 2 και ο Γ έχει το χρώμα 3.

Θεωρούμε το άλλο ισόπλευρο τρίγωνο του επιπέδου (με πλευρά d) που έχει πλευρά την ΒΓ, το ΔΒΓ. Το Δ έχει υποχρεωτικά το χρώμα 1 αφού απέχει d από τα Β και Γ.

Φανταζόμαστε όλη την παραπάνω διάταξη να περιστρέφεται γύρω από το Α. Δε χρειάζεται να γίνει πλήρης κύκλος, αρκεί το σημείο Δ να διαγράψει τόξο του οποίου η αντίστοιχη χορδή είναι d. Ας ονομάσουμε Ε το σημείο στο οποίο καταλήγει το Δ μετά την περιστροφή. Τα Β και Γ θα καταλήξουν σε 2 σημεία (έστω Ζ και Η) που αναγκαστικά θα έχουν χρώματα διαφορετικά από το 1, γιατί απέχουν d από το Α (όπως τα σημεία Β και Γ). Έτσι το Ε θα πρέπει να έχει το χρώμα 1 αφού απέχει d από τα Ζ και Η.

Καταλήξαμε λοιπόν στο ότι τα σημεία Δ και Ε που απέχουν μεταξύ τους d έχουν κατ' ανάγκη το ίδιο χρώμα. Άτοπο. Άρα 3 χρώματα δεν είναι αρκετά και ο μαθηματικός κερδίζει το στοίχημα.

Σωστά απάντησαν οι:

Δημήτρης Σκουτέρης
Βαγγέλης Καπούλας
Αθανάσιος Νικολακόπουλος Νίκος Καραντζούλης

Φιλικά

Γιώργος

--



_______________________________________________________________

      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org

        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________

• Next message: Skouteris Dimitris: "Re: Ippotes & paliatsoi (APANTHSH)"
• Previous message: George Papargiris: "Re: Η κατάλληλη διαδρομή (Λύση)"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]