Γράμματα σε πίνακα
Δημοσιεύτηκε: Τετ Απρ 26, 2017 2:05 pm
Σε κάθε κελί ενός
πίνακα είναι γραμμένο ένα από τα γράμματα
. Γνωρίζουμε ότι αν επιλέξουμε οποιεσδήποτε δύο γραμμές, υπάρχει το πολύ μία στήλη η οποία έχει σε αυτές τις δύο γραμμές ακριβώς το ίδιο γράμμα.
Να βρεθεί η μέγιστη δυνατή τιμή του
.
Επεξεργασία: Ο πίνακας είναι
. Δηλαδή έχει
σειρές και
στήλες.
πίνακα είναι γραμμένο ένα από τα γράμματα
. Γνωρίζουμε ότι αν επιλέξουμε οποιεσδήποτε δύο γραμμές, υπάρχει το πολύ μία στήλη η οποία έχει σε αυτές τις δύο γραμμές ακριβώς το ίδιο γράμμα.Να βρεθεί η μέγιστη δυνατή τιμή του
.Επεξεργασία: Ο πίνακας είναι
. Δηλαδή έχει
σειρές και
στήλες.
από το πλήθος των τρόπων επιλογής των γραμμών(
).Έστω
το πλήθος των ''Α'' στη στήλη 1,2,...,8 αντίστοιχα και όμοια ορίζονται τα
.Πρέπει λοιπόν
.Αν
η αριστερή ελαχιστοποιείται για 
, δηλαδή
.Με όμοιο τρόπο εργαζόμαστε και για
(εδώ το ελάχιστο πιάνεται για
κ.ο.κ. και η ανίσωση ισχύει για
),
και
όπου η ανίσωση δεν ισχύει για κανένα
...άρα η μέγιστη τιμή είναι η 
είναι κυρτή) έχουμε
ή ισοδύναμα
.
είναι
και επειδή ο
είναι ακέραιος έχουμε το ισχυρότερο
. Αυτό δίνει
που είναι άτοπο.
. Άρα πρέπει
.
διαφορετικά ζεύγη σειρών.