Putnam 1988/A4

[Demetres]

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

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

[Demetres]

Επαναφορά. Ίσως και να την έχουμε ξαναδεί.

[dement]

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

β. Όχι. Χρωματίζουμε κάθε σημείο σύμφωνα με το ζεύγος . Η supremum απόσταση ομόχρωμων σημείων στο ίδιο "τετραγωνάκι" είναι χωρίς να επιτυγχάνεται, ενώ η ελάχιστη απόσταση ομόχρωμων σημείων σε διαφορετικά τετραγωνάκια είναι .

[Demetres]

Ωραία.

Το (β) μπορεί να βελτιωθεί και σε χρώματα, χωρίζοντας το επίπεδο σε κανονικά εξάγωνα αντί σε τετράγωνα. Δείτε π.χ. εδώ.

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