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

[Al.Koutsouridis]

LXXX Μαθηματική Ολυμπιάδα Μόσχας 12 Μαρτίου 2017 - 10η τάξη


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


Πρόβλημα 2. Όλοι οι φυσικοί αριθμοί, μεγαλύτεροι του ένα, χρωματίστηκαν με δυο χρώματα μπλε και κόκκινο. Έτσι, ώστε το άθροισμα οποιονδήποτε δυο μπλε (συμπεριλαμβανομένου ίδιων) να είναι μπλε και το γινόμενο οποιονδήποτε δυο κόκκινων (συμπεριλαμβανομένου ίδιων) να είναι κόκκινο. Είναι γνωστό ότι στον χρωματισμό χρησιμοποιήθηκαν και τα δυο χρώματα και ότι ο αριθμός 1024 χρωματίστηκε με μπλε. Τι χρώμα μπορεί να έχει ο αριθμός 2017 υπό αυτές τις συνθήκες;


Πρόβλημα 3. Έστω το κέντρο του περιγεγραμμένου τριγώνου . Ο περιγεγραμμένος κύκλος του τριγώνου τέμνει εκ νέου τις πλευρές και στα σημεία και . Αν η ευθεία χωρίζει το τρίγωνο σε δυο ισοδύναμα χωρία, να βρείτε την γωνία .


Πρόβλημα 4. Ο Βασίλης έχει μια πέτρα (ομογενής, χωρίς εσωτερικές κοιλότητες), σχήματος κυρτού πολύεδρου το οποίο έχει μόνο τριγωνικές και εξαγωνικές έδρες. Ο Βασίλης ισχυρίζεται, ότι έσπασε την πέτρα σε δυο κομμάτια με τα οποία μπορεί να σχηματίσει κύβο (χωρίς εσωτερικές κοιλότητες). Μπορεί να αληθεύει ο ισχυρισμός του;


Πρόβλημα 5. Για ποιους μη μηδενικούς φυσικούς για κάθε φυσικό θα βρεθεί αριθμός με άθροισμα ψηφίων , που διαιρείται με το ;


Πρόβλημα 6. Στο Σικάγο δρουν 36 εγκληματικές συμμορίες μερικές από τις οποίες έχουν διενέξεις μεταξύ τους. Κάθε γκάγκστερ είναι μέλος μερικών συμμοριών, εξάλλου οποιοιδήποτε δυο γκάγκστερ είναι μέλη διαφορετικών ομάδων (συνόλων) συμμοριών. Είναι γνωστό ότι κανένας γκάγκστερ δεν είναι μέλος δυο συμμοριών που είναι σε διένεξη μεταξύ τους. Επιπλέον, προέκυψε ότι κάθε συμμορία, στην οποία δεν είναι μέλος ένας γκάγκστερ, είναι σε διένεξη με κάποια συμμορία της οποίας αυτός είναι μέλος. Ποιος είναι ο μέγιστος αριθμός των γκάγκστερ στο Σικάγο;


Στατιστικά: (1096 συμμετοχές)


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

[JimNt.]

LXXX Μαθηματική Ολυμπιάδα Μόσχας 12 Μαρτίου 2017 - 10η τάξη


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

Η έχει ρίζες και η τις . Έχουμε , και , . Από τις δύο πρώτες παίρνουμε αντικαθιστώντας στην τρίτη παίρνουμε . Συνεπώς, η ζητούμενη , που όμως δεν έχει πραγματικές λύσεις.

[Ορέστης Λιγνός]

Πρόβλημα 3

Έστω .

Από την εκφώνηση, , και αφού τα δύο αυτά τρίγωνα έχουν κοινή την γωνία , πρέπει .

Ακόμη, από Θ. τεμνόμενων χορδών έχουμε .

Με πολλαπλασιασμό κατά μέλη και απλοποιήση λαμβάνουμε .

Όπως φαίνεται και από το σχήμα, , άρα ισοσκελές με .

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

kyklos.png (20.77 KiB) Προβλήθηκε 1564 φορές

[mikemoke]

διαγραφη

[Demetres]

Πρόβλημα 6. Στο Σικάγο δρουν 36 εγκληματικές συμμορίες μερικές από τις οποίες έχουν διενέξεις μεταξύ τους. Κάθε γκάγκστερ είναι μέλος μερικών συμμοριών, εξάλλου οποιοιδήποτε δυο γκάγκστερ είναι μέλη διαφορετικών ομάδων (συνόλων) συμμοριών. Είναι γνωστό ότι κανένας γκάγκστερ δεν είναι μέλος δυο συμμοριών που είναι σε διένεξη μεταξύ τους. Επιπλέον, προέκυψε ότι κάθε συμμορία, στην οποία δεν είναι μέλος ένας γκάγκστερ, είναι σε διένεξη με κάποια συμμορία της οποίας αυτός είναι μέλος. Ποιος είναι ο μέγιστος αριθμός των γκάγκστερ στο Σικάγο;

Δύσκολο!

Θα δείξουμε ότι στο Σικάγο μπορούν να υπάρχουν γκαγκστερ (δηλαδή περίπου ένας στους πέντε κατοίκους του Σικάγο), αλλά όχι περισσότεροι.

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

Ας δείξουμε τώρα ότι δεν μπορούν να υπάρξουν περισσότεροι γκάγκστερ. Θα δείξουμε με επαγωγή στον αριθμό των των συμμοριών ότι μπορούν να υπάρξουν το πολύ γκάγκστερ.

Έστω η συμμορία η οποία έχει τις λιγότερες διενέξεις. Έστω ότι έχει διενέξεις με τις συμμορίες .

Κάθε γκάγκστερ πρέπει να είναι μέλος μιας από τις συμμορίες . Πράγματι, αν ο δεν ανήκει στην συμμορία , τότε η είναι σε διένεξη με μια συμμορία της οποίας είναι μέλος ο . Δηλαδή ο είναι μέλος μίας εκ των .

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

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





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

Δηλαδή, στην γλώσσα της θεωρίας γραφημάτων ψάχνουμε τον μέγιστο αριθμός «μέγιστων ανεξάρτητων υποσυνόλων» ενός γραφήματος σε κορυφές.

Για γράφημα σε κορυφές ο μέγιστος αριθμός έχει υπολογιστεί από τους Miller και Muller το 1960 και ανεξάρτητα (!) από τους Moon και Moser το 1965. Η απόδειξη που έδωσα είναι βασισμένη στο άρθρο εδώ.

[Al.Koutsouridis]

Πρόβλημα 6. Στο Σικάγο δρουν 36 εγκληματικές συμμορίες μερικές από τις οποίες έχουν διενέξεις μεταξύ τους. Κάθε γκάγκστερ είναι μέλος μερικών συμμοριών, εξάλλου οποιοιδήποτε δυο γκάγκστερ είναι μέλη διαφορετικών ομάδων (συνόλων) συμμοριών. Είναι γνωστό ότι κανένας γκάγκστερ δεν είναι μέλος δυο συμμοριών που είναι σε διένεξη μεταξύ τους. Επιπλέον, προέκυψε ότι κάθε συμμορία, στην οποία δεν είναι μέλος ένας γκάγκστερ, είναι σε διένεξη με κάποια συμμορία της οποίας αυτός είναι μέλος. Ποιος είναι ο μέγιστος αριθμός των γκάγκστερ στο Σικάγο;

Δύσκολο!

...

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

Δηλαδή, στην γλώσσα της θεωρίας γραφημάτων ψάχνουμε τον μέγιστο αριθμός «μέγιστων ανεξάρτητων υποσυνόλων» ενός γραφήματος σε κορυφές.

Για γράφημα σε κορυφές ο μέγιστος αριθμός έχει υπολογιστεί από τους Miller και Muller το 1960 και ανεξάρτητα (!) από τους Moon και Moser το 1965. Η απόδειξη που έδωσα είναι βασισμένη στο άρθρο εδώ.

Το αποκρυπτογραφήσατε πλήρως το πρόβλημα . Στις επίσημες λύσεις το πρόβλημα λύνεται στην γενική του περίπτωση. Σαν σχόλιο στο τέλος γίνεται αναφορά στο άρθρο των Moon, Moser (Moon J. W., Moser L. On cliques in graphs // Israel J. Math.-1965).

Το πρόβλημα το έλυσαν πλήρως 2 από τους 1096 συμμετέχοντες της 10ης τάξης και το προσέγγισε ικανοποιητικά άλλος ένας. Από τους μαθητές της 11ης όμως, δεν το έλυσε κανείς (ίσως επειδή ήταν και πιο δύσκολα τα προηγούμενα θέματα της 11 τάξης).

Να αναφέρω εδώ επί της ευκαιρίας, ότι στην Ρωσία γίνεται πολλές φορές κριτική και γράφονται αρκετά άρθρα με το ερώτημα « Ολυμπιάδες μαθηματικών, σπορ ή δρόμος προς τα ανώτερα μαθηματικά;». Ότι έχουν καταντήσει περισσότερο σαν σπορ και τα προβλήματα αποκλίνουν από τον πατροπαράδοτο τρόπο (εννοούν σοβιετικής εποχής) και υπάρχει ολόκληρη επιχειρηματολογία για αυτό. Όπως την όλο και περισσότερο ενασχόληση με τις ολυμπιάδες μεσαίου βεληνεκούς μαθηματικών, εκδυτικοποίηση των εισαγωγικών εξετάσεων, αυξανόμενο ρόλο εταιριών στην εκπαίδευση, το γεγονός ότι πολλοί εγκατέλειψαν την χώρα κ.α.

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

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

Η «συνέχιση» (θεωρία) του προβλήματος και γενικεύσεις θα αναπτυχθούν σε κάποια από τα καλοκαιρινά σχολεία, σεμινάρια. Αυτά συνήθως είναι δεκαήμερα με τους νικητές των ολυμπιάδων να έχουν την δυνατότητα να συμμετέχουν δωρεάν (έξοδα μεταφοράς, διαμονής, διατροφής).

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