Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Al.Koutsouridis · #1

LXXIX Μαθηματική Ολυμπιάδα Μόσχας

13 Μαρτίου 2016, 9η τάξη.

Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.

Πρόβλημα 2. Στο τρίγωνο ABC

και στην προέκταση της διαμέσου

, προς το

, θεωρούμε σημείο

τέτοιο, ώστε AM = CK

. Αν η γωνία BMC

είναι ίση με 60^0

να δείξετε, ότι AC=BK

.

Πρόβλημα 3. Ο Βασίλης έλαβε ως άσκηση για το σπίτι την εξίσωση $x^2+p_{1}x+q_{1} = 0$ , όπου $p_{1}, q_{1}$ ακέραιοι αριθμοί. Βρίσκοντας τις ρίζες της $p_{2}, q_{2}$ έγραψε μια νέα εξίσωση, την $x^2+p_{2}x+q_{2} = 0$ . Επανέλαβε αυτήν την διαδικασία άλλες τρεις φορές. Παρατήρησε ότι έλυσε τέσσερεις δευτεροβάθμιες εξισώσεις και καθεμιά τους είχε δυο διαφορετικές ακέραιες ρίζες (αν από τις δυο δυνατές εξισώσεις δυο διαφορετικές ρίζες έχει ακριβώς η μία, τότε πάντα διαλέγει αυτή, αν και οι δύο τότε οποιαδήποτε). Παρόλο που προσπάθησε πολύ ( ο Βασίλης είναι άριστος μαθητής), δεν μπόρεσε να γράψει πέμπτη εξίσωση, έτσι ώστε να έχει δυο διαφορετικές πραγματικές ρίζες. Ποια η εξίσωση που δόθηκε στον Βασίλη ως άσκηση;

Πρόβλημα 4. Δίνεται οξυγώνιο τρίγωνο ABC

και το κέντρο

του περιγεγραμμένου κύκλου του. Ευθεία κάθετη στην πλευρά

, τέμνει την πλευρά

και την ευθεία

στα σημεία

και

αντίστοιχα. Να αποδείξετε ότι τα σημεία B , O

και τα μέσα των τμημάτων

και

είναι ομοκυκλικά.

Πρόβλημα 5. Υπάρχει 2016-ψήφιος αριθμός, με αναδιάταξη των ψηφίων του οποίου μπορούμε να πάρουμε, 2016 διαφορετικά 2016-ψήφια τέλεια τετράγωνα;

Πρόβλημα 6. Στη χώρα των γλωσσολόγων υπάρχουν

γλώσσες. Στην οποία κατοικούν

άτομα, ο καθένας από τους οποίους γνωρίζει ακριβώς 3 γλώσσες και για διαφορετικά άτομα αυτή η τριάδα γλωσσών είναι διαφορετική. Είναι γνωστό ότι ο μέγιστος αριθμός ατόμων, οποιοιδήποτε δυο από τους οποίους μπορούν να συνομιλήσουν χωρίς μεταφραστή, ισούται με

. Προέκυψε ότι $11n \leq k \leq \dfrac{m}{2}$ . Να αποδείξετε ότι στη χώρα αυτή θα βρεθούν τουλάχιστον

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

Σημείωση: Σύμφωνα με την πηγή που είναι η επίσημη σελίδα της ολυμπιάδας εδώ. «Τα θέματα και οι λύσεις διατίθενται ελεύθερα για μη εμπορική χρήση (με επιθυμητή την αναφορά στην πηγή κατά την ανατύπωση)».

ealexiou · #2

Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας

13 Μαρτίου 2016, 9η τάξη.

Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .

Ωραία, η εκφώνηση διορθώθηκε ακριβώς όπως είχα υποθέσει ότι έπρεπε να είναι!

: Μαθηματική Ολυμπιάδα Μοσχας 2016 (9η) πρ. 2.png (22.53 KiB) Προβλήθηκε 2703 φορές

Το σχήμα τα λέει όλα, θα προσθέσω όμως κάποια λόγια το απόγευμα.

Προσθέτω τα λόγια.
Από το

φέρνω παράλληλη στην

που τέμνει την από το

κάθετη στην

στο

.
Εύκολα συνάγουμε ότι

μεσοκάθετη στην $BZ\Rightarrow \boxed{BK=ZK}\ (1)$ και ότι $\triangle AMZ$ ισόπλευρο $\Rightarrow \boxed{AZ=AM=CK}$ και επειδή $AZ//=CK \Rightarrow AZKC$ παραλληλόγραμμο $\Rightarrow \boxed{AC=ZK}\ (2)$

Από (1)

και

: $\boxed{\boxed{AC=BK}}$ που είναι το ζητούμενο.

edit: Πρόσθεσα τα λόγια.

#3

Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας

13 Μαρτίου 2016, 9η τάξη.

Πρόβλημα 2. Στο τρίγωνο και στην προέκταση της διαμέσου , προς το , θεωρούμε σημείο τέτοιο, ώστε . Αν η γωνία είναι ίση με να δείξετε, ότι .

Καλησπέρα!

: Μ.Ο.Μ 2016 (9η τάξη).png (13.43 KiB) Προβλήθηκε 2701 φορές

Επί της

θεωρώ σημείο

, ώστε

, οπότε το τρίγωνο MBN

είναι ισόπλευρο. Τα τρίγωνα AMC, BNK

είναι ίσα

γιατί έχουν: $AM=BN, \widehat{AMC}=\widehat{BNK}=120^0$ και $\displaystyle{MC = MN + NC = NC + CK = NK}$ . Άρα $\boxed{AC=BK}$

#4

Al.Koutsouridis έγραψε: Πρόβλημα 5. Υπάρχει 2016-ψήφιος αριθμός, με αναδιάταξη των ψηφίων του οποίου μπορούμε να πάρουμε, 2016 διαφορετικά 2016-ψήφια τέλεια τετράγωνα;

Ναι, υπάρχει!

Σε κάθε 2016

-ψήφιο αριθμό αντιστοιχούμε το διάνυσμα $(a_0,a_1,\ldots,a_9)$ όπου ο a_i

ισούται με το πλήθος των ψηφίων του αριθμού που ισούνται με

.

Επειδή οι $a_0,\ldots,a_9$ είναι μη αρνητικοί ακέραιοι με $a_0 + \cdots + a_9 = 2016$ , υπάρχουν

$\displaystyle{ \binom{2025}{9} \leqslant 2025^9 < (10^{4})^9 = 10^{36}}$

διαφορετικά διανύσματα.

Από την άλλη υπάρχουν τουλάχιστον

$\displaystyle{ (10^{1008}-1) - (\sqrt{10} \cdot 10^{1007}) > 10^{1007} }$

τέλεια τετράγωνα με 2016

ψηφία.

Οπότε θα υπάρχουν τουλάχιστον $10^{1007-36}$ τέλεια τετράγωνα στα οποία αντιστοιχεί το ίδιο διάνυσμα. Όλα αυτά τα τέλεια τετράγωνα είναι ασφαλώς περισσότερα από 2016

και προκύπτουν από αναδιάταξη του ίδιου 2016

-ψήφιου αριθμού οπότε ο ισχυρισμός αποδείχθηκε.

sakis1963 · #5

Al.Koutsouridis έγραψε:LXXIX Μαθηματική Ολυμπιάδα Μόσχας

13 Μαρτίου 2016, 9η τάξη.

Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.

Αν και οι τρείς είναι μικρότεροι τις μονάδος έχουμε 0<a<b<c<1

......(1) και abc=a+b+c

......(2).
Η (2) γράφεται $c=\dfrac{a+b}{ab-1}$ και από την (1) έχουμε ab-1<0

και συνεπώς c<0

άτοπο

Αν δύο είναι μικρότεροι τις μονάδος έχουμε 0<a<b<1<c

......(3) και abc=a+b+c

......(2).
Ομοίως η (2) γράφεται $c=\dfrac{a+b}{ab-1}$ και από την (3) έχουμε ab-1<0

και συνεπώς c<0

άτοπο

Αρα δύο τουλάχιστον πρέπει να είναι μεγαλύτεροι της μονάδος.

#6

Al.Koutsouridis έγραψε: Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.

Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του $\sqrt 3$ .

(Υπόψη το .. $\,\, \ge \sqrt 3$ δεν βελτιώνεται σε .. $\,\,>\sqrt 3$ όπως βλέπουμε από το παράδειγμα $a=b=c = \sqrt 3$ )

#7

Mihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του $\sqrt 3$ .

Υπάρχει οξυγώνιο τρίγωνο ABC

ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, $\tan A, \tan B, \tan C.$ Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από $60^{\circ}$ και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστον $45^{\circ}.$

#8

smar έγραψε:
Mihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του $\sqrt 3$ .
Υπάρχει οξυγώνιο τρίγωνο ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, $\tan A, \tan B, \tan C.$ Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από $60^{\circ}$ και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστον $45^{\circ}.$

Ακριβώς αυτό είχα κατά νου. Έβαλα την βελτιωμένη εκδοχή της άσκησης γιατί η αρχική μου φάνηκε πολλή απλή για τέτοιο διαγωνισμό.

Al.Koutsouridis · #9

Mihalis_Lambrou έγραψε:
smar έγραψε:
Mihalis_Lambrou έγραψε: Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του $\sqrt 3$ .
Υπάρχει οξυγώνιο τρίγωνο ώστε οι τρεις αυτοί αριθμοί να έχουν τη μορφή, $\tan A, \tan B, \tan C.$ Σίγουρα υπάρχει μία γωνία μεγαλύτερη ή ίση από $60^{\circ}$ και επειδή το τρίγωνο είναι οξυγώνιο, η δεύτερη μεγαλύτερη είναι σίγουρα τουλάχιστον $45^{\circ}.$
Ακριβώς αυτό είχα κατά νου. Έβαλα την βελτιωμένη εκδοχή της άσκησης γιατί η αρχική μου φάνηκε πολλή απλή για τέτοιο διαγωνισμό.

Με αφορμή την περαιτέρω έρευνα του προβλήματος από τον κ.Λάμπρου απλά να παραθέσω το πνεύμα του διαγωνισμού (αλλά και όλων των διαγωνισμών γενικότερα) κατά τους διοργανωτές.

"Τα προβλήματα της μαθηματικής ολυμπιάδας της Μόσχας επιλέγονται έτσι ώστε, για την λύση τους να μην απαιτούνται ειδικές γνώσεις, που να υπερβαίνουν τα παραδοσιακά πλαίσια του προγράμματος σπουδών των σχολείων. Παράλληλα τα προβλήματα αυτά δεν αποσκοπούν μόνο στο να ελέγξουν την επίδοση (πρόοδο) των μαθητών αλλά δίνουν την δυνατότητα στους μαθητές να συμμετάσχουν (ενταχθούν) στην πραγματική (ρεαλιστική) επιστήμη, να λύσουν διασκεδαστικά προβλήματα, τα οποία μπορούν να προκαλέσουν το ενδιαφέρον για περαιτέρω έρευνα, σε βαθύτερη μελέτη των μαθηματικών."

Αυτή η συζήτηση και μελέτη, μετά τον εκάστοτε διαγωνισμό, είναι το ζουμί και το επικοδομητικό στην γενικότερη διαδικασία.

#10

Μια διαφορετική απόδειξη της γενίκευσης του Μιχάλη:

Έχουμε $xyz = x+y+z \geqslant 3\sqrt[3]{xyz}$ . Οπότε παίρνουμε $xyz \geqslant \sqrt{27}$ . Άρα κάποιο από τα x,y,z

είναι μεγαλύτερο ή ίσο του $\sqrt{3}$ αφού σε αντίθετη περίπτωση θα είχαμε $xyz < \sqrt{27}$ .

Το άλλο κομμάτι έχει ήδη αποδειχθεί αλλά το κάνω λίγο διαφορετικά. Αν έχουμε δύο μικρότερους του

, έστω τους

και

, τότε είναι x+y+z > z > xyz

, άτοπο.

#11

Mihalis_Lambrou έγραψε:
Al.Koutsouridis έγραψε: Πρόβλημα 1. Το άθροισμα τριών θετικών αριθμών ισούται με το γινόμενό τους. Να αποδείξετε, ότι τουλάχιστον δυο από αυτούς είναι μεγαλύτεροι της μονάδας.
Να την δυσκολέψουμε: Δείξτε ότι κάποιος από αυτούς είναι (γνήσια) μεγαλύτερος της μονάδας και κάποιος άλλος μεγαλύτερος ή ίσος του $\sqrt 3$ .

Και αλλιώς: Αν a,b

οι δύο μεγαλύτεροι, τότε για τον τρίτο είναι υποχρεωτικά $c\le \frac {a+b}{2}$ .

Αν $a, b < \sqrt 3$ τότε ab< 3

, οπότε $c=\frac {a+b}{ab-1} > \frac {a+b}{3-1} =\frac {a+b}{2}$ , άτοπο.

#12

Al.Koutsouridis έγραψε: Πρόβλημα 4. Δίνεται οξυγώνιο τρίγωνο και το κέντρο του περιγεγραμμένου κύκλου του. Ευθεία κάθετη στην πλευρά , τέμνει την πλευρά και την ευθεία στα σημεία και αντίστοιχα. Να αποδείξετε ότι τα σημεία και τα μέσα των τμημάτων και είναι ομοκυκλικά.

: Moscow Math Olympiad 2016.png (58.64 KiB) Προβλήθηκε 2395 φορές

Έστω $\displaystyle{M}$ και $\displaystyle{N}$ τα μέσα των τμημάτων $\displaystyle{AP}$ και $\displaystyle{CQ}$ αντίστοιχα. Ζητείται να αποδειχθεί ότι το τετράπλευρο $\displaystyle{BMON}$ είναι εγγράψιμο.

Αρκεί να αποδείξουμε ότι $\displaystyle{\angle AMO = \angle ONB.}$

Έστω $\displaystyle{K}$ και $\displaystyle{L}$ τα μέσα των τμημάτων $\displaystyle{AB}$ και $\displaystyle{BC}$ αντίστοιχα. Αρκεί να αποδείξουμε ότι τα (ορθογώνια) τρίγωνα $\displaystyle{OKM}$ και $\displaystyle{OLN}$ είναι όμοια. Εμομένως, αρκεί να αποδείξουμε ότι

$\displaystyle{\frac{{OK}}{{OL}} = \frac{{MK}}{{NL}}.}$

Παρατηρούμε ότι:

$\displaystyle{MK = AM - AK = \frac{{AP}}{2} - \frac{{AB}}{2} = \frac{{AP - AB}}{2} = \frac{{BP}}{2}}$

και

$\displaystyle{NL = CL - CN = \frac{{BC}}{2} - \frac{{CQ}}{2} = \frac{{BC - CQ}}{2} = \frac{{BQ}}{2},}$

οπότε

$\displaystyle{\frac{{MK}}{{NL}} = \frac{{BP}}{{BQ}}.}$

Έτσι, αρκεί να δείξουμε ότι $\displaystyle{\frac{{OK}}{{OL}} = \frac{{BP}}{{BQ}},}$ δηλαδή αρκεί να δείξουμε ότι τα τρίγωνα $\displaystyle{OKL}$ και $\displaystyle{BPQ}$ είναι όμοια. Αυτό, όμως, προκύπτει από τις ισότητες γωνιών

$\displaystyle{\angle OKL = {90^ \circ } - \angle BKL = {90^ \circ } - \angle BAC = \angle BPQ}$

και

$\displaystyle{\angle OLK = {90^ \circ } - \angle BLK = {90^ \circ } - \angle BCA = \angle CQR = \angle BQP,}$

οπότε η απόδειξη ολοκληρώνεται.

Al.Koutsouridis · #13

Έγιναν διορθώσεις στην διατύπωση του 3 προβλήματος στην αρχική ανάρτηση έπειτα από τις εύστοχες επισημάνσεις του Βαγγέλη Μουρούκου.

#14

Al.Koutsouridis έγραψε:
Πρόβλημα 3. Ο Βασίλης έλαβε ως άσκηση για το σπίτι την εξίσωση $x^2+p_{1}x+q_{1} = 0$ , όπου $p_{1}, q_{1}$ ακέραιοι αριθμοί. Βρίσκοντας τις ρίζες της $p_{2}, q_{2}$ έγραψε μια νέα εξίσωση, την $x^2+p_{2}x+q_{2} = 0$ . Επανέλαβε αυτήν την διαδικασία άλλες τρεις φορές. Παρατήρησε ότι έλυσε τέσσερεις δευτεροβάθμιες εξισώσεις και καθεμιά τους είχε δυο διαφορετικές ακέραιες ρίζες (αν από τις δυο δυνατές εξισώσεις δυο διαφορετικές ρίζες έχει ακριβώς η μία, τότε πάντα διαλέγει αυτή, αν και οι δύο τότε οποιαδήποτε). Παρόλο που προσπάθησε πολύ ( ο Βασίλης είναι άριστος μαθητής), δεν μπόρεσε να γράψει πέμπτη εξίσωση, έτσι ώστε να έχει δυο διαφορετικές πραγματικές ρίζες. Ποια η εξίσωση που δόθηκε στον Βασίλη ως άσκηση;

Η πέμπτη εξίσωση που προσπάθησε να γράψει ο Βασίλης θα έχει τη μορφή

$\displaystyle{{x^2} + {p_5}x + {q_5} = 0,}$

ή

$\displaystyle{{x^2} + {q_5}x + {p_5} = 0,}$

όπου $\displaystyle{{p_5},{q_5}}$ οι (διαφορετικές μεταξύ τους) ακέραιες ρίζες της τέταρτης εξίσωσης.

Επειδή η πέμπτη εξίσωση δεν έχει δύο διαφορετικές πραγματικές ρίζες, θα πρέπει να ισχύουν οι ανισότητες

$\displaystyle{p_5^2 \le 4{q_5}}$

και

$\displaystyle{q_5^2 \le 4{p_5},}$

από τις οποίες προκύπτει ότι $\displaystyle{{p_5} \ge 0,}$ $\displaystyle{{q_5} \ge 0,}$

$\displaystyle{p_5^4 \le 16q_5^2 \Rightarrow p_5^4 \le 64{p_5}}$

και

$\displaystyle{q_5^4 \le 16p_5^2 \Rightarrow q_5^4 \le 64{q_5}.}$

Παρατηρούμε ότι αν $\displaystyle{{p_5} = 0,}$ τότε $\displaystyle{q_5^2 \le 0 \Rightarrow {q_5} = 0,}$ πράγμα άτοπο. Επομένως, είναι $\displaystyle{{p_5} > 0}$ και $\displaystyle{{q_5} > 0,}$ οπότε

$\displaystyle{p_5^3 \le 64 \Rightarrow {p_5} \in \left\{ {1,2,3,4} \right\}}$

και όμοια

$\displaystyle{q_5^3 \le 64 \Rightarrow {q_5} \in \left\{ {1,2,3,4} \right\}.}$

Εύκολα ελέγχουμε ότι τα μοναδικά ζεύγη $\displaystyle{\left( {{p_5},{q_5}} \right)}$ που ικανοποιούν τις σχέσεις $\displaystyle{p_5^2 \le 4{q_5}}$ και $\displaystyle{q_5^2 \le 4{p_5}}$ είναι τα

$\displaystyle{\left( {{p_5},{q_5}} \right) = \left( {1,2} \right)}$ και $\displaystyle{\left( {{p_5},{q_5}} \right) = \left( {2,1} \right).}$

Επομένως, η τέταρτη εξίσωση που έγραψε ο Βασίλης είναι η $\displaystyle{{x^2} - 3x + 2 = 0,}$ η τρίτη είναι η $\displaystyle{{x^2} + x - 6 = 0,}$ η δεύτερη είναι η $\displaystyle{{x^2} + 5x - 6 = 0}$ και η πρώτη είναι η $\displaystyle{\boxed{{x^2} + x - 30 = 0}}$ .

Σημείωση: Είναι άξια θαυμασμού η ευρηματικότητα των ανθρώπων που κατασκευάζουν τέτοια (κατά τη γνώμη μου) πανέμορφα προβλήματα, τα οποία μπορούν να λυθούν με ελάχιστες προαπαιτούμενες γνώσεις. Αντίθετα, κάποιοι άλλοι σκιαμαχούν για το τι είναι "εντός" και τι "εκτός ύλης" και πώς αυτό θα βαθμολογηθεί στις εξετάσεις, θυμίζοντας τους Γραμματείς που προσπαθούν να ερμηνεύσουν τις λεπτές αποχρώσεις των νόμων του Ταλμούδ...

Al.Koutsouridis · #15

Al.Koutsouridis έγραψε: ↑
Σάβ Απρ 16, 2016 3:14 pm
LXXIX Μαθηματική Ολυμπιάδα Μόσχας

Πρόβλημα 6. Στη χώρα των γλωσσολόγων υπάρχουν γλώσσες. Στην οποία κατοικούν άτομα, ο καθένας από τους οποίους γνωρίζει ακριβώς 3 γλώσσες και για διαφορετικά άτομα αυτή η τριάδα γλωσσών είναι διαφορετική. Είναι γνωστό ότι ο μέγιστος αριθμός ατόμων, οποιοιδήποτε δυο από τους οποίους μπορούν να συνομιλήσουν χωρίς μεταφραστή, ισούται με . Προέκυψε ότι $11n \leq k \leq \dfrac{m}{2}$ . Να αποδείξετε ότι στη χώρα αυτή θα βρεθούν τουλάχιστον ζεύγη κατοίκων, οι οποίοι δε θα μπορέσουν να συνομιλήσουν χωρίς μεταφραστή.

Μεταφέρω την επίσημη λύση και το σχόλιο που συνοδεύει αυτό το πρόβλημα. Για την ιστόρία δυσκόλεψε πιρισσότερο από όλα τους συμμετέχοντες της 9ης τάξης, καθώς το έλυσαν 2 (+) σε σύνολο 890 μαθητών.

Λύση. Θα συμβολίσουμε με

το σύνολο

ατόμων, οι οποίοι μπορούν να συνομιλήσουν χωρίς μεταφραστές. Εξετάζουμε ένα τυχαία άτομο (τον κύριο

), που δεν εμπίπτει στο σύνολο

. Για αυτόν υπάρχει ένα τέτοιο άτομο του συνόλου

(ο κύριος $X^{\prime}$ ), ώστε η ένωση των γλωσσών τους να είναι κενό σύνολο. Θα εκτιμήσουμε το πλήθος εκείνων των ατόμων του συνόλου

, τα οποία μπορούν να συνομιλήσουν με τον κύριο

. Τέτοια άτομα έχουν τουλάχιστον μια κοινή γλώσσα και με τον κύριο

και με τον κύριο $X^{\prime}$ (καθώς εμπίπτουν στο σύνολο

), άρα δεν είναι παραπάνω από $3 \cdot 3 \cdot n$ . Με αυτό το τρόπο, για κάθε άτομο, που δεν εμπίπτει στο σύνολο

, βρήκαμε τουλάχιστον k-9n

αντιπροσώπους του συνόλου

, οι οποίοι δεν μπορούν να συνομιλήσουν μαζί τους χωρίς μεταφραστή. Οπότε στο σύνολο τέτοια ζεύγη θα είναι

$(m-k) \cdot (k-9n) \geq \left ( m-\dfrac{m}{2}\right) \cdot (11n-9n) \geq \dfrac{m}{2} \cdot 2n=mn$ .

Σχόλιο. Το πρόβλημα σχετίζεται με ένα καθόλα γνωστό και σημαντικό τομέα της σύγχρονης θεωρίας γράφων. Και συγκεκριμένα, ένας γράφος ονομάζεται γράφος Κνέσερ( Kneser), αν οι κορυφές του είναι όλα τα δυνατά υποσύνολα δύναμης

του συνόλου $R_{n}={1, \dots , n}$ και ακμές του, ζεύγη μη τεμνόμενων υποσυνόλων. Για τους γράφους Κνέσερ υπάρχει «δημοφιλής» (εκλαϊκευμένη) βιβλιογραφία: Βλ. [1], [2]. Στο πρόβλημα 6 έχουμε να κάνουμε με ένα γράφο Κνέσερ, στον οποίο r=3

. Κάθε κορυφή του είναι μια τριάδα γλωσσών (ή αν θέλετε, γλωσσολόγος, που ξέρει αυτές τις τρεις γλώσσες). Δυο κορυφές ενώνονται με ακμή, αν οι αντίστοιχοι γλωσσολόγοι δεν μπορούν συνομιλήσουν χωρίς μεταφραστή. Θυμίζουμε, ότι ένα σύνολο κορυφών ενός γράφου ονομάζεται ανεξάρτητο, αν οποιεσδήποτε δυο κορυφές σε αυτό δεν ενώνονται με ακμή. Η δύναμη του μεγαλύτερου ανεξάρτητου υποσυνόλου κορυφών ενός γράφου

ονομάζεται αριθμός ανεξαρτησίας και συμβολίζεται με $\alpha (G)$ . Με αυτούς τους όρους το πρόβλημα 6 διατυπώνεται ως: «έστω ότι δίνεται ένας υπογράφος ενός γράφου Κνέσερ με και κορυφές, εξάλλου $\alpha(G)=k$ και $11n \leq k \leq m/2$ . Να αποδείξετε τότε, ότι ο αριθμός ακμών του γράφου είναι τουλάχιστον ».

Το πρόβλημα σε τέτοια διατύπωση μη τετριμμένα χρησιμοποιεί ακριβώς την δομή ενός γράφου Κνέσερ. Το γεγονός είναι ότι υπάρχει το κλασικό θεώρημα του Τουράν: αν γράφος με

κορυφές έχει βαθμό ανεξαρτησίας

, τότε έχει «περίπου» $\dfrac{m^2}{2k}$ ακμές ή περισσότερες. Στην περίπτωσή μας αυτή η εκτίμηση έχει το μέγεθος της τάξης του

, καθόλα διαφορετικό του

και αυτό είναι πολύ σημαντικό.

Να σημειώσουμε ότι ο αριθμός ανεξαρτησίας όλου του γράφου Κνέσερ είναι ίσος με $C_{n-1}^{r-1}$ , αν $r \leq n/2$ . Αυτό είναι το γνωστό θεώρημα Έρντος-Κο-Ραντό, την απόδειξη του οποίου για παράδειγμα μπορείτε να διαβάσετε στο [3]. Το πρόβλημα 6 προέκυψε κατά την στιγμή, που ο θεματοδότης και οι μαθητές του μπόρεσαν να δείξουν ότι σε τυχαίο υπογράφο ενός γράφου Κνέσερ ο αριθμός ανεξαρτησίας, αντίθετα με την διαίσθηση, σχεδόν δεν αλλάζει (βλ. [4]). Τώρα από αυτό έχει προκύψει σημαντικό επιστημονικό έργο, που επιτρέπει με νέα ματιά να κοιτάξουμε σε κλασικά αποτελέσματα της συνδυαστικής ακροτάτων (extremal combinatorics) βλ. [5].

Να σημειώσουμε επίσης ότι η εκτίμηση στο πρόβλημα 6 μακράν δεν είναι η βέλτιστη. Μπορεί να βελτιωθεί, αποδεικνύοντας το ακόλουθο αποτέλεσμα: «Στις συνθήκες του προβλήματος 6 τα μέγιστα ανεξάρτητα σύνολα αναγκαστικά θα αποτελούνται από κορυφές, οι οποίες όλες θα περιέχουν το ίδιο κοινό στοιχείο του συνόλου $R_{n}$ .» Προσπαθήστε να το αποδείξετε! Σε ποιο γενική μορφή ονομάζεται θεώρημα Χίλτον-Μίλνερ (βλ. [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

Υγ. Διάφοροι σύνδεσμοι στο κείμενο τοποθετήθηκαν από μένα.

Πηγή

Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

Re: Μαθηματική Ολυμπιάδα Μόσχας 2016 (9η τάξη)

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