socrates έγραψε: ↑Δευ Μαρ 23, 2020 1:32 am
ΘΕΜΑ 2
Σε μια παιδική χαρά παίζουν

παιδιά, όπου

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

διαφορετικού χρώματος κορδέλες και φοράει ένα, επίσης διαφορετικού χρώματος, καπέλο. Άρα, χρειαζόμαστε τουλάχιστον

χρώματα. Θα δείξω ότι

χρώματα αρκούν.
Σχηματίζω έναν

πίνακα. Συμβολίζω για ευκολία

τα χρώματα που θα χρησιμοποιήσω. Γεμίζω τον πίνακα ως εξής:
Στο κάτω αριστερά τετραγωνάκι βάζω τον αριθμό

. Σε όλα τα γειτονικά τετραγωνάκια του προηγούμενου βάζω τον

. Σε όλα τα γειτονικά τετραγωνάκια των προηγούμενων (που δεν έχουν αριθμό), βάζω τον

, κ.ο.κ. Κάνω την ίδια διαδικασία τώρα, ξεκινώντας από την πάνω δεξιά γωνία, δηλαδή βάζοντας στο πάνω δεξιά τετραγωνάκι

, και συνεχίζοντας.
(γειτονικά θεωρώ δύο κελιά με κοινή πλευρά)
Έτσι, για παράδειγμα, ένας

πίνακας θα γίνει:

- combo13.png (13.5 KiB) Προβλήθηκε 2683 φορές
Ας ονομάσω τώρα τα παιδιά

, και ας τα τοποθετήσω όπως στην περίπτωση

παραπάνω, δηλαδή:
στην

οστή γραμμή και στην

στήλη τοποθετώ το παιδί

.
Έτσι, η τομή της

οστής γραμμής με την

οστής στήλης, με

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

και

. Προφανώς, η τομή της

οστής γραμμής με την

οστής στήλη και η τομή της

οστής γραμμής με την

οστής στήλης θα πρέπει να έχουν το ίδιο νούμερο (και τα δύο συμβολίζουν το χρώμα της κορδέλας μεταξύ των

), αλλά από τον τρόπο που έβαλα τους αριθμούς στον πίνακα αυτό καλύπτεται.
Αν πάλι είναι

, η τομή της

οστής γραμμής με την

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

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

διαφορετικούς αριθμούς).
Άρα, ο ελάχιστος αριθμός χρωμάτων που χρειαζόμαστε είναι

.