Χρωματισμός σκακιέρας

[Demetres]

Έστω μια σκακιέρα με όλα τα τετραγωνάκια λευκά.

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

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

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

[socrates]

Επαναφορά!

[kimjonarfib]

γειτονικά εννοούμε αυτά που έχουν μια πλευρά κοινή(ή και τα διαγώνια με κοινή κορυφή)

[kimjonarfib]

Αν θεωρούμε γειτονικά ενός κουτιού μόνο τα κουτιά που έχουν μια κοινή πλευρά με αυτό τότε για το (α)

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

[Demetres]

Ναι γειτονικά σημαίνει κοινή πλευρά.

.To κάθε γειτονικό κουτί από τα αρχικό συνορεύει προς το παρών μόνο με ένα κουτί επομένως για να συνεχίσει να έχει περιττό αριθμό γειτονικών μαύρων κουτιών χρειάζεται άρτιο πλήθος νέων μαύρων.Όμως προσθέτοντας άρτια σε νούμερο μαύρα κουτιά...

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