Προχωρούμε σε τομές

dement · #1

Έστω $A_1, A_2, ..., A_{2n}$ υποσύνολα του $\{ 1, 2, ..., n \}$ , ανά δύο διαφορετικά.

Να βρεθεί η μέγιστη τιμή του $\displaystyle \sum_{i=1}^{2n} \frac{\left| A_i \cap A_{i+1} \right|}{|A_i| \cdot |A_{i+1}|}$ , με την υπόθεση $A_{2n+1} = A_1$ .

( |A|

είναι ο αριθμός των στοιχείων του

).

(Κολομβία 2011)

#2

Θα δείξουμε αρχικά ότι για κάθε δύο διαφορετικά σύνολα A,B

έχουμε $\displaystyle{ \frac{|A \cap B|}{|A||B|} \leqslant \frac{1}{2}}$

Έστω ότι |A| = a,|B|=b

και έστω χωρίς βλάβη της γενικότητας ότι $a \geqslant b$ . Αν a=0

το αποτέλεσμα είναι άμεσο. Το ίδιο και αν a = 1

αφού η συνθήκη ότι τα A,B

είναι διαφορετικά μας δίνει $|A \cap B| = 0$ . Πρέπει λοιπόν $a \geqslant 2$ . Τότε όμως είναι $|A \cap B| \leqslant |B| = b$ οπότε $\displaystyle{ \frac{|A \cap B|}{|A||B|} \leqslant \frac{1}{a} \leqslant \frac{1}{2}.}$

Άρα το ζητούμενο άθροισμα είναι μικρότερο ή ίσο του

. Η ισότητα λαμβάνεται αν επιλέξουμε τα σύνολα $\{1\},\{1,2\},\{2\},\{2,3\},\ldots,\{n\},\{n,1\}$ .

Προχωρούμε σε τομές

Προχωρούμε σε τομές

Re: Προχωρούμε σε τομές

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