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

#1

Σε κάθε κελί ενός $m \times 8$ πίνακα είναι γραμμένο ένα από τα γράμματα A,B,C,D

. Γνωρίζουμε ότι αν επιλέξουμε οποιεσδήποτε δύο γραμμές, υπάρχει το πολύ μία στήλη η οποία έχει σε αυτές τις δύο γραμμές ακριβώς το ίδιο γράμμα.

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

.

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

σειρές και

στήλες.

min## · #2

Έπειτα από αξιοποίηση των πληροφοριών, παίρνουμε ότι το πλήθος των ζεύγων γραμμάτων της ίδια σειρά είναι $\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=4k+1

(εδώ το ελάχιστο πιάνεται για $A_{1}=k,B_{1}=k,C_{1}=k,D_{1}=k+1$ κ.ο.κ. και η ανίσωση ισχύει για k=1

, δηλαδή

),

και

όπου η ανίσωση δεν ισχύει για κανένα

...άρα η μέγιστη τιμή είναι η m=5

.

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

#3

Σωστή και η ιδέα και η τελική απάντηση. Ας δούμε μια πληρέστερη δικαιολόγηση:

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

$\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

είναι

και επειδή ο $\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

. Αυτό δεν είναι δύσκολο. Σε κάθε στήλη θα βάλουμε μια φορά κάθε γράμμα εκτός από ένα που θα το βάλουμε δύο φορές. Το μόνο που χρειάζεται να ελέγξουμε είναι ότι σε κάθε στήλη επιλέγουμε διαφορετικό ζεύγος σειρών όπου βάλαμε το ίδιο γράμμα. Αυτό μπορούμε να το κάνουμε αφού έχουμε

στήλες και $\binom{5}{2} = 10$ διαφορετικά ζεύγη σειρών.

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

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

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

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

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

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

Μέλη σε σύνδεση