smar έγραψε:
Πρόβλημα 4.
Το επίπεδο χωρίζεται σε μοναδιαία τετράγωνα από δύο σύνολα παράλληλων ευθειών, σχηματίζοντας ένα άπειρο πλέγμα. Κάθε μοναδιαίο τετράγωνο χρωματίζεται με ένα από τα

χρώματα έτσι, ώστε να μην υπάρχει ορθογώνιο με περίμετρο

το οποίο να περιέχει δύο τετράγωνα του ιδίου χρώματος. Να αποδείξετε ότι δεν υπάρχει ορθογώνιο με διαστάσεις

ή

που να περιέχει δύο τετράγωνα του ιδίου χρώματος.
Σημείωση: Υποθέτουμε εδώ ότι κάθε ορθογώνιο έχει πλευρές που περιέχονται στις ευθείες του πλέγματος.
Πολύ όμορφο και δύσκολο πρόβλημα. Κάπως μπελαλίδικο να γραφτεί η λύση. Είναι μεν δύσκολο αλλά η λύση είναι πιο απλή από ότι φαίνεται από το μέγεθός της. Η χρήση αρκετών εικόνων θα βοηθούσε αλλά τις παραλείπω. Πάντως υπάρχουν μονάδες για να πάρει κάποιος που δεν μπόρεσε να φτάσει σε πλήρη λύση. Ίσως αυτές να διαχωρίσουν τα χρυσά από τα αργυρά μιας και όσοι πάνε για χρυσό μάλλον θα έλυσαν τα πρώτα τρία.
Σχόλιο πριν την λύση: Το κλειδί είναι να κατανοηθεί που χρειάζεται το

. Είναι σίγουρο ότι λιγότερα χρώματα δεν δουλεύουν. Π.χ. αν υπήρχε χρωματισμός με

χρώματα τότε κάθε

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

δεν εμφανίζεται καθόλου τυχαία. Είναι απαραίτητο λοιπόν να ψάξουμε να βρούμε γιατί να εμφανίζεται το

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

και

έχει διαστάσεις

επί

. Οπότε η δεδομένη συνθήκη είναι ισοδύναμη με την εξής:
Αν τα

και

έχουν το ίδιο χρώμα τότε

. Συχνά θα αναφέρομαι στο

ως την «απόσταση» μεταξύ των σημείων

και

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

διαδοχικά οριζόντια (αντίστοιχα κάθετα) σημεία είναι διαφορετικά χρωματισμένα.
Για κάθε

ορίζω
Παρατηρώ κοιτάζοντας π.χ. τις τιμές που μπορεί να πάρει το

ότι
Επίσης για κάθε

, κάθε δύο σημεία του

είναι χρωματισμένα διαφορετικά. Πράγματι αν

δύο τέτοια σημεία τότε είναι
Άρα στα σημεία του

χρησιμοποιώ όλα τα χρώματα από μία φορά το κάθε ένα.
Ξεκινώ κοιτάζοντας τα

και

. Η διαφορά μεταξύ των

και

είναι ότι το μεν πρώτο περιέχει επιπλέον τα

σημεία του συνόλου

ενώ το δε δεύτερο τα

σημεία του συνόλου
Επίσης η διαφορά μεταξύ των

και

είναι ότι το μεν πρώτο περιέχει επιπλέον τα

σημεία του συνόλου

ενώ το δε δεύτερο τα

σημεία του συνόλου
Ισχυρίζομαι ότι το χρώμα του

του συνόλου

είναι το ίδιο με το χρώμα είτε του

είτε του

του συνόλου

.
Αν αυτό δεν ισχύει τότε το

έχει το ίδιο χρώμα με κάποιο

για

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

. Επίσης δεν μπορεί να έχει το ίδιο χρώμα με κάποιο

όπου

αφού η απόσταση μεταξύ των δύο σημείων είναι

. Άρα τα

και

έχουν το ίδιο χρώμα. Επειδή το

ανήκει στο

πρέπει να έχει το ίδιο χρώμα με κάποιο σημείο του

. Δεν μπορεί να είναι κάποιο της μορφής

με

διότι η απόσταση από το

είναι

. Δεν μπορεί να είναι ούτε κάποιο της μορφής

με

διότι η απόσταση από το

είναι

. Πρέπει λοιπόν το

να έχει το ίδιο χρώμα με το

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

έχει το ίδιο χρώμα με το

. Αυτό είναι άτοπο αφού τα

και

δεν έχουν το ίδιο χρώμα.
Βέβαια το

δεν παίζει κάποιο ιδιαίτερο ρόλο. Ακριβώς με την ίδια λογική το

έχει το ίδιο χρώμα με ένα εκ των

και

. Επίσης έχει το ίδιο χρώμα με ένα εκ των

και

και με ένα εκ των

[Από συμμετρία.]
Ας ξεκινήσουμε τώρα από ένα αυθαίρετο σημείο. Έστω χωρίς βλάβη της γενικότητας το

. Θέλουμε να δείξουμε ότι τα

για

έχουν όλα διαφορετικό χρώμα από το

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

έχει το ίδιο χρώμα με το

. Το ίδιο και ένα εκ των

και

. Δεν μπορεί να είναι το

αφού είναι κοντά στο

άρα είναι το

. Το ίδιο χρώμα έχει και ένα εκ των

και

. Δεν μπορεί να είναι το

άρα είναι το

.
Μέχρι στιγμής έχω δείξει ότι τα

και

έχουν το ίδιο χρώμα με το

.
Θα δείξω επαγωγικά ότι για κάθε

τα

και

έχουν το ίδιο χρώμα με το

.
Ήδη έχει δειχθεί για

.
Αφού το

έχει το ίδιο χρώμα, το ίδιο ισχύει και για ένα εκ των

και

. Δεν μπορεί να είναι το

αφού η απόστασή του από το

είναι μικρή. Άρα είναι το

.
Αφού το

έχει το ίδιο χρώμα, το ίδιο ισχύει και για ένα εκ των

και

. Δεν μπορεί να είναι το

αφού η απόστασή του από το

είναι μικρή. Άρα είναι το

.
Αφού το

έχει το ίδιο χρώμα, το ίδιο ισχύει και για ένα εκ των

και

. Δεν μπορεί να είναι το

αφού η απόστασή του από το

είναι μικρή. Άρα είναι το

.
Δείξαμε λοιπόν πως και τα

και

έχουν το ίδιο χρώμα που είναι η επαγωγική υπόθεση για

.
Άρα ο ισχυρισμός έχει αποδειχθεί.
Ας επανέλθουμε τώρα στον τελικό στόχο που είναι να δείξουμε πως κανένα εκ των

για

δεν έχει ίδιο χρώμα με το

. Έστω λοιπόν

. Μπορώ να υποθέσω ότι

αφού αλλιώς είναι άμεσο. Επίσης για

το

έχει το ίδιο χρώμα με το

οπότε μπορώ επίσης να υποθέσω ότι

.
Μπορώ να γράψω

όπου

και

. Είναι

οπότε είναι

.
Τότε όμως η απόσταση του

από το

το οποίο έχει το ίδιο χρώμα με το

είναι

. Οπότε το

έχει διαφορετικό χρώμα από το

και άρα και από το

.
Η απόδειξη ολοκληρώθηκε.
