Δέκα στοιχεία

#1

Έστω υποσύνολα $A_1,\ldots,A_{2014}$ ενός πεπερασμένου συνόλου

ώστε $|A_k| > \frac{1}{2}|A|$ για κάθε

. Να δειχθεί ότι υπάρχει 10 στοιχεία $a_1,\ldots,a_{10}$ του

ώστε κάθε

να περιέχει τουλάχιστον ένα από τα $a_1,\ldots,a_{10}$ .

Nick1990 · #2

Demetres έγραψε:Έστω υποσύνολα $A_1,\ldots,A_{2014}$ ενός πεπερασμένου συνόλου ώστε $|A_k| > \frac{1}{2}|A|$ για κάθε . Να δειχθεί ότι υπάρχει 10 στοιχεία $a_1,\ldots,a_{10}$ του ώστε κάθε να περιέχει τουλάχιστον ένα από τα $a_1,\ldots,a_{10}$ .

Ωραίο πρόβλημα!

Αρχικά θεωρούμε S_0

το σύνολο που περιέχει τα σύνολα A_i

, οπότε ισχύει |S_0| = 2014

και έστω ακόμα $P_0 = \emptyset$

Κατασκευάζουμε τα σύνολα S_j, P_j

, για

, επαγωγικά ως εξής: Στο

ωστό βήμα, επιλέγουμε ένα στοιχείο

της ένωσης των συνόλων A_i

που ανήκουν στο $S_{j-1}$ (αν αυτή δεν είναι κενή), το οποίο ανήκει στο μέγιστο δυνατό αριθμό τέτοιων συνόλων, και υποθέτοντας ότι τα σύνολα αυτά είναι τα Y_1, ..., Y_m

ορίζουμε:
$S_j = S_{j-1}/\{Y_1, ...., Y_m\}$ και $P_j = P_{j-1}\cup\{x\}$

Η κατασκευή σταματάει αν το

γίνει τέτοιο ώστε να ισχύει $S_j = \emptyset$ , και τότε κάθε σύνολο A_i

περιέχει προφανώς τουλάχιστον ένα στοιχείο που ανήκει στο P_j

. Αρκεί να δείξουμε λοιπόν ότι η κατασκευή αυτή θα σταματήσει σίγουρα για $j \leq 10$ , διότι τότε θα ισχύει προφανώς $|P_j| = j \leq 10$ .

Για τυχαίο

τώρα, διατάσσουμε τα σύνολα που περιέχονται στο S_j

και τα στοιχεία που ΔΕΝ περιέχονται στο P_j

, και ορίζουμε $k_{j,m,n} = 1$ αν το

οστό σύνολο του S_j

περιέχει το

οστό στοιχείο που ΔΕΝ ανήκει στο P_j

, και $k_{j,m,n} = 0$ διαφορετικά. Παρατηρούμε τώρα ότι τα στοιχεία ενός τυχαίου συνόλου που ανήκει στο S_j

, δεν ανήκουν στο P_j

(προφανές από την κατασκευή) και από την υπόθεση είναι πιο πολλά από $\frac{|A|}{2}$ . Άρα τα για κάθε

το $k_{j,m,n} = 1$ για περισσότερα $\frac{|A|}{2}$ διαφορετικά

. Επομένως έχουμε:

$\displaystyle{\sum_{n=1}^{|A|-|P_j|}\sum_{m=1}^{|S_j|}k_{j,m,n} = \sum_{m=1}^{|S_j|}\sum_{n=1}^{|A|-|P_j|}k_{j,m,n}} > |S_j|\frac{|A|}{2}$
που σημαίνει ότι για ένα τουλάχιστον

, περισσότερα από $\frac{|S_j||A|}{2(|A|-|P_j|)}$ από τα $k_{j,m,n}$ θα είναι ίσα με

, οπότε για την κατασκευή του $S_{j+1}$ θα αφαιρεθούν από το S_j

περισσότερα από $\frac{|S_j||A|}{2(|A|-|P_j|)}$ σύνολα, επομένως, αφού |P_j|=j

, θα έχουμε:

$|S_{j+1}| \leq |S_j| - \frac{|S_j||A|}{2(|A|-|P_j|)} - 1 < \frac{|S_j|}{2} - 1 < ... < \frac{|S_0|}{2^{j+1}} - 1 = \frac{2014}{2^{j+1}} - 1 (*)$ .

Αν στο j+2-

οστό βήμα η διαδικασία σταματάει, θα έχουμε:

$1 \leq |S_{j+1}| < \frac{2014}{2^{j+1}} - 1 \Rightarrow 2 < \frac{2014}{2^{j+1}} \Rightarrow 2^{j+2} < 2014 < 2^{11} \Rightarrow j+2 < 11$

Οπότε $j+2 \leq 10$ και η απόδειξη είναι πλήρης.

(*) Εδώ κατά την αναδρομική εφαρμογή της ανισότητας, εφαρμόζουμε την πιο "χαλαρή" $|S_{l+1}| \leq \frac{|S_l|}{2}$ για $l \leq j-1$ .

#3

Ήταν το πρόβλημα Β4 από τον Putnam του 1980. (Αλλά με 1066 σύνολα. Δεν κατανοώ γιατί αυτή η επιλογή αριθμού.)

Ουσιαστικά παρόμοια και η δική μου απόδειξη:

Ισχυρισμός: Αν έχω $2^{n+1}-2$ υποσύνολα ενός συνόλου

ώστε κάθε υποσύνολο

να ικανοποιεί |A| > |X|/2

τότε μπορώ να βρω

στοιχεία του

ώστε κάθε υποσύνολο να περιέχει τουλάχιστον ένα από αυτά το τα στοιχεία.

Για n=1

άμεσο αφού αν έχω δύο υποσύνολα A,B

του

με

τότε

άρα τα

έχουν τουλάχιστον ένα κοινό στοιχείο το οποίο μπορώ να επιλέξω.

Έστω ότι ισχύει για n=k

και ότι έχω $2^{k+2} - 2$ υποσύνολα του

, έστω $A_1,\ldots,A_{2^{k+2}-2}$ , με |A_i| > |X|/2

. Τότε $\displaystyle{ \sum{|A_i|} > (2^{k+1}-1)|X|}$ άρα από περιστεροφωλιά υπάρχει ένα στοιχείο του

που ανήκει σε τουλάχιστον $2^{k+1}$ από τα A_i

. Για τα υπόλοιπα $2^{k+2}-2 - 2^{k+1} = 2^{k+1}-2$ υποσύνολα χρησιμοποιώ την επαγωγική υπόθεση για να βρω

στοιχεία ώστε κάθε ένα από τα υπόλοιπα υποσύνολα να περιέχει τουλάχιστον ένα από αυτά το τα στοιχεία.

Οπότε ο ισχυρισμός ισχύει επαγωγικά.

Επιπλέον ερώτημα: Ας δειχθεί πως το $2^{n+1} - 2$ στον πιο πάνω ισχυρισμό είναι το καλύτερο δυνατό.

Δέκα στοιχεία

Δέκα στοιχεία

Re: Δέκα στοιχεία

Re: Δέκα στοιχεία

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