IMC 2016/1/4
Συντονιστής: Demetres
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
IMC 2016/1/4
Έστω θετικοί ακέραιοι και έστω οικογένεια πεπερασμένων συνόλων με τις εξής ιδιότητες:
(α) H περιέχει τουλάχιστον διακεκριμένα σύνολα με ακριβώς στοιχεία.
(β) Για κάθε δύο σύνολα έχουμε .
Να δειχθεί ότι η περιέχει τουλάχιστον τρία σύνολα με τουλάχιστον στοιχεία.
(α) H περιέχει τουλάχιστον διακεκριμένα σύνολα με ακριβώς στοιχεία.
(β) Για κάθε δύο σύνολα έχουμε .
Να δειχθεί ότι η περιέχει τουλάχιστον τρία σύνολα με τουλάχιστον στοιχεία.
Λέξεις Κλειδιά:
Re: IMC 2016/1/4
Έχω βάλει λύση στα Αγγλικά εδώ: http://www.artofproblemsolving.com/comm ... 83p6722154
Αν θέλει κάποιος μπορεί να τη μεταφέρει.
ΥΓ: Είναι καλό πρόβλημα για 4ο καθώς έχει και πολλές παγίδες. Όπως είχα συνηθίσει το διαγωνισμό παλιότερα, σε τέτοιο επίπεδο θα έπρεπε να ήταν και τα 3άρια, και ένα από τα 2 2άρια.
Αν θέλει κάποιος μπορεί να τη μεταφέρει.
ΥΓ: Είναι καλό πρόβλημα για 4ο καθώς έχει και πολλές παγίδες. Όπως είχα συνηθίσει το διαγωνισμό παλιότερα, σε τέτοιο επίπεδο θα έπρεπε να ήταν και τα 3άρια, και ένα από τα 2 2άρια.
Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: IMC 2016/1/4
Ας μεταφέρω λοιπόν την λύση του Νίκου:
Παίρνουμε την ένωση όλων των συνόλων . Έστω ένα στοιχείο του . Θεωρούμε τις ακόλουθες οικογένειες συνόλων:
Δεν είναι δύσκολο να ελέγξουμε ότι και οι είναι κλειστές υπό την ένωση συνόλων. Επιπλέον, οι περιέχουν σύνολα με ακριβώς στοιχεία, ενώ η περιέχει σύνολα με ακριβώς στοιχεία. Τέλος είναι και
Αν ονομάσουμε την προς απόδειξη πρόταση, τότε αν και προσθέτοντας λαμβάνουμε
άτοπο.
Άρα τουλάχιστον μία από τις ανισότητες πρέπει να είναι αντίστροφη και αυστηρή.
Αν η πρώτη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η , έχουμε σύνολα στο με τουλάχιστον στοιχεία. Επειδή , παίρνοντας την ένωση αυτών των τριών συνόλων μαζί με ένα υποσύνολο της που περιέχει το , έχουμε δύο από τα τρία σύνολα που θέλουμε για την . Αυτά τα δύο σύνολα προφανώς έχουν ένα κοινό στοιχείο . Επαναλαμβάνουμε την διαδικασία με το στοιχείο . Τότε είτε λαμβάνουμε τρία νέα σύνολα με τουλάχιστον στοιχεία, τα οποία δεν περιέχουν το , και άρα η ένωσή τους μας δίνει το επιθυμητό τρίτο σύνολο για την ή πέφτουμε στην περίπτωση όπου η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή, την οποία και θα μελετήσουμε πιο κάτω.
Τώρα αν η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η , έχουμε σύνολα στην με τουλάχιστον στοιχεία. Η ένωση του κάθε ενός ξεχωριστά με το ανήκει στην , όλες αυτές οι ενώσεις είναι διακεκριμένες και έχουν τουλάχιστον στοιχεία η κάθε μία. Άρα πάλι έχουμε την .
Άρα για να δείξουμε την αρκεί να δείξουμε τις και . Άρα είναι αρκετό να δείξουμε ότι οι και είναι αληθείς για κάθε .
Για την , έχουμε δύο διακεκριμένα σύνολα με στοιχεία το ένα, των οποίων η ένωση προφανώς περιέχει στοιχεία, άρα έχουμε σύνολα με τουλάχιστον στοιχεία και η πρόταση είναι αληθής.
Για την , έχουμε σύνολα με ένα στοιχείο το κάθε ένα, και μπορούν να πάρουμε την ένωση οποιονδήποτε από αυτά ή όλων για να πάρουμε διακεκριμένα σύνολα με τουλάχιστον στοιχεία το κάθε ένα και άρα η είναι επίσης αληθείς.
Παίρνουμε την ένωση όλων των συνόλων . Έστω ένα στοιχείο του . Θεωρούμε τις ακόλουθες οικογένειες συνόλων:
Δεν είναι δύσκολο να ελέγξουμε ότι και οι είναι κλειστές υπό την ένωση συνόλων. Επιπλέον, οι περιέχουν σύνολα με ακριβώς στοιχεία, ενώ η περιέχει σύνολα με ακριβώς στοιχεία. Τέλος είναι και
Αν ονομάσουμε την προς απόδειξη πρόταση, τότε αν και προσθέτοντας λαμβάνουμε
άτοπο.
Άρα τουλάχιστον μία από τις ανισότητες πρέπει να είναι αντίστροφη και αυστηρή.
Αν η πρώτη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η , έχουμε σύνολα στο με τουλάχιστον στοιχεία. Επειδή , παίρνοντας την ένωση αυτών των τριών συνόλων μαζί με ένα υποσύνολο της που περιέχει το , έχουμε δύο από τα τρία σύνολα που θέλουμε για την . Αυτά τα δύο σύνολα προφανώς έχουν ένα κοινό στοιχείο . Επαναλαμβάνουμε την διαδικασία με το στοιχείο . Τότε είτε λαμβάνουμε τρία νέα σύνολα με τουλάχιστον στοιχεία, τα οποία δεν περιέχουν το , και άρα η ένωσή τους μας δίνει το επιθυμητό τρίτο σύνολο για την ή πέφτουμε στην περίπτωση όπου η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή, την οποία και θα μελετήσουμε πιο κάτω.
Τώρα αν η δεύτερη ανισότητα είναι αντίστροφη και αυστηρή και ισχύει η , έχουμε σύνολα στην με τουλάχιστον στοιχεία. Η ένωση του κάθε ενός ξεχωριστά με το ανήκει στην , όλες αυτές οι ενώσεις είναι διακεκριμένες και έχουν τουλάχιστον στοιχεία η κάθε μία. Άρα πάλι έχουμε την .
Άρα για να δείξουμε την αρκεί να δείξουμε τις και . Άρα είναι αρκετό να δείξουμε ότι οι και είναι αληθείς για κάθε .
Για την , έχουμε δύο διακεκριμένα σύνολα με στοιχεία το ένα, των οποίων η ένωση προφανώς περιέχει στοιχεία, άρα έχουμε σύνολα με τουλάχιστον στοιχεία και η πρόταση είναι αληθής.
Για την , έχουμε σύνολα με ένα στοιχείο το κάθε ένα, και μπορούν να πάρουμε την ένωση οποιονδήποτε από αυτά ή όλων για να πάρουμε διακεκριμένα σύνολα με τουλάχιστον στοιχεία το κάθε ένα και άρα η είναι επίσης αληθείς.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: IMC 2016/1/4
Βάζω και την δική μου απόδειξη. Θα αποδείξω κάτι πιο ισχυρό αλλάζοντας την συνθήκη (α) στην
(α') H περιέχει τουλάχιστον διακεκριμένα σύνολα με το πολύ στοιχεία.
Για μια οικογένεια συνόλων και ένα στοιχείο ορίζω τα εξής:
Για ορίζω αν ή αν . Αλλιώς ορίζω .
Ορίζω επίσης
Είναι απλό ότι η είναι 1 προς 1 στην . Είναι επίσης απλό ότι αν η ικανοποιεί τις (α') και (β) το ίδιο ισχύει και για την . Τέλος αν η έχει τρία διακεκριμένα σύνολα, έστω τα και , με τουλάχιστον στοιχεία το ίδιο ισχύει και για την θεωρώντας τα σύνολα .
Ξεκινάμε λοιπόν από την . Αν η έχει ένα σύνολο με στοιχεία ώστε κάποιο από τα υποσύνολά του με στοιχεία να μην ανήκει στη , έστω το , τότε αντί με την εργαζόμαστε με την και αρκεί να αποδείξουμε το ζητούμενο για αυτήν.
Επαναλαμβάνοντας την διαδικασία, μπορούμε να υποθέσουμε ότι αν και , τότε είναι και . [Η διαδικασία τελειώνει επειδή κάθε φορά μειώνεται αυστηρά το άθροισμα των πληθικών αριθμών των συνόλων της οικογενείας.]
Επειδή τώρα η έχει τουλάχιστον σύνολα με το πολύ στοιχεία, η ένωση των συνόλων της θα περιέχει τουλάχιστον στοιχεία.
Χωρίς βλάβη της γενικότητας λοιπόν έχουμε . Τότε όμως τα και είναι τρία διακεκριμένα σύνολα της με τουλάχιστον στοιχεία.
(α') H περιέχει τουλάχιστον διακεκριμένα σύνολα με το πολύ στοιχεία.
Για μια οικογένεια συνόλων και ένα στοιχείο ορίζω τα εξής:
Για ορίζω αν ή αν . Αλλιώς ορίζω .
Ορίζω επίσης
Είναι απλό ότι η είναι 1 προς 1 στην . Είναι επίσης απλό ότι αν η ικανοποιεί τις (α') και (β) το ίδιο ισχύει και για την . Τέλος αν η έχει τρία διακεκριμένα σύνολα, έστω τα και , με τουλάχιστον στοιχεία το ίδιο ισχύει και για την θεωρώντας τα σύνολα .
Ξεκινάμε λοιπόν από την . Αν η έχει ένα σύνολο με στοιχεία ώστε κάποιο από τα υποσύνολά του με στοιχεία να μην ανήκει στη , έστω το , τότε αντί με την εργαζόμαστε με την και αρκεί να αποδείξουμε το ζητούμενο για αυτήν.
Επαναλαμβάνοντας την διαδικασία, μπορούμε να υποθέσουμε ότι αν και , τότε είναι και . [Η διαδικασία τελειώνει επειδή κάθε φορά μειώνεται αυστηρά το άθροισμα των πληθικών αριθμών των συνόλων της οικογενείας.]
Επειδή τώρα η έχει τουλάχιστον σύνολα με το πολύ στοιχεία, η ένωση των συνόλων της θα περιέχει τουλάχιστον στοιχεία.
Χωρίς βλάβη της γενικότητας λοιπόν έχουμε . Τότε όμως τα και είναι τρία διακεκριμένα σύνολα της με τουλάχιστον στοιχεία.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 4 επισκέπτες