IMC 2011

Nick1990

Ανοίγω το θέμα αυτό καθώς αύριο η ομάδα μας (ομάδα ΕΜΠ) μαζί με την ομάδα του Μαθηματικού τμήματος του ΕΚΠΑ, αναχωρούμε για το Μπλαγκόεβγκραντ της Βουλγαρίας όπου θα πραγματοποιηθεί ο διαγωνισμός IMC 2011.
Εδώ θα βάλουμε τα θέματα των 2 ημερών του διαγωνισμού, θα προτείνουμε λύσεις, και θα συζητήσουμε οτιδήποτε άλλο σχετικό με το διαγωνισμό.

Καλή σας επιτυχία!!

Φιλικά,

Αχιλλέας

Καλή επιτυχία και από εμένα.

S.E.Louridas

Καλή επιτυχία !!!!

Σ.Ε.Λουρίδας

Καλό ταξίδι και καλή επιτυχία !!!

Να χαρείτε τη συμμετοχή σας , χωρίς άγχος , και όλα τα άλλα θα έρθουν μόνα τους.

Μπάμπης

Καλή επιτυχία!
Εύχομαι ότι καλύτερο!

Νίκος Κατσίπης

Ό,τι καλύτερο και από μένα στους συμμετέχοντες!

kwstas12345

Καλή επιτυχια, στην ελληνική ομάδα για αύριο.

Καλή επιτυχία παιδιά!!!

nikoszan

Καλη επιτυχια σε ολα τα παιδια της Ελληνικης ομαδας.
Ν.Ζ.

Eukleidis

ΠΡΟΒΛΗΜΑΤΑ ΜΕΡΑΣ ΠΡΩΤΗΣ

Πρόβλημα 1

Έστω συνεχής συνάρτηση $\displaystyle{f:\mathbb{R} \to \mathbb{R}}$ . Ένα σημείο $\displaystyle{x}$ λέγεται σκιώδες αν υπάρχει σημείο y > x

ώστε $\displaystyle{f\left( y \right) > f\left( x \right)}$ . Έστω οι πραγματικοί $\displaystyle{a < b}$ για τους οποίους

όλα τα σημεία του ανοικτού διαστήματος $\displaystyle{I = \left( {a,b} \right)}$ είναι σκιώδη σημεία.
τα $\displaystyle{a}$ και $\displaystyle{b}$ δεν είναι σκιώδη σημεία.

Αποδείξτε ότι:

α) $\displaystyle{f\left( x \right) \leqslant f\left( b \right)}$ για κάθε $\displaystyle{a < x < b}$ .
β) $\displaystyle{f\left( a \right) = f\left( b \right)}$ .

Πρόβλημα 2

Υπάρχει πραγματικός πίνακας $\displaystyle{A}$ , $\displaystyle{3 \times 3}$ ώστε $\displaystyle{tr\left( A \right) = 0}$ και $\displaystyle{{A^2} + {A^t} = I}$ ;

Πρόβλημα 3

Έστω $\displaystyle{p}$ ένας πρώτος αριθμός.Καλούμε ενδιαφέροντα έναν θετικό ακέραιο $\displaystyle{n}$ αν $\displaystyle{{x^n} - 1 = \left( {{x^p} - x + 1} \right)f\left( x \right) + pg\left( x \right)}$ για κάποια πολυώνυμα $\displaystyle{f,g}$ με ακέραιους συντελεστές.

α) Αποδείξτε ότι ο αριθμός $\displaystyle{{p^p} - 1}$ είναι ενδιαφέροντας.
β) Για ποιους

ο αριθμός $\displaystyle{{p^p} - 1}$ είναι ο μικρότερος ενδιαφέρων αριθμός.

Πρόβλημα 4

Έστω τα $\displaystyle{{A_1},{A_2},...,{A_n}}$ , τα οποία είναι πεπερασμένα, μη κενά σύνολα. Ορίστε τη συνάρτηση $\displaystyle{f(t) = \sum\limits_{k = 1}^n {\sum\limits_{1 \leqslant {i_1} < {i_2} < \ldots < {i_k} \leqslant n} {{{( - 1)}^{k - 1}}} } {t^{|{A_{{i_1}}} \cup {A_{{i_2}}} \cup \ldots \cup {A_{{i_k}}}|}}.}$ .
Αποδείξτε ότι η $\displaystyle{f}$ είναι μη φθίνουσα στο $\displaystyle{\left[ {0,1} \right]}$ .
(Το $\displaystyle{\left| A \right|}$ συμβολίζει τον αριθμό των στοιχείων του Α)

Πρόβλημα 5
Έστω

ένας θετικός ακέραιος και έστω

ένας

-διάστατος διανυσματικός χώρος υπέρ του σώματος των δύο στοιχείων. Να αποδειχθεί ότι για τυχόντα διανύσματα $v_1,\dots,v_{4n-1} \in V,$ υπάρχει ακολουθία $1\leq i_1<\cdots<i_{2n}\leq 4n-1$ δεικτών έτσι ώστε $v_{i_1}+\dots+v_{i_{2n}}=0.$

ΠΡΟΒΛΗΜΑΤΑ ΜΕΡΑΣ ΔΕΥΤΕΡΗΣ

Πρόβλημα 1
Έστω $\displaystyle{\left( {{a_n}} \right) \subset \left( {\tfrac{1}{2},1} \right)}$ . Ορίστε την ακολουθία $\displaystyle{{x_0} = 0}$ , $\displaystyle{{x_{n + 1}} = \tfrac{{{a_{n + 1}} + {x_n}}}{{1 + {a_{n + 1}}{x_n}}}}$ . Συγκλίνει; Αν ναι, βρείτε το όριο της.

Πρόβλημα 2
Μια εξωγήινη φυλή έχει τρία φύλα: αρσενικό,θυληκό και ουδέτερο. Μια παντρεμένη τριάδα αποτελείται από τρία άτομα, ένα από κάθε φύλο, από τα οποία ο καθένας αρέσει στον άλλον. Κάθε άτομο επιτρέπεται να ανήκει στο πολύ μια παντρεμένη τριάδα. Τα αισθήματα είναι πάντα αμοιβαία. (Αν ο $\displaystyle{x}$ αρέσει τον $\displaystyle{y}$ , τότε ο $\displaystyle{y}$ αρέσει τον $\displaystyle{x}$ )

H φυλή θέλει να αποικήσει έναν πλανήτη, οποτε στέλνει $\displaystyle{n}$ αρσενικά, $\displaystyle{n}$ θυληκά και $\displaystyle{n}$ ουδέτερα. Κάθε μέλος της αποστολής αρέσει τουλάχιστον $\displaystyle{k}$ μέλη των υπολοίπων δύο φύλων. Το πρόβλημα είναι να δημιουργηθούν όσο το δυνατόν περισσότερες παντρεμένες τριάδες για να αποικήσουν τον πλανήτη.

α) Αποδείξτε ότι ότι αν ο $\displaystyle{n}$ είναι άρτιος και $\displaystyle{k \geqslant \tfrac{n}{2}}$ , τότε μπορεί να μην υπάρχει καμία παντρεμένη τριάδα.
β) Αποδείξτε ότι αν $\displaystyle{k \geqslant \tfrac{3}{4}n}$ , τότε μπορούν να δημιουργηθούν $\displaystyle{n}$ παντρεμένες τριάδες.

Πρόβλημα 3

Υπολογίστε το $\displaystyle{\sum\limits_{n = 1}^\infty {\ln \left( {1 + \tfrac{1}{n}} \right)\left( {1 + \tfrac{1}{{2n}}} \right)\left( {1 + \tfrac{1}{{2n + 1}}} \right)} }$

Διόρθωση: Υπολογίστε το $\displaystyle{\sum\limits_{n = 1}^\infty {\ln \left( {1 + \tfrac{1}{n}} \right)\ln{\left( {1 + \tfrac{1}{{2n}}} \right)}\ln{\left( {1 + \tfrac{1}{{2n + 1}}} \right)}} }$

Πρόβλημα 4

Έστω $\displaystyle{f}$ ένα πολυώνυμο με πραγματικούς συντελέστές βαθμού n. Έστω πως το κλάσμα $\displaystyle{\tfrac{{f\left( x \right) - f\left( y \right)}}{{x - y}}}$ είναι ακέραιο για κάθε $\displaystyle{0 \leqslant x < y \leqslant n}$ . Αποδείξτε ότι $\displaystyle{a - b|f\left( a \right) - f\left( b \right)}$ για κάθε διαφορετικά $\displaystyle{a,b}$ .

Πρόβλημα 5
Έστω $F=A_0A_1 \cdots A_n$ κυρτό πολύγωνο στο επίπεδο. Ορίζουμε για κάθε $1 \leq k \leq n-1$ την πράξη f_k

η οποία αντικαθιστά το

με ένα νέο πολύγωνο $f_k(F)=A_0A_1 \cdots A_{k-1}A{'}_k A_{k+1} \cdots A_n$ όπου το $A{'}_k$ είναι το συμμετρικό του A_k

ως προς την μεσοκάθετη της ευθείας $A_{k-1}A_{k+1}$ . Να αποδειχθεί ότι $(f_1\circ f_2 \circ f_3 \circ \cdots \circ f_{n-1})^n(F)=F$ .

Συγχωρέστε με για όποια λάθη στη μετάφραση ή τυπογραφικά.
Πηγή:http://mathproblems123.wordpress.com/

Κάτι δε μου παει καλά με το πρόβλημα 3 της δεύτερης μέρας. Κατ' αρχάς νομίζω ότι είναι κακός ο συμβολισμός.

Αν το γινόμενο ήταν όλο μες το λογάριθμο νομίζω θα ήταν καλύτερο να γραφτεί ως $\displaystyle{\ln\left((1+\frac{1}{n})(1+\frac{1}{2n})(1+\frac{1}{2n+1})\right)}$ .

Αν πάλι είναι μόνο η πρώτη παρένθεση μέσα στο λογάριθμο, νομίζω θα ήταν καλύτερο να γραφεί ως $\displaystyle{(1+\frac{1}{2n})(1+\frac{1}{2n+1})\ln(1+\frac{1}{n})}$ .

Όπως και νάχει, στην πρώτη περίπτωση έχουμε $\displaystyle{\ln\left((1+\frac{1}{n})(1+\frac{1}{2n})(1+\frac{1}{2n+1})\right)=\ln(1+\frac{2}{n}+\frac{1}{n^2})\sim\frac{2}{n}+\mathcal O(n^{-2})}$ , άρα $\displaystyle{\sum\ln\left((1+\frac{1}{n})(1+\frac{1}{2n})(1+\frac{1}{2n+1})\right)\sim\sum\frac{1}{n}+c=\infty}$

ενώ στη δεύτερη $\displaystyle{(1+\frac{1}{2n})(1+\frac{1}{2n+1})\ln(1+\frac{1}{n})=\left(1+\frac{1}{n}\right)\ln\left(1+\frac{1}{n}\right)\sim\frac{n+1}{n}\cdot\frac{1}{n}\sim\frac{1}{n}}$ , οπότε πάλι έχουμε $+\infty$ .

Το πρόβλημα 1 της πρώτης μέρας αν θυμάμαι καλά είναι γνωστό ως Λήμμα το Ανατέλλοντος Ηλίου και υπάρχει στο βιβλίο του Απειροστικού του Spivak και του Νεγρεπόντη.

Αναστάση, στην πηγή που το βρήκε ο Γιώργος έτσι ακριβώς το γράφει. Και εμένα μου φαίνεται περίεργο. Ιδίως διότι όπως και να ερμηνευθεί αποκλίνει αφού και το $\displaystyle{ \sum_{n=1}^{\infty} \ln{\left(1 + 1/n\right)}}$ αποκλίνει.

Κοτρώνης Αναστάσιος έγραψε:Το πρόβλημα 1 της πρώτης μέρας αν θυμάμαι καλά είναι γνωστό ως Λήμμα το Ανατέλλοντος Ηλίου και υπάρχει στο βιβλίο του Απειροστικού του Spivak και του Νεγρεπόντη.

Το 1 μου φάνηκε τελείως προφανές. Δεν χρειαζόταν καν η συνέχεια. Υπάρχει όμως λάθος στην μετάφραση. Εκεί που λέει «υπάρχει $y \in \mathbb{R}$ » πρέπει να λέει «υπάρχει y > x

». Θα το διορθώσω.

Eukleidis έγραψε: Πρόβλημα 2 (1ης μέρας)

Υπάρχει πραγματικός πίνακας $\displaystyle{A}$ , $\displaystyle{3 \times 3}$ ώστε $\displaystyle{tr\left( A \right) = 0}$ και $\displaystyle{{A^2} + {A^t} = I}$ ;

Ας υποθέσουμε πως υπάρχει. Θα συμβολίζω το A^t

με

. Τότε

, άρα

και άρα

, δηλαδή

. Η εξίσωση x^4 - 2x^2 + x = 0

έχει ρίζες τις 0,1

και $\displaystyle{ \frac{-1 \pm \sqrt{5}}{2}}$ . Επειδή όμως ο

είναι $3 \times 3$ πίνακας με tr(B) = tr(A) = 0

οι ιδιοτιμές του

πρέπει να είναι οι

και $\displaystyle{ \frac{-1 \pm \sqrt{5}}{2}}$ . Το ίδιο πρέπει να ισχύει και για τις ιδιοτιμές του

. Επειδή οι ιδιοτιμές του

είναι διακεκριμένες, υπάρχει αντιστρέψιμος πίνακας

ώστε $\displaystyle{P^{-1}AP = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \frac{-1 + \sqrt{5}}{2} & 0 \\ 0 & 0 & \frac{-1 - \sqrt{5}}{2}\end{pmatrix}.}$ Αλλά τότε θα είχαμε $\displaystyle{P^{-1}BP = I - P^{-1}A^2P = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -\frac{\sqrt{5}}{2} & 0 \\ 0 & 0 & \frac{\sqrt{5}}{2}\end{pmatrix}}$ . Αυτό είναι άτοπο αφού ο $P^{-1}BP$ πρέπει να είναι όμοιος με τον

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

Eukleidis έγραψε:
Πρόβλημα 4

Έστω τα $\displaystyle{{A_1},{A_2},...,{A_n}}$ , τα οποία είναι πεπερασμένα, μη κενά σύνολα. Ορίστε τη συνάρτηση $\displaystyle{f(t) = \sum\limits_{k = 1}^n {\sum\limits_{1 \leqslant {i_1} < {i_2} < \ldots < {i_k} \leqslant n} {{{( - 1)}^{k - 1}}} } {t^{|{A_{{i_1}}} \cup {A_{{i_2}}} \cup \ldots \cup {A_{{i_k}}}|}}.}$ .
Αποδείξτε ότι η $\displaystyle{f}$ είναι μη φθίνουσα στο $\displaystyle{\left[ {0,1} \right]}$ .
(Το $\displaystyle{\left| A \right|}$ συμβολίζει τον αριθμό των στοιχείων του Α)

Αυτή η άσκηση έχει σύντομη απόδειξη αν την δούμε από την σωστή μεριά.

Για κάθε $x \in A_1 \cup \cdots \cup A_n$ ρίχνουμε ένα νόμισμα το οποίο έχει πιθανότητα

να έρθει κορώνα. (Όλες οι ρίψεις ανεξάρτητες.) Έστω

το ενδεχόμενο τουλάχιστον σε ένα από τα από τα A_i

να έρθουν όλες οι ρίψεις κορώνες. Προφανώς το $\Pr(E)$ είναι αύξουσα συνάρτηση του

(στο

).

Για $I \subseteq [n]$ , έστω E_I

το ενδεχόμενο για κάθε $x \in \cup_{i\in I}A_i$ να φέρουμε κορώνα. (Όπου $[n] = \{1,\ldots,n\}$ .) Τότε $\Pr(E_i) = t^{|\cup_{i\in I}A_i|}$ . Άρα από την αρχή εγκλισμού-αποκλισμού έχουμε

$\displaystyle{ \Pr(E) = \sum_{I \subseteq [n]} (-1)^{|I|-1}\Pr(E_i) = f(t)}$

και άρα το f(t)

είναι όντως αύξουσα συνάρτηση στο [0,1]

.

Σβήνω την λύση λόγω σφάλματος. Νομίζω ότι μπαλώνεται, αλλά βλέπουμε...

Φιλικά,

Μιχάλης

Eukleidis έγραψε: Πρόβλημα 2
Μια εξωγήινη φυλή έχει τρία φύλα: αρσενικό,θυληκό και ουδέτερο. Μια παντρεμένη τριάδα αποτελείται από τρία άτομα, ένα από κάθε φύλο, από τα οποία ο καθένας αρέσει στον άλλον. Κάθε άτομο επιτρέπεται να ανήκει στο πολύ μια παντρεμένη τριάδα. Τα αισθήματα είναι πάντα αμοιβαία. (Αν ο $\displaystyle{x}$ αρέσει τον $\displaystyle{y}$ , τότε ο $\displaystyle{y}$ αρέσει τον $\displaystyle{x}$ )

H φυλή θέλει να αποικήσει έναν πλανήτη, οποτε στέλνει $\displaystyle{n}$ αρσενικά, $\displaystyle{n}$ θυληκά και $\displaystyle{n}$ ουδέτερα. Κάθε μέλος της αποστολής αρέσει τουλάχιστον $\displaystyle{k}$ μέλη των υπολοίπων δύο φύλων. Το πρόβλημα είναι να δημιουργηθούν όσο το δυνατόν περισσότερες παντρεμένες τριάδες για να αποικήσουν τον πλανήτη.

α) Αποδείξτε ότι ότι αν ο $\displaystyle{n}$ είναι άρτιος και $\displaystyle{k \geqslant \tfrac{n}{2}}$ , τότε μπορεί να μην υπάρχει καμία παντρεμένη τριάδα.
β) Αποδείξτε ότι αν $\displaystyle{k \geqslant \tfrac{3}{4}n}$ , τότε μπορούν να δημιουργηθούν $\displaystyle{n}$ παντρεμένες τριάδες.

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

Τα (όχι τελικά -preliminary) αποτελέσματα βρίσκονται εδώ. Από ότι φαίνεται για το συγκεκριμένο πρόβλημα παρόλο που το ήξεραν τα παιδιά δεν έλυσαν το συγκεκριμένο πρόβλημα.
http://www.artofproblemsolving.com/Foru ... 9&t=421313

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

με πραγματικούς συντελεστές έχει n+1

ακέραιες τιμές σε ακέραια σημεία, τότε το πολυώνυμο έχει ακεραίους συντελεστές.
Η απόδειξη είναι άμεση από το Lagrange Interpolation Formula.
Στη λύση της άσκησης τώρα.
Θεωρούμε το πολυώνυμο g(x)=f(x)-f(0)

. Τότε

και $1\leq i\leq n$
έχουμε από την συνθήκη (για x=0

, και

) ότι

είναι ακέραιος.
Επομένως το λήμμα εφαρμόζεται στο πολυώνυμο

, άρα το

έχει ακεραίους συντελεστές.
Τότε όμως είναι γνωστό ότι για οποιουσδήποτε ακεραίους a,b

έχουμε

που είναι και το ζητούμενο.

IMC 2011

IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

Re: IMC 2011

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