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

Συντονιστές: Demetres, socrates, silouan

dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1389
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#1

Μη αναγνωσμένη δημοσίευση από dement » Σάβ Απρ 01, 2017 8:12 am

Έστω 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| είναι ο αριθμός των στοιχείων του A).

(Κολομβία 2011)


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.

Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7887
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Απρ 05, 2017 3:36 pm

Θα δείξουμε αρχικά ότι για κάθε δύο διαφορετικά σύνολα 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}.}

Άρα το ζητούμενο άθροισμα είναι μικρότερο ή ίσο του n. Η ισότητα λαμβάνεται αν επιλέξουμε τα σύνολα \{1\},\{1,2\},\{2\},\{2,3\},\ldots,\{n\},\{n,1\}.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Juniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης