IMC 2022
Συντονιστής: Demetres
IMC 2022
Καλησπέρα από το όμορφο αλλά και πολύ ζεστό Blagoevgrad της Βουλγαρίας, όπου πριν από λίγες μέρες έλαβε χώρα ο διεθνής διαγωνισμός IMC υβριδικά. Συνολικά συμμετείχαν (!) φοιτητές, εκ των οποίων οι διαγωνίστηκαν δια ζώσης.
Να σημειωθεί ότι λόγω του αυξημένου αριθμού των συμμετεχόντων χωρίς αρχηγό, το βάρος ανά διορθωτή ήταν ιδιαίτερα αυξημένο και όπως πληροφορηθήκαμε από τους διοργανωτές τα αποτελέσματα για τους εξ αποστάσεως συμμετέχοντες μπορεί να αργήσουν ακόμα και μερικές μέρες. Από την Ελλάδα συμμετείχαν δια ζώσης ομάδες από τη Θεσσαλονίκη και την Πάτρα, ενώ υπήρχαν και φοιτητές από Θεσσαλονίκη, Αθήνα και Πάτρα που συμμετείχαν διαδικτυακά.
Μιας και πλέον έχουν αναρτηθεί τα θέματα στην επίσημη ιστοσελίδα του διαγωνισμού, τα παραθέτω και εδώ για συζήτηση.
Μέρα 1
Πρόβλημα 1: Έστω ολοκληρώσιμη συνάρτηση τέτοια ώστε για κάθε . Να δειχθεί ότι
Πρόβλημα 2: Έστω θετικός ακέραιος. Να βρεθούν όλοι οι πραγματικοί πίνακες με μόνο πραγματικές ιδιοτιμές που ικανοποιούν τη σχέση για κάποιον ακέραιο
Πρόβλημα 3: Έστω πρώτος αριθμός. Ένας ψύλλος στέκεται στο σημείο του πραγματικού άξονα. Κάθε λεπτό ο ψύλλος έχει τις εξής δυνατότητες: να μείνει στη θέση του, να κινηθεί κατά 1 αριστερά ή κατά 1 δεξιά. Μετά από λεπτά ο ψύλλος θέλει να βρίσκεται ξανά στο . Έστω ο αριθμός των τρόπων να το κάνει αυτό. Να βρεθεί το modulo (Για παράδειγμα για : είτε δεν κουνιέται από τη θέση του, είτε πάει αριστερά και μετά δεξιά, είτε δεξιά και μετά αριστερά)
Πρόβλημα 4: Έστω ακέραιος. Έστω το σύνολο όλων των μη διατεταγμένων τριάδων με διακριτά στοιχεία από το σύνολο . Έστω ο ελάχιστος αριθμός χρωμάτων που αρκούν για να χρωματίσουμε τα στοιχεία του , έτσι ώστε, αν , οι τριάδες και να έχουν διαφορετικά χρώματα. Να δειχθεί ότι
Μέρα 2
Πρόβλημα 5: Χρωματίζουμε όλες τις πλευρές και τις διαγωνίους ενός κανονικού πολυγώνου με γωνίες είτε μπλε είτε κόκκινες, έτσι ώστε από κάθε κορυφή του πολυγώνου να είναι άκρο κόκκινων και μπλε τμημάτων. Ένα τρίγωνο που σχηματίζεται από κορυφές του λέγεται μονοχρωματικό αν όλες οι πλευρές του έχουν το ίδιο χρώμα. Υποθέτουμε ότι υπάρχουν μονοχρωματικά μπλε τρίγωνα. Πόσα μονοχρωματικά κόκκινα τρίγωνα υπάρχουν;
Πρόβλημα 6: Έστω πρώτος αριθμός. Να δειχθεί ότι υπάρχει μετάθεση του τέτοια ώστε
Πρόβλημα 7: Έστω ταυτοδύναμοι πραγματικοί πίνακες τέτοιοι ώστε για κάθε . Να δειχθεί ότι τουλάχιστον ένας από τους πίνακες έχει
Πρόβλημα 8: Έστω ακέραιοι και έστω ένας κύκλος. Επιλέγουμε μπλε και κόκκινα σημεία ομοιόμορφα και ανεξάρτητα τυχαία πάνω στον κύκλο . Έστω η τομή του κυρτού καλύμματος των κόκκινων σημείων και του κυρτού καλύμματος των μπλε σημείων. Έστω ο αριθμός των κορυφών του κυρτού πολυγώνου (συγκεκριμένα όταν το είναι κενό). Να βρεθεί η μέση τιμή του .
Να σημειωθεί ότι λόγω του αυξημένου αριθμού των συμμετεχόντων χωρίς αρχηγό, το βάρος ανά διορθωτή ήταν ιδιαίτερα αυξημένο και όπως πληροφορηθήκαμε από τους διοργανωτές τα αποτελέσματα για τους εξ αποστάσεως συμμετέχοντες μπορεί να αργήσουν ακόμα και μερικές μέρες. Από την Ελλάδα συμμετείχαν δια ζώσης ομάδες από τη Θεσσαλονίκη και την Πάτρα, ενώ υπήρχαν και φοιτητές από Θεσσαλονίκη, Αθήνα και Πάτρα που συμμετείχαν διαδικτυακά.
Μιας και πλέον έχουν αναρτηθεί τα θέματα στην επίσημη ιστοσελίδα του διαγωνισμού, τα παραθέτω και εδώ για συζήτηση.
Μέρα 1
Πρόβλημα 1: Έστω ολοκληρώσιμη συνάρτηση τέτοια ώστε για κάθε . Να δειχθεί ότι
Πρόβλημα 2: Έστω θετικός ακέραιος. Να βρεθούν όλοι οι πραγματικοί πίνακες με μόνο πραγματικές ιδιοτιμές που ικανοποιούν τη σχέση για κάποιον ακέραιο
Πρόβλημα 3: Έστω πρώτος αριθμός. Ένας ψύλλος στέκεται στο σημείο του πραγματικού άξονα. Κάθε λεπτό ο ψύλλος έχει τις εξής δυνατότητες: να μείνει στη θέση του, να κινηθεί κατά 1 αριστερά ή κατά 1 δεξιά. Μετά από λεπτά ο ψύλλος θέλει να βρίσκεται ξανά στο . Έστω ο αριθμός των τρόπων να το κάνει αυτό. Να βρεθεί το modulo (Για παράδειγμα για : είτε δεν κουνιέται από τη θέση του, είτε πάει αριστερά και μετά δεξιά, είτε δεξιά και μετά αριστερά)
Πρόβλημα 4: Έστω ακέραιος. Έστω το σύνολο όλων των μη διατεταγμένων τριάδων με διακριτά στοιχεία από το σύνολο . Έστω ο ελάχιστος αριθμός χρωμάτων που αρκούν για να χρωματίσουμε τα στοιχεία του , έτσι ώστε, αν , οι τριάδες και να έχουν διαφορετικά χρώματα. Να δειχθεί ότι
Μέρα 2
Πρόβλημα 5: Χρωματίζουμε όλες τις πλευρές και τις διαγωνίους ενός κανονικού πολυγώνου με γωνίες είτε μπλε είτε κόκκινες, έτσι ώστε από κάθε κορυφή του πολυγώνου να είναι άκρο κόκκινων και μπλε τμημάτων. Ένα τρίγωνο που σχηματίζεται από κορυφές του λέγεται μονοχρωματικό αν όλες οι πλευρές του έχουν το ίδιο χρώμα. Υποθέτουμε ότι υπάρχουν μονοχρωματικά μπλε τρίγωνα. Πόσα μονοχρωματικά κόκκινα τρίγωνα υπάρχουν;
Πρόβλημα 6: Έστω πρώτος αριθμός. Να δειχθεί ότι υπάρχει μετάθεση του τέτοια ώστε
Πρόβλημα 7: Έστω ταυτοδύναμοι πραγματικοί πίνακες τέτοιοι ώστε για κάθε . Να δειχθεί ότι τουλάχιστον ένας από τους πίνακες έχει
Πρόβλημα 8: Έστω ακέραιοι και έστω ένας κύκλος. Επιλέγουμε μπλε και κόκκινα σημεία ομοιόμορφα και ανεξάρτητα τυχαία πάνω στον κύκλο . Έστω η τομή του κυρτού καλύμματος των κόκκινων σημείων και του κυρτού καλύμματος των μπλε σημείων. Έστω ο αριθμός των κορυφών του κυρτού πολυγώνου (συγκεκριμένα όταν το είναι κενό). Να βρεθεί η μέση τιμή του .
Νάκος Ιωάννης, ΗΜΜΥ ΑΠΘ
Λέξεις Κλειδιά:
Re: IMC 2022
Συγχαρητήρια σε όλους τους συμμετέχοντες και ιδιαίτερα στον Γιάννη Νάκο (Summand), για την κατάκτηση ασημένιου μεταλλίου!
Μια λύση για το Πρόβλημα 1:
Ας είναι . Σπάμε το αρχικό ολοκλήρωμα και εργαζόμαστε με αλλαγή μεταβλητής:
.
Όμως από ανισότητα ΑΜ-ΓΜ ( θετική) έχουμε .
Ολοκληρώνοντας την παραπάνω λαμβάνουμε όπως έπρεπε.
Μια λύση για το Πρόβλημα 1:
Ας είναι . Σπάμε το αρχικό ολοκλήρωμα και εργαζόμαστε με αλλαγή μεταβλητής:
.
Όμως από ανισότητα ΑΜ-ΓΜ ( θετική) έχουμε .
Ολοκληρώνοντας την παραπάνω λαμβάνουμε όπως έπρεπε.
-
- Δημοσιεύσεις: 9
- Εγγραφή: Κυρ Ιαν 20, 2019 8:46 am
Re: IMC 2022
Η λύση μου για το Πρόβλημα 6 :
Καλούμε το υπόλοιπο του αθροίσματος modulo .
Ώς ορίζουμε το υπόλοιπο που προκύπτει από μια αρχική μετάθεση αν εναλλάξουμε τα και στοιχεία.
Ορίζω την ταυτοτικη μετάθεση των στοιχείων.
Για την συνέχεια της λύσης παράγω 2 ιδιότητες:
και
Η απόδειξη των οποίων γίνεται άμεσα με πράξεις.
Παρατηρώ ότι :
Απόδειξη:
Για και άρα
Ξεκινώντας από την ταυτοτική μετάθεση θα καταλήξουμε με τις ιδιότητες 1,2 σε μετάθεση που έχει υπόλοιπο ισο με .
Για :
Παρατηρούμε οτι η εφαρμογή της 1 στην μετάθεση Α δίνει:
εφόσον στην μετάθεση Α.
Οπότε αν εκτελούμε τις εξής πράξεις διαδοχικά:
Οπότε ξεκινώντας απο το Α μειώνουμε το υπόλοιπο κατά 3 φορές και τελικά καταλήγουμε σε υπόλοιπο .
Για :
Έστω
Εκτελώντας μια φορά την πράξη ξεκινώντας από το Α μειώνουμε το υπόλοιπο κατά απο την ιδιότητα 2.
Τώρα το είναι οπότε εκτελούμε ακόμα πράξεις τύπου (1) (Αν ) ως εξής:
Πρώτα (2)
(1)
Καταλήγουμε σε υπόλοιπο 2.
Μένουν οι περιπτώσεις όπου δουλεύουν οι μεταθέσεις αντίστοιχα.
Γενίκευση : Θα μπορούσε να μην είναι πρώτος αριθμός αλλά πρώτος με το 6 και θα γινόταν ακριβώς η ίδια απόδειξη .
Καλούμε το υπόλοιπο του αθροίσματος modulo .
Ώς ορίζουμε το υπόλοιπο που προκύπτει από μια αρχική μετάθεση αν εναλλάξουμε τα και στοιχεία.
Ορίζω την ταυτοτικη μετάθεση των στοιχείων.
Για την συνέχεια της λύσης παράγω 2 ιδιότητες:
και
Η απόδειξη των οποίων γίνεται άμεσα με πράξεις.
Παρατηρώ ότι :
Απόδειξη:
Για και άρα
Ξεκινώντας από την ταυτοτική μετάθεση θα καταλήξουμε με τις ιδιότητες 1,2 σε μετάθεση που έχει υπόλοιπο ισο με .
Για :
Παρατηρούμε οτι η εφαρμογή της 1 στην μετάθεση Α δίνει:
εφόσον στην μετάθεση Α.
Οπότε αν εκτελούμε τις εξής πράξεις διαδοχικά:
Οπότε ξεκινώντας απο το Α μειώνουμε το υπόλοιπο κατά 3 φορές και τελικά καταλήγουμε σε υπόλοιπο .
Για :
Έστω
Εκτελώντας μια φορά την πράξη ξεκινώντας από το Α μειώνουμε το υπόλοιπο κατά απο την ιδιότητα 2.
Τώρα το είναι οπότε εκτελούμε ακόμα πράξεις τύπου (1) (Αν ) ως εξής:
Πρώτα (2)
(1)
Καταλήγουμε σε υπόλοιπο 2.
Μένουν οι περιπτώσεις όπου δουλεύουν οι μεταθέσεις αντίστοιχα.
Γενίκευση : Θα μπορούσε να μην είναι πρώτος αριθμός αλλά πρώτος με το 6 και θα γινόταν ακριβώς η ίδια απόδειξη .
Re: IMC 2022
Ευχαριστώ τον φίλο μου Γιάννη Ιακωβάκη (abfx) για τις όμορφες ευχές. Να δώσω και εγώ με τη σειρά μου συγχαρητήρια σε όλους τους φοιτητές που συμμετείχαν και διακρίθηκαν. Όσον αφορά το δια ζώσης κομμάτι, η Ελλάδα, που εκπροσωπήθηκε από Θεσσαλονίκη και Πάτρα, απέσπασε 3 ασημένια, 1 χάλκινο και 2 εύφημες μνείες. Υπήρχαν επίσης πολύ καλές επιδόσεις Ελλήνων φοιτητών εξ αποστάσεως, οπότε αναμένω σίγουρα να έχουμε και χρυσά! Παραθέτω τις λύσεις μου στα προβλήματα.
Θέλουμε να ξεφορτωθούμε τον ανάστροφο. Για το λόγο αυτό παίρνουμε ανάστροφο στη δοσμένη σχέση
και επειδή ισχύει και αντικαθιστώντας τη δοθείσα έχουμε
Από Cayley-Hamilton ισχύει ότι το ελάχιστο πολυώνυμο του πίνακα διαιρεί το
Δηλαδή . Προφανώς
Θα δείξουμε ότι για το πολυώνυμο ισχύει
Προφανώς αν περιττός τότε ο άρτιος οπότε ανεξάρτητα από το πρόσημο του ισχύει και το ζητούμενο έπεται. Αν άρτιος το ζητούμενο είναι πάλι προφανές, αφού
Αφού ο πίνακας έχει μόνο πραγματικές ιδιοτιμές (που είναι οι ρίζες του ελάχιστου πολυωνύμου) συμπεραίνουμε ότι η μοναδική πραγματική ρίζα του ελάχιστου πολυωνύμου είναι το και άρα η μοναδική δυνατή ιδιοτιμή του είναι η
Οπότε ισχύει ότι για κάποιο
Επομένως ο είναι μηδενοδύναμος τάξης αφού από Cayley-Hamilton ισχύει
Αφού ισχύει προφανώς και άρα αντικαθιστώντας στη δοθείσα παίρνουμε , άρα ο είναι συμμετρικός και ως τέτοιος είναι ορθογώνια διαγωνιοποιήσιμος.
Διαγωνιοποιώντας τον έχουμε , όπου
Έτσι προκύπτει ότι ο μοναδικός πίνακας που ικανοποιεί την σχέση είναι ο
Νάκος Ιωάννης, ΗΜΜΥ ΑΠΘ
Re: IMC 2022
Η ιδέα είναι παρόμοια με της επίσημης, αλλά διαφέρει λίγο στην εκτέλεση.
Αρχικά παρατηρούμε ότι, αν οποιοσδήποτε από τους πίνακες είναι ο μηδενικός, ισχύουν οι υποθέσεις του προβλήματος και το ζητούμενο είναι άμεσο.
Οπότε από εδώ και πέρα υποθέτουμε ότι
Πολλαπλασιάζοντας τη δοθείσα με από τα αριστερά και με από τα δεξιά και αξιοποιώντας την ιδιότητα ότι
προκύπτει ότι ή ισοδύναμα θέτοντας έχουμε
Έστω το ελάχιστο πολυώνυμο του πίνακα
Από Cayley-Hamilton:
Άρα οι πιθανές ιδιοτιμές του είναι οι και άρα
H ισότητα ισχύει αν και μόνο αν όλες οι ιδιοτιμές του είναι
Όμως από τον τρόπο που ορίστηκε ο είναι
Άρα θα ισχύει , οπότε πρέπει όλες οι ιδιοτιμές του να είναι μηδενικές.
Άρα και άρα από Cayley-Hamilton δηλαδή
Θα δείξουμε τώρα ότι .
Μέχρι τώρα έχουμε ότι και
Άρα από την πρώτη σχέση για κάθε υπάρχει μια στήλη του , έστω , τέτοια ώστε .
Προφανώς επίσης από τη δεύτερη σχέση
Θα αποδείξουμε ότι τα -διάστατα διανύσματα είναι γραμμικά ανεξάρτητα από όπου το ζητούμενο έπεται άμεσα.
Έστω
Πολλαπλασιάζοντας με από αριστερά έχουμε
Όλοι οι όροι εκτός του -οστού είναι της μορφής άρα πρέπει να είναι
Για τον -οστό όρο έχουμε και αφού προκύπτει
Τέλος παρατηρούμε ότι αφού οι πίνακες είναι ταυτοδύναμοι, το ελάχιστο πολυώνυμό τους έχει μόνο απλές ρίζες άρα είναι διαγωνιοποιήσιμοι.
Επίσης προφανώς ισχύει άρα όλοι οι πίνακες διαγωνιοποιούνται ταυτόχρονα από την ίδια βάση ιδιοδιανυσμάτων.
Έστω ο πίνακας που διαγωνιοποιεί τους τότε άρα
Παρατηρούμε ότι οι σχέσεις που ισχύουν για τους αρχικούς πίνακες ισχύουν και για τις διαγώνιες μορφές τους:
Άρα μπορούμε να υποθέσουμε ότι οι πίνακες είναι διαγώνιοι. Έστω που είναι ακριβώς το πλήθος των άσσων στη διαγώνιο του
Ο έχει άσσους στη διαγώνιο και τα υπόλοιπα στοιχεία του είναι
Τότε ο πίνακας έχει άσσους στη διαγώνιο. Όμως για να ισχύει πρέπει ο να έχει εκεί που ο έχει
Άρα
Με την ίδια λογική ο θα πρέπει να έχει στη διαγώνιο εκεί που ο ή ο έχει
Άρα
Συνεχίζοντας επαγωγικά καταλήγουμε ότι
Αν υποθέσουμε ότι για κάθε πίνακα ισχύει τότε καταλήγουμε ότι , άτοπο
Άρα πάντα υπάρχει τουλάχιστον ένας πίνακας με
Σημείωση: Η παραπάνω κατασκευή υπέθεσε μια μετάθεση των πινάκων, γι' αυτό καταλήγει ότι αναγκαστικά ο τελευταίος πρέπει να είναι ο πίνακας με τη ζητούμενη ιδιότητα. Προφανώς οι ιδιότητες είναι συμμετρικές και ανεξάρτητες της σειράς των πινάκων οπότε οποιοσδήποτε (αλλά τουλάχιστον ένας) από τους πίνακες μπορεί (πρέπει) να έχει την ζητούμενη ιδιότητα.
τελευταία επεξεργασία από Summand σε Πέμ Μαρ 09, 2023 7:07 pm, έχει επεξεργασθεί 3 φορές συνολικά.
Νάκος Ιωάννης, ΗΜΜΥ ΑΠΘ
Re: IMC 2022
Θερμά συγχαρητήρια σε όλους τους φοιτητές μας για τη συμμετοχή και τα βραβεία (δεκαέξι!) που απέσπασαν, που είναι πολλά!
Ας μου επιτραπεί να αναφέρω εδώ τους τωρινούς φοιτητές του Πανεπιστημίου Αθηνών και παλιά μέλη της εθνικής ομάδας μαθητών πριν από χρόνια και διακριθέντες σε ΙΜΟ:
Τα συνολικά αποτέλεσμα είναι διαθέσιμα εδώ.
Φιλικά,
Αχιλλέας
Ας μου επιτραπεί να αναφέρω εδώ τους τωρινούς φοιτητές του Πανεπιστημίου Αθηνών και παλιά μέλη της εθνικής ομάδας μαθητών πριν από χρόνια και διακριθέντες σε ΙΜΟ:
- τον Δημήτρη Χρυσοβαλάντη Μελά, ο οποίος πέτυχε βαθμολογία 79/80, κατατάχτηκε 3ος ανάμεσα σε 664 συμμετέχοντες, και βραβεύτηκε με το Grand Grand First Prize, και
- τον Μίνο Μαργαρίτη, ο οποίος βραβεύτηκε με First Prize.
Τα συνολικά αποτέλεσμα είναι διαθέσιμα εδώ.
Φιλικά,
Αχιλλέας
-
- Δημοσιεύσεις: 786
- Εγγραφή: Σάβ Ιαν 17, 2015 1:04 pm
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες