Σελίδα 1 από 1

Γράμματα σε πίνακα

Δημοσιεύτηκε: Τετ Απρ 26, 2017 2:05 pm
από Demetres
Σε κάθε κελί ενός m \times 8 πίνακα είναι γραμμένο ένα από τα γράμματα A,B,C,D. Γνωρίζουμε ότι αν επιλέξουμε οποιεσδήποτε δύο γραμμές, υπάρχει το πολύ μία στήλη η οποία έχει σε αυτές τις δύο γραμμές ακριβώς το ίδιο γράμμα.

Να βρεθεί η μέγιστη δυνατή τιμή του m.

Επεξεργασία: Ο πίνακας είναι m \times 8. Δηλαδή έχει m σειρές και 8 στήλες.

Re: Γράμματα σε πίνακα

Δημοσιεύτηκε: Πέμ Απρ 27, 2017 10:17 pm
από min##
Έπειτα από αξιοποίηση των πληροφοριών, παίρνουμε ότι το πλήθος των ζεύγων γραμμάτων της ίδια σειρά είναι\leqαπό το πλήθος των τρόπων επιλογής των γραμμών(\binom{m}{2}).Έστω A_{1},A_{2}...,A_{8} το πλήθος των ''Α'' στη στήλη 1,2,...,8 αντίστοιχα και όμοια ορίζονται τα B_{1},...B_{8}, C_{1},...C_{8}, D_{1},...D_{8}.Πρέπει λοιπόν \sum_{i=1}^{8}\binom{A_{i}}{2}+\binom{B_{i}}{2}+\binom{C_{i}}{2}+\binom{D_{i}}{2}\leq \binom{m}{2}.Αν m=4k η αριστερή ελαχιστοποιείται για A_{1}=B_{1}=C_{1}=D_{1}=k
και λύνοντας την ανίσωση ισχύει μόνο για k=1, δηλαδή m=4.Με όμοιο τρόπο εργαζόμαστε και για m=4k+1 (εδώ το ελάχιστο πιάνεται για A_{1}=k,B_{1}=k,C_{1}=k,D_{1}=k+1 κ.ο.κ. και η ανίσωση ισχύει για k=1, δηλαδή m=5),m=4k+2 και m=4k+3 όπου η ανίσωση δεν ισχύει για κανένα k...άρα η μέγιστη τιμή είναι η m=5.

Αυτή η ιδέα πάνω-κάτω αλλά με επιφυλάξεις..

Re: Γράμματα σε πίνακα

Δημοσιεύτηκε: Παρ Απρ 28, 2017 10:04 am
από Demetres
Σωστή και η ιδέα και η τελική απάντηση. Ας δούμε μια πληρέστερη δικαιολόγηση:

Έχουμε ήδη δει ότι

\displaystyle{ \sum \binom{A_i}{2} + \cdots + \sum \binom{D_i}{2} \leqslant \binom{m}{2}}

Από την ανισότητα Jensen (η συνάρτηση f(x) = x(x-1)/2 είναι κυρτή) έχουμε

\displaystyle{ \binom{A_1}{2} + \cdots + \binom{D_1}{2} \geqslant 4 \binom{(A_1+\cdots + D_1)/4}{2} = 4\binom{m/4}{2} = \frac{m(m-4)}{8}}

Ομοίως και για τις άλλες στήλες οπότε παίρνουμε \displaystyle{ m(m-4) \leqslant \frac{m(m-1)}{2}} ή ισοδύναμα m \leqslant 7.

Όμως για m=7 είναι m(m-4)/8 = 21/8 και επειδή ο \binom{A_1}{2} + \cdots + \binom{D_1}{2} είναι ακέραιος έχουμε το ισχυρότερο \binom{A_1}{2} + \cdots + \binom{D_1}{2} \geqslant 3. Αυτό δίνει 8 \cdot 3 \leqslant 8(8-1)/2 που είναι άτοπο.

Ομοίως καταλήγουμε σε άτοπο και για m=6. Άρα πρέπει m \leqslant 5.

Τέλος, είναι αρκετά σημαντικό να δείξουμε ότι υπάρχει παράδειγμα για m=5. Αυτό δεν είναι δύσκολο. Σε κάθε στήλη θα βάλουμε μια φορά κάθε γράμμα εκτός από ένα που θα το βάλουμε δύο φορές. Το μόνο που χρειάζεται να ελέγξουμε είναι ότι σε κάθε στήλη επιλέγουμε διαφορετικό ζεύγος σειρών όπου βάλαμε το ίδιο γράμμα. Αυτό μπορούμε να το κάνουμε αφού έχουμε 8 στήλες και \binom{5}{2} = 10 διαφορετικά ζεύγη σειρών.

Την άσκηση την πήρα από εδώ.

ΥΓ: min## βάζε όλα τα μαθηματικά σε latex. Ακόμη και τα m=5 κ.τ.λ. (Το διόρθωσα στην πιο πάνω ανάρτησή σου.)