Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Συντονιστές: cretanman, ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ, socrates
- Al.Koutsouridis
- Δημοσιεύσεις: 1807
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
LXXIX Μαθηματική Ολυμπιάδα Μόσχας
13 Μαρτίου 2016, 9η τάξη.
Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .
Πρόβλημα 3. Ο Βασίλης έλαβε ως άσκηση για το σπίτι την εξίσωση , όπου ακέραιοι αριθμοί. Βρίσκοντας τις ρίζες της έγραψε μια νέα εξίσωση, την . Επανέλαβε αυτήν την διαδικασία άλλες τρεις φορές. Παρατήρησε ότι έλυσε τέσσερεις δευτεροβάθμιες εξισώσεις και καθεμιά τους είχε δυο διαφορετικές ακέραιες ρίζες (αν από τις δυο δυνατές εξισώσεις δυο διαφορετικές ρίζες έχει ακριβώς η μία, τότε πάντα διαλέγει αυτή, αν και οι δύο τότε οποιαδήποτε). Παρόλο που προσπάθησε πολύ ( ο Βασίλης είναι άριστος μαθητής), δεν μπόρεσε να γράψει πέμπτη εξίσωση, έτσι ώστε να έχει δυο διαφορετικές πραγματικές ρίζες. Ποια η εξίσωση που δόθηκε στον Βασίλη ως άσκηση;
Πρόβλημα 4. Δίνεται οξυγώνιο τρίγωνο και το κέντρο του περιγεγραμμένου κύκλου του. Ευθεία κάθετη στην πλευρά , τέμνει την πλευρά και την ευθεία στα σημεία και αντίστοιχα. Να αποδείξετε ότι τα σημεία και τα μέσα των τμημάτων και είναι ομοκυκλικά.
Πρόβλημα 5. Υπάρχει 2016-ψήφιος αριθμός, με αναδιάταξη των ψηφίων του οποίου μπορούμε να πάρουμε, 2016 διαφορετικά 2016-ψήφια τέλεια τετράγωνα;
Πρόβλημα 6. Στη χώρα των γλωσσολόγων υπάρχουν γλώσσες. Στην οποία κατοικούν άτομα, ο καθένας από τους οποίους γνωρίζει ακριβώς 3 γλώσσες και για διαφορετικά άτομα αυτή η τριάδα γλωσσών είναι διαφορετική. Είναι γνωστό ότι ο μέγιστος αριθμός ατόμων, οποιοιδήποτε δυο από τους οποίους μπορούν να συνομιλήσουν χωρίς μεταφραστή, ισούται με . Προέκυψε ότι . Να αποδείξετε ότι στη χώρα αυτή θα βρεθούν τουλάχιστον ζεύγη κατοίκων, οι οποίοι δε θα μπορέσουν να συνομιλήσουν χωρίς μεταφραστή.
Σημείωση: Σύμφωνα με την πηγή που είναι η επίσημη σελίδα της ολυμπιάδας εδώ. «Τα θέματα και οι λύσεις διατίθενται ελεύθερα για μη εμπορική χρήση (με επιθυμητή την αναφορά στην πηγή κατά την ανατύπωση)».
13 Μαρτίου 2016, 9η τάξη.
Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .
Πρόβλημα 3. Ο Βασίλης έλαβε ως άσκηση για το σπίτι την εξίσωση , όπου ακέραιοι αριθμοί. Βρίσκοντας τις ρίζες της έγραψε μια νέα εξίσωση, την . Επανέλαβε αυτήν την διαδικασία άλλες τρεις φορές. Παρατήρησε ότι έλυσε τέσσερεις δευτεροβάθμιες εξισώσεις και καθεμιά τους είχε δυο διαφορετικές ακέραιες ρίζες (αν από τις δυο δυνατές εξισώσεις δυο διαφορετικές ρίζες έχει ακριβώς η μία, τότε πάντα διαλέγει αυτή, αν και οι δύο τότε οποιαδήποτε). Παρόλο που προσπάθησε πολύ ( ο Βασίλης είναι άριστος μαθητής), δεν μπόρεσε να γράψει πέμπτη εξίσωση, έτσι ώστε να έχει δυο διαφορετικές πραγματικές ρίζες. Ποια η εξίσωση που δόθηκε στον Βασίλη ως άσκηση;
Πρόβλημα 4. Δίνεται οξυγώνιο τρίγωνο και το κέντρο του περιγεγραμμένου κύκλου του. Ευθεία κάθετη στην πλευρά , τέμνει την πλευρά και την ευθεία στα σημεία και αντίστοιχα. Να αποδείξετε ότι τα σημεία και τα μέσα των τμημάτων και είναι ομοκυκλικά.
Πρόβλημα 5. Υπάρχει 2016-ψήφιος αριθμός, με αναδιάταξη των ψηφίων του οποίου μπορούμε να πάρουμε, 2016 διαφορετικά 2016-ψήφια τέλεια τετράγωνα;
Πρόβλημα 6. Στη χώρα των γλωσσολόγων υπάρχουν γλώσσες. Στην οποία κατοικούν άτομα, ο καθένας από τους οποίους γνωρίζει ακριβώς 3 γλώσσες και για διαφορετικά άτομα αυτή η τριάδα γλωσσών είναι διαφορετική. Είναι γνωστό ότι ο μέγιστος αριθμός ατόμων, οποιοιδήποτε δυο από τους οποίους μπορούν να συνομιλήσουν χωρίς μεταφραστή, ισούται με . Προέκυψε ότι . Να αποδείξετε ότι στη χώρα αυτή θα βρεθούν τουλάχιστον ζεύγη κατοίκων, οι οποίοι δε θα μπορέσουν να συνομιλήσουν χωρίς μεταφραστή.
Σημείωση: Σύμφωνα με την πηγή που είναι η επίσημη σελίδα της ολυμπιάδας εδώ. «Τα θέματα και οι λύσεις διατίθενται ελεύθερα για μη εμπορική χρήση (με επιθυμητή την αναφορά στην πηγή κατά την ανατύπωση)».
τελευταία επεξεργασία από Al.Koutsouridis σε Κυρ Ιουν 25, 2017 11:41 am, έχει επεξεργασθεί 6 φορές συνολικά.
Λέξεις Κλειδιά:
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Ωραία, η εκφώνηση διορθώθηκε ακριβώς όπως είχα υποθέσει ότι έπρεπε να είναι!Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας
13 Μαρτίου 2016, 9η τάξη.
Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .
Το σχήμα τα λέει όλα, θα προσθέσω όμως κάποια λόγια το απόγευμα.
Προσθέτω τα λόγια.
Από το φέρνω παράλληλη στην που τέμνει την από το κάθετη στην στο .
Εύκολα συνάγουμε ότι μεσοκάθετη στην και ότι ισόπλευρο και επειδή παραλληλόγραμμο
Από και : που είναι το ζητούμενο.
edit: Πρόσθεσα τα λόγια.
τελευταία επεξεργασία από ealexiou σε Σάβ Απρ 16, 2016 6:51 pm, έχει επεξεργασθεί 2 φορές συνολικά.
- george visvikis
- Επιμελητής
- Δημοσιεύσεις: 13298
- Εγγραφή: Παρ Νοέμ 01, 2013 9:35 am
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Καλησπέρα!Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας
13 Μαρτίου 2016, 9η τάξη.
Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .
Επί της θεωρώ σημείο , ώστε , οπότε το τρίγωνο είναι ισόπλευρο. Τα τρίγωνα είναι ίσα
γιατί έχουν: και . Άρα
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Ναι, υπάρχει!Al.Koutsouridis έγραψε: Πρόβλημα 5. Υπάρχει 2016-ψήφιος αριθμός, με αναδιάταξη των ψηφίων του οποίου μπορούμε να πάρουμε, 2016 διαφορετικά 2016-ψήφια τέλεια τετράγωνα;
Σε κάθε -ψήφιο αριθμό αντιστοιχούμε το διάνυσμα όπου ο ισούται με το πλήθος των ψηφίων του αριθμού που ισούνται με .
Επειδή οι είναι μη αρνητικοί ακέραιοι με , υπάρχουν
διαφορετικά διανύσματα.
Από την άλλη υπάρχουν τουλάχιστον
τέλεια τετράγωνα με ψηφία.
Οπότε θα υπάρχουν τουλάχιστον τέλεια τετράγωνα στα οποία αντιστοιχεί το ίδιο διάνυσμα. Όλα αυτά τα τέλεια τετράγωνα είναι ασφαλώς περισσότερα από και προκύπτουν από αναδιάταξη του ίδιου -ψήφιου αριθμού οπότε ο ισχυρισμός αποδείχθηκε.
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Αν και οι τρείς είναι μικρότεροι τις μονάδος έχουμε ......(1) και ......(2).Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας
13 Μαρτίου 2016, 9η τάξη.
Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
Η (2) γράφεται και από την (1) έχουμε και συνεπώς άτοπο
Αν δύο είναι μικρότεροι τις μονάδος έχουμε ......(3) και ......(2).
Ομοίως η (2) γράφεται και από την (3) έχουμε και συνεπώς άτοπο
Αρα δύο τουλάχιστον πρέπει να είναι μεγαλύτεροι της μονάδος.
''Οσοι σου λένε δεν μπορείς, είναι πιθανότατα αυτοί, που φοβούνται μήπως τα καταφέρεις''
Νίκος Καζαντζάκης
Νίκος Καζαντζάκης
-
- Επιμελητής
- Δημοσιεύσεις: 15767
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του .Al.Koutsouridis έγραψε: Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
(Υπόψη το .. δεν βελτιώνεται σε .. όπως βλέπουμε από το παράδειγμα )
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Υπάρχει οξυγώνιο τρίγωνο ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστονMihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του .
Σιλουανός Μπραζιτίκος
-
- Επιμελητής
- Δημοσιεύσεις: 15767
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Ακριβώς αυτό είχα κατά νου. Έβαλα την βελτιωμένη εκδοχή της άσκησης γιατί η αρχική μου φάνηκε πολλή απλή για τέτοιο διαγωνισμό.smar έγραψε:Υπάρχει οξυγώνιο τρίγωνο ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστονMihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του .
- Al.Koutsouridis
- Δημοσιεύσεις: 1807
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Με αφορμή την περαιτέρω έρευνα του προβλήματος από τον κ.Λάμπρου απλά να παραθέσω το πνεύμα του διαγωνισμού (αλλά και όλων των διαγωνισμών γενικότερα) κατά τους διοργανωτές.Mihalis_Lambrou έγραψε:Ακριβώς αυτό είχα κατά νου. Έβαλα την βελτιωμένη εκδοχή της άσκησης γιατί η αρχική μου φάνηκε πολλή απλή για τέτοιο διαγωνισμό.smar έγραψε:Υπάρχει οξυγώνιο τρίγωνο ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστονMihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του .
"Τα προβλήματα της μαθηματικής ολυμπιάδας της Μόσχας επιλέγονται έτσι ώστε, για την λύση τους να μην απαιτούνται ειδικές γνώσεις, που να υπερβαίνουν τα παραδοσιακά πλαίσια του προγράμματος σπουδών των σχολείων. Παράλληλα τα προβλήματα αυτά δεν αποσκοπούν μόνο στο να ελέγξουν την επίδοση (πρόοδο) των μαθητών αλλά δίνουν την δυνατότητα στους μαθητές να συμμετάσχουν (ενταχθούν) στην πραγματική (ρεαλιστική) επιστήμη, να λύσουν διασκεδαστικά προβλήματα, τα οποία μπορούν να προκαλέσουν το ενδιαφέρον για περαιτέρω έρευνα, σε βαθύτερη μελέτη των μαθηματικών."
Αυτή η συζήτηση και μελέτη, μετά τον εκάστοτε διαγωνισμό, είναι το ζουμί και το επικοδομητικό στην γενικότερη διαδικασία.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Μια διαφορετική απόδειξη της γενίκευσης του Μιχάλη:
Έχουμε . Οπότε παίρνουμε . Άρα κάποιο από τα είναι μεγαλύτερο ή ίσο του αφού σε αντίθετη περίπτωση θα είχαμε .
Το άλλο κομμάτι έχει ήδη αποδειχθεί αλλά το κάνω λίγο διαφορετικά. Αν έχουμε δύο μικρότερους του , έστω τους και , τότε είναι , άτοπο.
Έχουμε . Οπότε παίρνουμε . Άρα κάποιο από τα είναι μεγαλύτερο ή ίσο του αφού σε αντίθετη περίπτωση θα είχαμε .
Το άλλο κομμάτι έχει ήδη αποδειχθεί αλλά το κάνω λίγο διαφορετικά. Αν έχουμε δύο μικρότερους του , έστω τους και , τότε είναι , άτοπο.
-
- Επιμελητής
- Δημοσιεύσεις: 15767
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Και αλλιώς: Αν οι δύο μεγαλύτεροι, τότε για τον τρίτο είναι υποχρεωτικά .Mihalis_Lambrou έγραψε:Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του .Al.Koutsouridis έγραψε: Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
Αν τότε , οπότε , άτοπο.
- emouroukos
- Συντονιστής
- Δημοσιεύσεις: 1447
- Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
- Τοποθεσία: Αγρίνιο
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Έστω και τα μέσα των τμημάτων και αντίστοιχα. Ζητείται να αποδειχθεί ότι το τετράπλευρο είναι εγγράψιμο.Al.Koutsouridis έγραψε: Πρόβλημα 4. Δίνεται οξυγώνιο τρίγωνο και το κέντρο του περιγεγραμμένου κύκλου του. Ευθεία κάθετη στην πλευρά , τέμνει την πλευρά και την ευθεία στα σημεία και αντίστοιχα. Να αποδείξετε ότι τα σημεία και τα μέσα των τμημάτων και είναι ομοκυκλικά.
Αρκεί να αποδείξουμε ότι
Έστω και τα μέσα των τμημάτων και αντίστοιχα. Αρκεί να αποδείξουμε ότι τα (ορθογώνια) τρίγωνα και είναι όμοια. Εμομένως, αρκεί να αποδείξουμε ότι
Παρατηρούμε ότι:
και
οπότε
Έτσι, αρκεί να δείξουμε ότι δηλαδή αρκεί να δείξουμε ότι τα τρίγωνα και είναι όμοια. Αυτό, όμως, προκύπτει από τις ισότητες γωνιών
και
οπότε η απόδειξη ολοκληρώνεται.
Βαγγέλης Μουρούκος
Erro ergo sum.
Erro ergo sum.
- Al.Koutsouridis
- Δημοσιεύσεις: 1807
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Έγιναν διορθώσεις στην διατύπωση του 3 προβλήματος στην αρχική ανάρτηση έπειτα από τις εύστοχες επισημάνσεις του Βαγγέλη Μουρούκου.
- emouroukos
- Συντονιστής
- Δημοσιεύσεις: 1447
- Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
- Τοποθεσία: Αγρίνιο
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Η πέμπτη εξίσωση που προσπάθησε να γράψει ο Βασίλης θα έχει τη μορφήAl.Koutsouridis έγραψε:
Πρόβλημα 3. Ο Βασίλης έλαβε ως άσκηση για το σπίτι την εξίσωση , όπου ακέραιοι αριθμοί. Βρίσκοντας τις ρίζες της έγραψε μια νέα εξίσωση, την . Επανέλαβε αυτήν την διαδικασία άλλες τρεις φορές. Παρατήρησε ότι έλυσε τέσσερεις δευτεροβάθμιες εξισώσεις και καθεμιά τους είχε δυο διαφορετικές ακέραιες ρίζες (αν από τις δυο δυνατές εξισώσεις δυο διαφορετικές ρίζες έχει ακριβώς η μία, τότε πάντα διαλέγει αυτή, αν και οι δύο τότε οποιαδήποτε). Παρόλο που προσπάθησε πολύ ( ο Βασίλης είναι άριστος μαθητής), δεν μπόρεσε να γράψει πέμπτη εξίσωση, έτσι ώστε να έχει δυο διαφορετικές πραγματικές ρίζες. Ποια η εξίσωση που δόθηκε στον Βασίλη ως άσκηση;
ή
όπου οι (διαφορετικές μεταξύ τους) ακέραιες ρίζες της τέταρτης εξίσωσης.
Επειδή η πέμπτη εξίσωση δεν έχει δύο διαφορετικές πραγματικές ρίζες, θα πρέπει να ισχύουν οι ανισότητες
και
από τις οποίες προκύπτει ότι
και
Παρατηρούμε ότι αν τότε πράγμα άτοπο. Επομένως, είναι και οπότε
και όμοια
Εύκολα ελέγχουμε ότι τα μοναδικά ζεύγη που ικανοποιούν τις σχέσεις και είναι τα
και
Επομένως, η τέταρτη εξίσωση που έγραψε ο Βασίλης είναι η η τρίτη είναι η η δεύτερη είναι η και η πρώτη είναι η .
Σημείωση: Είναι άξια θαυμασμού η ευρηματικότητα των ανθρώπων που κατασκευάζουν τέτοια (κατά τη γνώμη μου) πανέμορφα προβλήματα, τα οποία μπορούν να λυθούν με ελάχιστες προαπαιτούμενες γνώσεις. Αντίθετα, κάποιοι άλλοι σκιαμαχούν για το τι είναι "εντός" και τι "εκτός ύλης" και πώς αυτό θα βαθμολογηθεί στις εξετάσεις, θυμίζοντας τους Γραμματείς που προσπαθούν να ερμηνεύσουν τις λεπτές αποχρώσεις των νόμων του Ταλμούδ...
Βαγγέλης Μουρούκος
Erro ergo sum.
Erro ergo sum.
- Al.Koutsouridis
- Δημοσιεύσεις: 1807
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)
Μεταφέρω την επίσημη λύση και το σχόλιο που συνοδεύει αυτό το πρόβλημα. Για την ιστόρία δυσκόλεψε πιρισσότερο από όλα τους συμμετέχοντες της 9ης τάξης, καθώς το έλυσαν 2 (+) σε σύνολο 890 μαθητών.Al.Koutsouridis έγραψε: ↑Σάβ Απρ 16, 2016 3:14 pmLXXIX Μαθηματική Ολυμπιάδα Μόσχας
Πρόβλημα 6. Στη χώρα των γλωσσολόγων υπάρχουν γλώσσες. Στην οποία κατοικούν άτομα, ο καθένας από τους οποίους γνωρίζει ακριβώς 3 γλώσσες και για διαφορετικά άτομα αυτή η τριάδα γλωσσών είναι διαφορετική. Είναι γνωστό ότι ο μέγιστος αριθμός ατόμων, οποιοιδήποτε δυο από τους οποίους μπορούν να συνομιλήσουν χωρίς μεταφραστή, ισούται με . Προέκυψε ότι . Να αποδείξετε ότι στη χώρα αυτή θα βρεθούν τουλάχιστον ζεύγη κατοίκων, οι οποίοι δε θα μπορέσουν να συνομιλήσουν χωρίς μεταφραστή.
Λύση. Θα συμβολίσουμε με το σύνολο ατόμων, οι οποίοι μπορούν να συνομιλήσουν χωρίς μεταφραστές. Εξετάζουμε ένα τυχαία άτομο (τον κύριο ), που δεν εμπίπτει στο σύνολο . Για αυτόν υπάρχει ένα τέτοιο άτομο του συνόλου (ο κύριος ), ώστε η ένωση των γλωσσών τους να είναι κενό σύνολο. Θα εκτιμήσουμε το πλήθος εκείνων των ατόμων του συνόλου , τα οποία μπορούν να συνομιλήσουν με τον κύριο . Τέτοια άτομα έχουν τουλάχιστον μια κοινή γλώσσα και με τον κύριο και με τον κύριο (καθώς εμπίπτουν στο σύνολο ), άρα δεν είναι παραπάνω από . Με αυτό το τρόπο, για κάθε άτομο, που δεν εμπίπτει στο σύνολο , βρήκαμε τουλάχιστον αντιπροσώπους του συνόλου , οι οποίοι δεν μπορούν να συνομιλήσουν μαζί τους χωρίς μεταφραστή. Οπότε στο σύνολο τέτοια ζεύγη θα είναι
.
Σχόλιο. Το πρόβλημα σχετίζεται με ένα καθόλα γνωστό και σημαντικό τομέα της σύγχρονης θεωρίας γράφων. Και συγκεκριμένα, ένας γράφος ονομάζεται γράφος Κνέσερ( Kneser), αν οι κορυφές του είναι όλα τα δυνατά υποσύνολα δύναμης του συνόλου και ακμές του, ζεύγη μη τεμνόμενων υποσυνόλων. Για τους γράφους Κνέσερ υπάρχει «δημοφιλής» (εκλαϊκευμένη) βιβλιογραφία: Βλ. [1], [2]. Στο πρόβλημα 6 έχουμε να κάνουμε με ένα γράφο Κνέσερ, στον οποίο . Κάθε κορυφή του είναι μια τριάδα γλωσσών (ή αν θέλετε, γλωσσολόγος, που ξέρει αυτές τις τρεις γλώσσες). Δυο κορυφές ενώνονται με ακμή, αν οι αντίστοιχοι γλωσσολόγοι δεν μπορούν συνομιλήσουν χωρίς μεταφραστή. Θυμίζουμε, ότι ένα σύνολο κορυφών ενός γράφου ονομάζεται ανεξάρτητο, αν οποιεσδήποτε δυο κορυφές σε αυτό δεν ενώνονται με ακμή. Η δύναμη του μεγαλύτερου ανεξάρτητου υποσυνόλου κορυφών ενός γράφου ονομάζεται αριθμός ανεξαρτησίας και συμβολίζεται με . Με αυτούς τους όρους το πρόβλημα 6 διατυπώνεται ως: «έστω ότι δίνεται ένας υπογράφος ενός γράφου Κνέσερ με και κορυφές, εξάλλου και . Να αποδείξετε τότε, ότι ο αριθμός ακμών του γράφου είναι τουλάχιστον ».
Το πρόβλημα σε τέτοια διατύπωση μη τετριμμένα χρησιμοποιεί ακριβώς την δομή ενός γράφου Κνέσερ. Το γεγονός είναι ότι υπάρχει το κλασικό θεώρημα του Τουράν: αν γράφος με κορυφές έχει βαθμό ανεξαρτησίας , τότε έχει «περίπου» ακμές ή περισσότερες. Στην περίπτωσή μας αυτή η εκτίμηση έχει το μέγεθος της τάξης του , καθόλα διαφορετικό του και αυτό είναι πολύ σημαντικό.
Να σημειώσουμε ότι ο αριθμός ανεξαρτησίας όλου του γράφου Κνέσερ είναι ίσος με , αν . Αυτό είναι το γνωστό θεώρημα Έρντος-Κο-Ραντό, την απόδειξη του οποίου για παράδειγμα μπορείτε να διαβάσετε στο [3]. Το πρόβλημα 6 προέκυψε κατά την στιγμή, που ο θεματοδότης και οι μαθητές του μπόρεσαν να δείξουν ότι σε τυχαίο υπογράφο ενός γράφου Κνέσερ ο αριθμός ανεξαρτησίας, αντίθετα με την διαίσθηση, σχεδόν δεν αλλάζει (βλ. [4]). Τώρα από αυτό έχει προκύψει σημαντικό επιστημονικό έργο, που επιτρέπει με νέα ματιά να κοιτάξουμε σε κλασικά αποτελέσματα της συνδυαστικής ακροτάτων (extremal combinatorics) βλ. [5].
Να σημειώσουμε επίσης ότι η εκτίμηση στο πρόβλημα 6 μακράν δεν είναι η βέλτιστη. Μπορεί να βελτιωθεί, αποδεικνύοντας το ακόλουθο αποτέλεσμα: «Στις συνθήκες του προβλήματος 6 τα μέγιστα ανεξάρτητα σύνολα αναγκαστικά θα αποτελούνται από κορυφές, οι οποίες όλες θα περιέχουν το ίδιο κοινό στοιχείο του συνόλου .» Προσπαθήστε να το αποδείξετε! Σε ποιο γενική μορφή ονομάζεται θεώρημα Χίλτον-Μίλνερ (βλ. [3]).
[1] А. М. Райгородский. Гипотеза Кнезера и топологические методы в комбинаторике // «Квант», №1 (2011), 7—16. (Υπόθεση Κνέσερ και τοπολογικές μέθοδου στην συνδυαστική, κβαντ ν1, 2011)
[2] А. М. Райгородский. Гипотеза Кнезера и топологический метод в комбинаторике. М: МЦНМО, 2011.(Υπόθεση Κνέσερ και τοπολογικές μέθοδου στην συνδυαστική)
[3] А. М. Райгородский. Вероятность и алгебра в комбинаторике. М: МЦНМО, 2015. (Πιθανότητες και άλγεβρα στην συνδυαστική)
[4] Л. И. Боголюбский, А. С. Гусев, М. М. Пядёркин, А. М. Райгородский. Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов. Математический сборник, 206 (2015), №10, 3—36. (αριθμοί ανεξαρτησίας και χρωματικοί αριθμοί τυχαίων υπογράφων μερικών γράφων αποστάσεων)
[5] B. Bollobas, B. P. Narayanan, A. M. Raigorodskii. On the stability of the Erdos—Ko—Rado theorem // J. Comb. Th. Ser. A, 137 (2016), 64—78
Υγ. Διάφοροι σύνδεσμοι στο κείμενο τοποθετήθηκαν από μένα.
Πηγή
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 8 επισκέπτες