mathematica.gr

Δημοσιεύτηκε: **Δευ Φεβ 15, 2021 9:22 pm**

Το παρακάτω είναι ένα θέμα που το παλεύω καιρό και θα ήθελα λίγη βοήθεια αν κάποιος έχει τον χρόνο, καθώς δεν το βρήκα με τη λύση.
Τα τετράγωνα σε έναν $n \times n$ πίνακα βάφονται άσπρα και μπλε με τέτοιο τρόπο ώστε ποτέ δύο άσπρα τετράγωνα να μη γειτονεύουν (ούτε να έχουν κοινή πλευρά ούτε κοινή κορυφή). (1)
α. Αν επιπρόσθετα πρέπει να υπάρχουν ακριβώς δύο άσπρα τετράγωνα σε κάθε στήλη και ακριβώς δύο άσπρα τετράγωνα σε κάθε σειρά (2) να αποδειχθεί ότι για n=7

δεν γίνεται κάτι τέτοιο.

Δημοσιεύτηκε: **Δευ Φεβ 15, 2021 10:53 pm**

mathematicauser έγραψε: Δευ Φεβ 15, 2021 9:22 pm Τα τετράγωνα σε έναν $n \times n$ πίνακα βάφονται άσπρα και μπλε με τέτοιο τρόπο ώστε ποτέ δύο άσπρα τετράγωνα να μη γειτονεύουν (ούτε να έχουν κοινή πλευρά ούτε κοινή κορυφή). (1)
α. Αν επιπρόσθετα πρέπει να υπάρχουν ακριβώς δύο άσπρα τετράγωνα σε κάθε στήλη και ακριβώς δύο άσπρα τετράγωνα σε κάθε σειρά (2) να αποδειχθεί ότι για δεν γίνεται κάτι τέτοιο.

Είναι πολύ εύκολο να αποδείξουμε ότι για n=7

η κατασκευή είναι αδύνατη.

Πράγματι, μία τέτοια κατασκευή θα είχε $2\times 7 = 14$ άσπρα τετράγωνα. Βάφουμε τώρα τον $7\times 7$ πίνακα όπως στο επiσυναπτόμενο σχήμα. Παρατηρούμε ότι στην κόκκινη περιοχή μπορούμε να βάλουμε το πολύ 2+2=4

άσπρα τετράγωνα. Επίσης σε κάθε $2\times 2$ κίτρινο και σε κάθε $2\times 2$ γαλάζιο τετράγωνο μπορούμε να βάλουμε το πολύ

άσπρο. Αυτό δίνει ένα σύνολο από το πολύ 9 άσπρα. Μαζί με τα 4 στα κόκκινα δίνει το πολύ 9+4=13 <14

άσπρα. Άρα δεν φτάνουμε στα

.

mathematica.gr

Θέμα συνδυαστικής από εθνική ολυμπιάδα

Θέμα συνδυαστικής από εθνική ολυμπιάδα

Re: Θέμα συνδυαστικής από εθνική ολυμπιάδα