IMC 2016/1/4

#1

Έστω θετικοί ακέραιοι $n \geqslant k$ και έστω οικογένεια πεπερασμένων συνόλων $\mathcal{F}$ με τις εξής ιδιότητες:

(α) H $\mathcal{F}$ περιέχει τουλάχιστον $\binom{n}{k}+1$ διακεκριμένα σύνολα με ακριβώς

στοιχεία.

(β) Για κάθε δύο σύνολα $A,B \in \mathcal{F}$ έχουμε $A \cup B \in \mathcal{F}$ .

Να δειχθεί ότι η $\mathcal{F}$ περιέχει τουλάχιστον τρία σύνολα με τουλάχιστον

στοιχεία.

#2

Η άσκηση μπορεί να λυθεί χρησιμοποιώντας ιδέες από εδώ.

Nick1990 · #3

Έχω βάλει λύση στα Αγγλικά εδώ: http://www.artofproblemsolving.com/comm ... 83p6722154

Αν θέλει κάποιος μπορεί να τη μεταφέρει.

ΥΓ: Είναι καλό πρόβλημα για 4ο καθώς έχει και πολλές παγίδες. Όπως είχα συνηθίσει το διαγωνισμό παλιότερα, σε τέτοιο επίπεδο θα έπρεπε να ήταν και τα 3άρια, και ένα από τα 2 2άρια.

#4

Ας μεταφέρω λοιπόν την λύση του Νίκου:

Παίρνουμε την ένωση

όλων των συνόλων

. Έστω

ένα στοιχείο του

. Θεωρούμε τις ακόλουθες οικογένειες συνόλων:

$\displaystyle{F_1 = \{ A \in F : a \in A \}}$
$\displaystyle{F_2 = \{ A \in F : a \notin A \}}$
$\displaystyle{F_3 = \{ A/ \{a\} \in F : A \in F_1 \}}$

Δεν είναι δύσκολο να ελέγξουμε ότι και οι

είναι κλειστές υπό την ένωση συνόλων. Επιπλέον, οι F_1, F_2

περιέχουν σύνολα με ακριβώς

στοιχεία, ενώ η F_3

περιέχει σύνολα με ακριβώς k-1

στοιχεία. Τέλος είναι |F_1| = |F_3|

και $\displaystyle{|F_2| + |F_3| = \binom{n}{k} + 1.}$

Αν ονομάσουμε P(n, k)

την προς απόδειξη πρόταση, τότε αν $\displaystyle{|F_2| \leq \binom{n-1}{k}}$ και $\displaystyle{|F_3| \leq \binom{n-1}{k-1},}$ προσθέτοντας λαμβάνουμε

$\displaystyle{\binom{n}{k} + 1 \leq \binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k},}$

άτοπο.

Άρα τουλάχιστον μία από τις ανισότητες πρέπει να είναι αντίστροφη και αυστηρή.

Αν η πρώτη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η P(n-1,k)

, έχουμε

σύνολα στο F_2

με τουλάχιστον n-1

στοιχεία. Επειδή $F_2 \subset F$ , παίρνοντας την ένωση αυτών των τριών συνόλων μαζί με ένα υποσύνολο της

που περιέχει το

, έχουμε δύο από τα τρία σύνολα που θέλουμε για την P(n,k)

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

. Επαναλαμβάνουμε την διαδικασία με το στοιχείο

. Τότε είτε λαμβάνουμε τρία νέα σύνολα με τουλάχιστον n-1

στοιχεία, τα οποία δεν περιέχουν το

, και άρα η ένωσή τους μας δίνει το επιθυμητό τρίτο σύνολο για την P(n,k)

ή πέφτουμε στην περίπτωση όπου η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή, την οποία και θα μελετήσουμε πιο κάτω.

Τώρα αν η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η P(n-1,k-1)

, έχουμε

σύνολα στην F_3

με τουλάχιστον n-1

στοιχεία. Η ένωση του κάθε ενός ξεχωριστά με το

ανήκει στην

, όλες αυτές οι ενώσεις είναι διακεκριμένες και έχουν τουλάχιστον

στοιχεία η κάθε μία. Άρα πάλι έχουμε την P(n, k)

.

Άρα για να δείξουμε την P(n, k)

αρκεί να δείξουμε τις P(n-1,k)

και

. Άρα είναι αρκετό να δείξουμε ότι οι P(m, m)

και

είναι αληθείς για κάθε

.

Για την P(m, m)

, έχουμε δύο διακεκριμένα σύνολα με

στοιχεία το ένα, των οποίων η ένωση προφανώς περιέχει m+2 > m

στοιχεία, άρα έχουμε

σύνολα με τουλάχιστον

στοιχεία και η πρόταση είναι αληθής.

Για την P(m, 1)

, έχουμε

σύνολα με ένα στοιχείο το κάθε ένα, και μπορούν να πάρουμε την ένωση οποιονδήποτε

από αυτά ή όλων για να πάρουμε $m+2 \geq 3$ διακεκριμένα σύνολα με τουλάχιστον

στοιχεία το κάθε ένα και άρα η P(m, 1)

είναι επίσης αληθείς.

#5

Βάζω και την δική μου απόδειξη. Θα αποδείξω κάτι πιο ισχυρό αλλάζοντας την συνθήκη (α) στην

(α') H $\mathcal{F}$ περιέχει τουλάχιστον $\binom{n}{k}+1$ διακεκριμένα σύνολα με το πολύ

στοιχεία.

Για μια οικογένεια συνόλων $\mathcal{A}$ και ένα στοιχείο

ορίζω τα εξής:

Για $A \in \mathcal{A}$ ορίζω D_i(A) = A

αν $i \notin A$ ή αν $A \setminus \{i\} \in \mathcal{A}$ . Αλλιώς ορίζω $D_i(A) = A \setminus \{i\}$ .

Ορίζω επίσης $D_i(\mathcal{A}) = \{D_i(A) : A \in \mathcal{A}\}$

Είναι απλό ότι η D_i

είναι 1 προς 1 στην $\mathcal{A}$ . Είναι επίσης απλό ότι αν η $\mathcal{A}$ ικανοποιεί τις (α') και (β) το ίδιο ισχύει και για την $D_i(\mathcal{A})$ . Τέλος αν η $D_i(\mathcal{A})$ έχει τρία διακεκριμένα σύνολα, έστω τα D_i(A),D_i(B)

και

, με τουλάχιστον

στοιχεία το ίδιο ισχύει και για την $\mathcal{A}$ θεωρώντας τα σύνολα A,B,C

.

Ξεκινάμε λοιπόν από την $\mathcal{F}$ . Αν η $\mathcal{F}$ έχει ένα σύνολο

με

στοιχεία ώστε κάποιο από τα υποσύνολά του με m-1

στοιχεία να μην ανήκει στη $\mathcal{F}$ , έστω το $A \setminus \{i\}$ , τότε αντί με την $\mathcal{F}$ εργαζόμαστε με την $D_i(\mathcal{F})$ και αρκεί να αποδείξουμε το ζητούμενο για αυτήν.

Επαναλαμβάνοντας την διαδικασία, μπορούμε να υποθέσουμε ότι αν $A \in \mathcal{F}$ και $B \subseteq A$ , τότε είναι και $B \in \mathcal{F}$ . [Η διαδικασία τελειώνει επειδή κάθε φορά μειώνεται αυστηρά το άθροισμα των πληθικών αριθμών των συνόλων της οικογενείας.]

Επειδή τώρα η $\mathcal{F}$ έχει τουλάχιστον $\displaystyle{ \binom{n}{k}+1}$ σύνολα με το πολύ

στοιχεία, η ένωση των συνόλων της $\mathcal{F}$ θα περιέχει τουλάχιστον $m \geqslant n+1$ στοιχεία.

Χωρίς βλάβη της γενικότητας λοιπόν έχουμε $\{1,2,\ldots,m\} \in \mathcal{F}$ . Τότε όμως τα $\{1,2,\ldots,m-1\},\{1,2,\ldots,m-2,m\}$ και $\{1,2,\ldots,m\}$ είναι τρία διακεκριμένα σύνολα της $\mathcal{F}$ με τουλάχιστον

στοιχεία.

IMC 2016/1/4

IMC 2016/1/4

Re: IMC 2016/1/4

Re: IMC 2016/1/4

Re: IMC 2016/1/4

Re: IMC 2016/1/4

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