Σκακιέρα 5 x 5

[socrates]

Ποιος ο ελάχιστος αριθμός κελιών ενός πίνακα που πρέπει να βάψουμε ώστε σε κάθε γραμμή, σε κάθε στήλη και σε κάθε τετράγωνο να υπάρχει ένα τουλάχιστον βαμμένο κελί;

https://artofproblemsolving.com/communi ... 2016_l2_p2

[Mihalis_Lambrou]

Ποιος ο ελάχιστος αριθμός κελιών ενός πίνακα που πρέπει να βάψουμε ώστε σε κάθε γραμμή, σε κάθε στήλη και σε κάθε τετράγωνο να υπάρχει ένα τουλάχιστον βαμμένο κελί;

Απάντηση: βαμμένα.

Ένα παράδειγμα με έχουμε στην τρίτη εικόνα. Θα δείξουμε ότι δεν γίνεται με λιγότερα από βαμμένα.

Πράγματι, αν σε κάποια βαφή είναι βαμμένα τα τέσσερα γωνιακά τετράγωνα (αριστερό σχήμα) τότε η βαφή αυτή χρειάζεται τουλάχιστον άλλα τρία βαμμένα, ένα για κάθε μία από τις τρεις κενές στήλες. Άρα θέλουμε και πάνω βαμμένα.

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

Δηλαδή πάντα χρειαζόμαστε ή περισσότερα βαμμένα τετράγωνα.