Προκριματικός ΕΜΠ για IMC 2013

Συντονιστής: Demetres

Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Προκριματικός ΕΜΠ για IMC 2013

#1

Μη αναγνωσμένη δημοσίευση από Nick1990 » Παρ Μάιος 17, 2013 1:29 pm

Ανοίγω αυτό το θέμα για να ενημερώσω τους φοιτητές του ΕΜΠ που παρακολουθούν το forum για τον προκριματικό αλλά και για να συζητήσουμε τα θέματα σε 2 εβδομάδες.

Η Επίσημη ανακοίνωση: http://147.102.206.2/imc_2013.pdf


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: Προκριματικός ΕΜΠ για IMC 2013

#2

Μη αναγνωσμένη δημοσίευση από Nick1990 » Δευ Ιουν 03, 2013 4:12 pm

Ο διαγωνισμός είχε 5 θέματα, 2 εκ των οποίων ήταν αποδείξεις θεωρημάτων που σχετίζονταν με παρεμβολή Lagrange και ομοιόμορφη σύγκλιση. Τα άλλα ήταν τα 3 - ίσως αρκετά γνωστά - παρακάτω προβλήματα:



1) Έστω I ο n \times n μοναδιαίος πίνακας και J ο αντίστοιχος τετραγωνικός πίνακας με όλα τα στοιχεία του ίσα με 1.

α) Νδο det(aI + bJ) = a^{n-1}(a + nb)

β) Να δειχτεί ότι αν υπάρχει n \times m πραγματικός πίνακας A ώστε AA^{T}=aI + bJ με a,b > 0, τότε m \geq n

γ) Να δειχτεί ότι αν a,b > 0 τότε για κάθε m \geq n υπάρχει πραγματικός n \times m πίνακας A ώστε AA^{T}=aI + bJ



2) Έστω f(x,y,z,w) = \frac{x}{x+y+w} + \frac{y}{x+y+z} + \frac{z}{z+w+y} + \frac{w}{x+z+w}

Νδο 1 < f(x,y,z,w) < 2 και να βρεθεί το σύνολο τιμών της

* Είναι το 5ο από την IMO του 1974. Υπάρχει και στον Engel και νομίζω ότι δεν έχει ιδιαίτερη δυσκολία (βέβαια, άλλα τα δεδομένα του 74 σε σχέση με σήμερα).


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

Έστω n άρτιος θετικός ακέραιος, να δειχτεί ότι το πολυώνυμο:

P(x) = (x^2 - 2x + 10)(x^2 - 4x + 40)...(x^2 - 2nx + 10n^2) + 1

είναι ανάγωγο στο Z[x]


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8586
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Προκριματικός ΕΜΠ για IMC 2013

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιουν 03, 2013 6:05 pm

Nick1990 έγραψε: 3) Το όμορφο πρόβλημα του διαγωνισμού (προσωπικά αν και νομίζω πως έχω δει κάτι παρόμοιο εδώ στο :logo: , ακόμα και 3 μέρες μετά το διαγωνισμό δεν έχω καμία ιδέα για το πως λύνεται... έχω σκεφτεί κάποια πράγματα αλλά δε φαίνονται να προχωράνε, ίσως όμως να είναι απλό και να μη βλέπω κάτι):

Έστω n άρτιος θετικός ακέραιος, να δειχτεί ότι το πολυώνυμο:

P(x) = (x^2 - 2x + 10)(x^2 - 4x + 40)...(x^2 - 2nx + 10n^2) + 1

είναι ανάγωγο στο Z[x]
Παρόμοιο εδώ αλλά για την γενίκευση που είναι πιο κοντά σε αυτήν την άσκηση λείπει η λύση. Βρήκα μια λύση με παρόμοια λογική. Ελπίζω να είμαι σωστός.

Έστω ότι το ζητούμενο δεν ισχύει και ότι P(x) = Q(x)R(x) με τα Q,R να έχουν συντελεστές στο \mathbb{Z} και να έχουν βαθμό μικρότερο του 2n.

Τότε Q(m \pm 3m i)R(m \pm 3m i) = 1 για κάθε m \in \{1,2,\ldots,n\} και αφού Q(m \pm 3m i),R(m \pm 3m i) \in \mathbb{Z}<em class="text-italics"> πρέπει Q(m \pm 3m i) \in \{1,-1,i,-i\} και επιπλέον πρέπει Q(m \pm 3m i) = \overline{R(m \pm 3m i)}

Τότε όμως το πολυώνυμο F(x) = Q(x) - R(x) = Q(x) - \overline{R}(x) (*) έχει βαθμο το πολύ \max\{\mathrm{deg}(Q),\mathrm{deg}(R)\} < 2n και έχει ως ρίζες όλα τα m \pm 3m i με m \in \{1,2,\ldots,n\}. Πρέπει λοιπόν απαραίτητα το F να είναι το μηδενικό πολυώνυμο.

Τότε είναι P(x) = R(x)^2 που δίνει R(0)^2 = 10^n (n!)^2 + 1 το οποίο είναι άτοπο αφού το n είναι άρτιος. [Αλλιώς θα είχαμε μη μηδενικούς ακεραίος a,b με a^2 = b^2 + 1 το οποίο δεν ισχύει.]

Έχω την υποψία ότι είναι αρκετά απίθανο να παραγοντοποιείται ακόμη και στην περίπτωση που ο n είναι περιττός. Αν n = 2m+1 τότε θα πρέπει R(0)^2 - 10((2m+1)!10^{m})^2 = 1. Θεωρώντας την εξίσωση Pell: x^2 - 10y^2 = 1 της οποίας οι λύσεις είναι γνωστό πως να βρεθούν αρκεί να δειχθεί πως δεν υπάρχουν λύσεις με y = (2m+1)!10^m. (Εκτός ίσως από πεπερασμένες περιπτώσεις;) Δεν το έψαξα περισσότερο.

(*) Εδώ υπάρχει λάθος. Το αφήνω όμως ως σκέψη μιας και ελπίζω να είναι κοντά στην λύση.


Άβαταρ μέλους
silouan
Επιμελητής
Δημοσιεύσεις: 1303
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Προκριματικός ΕΜΠ για IMC 2013

#4

Μη αναγνωσμένη δημοσίευση από silouan » Δευ Ιουν 03, 2013 7:15 pm

Θυμίζει αυτό το πρόβλημα viewtopic.php?f=58&t=36924&p=170127#p170127


Σιλουανός Μπραζιτίκος
Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: Προκριματικός ΕΜΠ για IMC 2013

#5

Μη αναγνωσμένη δημοσίευση από Nick1990 » Δευ Ιουν 03, 2013 7:53 pm

Νομίζω βρήκα λύση δουλεύοντας στο Z. Θα τη γράψω αύριο από pc διότι από κινητό δε βολεύει

Για την ώρα ένα hint:

Τα στοιχεία i+1, 1-i, 2 δεν έχουν διαιρετη στο Z με φανταστικό μέρος μη μηδενικό πολλαπλάσιο του 3. Από αυτό μπορεί να δειχτεί ότι n=2


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8586
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Προκριματικός ΕΜΠ για IMC 2013

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Ιουν 04, 2013 10:15 am

Προσπάθεια 2η:

Έστω ότι το ζητούμενο δεν ισχύει και ότι P(x) = Q(x)R(x) με τα Q,R να έχουν συντελεστές στο \mathbb{Z} και να έχουν βαθμό μικρότερο του 2n.

Τότε Q(m \pm 3m i)R(m \pm 3m i) = 1 για κάθε m \in \{1,2,\ldots,n\} και αφού Q(m \pm 3m i),R(m \pm 3m i) \in \mathbb{Z}<em class="text-italics"> πρέπει Q(m \pm 3m i) \in \{1,-1,i,-i\}.

Κάνοντας ευκλείδια διαίρεση στον πολυωνιμικό δακτύλιο \mathbb{Z}[x] μπορώ να γράψω

Q(x) = (x^2 + 2mx + 10m^2)T(x) + ax + b

για κάποιο T(x) \in \mathbb{Z}[x] και κάποια a,b \in  \mathbb{Z}. Αφού Q(m + 3mi) \in \{1,-1,i,-i\} πρέπει a(m+3mi) + b \in \{1,-1,i,-i\} και κοιτάζοντας τα φανταστικά μέρη, πρέπει a=0 και άρα πρέπει Q(m + 3mi) \in \{1,-1\}. Επειδή επιπλέον Q(m + 3mi)R(m + 3mi) = 1 θα ισχύει ότι Q(m + 3mi)=R(m + 3mi). Ομοίως ισχύει ότι Q(m - 3mi)=R(m - 3mi) για κάθε m \in \{1,2,\ldots,n\}.

Κοιτάμε τώρα το πολυώνυμο F(x) = Q(x) - R(x) το οποίο έχει βαθμό μικρότερο του 2n αλλά έχει ως ρίζες όλα τα m \pm 3m i με m \in \{1,2,\ldots,n\} οπότε απαραίτητα το F είναι το μηδενικό πολυώνυμο.

Τότε είναι P(x) = R(x)^2 που δίνει R(0)^2 = 10^n (n!)^2 + 1 το οποίο είναι άτοπο αφού το n είναι άρτιος. [Αλλιώς θα είχαμε μη μηδενικούς ακεραίος a,b με a^2 = b^2 + 1 το οποίο δεν ισχύει.]


Άβαταρ μέλους
Nick1990
Δημοσιεύσεις: 659
Εγγραφή: Παρ Ιαν 23, 2009 3:15 pm
Τοποθεσία: Peking University, Πεκίνο

Re: Προκριματικός ΕΜΠ για IMC 2013

#7

Μη αναγνωσμένη δημοσίευση από Nick1990 » Τρί Ιουν 04, 2013 4:16 pm

Γράφω και τη δική μου σκέψη:

Έστω n=2k και P(x)=Q(x)R(X) με deg(Q) = d < 2n = 4k. Έστω ακόμα k>1.

Επειδή για όλα τα y = a \pm 3a θα είναι Q(y)R(y) = 1 με R(y), Q(y) \in \mathbb{Z}<em class="text-italics">, πρέπει Q(y) \in \{1, -1, i, -i\} για όλους αυτούς τους y που είναι 4k το πλήθος. Για κάποια από αυτές τις 4 μονάδες του δακτυλίου \mathbb{Z}<em class="text-italics"> θα αντιστοιχούν s \geq k \geq 2 αριθμοί από τους y που αναφέραμε παραπάνω, έστω χωρίς βλάβη ότι αυτό γίνεται για το i. Τότε θα πρέπει Q(x) - i = Q'(x)(x - y_1)...(x - y_m) με τα y_j διακεκριμένα, οπότε θέτοντας όπου x ένα y που αντιστοιχεί σε άλλη μονάδα (αν υπάρχει) θα έχουμε στο ένα μέλος ένα στοιχείο z \in \{1+i, 1-i, -i-1, -i+1, 2i, 2, -2i, -2\}, όταν το άλλο θα έχει 2 διαφορετικούς διαιρέτες y - y_l, x - y_j με y = a + 3bi, y_l = c + 3di, y_j = e + 3fi και |a|=|b|, |c| = |d|, |e|=|f|. Οι δύο αυτοί διαιρέτες για να διαιρούν το z δε μπορούν να έχουν φανταστικό μέρος μη μηδενικό πολλαπλάσιο του 3, οπότε πρέπει b - f = b - d = 0 \Rightarrow b=d=f \Rightarrow a = \pm b = \pm d = \pm c όπου ο y - y_l δε μπορεί να είναι 0 οπότε θα πρέπει a = -c και με την ίδια λογική a = -e. Άρα y_l = c + di = -a + bi = e + fi = y_j άτοπο. Άρα για να μην έχουμε άτοπο πρέπει το y που αναφέραμε πιο πάνω να μην υπάρχει, οπότε τότε το Q(x) - i έχει 2n ρίζες, άρα είναι είτε μηδενικό είτε βαθμού 2n που είναι πάλι άτοπο.

Άρα πρέπει k=1 που δίνει P(x) = (x^2 - 2x + 10)(x^2 - 4x + 40) + 1 = x^4 - 6x^3 + 58x^2 - 120x + 401

Όπως είδαμε δεν έχει πραγματικές ρίζες, άρα αφού είναι μονικό αν δεν είναι ανάγωγο στους ακεραίους θα διαιρείται με κάποια R(x) =x^2 + ax + b και Q(x) = x^2 + cx + d.
Επειδή αυτά δε θα έχουν πραγματικές ρίζες θα είναι b,d >0 οπότε με εξίσωση συντελεστών θα πρέπει (αν χβτγ b \geq d) b= 401, d = 1 και ακόμα: bc + ad = 401c + a = -120 \Rightarrow a = -120 - 401c και 58 = 401 + 1 + ac = 402 - 120c - 401c^2 \Rightarrow 401c^2 + 120c - 344 = 0 που εύκολα δεν έχει ακέραιες ρίζες. Άρα το P είναι ανάγωγο.


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης