IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

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

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

IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#1

Μη αναγνωσμένη δημοσίευση από Nick1990 » Πέμ Ιούλ 17, 2014 8:21 pm

Ανοίγω αυτό το τόπικ για να συζητήσουμε εδώ οτιδήποτε σχετικό με τον φετινό IMC που θα διεξαχθεί στο γνωστό μέρος (Blagoevgrad) μεταξύ 28 Ιουλίου και 4 Αυγούστου. Αρχίζω ανεβάζοντας 2 αρχεία με τα θέματα του προκριματικού του ΕΜΠ, όποιος θέλει ας ποστάρει λύσεις (αν και τα θέματα φαίνονται βατά):
τελευταία επεξεργασία από Demetres σε Παρ Ιούλ 18, 2014 6:25 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Αφαίρεση αρχείων και μεταφορά των προβλημάτων σε latex


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 17, 2014 10:00 pm

Θέματα Διαγωνισμού ΕΜΠ για τον IMC 2014

Άσκηση 1:

(α) Αν a,b,c θετικοί πραγματικοί αριθμοί να δείξετε ότι \displaystyle{ \frac{a}{b} + \frac{b}{c} + \frac{c}{a} \geqslant 3.}

(β) Έστω \varphi: \mathbb{R} \to (0,\infty) συνεχής περιοδική συνάρτηση με περίοδο T > 0 (δηλαδή \varphi(x) = \varphi(x+T) για κάθε x \in \mathbb{R}). Δείξτε ότι

\displaystyle{ \int_0^T \frac{\varphi(x+T/3)}{\varphi(x)} \, dx \geqslant T.}


Άσκηση 2:

(α) Έστω η ακολουθία \{x_n\}_{n \in \mathbb{N}} με x_1 > 1 και

\displaystyle{ x_{n+1} = \frac{x_n^2}{x_n-1}}

για n \in \mathbb{N}. Υπολογίστε το όριο \displaystyle{ \lim_{n \to \infty} \frac{x_n}{n}.}

(β) Δείξτε ότι η τιμή του ολοκληρώματος

\displaystyle{ I_n = \int_0^1 e^x\left( e^{x^n} + e^{\sqrt[n]{x}}\right) \, dx}

είναι ανεξάρτητη του n.


Άσκηση 3: Αν A,B \in \mathcal{M}_n(\mathbb{C}) και A^2+B^2 = 2AB να δείξετε ότι:

(α) Ο πίνακας AB-BA δεν είναι αντιστρέψιμος.

(β) Αν \mathrm{rank}(A-B) = 1 τότε AB=BA.


Άσκηση 4: Δείξτε ότι αν ένα σύνολο A \subseteq \mathbb{N}
(i) είναι κλειστό ως προς την πρόσθεση, δηλαδή m,n \in A \Rightarrow m+n \in A, και
(ii) έχει μέγιστο κοινό διαιρέτη των στοιχείων του το 1,
τότε περιέχει όλους τους φυσικούς που είναι μεγαλύτεροι από κάποιο n_0 \in \mathbb{N}.


Άσκηση 5: Στα επόμενα, αν X πεπερασμένο σύνολο, με |X| συμβολίζουμε τον πληθάριθμο του X και αν x \in \mathbb{R} με \lceil x \rceil συμβολίζουμε τον μικρότερο ακέραιο που είναι μεγαλύτερος ή ίσος με x.

(i) Έστω N θετικός ακέραιος και \delta_1,\ldots,\delta_N πραγματικοί αριθμοί στο [0,1]. Θέτουμε \delta = (\delta_1 + \cdots + \delta_N)/N και υποθέτουμε ότι \delta > 0. Δείξτε ότι για κάθε 0 < \varepsilon < \delta έχουμε

\displaystyle{ |\{i \in \{1,2,\ldots,N\}: \delta_i > \delta - \varepsilon\}| \geqslant \varepsilon N.}

(ii) Έστω 0 < \delta \leqslant 1, Χ,Υ πεπερασμένα μη κενά σύνολα και D \subseteq X \times Y με |D| \geqslant \delta |X| |Y|. Για κάθε x \in X θέτουμε D_x = \{y\in Y: (x,y) \in D\}. Δείξτε ότι

\displaystyle{ \left|\left\{x \in X: |D_x| \geqslant \frac{\delta}{2} |Y|\right\}\right| \geqslant \frac{\delta}{2}|X|.}

(iii) Έστω m θετικός ακέραιος και 0 < \delta \leqslant 1. Έστω επίσης X,Y πεπερασμένα σύνολα με

\displaystyle{ |X| \geqslant \lceil 2m/\delta\rceil \binom{\lceil 2m/\delta\rceil}{m} } και \displaystyle{ |Y| = \lceil 2m/\delta\rceil}

Δείξτε ότι για κάθε D \subseteq X \times Y με |D| \geqslant \delta |X| |Y| υπάρχουν A \subseteq X και B \subseteq Y με |A| = |B| = m και A \times B \subseteq D.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 17, 2014 10:33 pm

Demetres έγραψε: Άσκηση 1:

(α) Αν a,b,c θετικοί πραγματικοί αριθμοί να δείξετε ότι \displaystyle{ \frac{a}{b} + \frac{b}{c} + \frac{c}{a} \geqslant 3.}

(β) Έστω \varphi: \mathbb{R} \to (0,\infty) συνεχής περιοδική συνάρτηση με περίοδο T > 0 (δηλαδή \varphi(x) = \varphi(x+T) για κάθε x \in \mathbb{R}). Δείξτε ότι

\displaystyle{ \int_0^T \frac{\varphi(x+T/3)}{\varphi(x)} \, dx \geqslant T.}
Κρίμα θα ήταν πολύ πιο όμορφο χωρίς την υπόδειξη του (α). Το (α) είναι απλή ΑΜ-ΓΜ. Αλλά μας προϊδεάζει για τα (β). Από το (α) παίρνουμε

\displaystyle{ \int_0^T \frac{\varphi(x+T/3)}{\varphi(x)} \, dx + \int_0^T \frac{\varphi(x+2T/3)}{\varphi(x+T/3)} \, dx + \int_0^T \frac{\varphi(x)}{\varphi(x+2T/3)} \, dx \geqslant 3T.}

Όμως τα τρία ολοκληρώματα είναι ίσα (απλή αλλαγή μεταβλητών και χρήση της περιοδικότητας) οπότε τελειώσαμε.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 17, 2014 10:41 pm

Demetres έγραψε: Άσκηση 2:

(α) Έστω η ακολουθία \{x_n\}_{n \in \mathbb{N}} με x_1 > 1 και

\displaystyle{ x_{n+1} = \frac{x_n^2}{x_n-1}}

για n \in \mathbb{N}. Υπολογίστε το όριο \displaystyle{ \lim_{n \to \infty} \frac{x_n}{n}.}
Παρατηρούμε ότι η (x_n) είναι γνησίως αύξουσα. Δεν μπορεί να τείνει σε κάποιο πεπερασμένο όριο \ell αφού τότε θα είχαμε \ell > 1 και \ell = \ell^2/(\ell-1), άτοπο. Οπότε τείνει στο +\infty και άρα ισχύει ότι
\displaystyle{ \lim_{n \to \infty} (x_{n+1}-x_n) = \lim_{n \to \infty} \left( \frac{x_n^2}{x_n - 1} - x_n\right) = \lim_{n \to \infty} \frac{x_n}{x_n-1} = \lim_{n \to \infty} \frac{1}{1-1/x_n} = 1.}

Οπότε οι συνθήκες του θεωρήματος Cesaro-Stolz ικανοποιούνται και παίρνουμε

\displaystyle{ \lim_{n\to \infty} \frac{x_n}{n} = \lim_{n \to \infty} (x_{n+1}-x_n) = 1.}


nikoszan
Δημοσιεύσεις: 952
Εγγραφή: Τρί Νοέμ 17, 2009 2:22 pm

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#5

Μη αναγνωσμένη δημοσίευση από nikoszan » Πέμ Ιούλ 17, 2014 10:56 pm

Z1 Α){\frac{a}{b} + \frac{b}{c} + \frac{c}{a} \ge 3\sqrt[3]{{\frac{a}{b}\frac{b}{c}\frac{c}{a}}} = 3}

B)Για την συνάρτηση f\left( x \right) = \frac{{\varphi \left( {x + \frac{T}{3}} \right)}}{{\varphi \left( x \right)}},x \in R ,ισχύει f\left( x \right)f\left( {x + \frac{T}{3}} \right)f\left( {x + \frac{{2T}}{3}} \right) = 1,\forall x \in R.
Έχουμε \left( {f\left( x \right) + f\left( {x + \frac{T}{3}} \right) + f\left( {x + \frac{{2T}}{3}} \right) \ge 3\sqrt[3]{{f\left( x \right)f\left( {x + \frac{T}{3}} \right)f\left( {x + \frac{{2T}}{3}} \right)}} = 3\sqrt[3]{1} = 3,\forall x \in R} \right) \Rightarrow
\Rightarrow \int\limits_0^{\frac{T}{3}} {\left( {f\left( x \right) + f\left( {x + \frac{T}{3}} \right) + f\left( {x + \frac{{2T}}{3}} \right)} \right)dx \ge \int\limits_0^{\frac{T}{3}} {3dx} }  \Rightarrow\int\limits_0^{\frac{T}{3}} {f\left( x \right)dx + } \int\limits_0^{\frac{T}{3}} {f\left( {x + \frac{T}{3}} \right)dx + \int\limits_0^{\frac{T}{3}} {f\left( {x + \frac{{2T}}{3}} \right)} } dx \ge T \Rightarrow

\begin{array}{l} 
 \Rightarrow \int\limits_0^{\frac{T}{3}} {f\left( x \right)dx + } \int\limits_{\frac{T}{3}}^{\frac{{2T}}{3}} {f\left( x \right)dx + \int\limits_{\frac{{2T}}{3}}^T {f\left( x \right)} } dx \ge T \Rightarrow \int\limits_0^T {f\left( x \right)} dx \ge T \Rightarrow \int\limits_0^T {\frac{{\varphi \left( {x + \frac{T}{3}} \right)}}{{\varphi \left( x \right)}}} dx \ge T\\ 
 
\end{array}.
Ν.Ζ.


nikoszan
Δημοσιεύσεις: 952
Εγγραφή: Τρί Νοέμ 17, 2009 2:22 pm

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#6

Μη αναγνωσμένη δημοσίευση από nikoszan » Πέμ Ιούλ 17, 2014 11:23 pm

Ζ2Β)
Είναι {I_n} = \int\limits_0^1 {{e^x}} \left( {{e^{{x^n}}} + {e^{\sqrt[n]{x}}}} \right){\mkern 1mu} dx = \int\limits_0^1 {{e^x}{e^{{x^n}}}} dx + \int\limits_0^1 {{e^x}} {e^{\sqrt[n]{x}}}dx:\left( 1 \right) και \int\limits_0^1 {{e^x}} {e^{\sqrt[n]{x}}}dx\mathop  = \limits_{\left( {dx = n{u^{n - 1}}du} \right)}^{\left( {u = \sqrt[n]{x}} \right)} \int\limits_0^1 {{e^{{u^n}}}} {e^u}n{u^{n - 1}}du = \int\limits_0^1 {{e^{{x^n}}}} {e^x}n{x^{n - 1}}dx:\left( 2 \right),οπότε
{I_n}\mathop  = \limits^{\left( {\left( 1 \right),\left( 2 \right)} \right)} \int\limits_0^1 {{e^x}{e^{{x^n}}}} dx + \int\limits_0^1 {{e^{{x^n}}}} {e^x}n{x^{n - 1}}dx = \int\limits_0^1 {\left( {{e^x}{e^{{x^n}}} + {e^{{x^n}}}{e^x}n{x^{n - 1}}} \right)} dx = \int\limits_0^1 {\left( {{e^{x + {x^n}}}\left( {1 + n{x^{n - 1}}} \right)} \right)} dx =
= {\int\limits_0^1 {\left( {{e^{x + {x^n}}}} \right)} ^\prime }dx = \left[ {{e^{x + {x^n}}}} \right]_0^1 = {e^2} - 1 ( ανεξάρτητη του n).
Ν.Ζ.


Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 4518
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα, Βαρκελώνη
Επικοινωνία:

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#7

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Πέμ Ιούλ 17, 2014 11:27 pm

nikoszan έγραψε:Ζ2Β)
Είναι {I_n} = \int\limits_0^1 {{e^x}} \left( {{e^{{x^n}}} + {e^{\sqrt[n]{x}}}} \right){\mkern 1mu} dx = \int\limits_0^1 {{e^x}{e^{{x^n}}}} dx + \int\limits_0^1 {{e^x}} {e^{\sqrt[n]{x}}}dx:\left( 1 \right) και \int\limits_0^1 {{e^x}} {e^{\sqrt[n]{x}}}dx\mathop  = \limits_{\left( {dx = n{u^{n - 1}}du} \right)}^{\left( {u = \sqrt[n]{x}} \right)} \int\limits_0^1 {{e^{{u^n}}}} {e^u}n{u^{n - 1}}du = \int\limits_0^1 {{e^{{x^n}}}} {e^x}n{x^{n - 1}}dx:\left( 2 \right),οπότε
{I_n}\mathop  = \limits^{\left( {\left( 1 \right),\left( 2 \right)} \right)} \int\limits_0^1 {{e^x}{e^{{x^n}}}} dx + \int\limits_0^1 {{e^{{x^n}}}} {e^x}n{x^{n - 1}}dx = \int\limits_0^1 {\left( {{e^x}{e^{{x^n}}} + {e^{{x^n}}}{e^x}n{x^{n - 1}}} \right)} dx = \int\limits_0^1 {\left( {{e^{x + {x^n}}}\left( {1 + n{x^{n - 1}}} \right)} \right)} dx =
= {\int\limits_0^1 {\left( {{e^{x + {x^n}}}} \right)} ^\prime }dx = \left[ {{e^{x + {x^n}}}} \right]_0^1 = {e^2} - 1 ( ανεξάρτητη του n).
Ν.Ζ.
Με προλάβατε κ. Νίκο... στη στροφή.
Την ώρα που πήγα να το γράψω... Κρίμα.. δε πειράζει.


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 18, 2014 12:16 pm

Demetres έγραψε:
Άσκηση 3: Αν A,B \in \mathcal{M}_n(\mathbb{C}) και A^2+B^2 = 2AB να δείξετε ότι:

(α) Ο πίνακας AB-BA δεν είναι αντιστρέψιμος.

(β) Αν \mathrm{rank}(A-B) = 1 τότε AB=BA.
(α) Η συνθήκη δίνει (A-B)^2 = AB-BA. Αν λοιπόν AB-BA αντιστρέψιμος τότε είναι και ο A-B αντιστρέψιμος. Έστω λοιπόν X ώστε (A-B)X = I. Τότε AX-BX = I. Η συνθήκη όμως δίνει επίσης ότι A(A-B) = (A-B)B και πολλαπλασιάζοντας και τα δύο μέρη από αριστερά και από δεξιά με X παίρνουμε XA = BX. Οπότε καταλήγουμε στο AX-XA = I το οποίο είναι αδύνατον αφού \mathrm{tr}(AX-XA) = 0 ενώ \mathrm{tr}(I) = n.

(β) Αν \mathrm{rank}(A-B) = 1 τότε υπάρχουν n \times 1 διανύσματα u,v ώστε A-B = uv^T. Τότε είναι

\displaystyle{ AB-BA = (A-B)^2 = u(v^Tu)v = u(\mathrm{tr}(A-B))v^T = (A-B)\mathrm{tr}(A-B)}

Επομένως \displaystyle{ 0 =  \mathrm{tr}(AB-BA) = (\mathrm{tr}(A-B))^2 } άρα \mathrm{tr}(A-B) = 0 και άρα όντως AB=BA.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#9

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 18, 2014 1:03 pm

Demetres έγραψε: Άσκηση 4: Δείξτε ότι αν ένα σύνολο A \subseteq \mathbb{N}
(i) είναι κλειστό ως προς την πρόσθεση, δηλαδή m,n \in A \Rightarrow m+n \in A, και
(ii) έχει μέγιστο κοινό διαιρέτη των στοιχείων του το 1,
τότε περιέχει όλους τους φυσικούς που είναι μεγαλύτεροι από κάποιο n_0 \in \mathbb{N}.
Έστω m \in A και έστω p_1,\ldots,p_k οι πρώτοι διαιρέτες του m. Από το (ii) μπορούμε να βρούμε m_1,\ldots,m_k \in A με p_i \nmid m_i για κάθε i. Άρα είναι \mathrm{gcd}(m,m_1,\ldots,m_k) = 1. Τότε μπορώ να βρω a,a_1,\ldots,a_k \in \mathbb{Z} ώστε am + a_1m_1 + \cdots + a_km_k = 1.

Θέτοντας a_i' = a_i + t_im όπου t_i αρκετά μεγάλος θετικός ακέραιος, μπορώ να βρω θετικούς ακεραίους a_1',\ldots, a_k' ώστε a_1' m_1 + \cdots + a_k' m_k \equiv 1 \bmod m. Άρα υπάρχει N_1 \equiv 1 \bmod m με N_1 \in A και ομοίως μπορώ να βρω Ν_1,\ldots,N_m \in A με N_i \equiv i \bmod m για κάθε i. Έστω N = \max\{N_1,\ldots,N_m\}. Τότε σίγουρα n \in A για κάθε n \geqslant N αφού μπορώ να γράψω n = N_i + tm όπου i \equiv n \bmod m και t μη αρνητικός ακέραιος.

Ουσιαστικά αυτό το πρόβλημα σχετίζεται με το πρόβλημα νομισμάτων του Frobenious.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#10

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 18, 2014 1:37 pm

Demetres έγραψε:
Άσκηση 5: Στα επόμενα, αν X πεπερασμένο σύνολο, με |X| συμβολίζουμε τον πληθάριθμο του X και αν x \in \mathbb{R} με \lceil x \rceil συμβολίζουμε τον μικρότερο ακέραιο που είναι μεγαλύτερος ή ίσος με x.

(i) Έστω N θετικός ακέραιος και \delta_1,\ldots,\delta_N πραγματικοί αριθμοί στο [0,1]. Θέτουμε \delta = (\delta_1 + \cdots + \delta_N)/N και υποθέτουμε ότι \delta > 0. Δείξτε ότι για κάθε 0 < \varepsilon < \delta έχουμε

\displaystyle{ |\{i \in \{1,2,\ldots,N\}: \delta_i > \delta - \varepsilon\}| \geqslant \varepsilon N.}

(ii) Έστω 0 < \delta \leqslant 1, Χ,Υ πεπερασμένα μη κενά σύνολα και D \subseteq X \times Y με |D| \geqslant \delta |X| |Y|. Για κάθε x \in X θέτουμε D_x = \{y\in Y: (x,y) \in D\}. Δείξτε ότι

\displaystyle{ \left|\left\{x \in X: |D_x| \geqslant \frac{\delta}{2} |Y|\right\}\right| \geqslant \frac{\delta}{2}|X|.}

(iii) Έστω m θετικός ακέραιος και 0 < \delta \leqslant 1. Έστω επίσης X,Y πεπερασμένα σύνολα με

\displaystyle{ |X| \geqslant \lceil 2m/\delta\rceil \binom{\lceil 2m/\delta\rceil}{m} } και \displaystyle{ |Y| = \lceil 2m/\delta\rceil}

Δείξτε ότι για κάθε D \subseteq X \times Y με |D| \geqslant \delta |X| |Y| υπάρχουν A \subseteq X και B \subseteq Y με |A| = |B| = m και A \times B \subseteq D.
Καλό, αλλά πάλι τα (i),(ii) βοηθάνε στο (iii) που είναι το κύριο ερώτημα. Τέτοιες τεχνικές πάντως χρησιμοποιούνται συχνά στην συνδυαστική οπότε καλό είναι να γνωρίζουμε την μέθοδο.

(i) Έστω S=\{i \in \{1,2,\ldots,N\}: \delta_i > \delta - \varepsilon\}. Τότε αν i \in S είναι \delta_i \leqslant 1 ενώ αν i \notin S είναι \delta_i \leqslant \delta - \varepsilon. Οπότε

\displaystyle{ \delta N = \delta_1 + \cdots + \delta_N \leqslant |S| \cdot 1 + (N-|S|)(\delta - \varepsilon) \leqslant |S| + N(\delta - \varepsilon)}

οπότε το ζητούμενο έπεται.

(ii) Ακριβώς ίδια λογική. Αν T το δεδομένο σύνολο τότε είναι

\displaystyle{ \delta|X||Y| \leqslant |D| = \sum_{x \in X} |D_x| \leqslant |T||Y| + \frac{\delta}{2}|Y||X|}

και πάλι το ζητούμενο έπεται.

(iii) Θεωρούμε όλα τα x \in X για τα οποία |D_x| \geqslant \delta|Y|/2. Από το (ii) έχουμε τουλάχιστον \delta|X|/2 τέτοια x. Επειδή (\delta/2)  \lceil 2m/\delta\rceil \geqslant m έχουμε τουλάχιστον \displaystyle{m\binom{\lceil 2m/\delta\rceil}{m}} στοιχεία του x με |D_x| \geqslant m. Σε κάθε στοιχείο x \in X με |D_x| \geqslant m παίρνουμε ένα υποσύνολο B_x του Y με (x,y) \in D για κάθε y \in B_x. Έχουμε \displaystyle{m\binom{\lceil 2m/\delta\rceil}{m}} τέτοια υποσύνολα. Όμως το Y έχει ακριβώς \displaystyle{\binom{\lceil 2m/\delta\rceil}{m}} υποσύνολα μεγέθους m. Οπότε κάποιο από αυτά τα υποσύνολα εμφανίζεται m φορές ως B_x. Τώρα θέτουμε ως B αυτό το υποσύνολο του Y και ως A παίρνουμε m στοιχεία x\in X με B_x = B.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#11

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 18, 2014 3:36 pm

Demetres έγραψε:
(iii) Έστω m θετικός ακέραιος και 0 < \delta \leqslant 1. Έστω επίσης X,Y πεπερασμένα σύνολα με

\displaystyle{ |X| \geqslant \lceil 2m/\delta\rceil \binom{\lceil 2m/\delta\rceil}{m} } και \displaystyle{ |Y| = \lceil 2m/\delta\rceil}

Δείξτε ότι για κάθε D \subseteq X \times Y με |D| \geqslant \delta |X| |Y| υπάρχουν A \subseteq X και B \subseteq Y με |A| = |B| = m και A \times B \subseteq D.
Θα δείξω και έναν άλλο τρόπο που οδηγεί σε καλύτερο αποτέλεσμα.

Θα δείξω ότι αν \displaystyle{ |Y| = \lceil 2m/\delta\rceil}, D \subseteq X \times Y με |D| \geqslant \delta|X||Y| και δεν υπάρχουν A \subseteq X,B \subseteq Y με |A|=|B| = m και A \times B \subseteq D, τότε

\displaystyle{ |X| \leqslant \frac{m-1}{\binom{2m}{m}} \binom{\lceil 2m/\delta\rceil}{m}.}

Φτιάχνουμε ένα διμερές γράφημα με μέρη τα X και Y και ακμή από το x\in X στο y \in Y αν και μόνο αν (x,y) \in D.

Μετρούμε τώρα όλες τις δυάδες της μορφής (x,\{y_1,\ldots,y_m\}) όπου x\in X, y_1,\ldots,y_m είναι διακεκριμένα στοιχεία του Y και (x,y_i) \in D για κάθε i. Από την μία και κάθε υποσύνολο \{y_1,\ldots,y_m\} του Y μεγέθους m έχουμε το πολύ m-1 τέτοια x. (Αφού αλλιώς θα μπορούσαμε να βρούμε τα A \subseteq X,B \subseteq Y με |A|=|B| = m και A \times B \subseteq D.) Από την άλλη, αν d_x ο βαθμός της κορυφής x \in X τότε έχουμε ακριβώς \displaystyle{ \sum_{x\in X} \binom{d_x}{m}} τέτοιες δυάδες. Οπότε

\displaystyle{ (m-1)\binom{\lceil 2m/\delta\rceil}{m} = (m-1)\binom{|Y|}{m} \geqslant \sum_{x\in X} \binom{d_x}{m} \geqslant |X|  \binom{\frac{1}{|X|}\sum_{x \in X}d_x}{m} \geqslant |X| \binom{\delta|Y|}{m} \geqslant |X| \binom{2m}{m}}.

Ο ισχυρισμός έπεται.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#12

Μη αναγνωσμένη δημοσίευση από Nick1990 » Πέμ Ιούλ 31, 2014 4:59 pm

Σήμερα ήταν η πρώτη μέρα του διαγωνισμού. Αν μάθει κάποιος τα προβλήματα, ας τα βάλει εδώ!


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#13

Μη αναγνωσμένη δημοσίευση από Nick1990 » Πέμ Ιούλ 31, 2014 5:23 pm

Στο τελευταίο link εδώ μπήκαν τα προβλήματα αλλά δε μπορώ να τα δω από κινητό. Αν θέλει κάποιος ας τα μεταφέρει εδώ.

http://www.artofproblemsolving.com/Foru ... 9&t=568023


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#14

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 31, 2014 5:26 pm

Νίκο θα τα μεταφράσω εγώ. Θα ανοίξω καινούργιο θέμα για κάθε άσκηση.

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


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#15

Μη αναγνωσμένη δημοσίευση από Nick1990 » Παρ Αύγ 01, 2014 6:01 pm

Μπήκαν και αυτά της 2ης μέρας εδώ: http://clph.elte.hu/imc/IMC2014-day2-questions.pdf

Έχω ανοίξει θέματα για τα 1,2 και 3. Όποιος έχει χρόνο ας μεταφράσει και τα 2 τελευταία.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#16

Μη αναγνωσμένη δημοσίευση από Nick1990 » Σάβ Αύγ 02, 2014 11:14 pm

Ενημερωτικά, ο πρωτοετής φοιτητής που εκπροσώπησε το ΕΜΠ έχει σκορ 70/100 και το καλύτερο ranking που έχει κάνει Έλληνας φοιτητής στο διαγωνισμό (σίγουρο χρυσό). Έλυσε και το 5 της 1ης μέρας που ήταν ένα δύσκολο θέμα, παρά τη γενικότερη ευκολία των άλλων θεμάτων. Συγχαρητήρια


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#17

Μη αναγνωσμένη δημοσίευση από Nick1990 » Δευ Αύγ 04, 2014 7:55 pm

Τελικά ο Ορέστης Πλευρακης πήρε χρυσό με 60/100. Του είχαν χρεώσει μια λύση που δεν είχε κανει στο 5 της 1ης μέρας. Από εκεί και πέρα είχαμε και αργυρά και χάλκινα. Πολλά συγχαρητήρια. Αν μπορεί κάποιος ας τα βάλει αναλυτικά γιατί γράφω από κινητό


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#18

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 06, 2014 9:53 pm

Με κάποια καθυστέρηση συγχαρητήρια στον Ορέστη αλλά και στους υπόλοιπους διακριθέντες. Εύχομαι ανάλογες και καλύτερες επιτυχίες στο μέλλον.


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

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#19

Μη αναγνωσμένη δημοσίευση από Nick1990 » Παρ Αύγ 08, 2014 10:19 pm

Αναλυτικά τα αποτελέσματα των Ελλήνων, μιας και τώρα έχω pc:

Πλευράκης Ορέστης, 3ο έτος ΗΜΜΥ - ΕΜΠ: Χρυσό

Κωνσταντίνος Κάρτας, 2ο έτος Μαθηματικό ΑΠΘ - slash στο mathematica: Αρυγρό

Κώστας Ψαρομήλιγκος, Μαθηματικό ΈΚΠΑ: Αργυρό

Μπόλκας Ελευθέριος, Μαθηματικό ΕΚΠΑ: Χάλκινο

Φαίδονας Ανδριόπουλος, Μαθηματικό ΕΚΠΑ: Χάλκινο

Φοίβος Κατσετσιάδης, ΑΠΘ (δεν ξέρω σχολή - έτος): Εύφημη μνεία

Παναγιώτης Παπαδόπουλος, ΑΠΘ (δεν ξέρω σχολή): Εύφημη μνεία

Συγχαρητήρια σε όλους.
τελευταία επεξεργασία από Nick1990 σε Τετ Αύγ 13, 2014 3:04 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Κολλιοπουλος Νικος.
Μεταδιδακτορικός ερευνητής.
Ερευνητικά ενδιαφέροντα: Στοχαστικές ΜΔΕ, ασυμπτωτική ανάλυση στοχαστικών συστημάτων, εφαρμογές αυτών στα χρηματοοικονομικά και στη διαχείριση ρίσκων.
Natassa Liapaki
Δημοσιεύσεις: 1
Εγγραφή: Τρί Αύγ 12, 2014 3:33 pm

Re: IMC 2014: Θέματα, Θέματα Προκριματικών, σχόλια κτλ

#20

Μη αναγνωσμένη δημοσίευση από Natassa Liapaki » Τρί Αύγ 12, 2014 3:38 pm

Καλησπέρα σας,

επικοινωνώ μαζί σας από το GoodNews, το πρώτο συνδρομητικό πρακτορείο που μεταδίδει μόνο Καλές Ειδήσεις για την Ελλάδα. Θα μπορούσατε να μας στείλετε άμεσα μια φωτογραφία της ελληνικής αποστολής στη μαθηματική ολυμπιάδα για φοιτητές Πανεπιστημίου;

Ευχαριστούμε.

Υ.Γ. Άλλος ένας φοιτητής διακρίθηκε, ο οποίος έχει παραλειφθεί παραπάνω: Faidon Andriopoulos, National and Kapodistrian University of Athens third prize

Με εκτίμηση,

Νατάσα Λιαπάκη
goodnewsgreece@gmail.com
https://www.facebook.com/GoodNewsGR


Απάντηση

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

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

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