IMC 2016/1/4

Συντονιστής: Demetres

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

IMC 2016/1/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 28, 2016 10:35 am

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

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

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

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



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

Re: IMC 2016/1/4

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 28, 2016 6:47 pm

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


Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: IMC 2016/1/4

#3

Μη αναγνωσμένη δημοσίευση από Nick1990 » Παρ Αύγ 12, 2016 3:11 pm

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

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

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


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

Re: IMC 2016/1/4

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Σεπ 07, 2016 3:10 pm

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

Παίρνουμε την ένωση S όλων των συνόλων a. Έστω a ένα στοιχείο του S. Θεωρούμε τις ακόλουθες οικογένειες συνόλων:

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

Δεν είναι δύσκολο να ελέγξουμε ότι και οι 3 είναι κλειστές υπό την ένωση συνόλων. Επιπλέον, οι F_1, F_2 περιέχουν σύνολα με ακριβώς k στοιχεία, ενώ η 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), έχουμε 3 σύνολα στο F_2 με τουλάχιστον n-1 στοιχεία. Επειδή F_2 \subset F, παίρνοντας την ένωση αυτών των τριών συνόλων μαζί με ένα υποσύνολο της F που περιέχει το a, έχουμε δύο από τα τρία σύνολα που θέλουμε για την P(n,k). Αυτά τα δύο σύνολα προφανώς έχουν ένα κοινό στοιχείο b. Επαναλαμβάνουμε την διαδικασία με το στοιχείο b. Τότε είτε λαμβάνουμε τρία νέα σύνολα με τουλάχιστον n-1 στοιχεία, τα οποία δεν περιέχουν το b, και άρα η ένωσή τους μας δίνει το επιθυμητό τρίτο σύνολο για την P(n,k) ή πέφτουμε στην περίπτωση όπου η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή, την οποία και θα μελετήσουμε πιο κάτω.

Τώρα αν η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η P(n-1,k-1), έχουμε 3 σύνολα στην F_3 με τουλάχιστον n-1 στοιχεία. Η ένωση του κάθε ενός ξεχωριστά με το a ανήκει στην F, όλες αυτές οι ενώσεις είναι διακεκριμένες και έχουν τουλάχιστον n στοιχεία η κάθε μία. Άρα πάλι έχουμε την P(n, k).

Άρα για να δείξουμε την P(n, k) αρκεί να δείξουμε τις P(n-1,k) και P(n-1,k-1). Άρα είναι αρκετό να δείξουμε ότι οι P(m, m) και P(m, 1) είναι αληθείς για κάθε m.

Για την P(m, m), έχουμε δύο διακεκριμένα σύνολα με m στοιχεία το ένα, των οποίων η ένωση προφανώς περιέχει m+2 > m στοιχεία, άρα έχουμε 3 σύνολα με τουλάχιστον m στοιχεία και η πρόταση είναι αληθής.

Για την P(m, 1), έχουμε m+1 σύνολα με ένα στοιχείο το κάθε ένα, και μπορούν να πάρουμε την ένωση οποιονδήποτε m από αυτά ή όλων για να πάρουμε m+2 \geq 3 διακεκριμένα σύνολα με τουλάχιστον m στοιχεία το κάθε ένα και άρα η P(m, 1) είναι επίσης αληθείς.


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

Re: IMC 2016/1/4

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Σεπ 07, 2016 3:32 pm

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

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


Για μια οικογένεια συνόλων \mathcal{A} και ένα στοιχείο i ορίζω τα εξής:

Για 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) και D_i(C), με τουλάχιστον n στοιχεία το ίδιο ισχύει και για την \mathcal{A} θεωρώντας τα σύνολα A,B,C.

Ξεκινάμε λοιπόν από την \mathcal{F}. Αν η \mathcal{F} έχει ένα σύνολο A με m στοιχεία ώστε κάποιο από τα υποσύνολά του με 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} σύνολα με το πολύ k στοιχεία, η ένωση των συνόλων της \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} με τουλάχιστον n στοιχεία.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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