IMC 2011

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

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

IMC 2011

#1

Μη αναγνωσμένη δημοσίευση από Nick1990 » Τετ Ιούλ 27, 2011 6:00 pm

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


Κολλιοπουλος Νικος -- Απόφοιτος ΣΕΜΦΕ - ΕΜΠ, Υποψήφιος διδάκτωρ στο πανεπιστήμιο της Οξφόρδης

https://www.maths.ox.ac.uk/people/nikolaos.kolliopoulos
achilleas
Επιμελητής
Δημοσιεύσεις: 2624
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: IMC 2011

#2

Μη αναγνωσμένη δημοσίευση από achilleas » Τετ Ιούλ 27, 2011 9:10 pm

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

Φιλικά,

Αχιλλέας


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

Re: IMC 2011

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Ιούλ 27, 2011 11:20 pm

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


Άβαταρ μέλους
S.E.Louridas
Δημοσιεύσεις: 5335
Εγγραφή: Σάβ Μαρ 21, 2009 10:53 am
Τοποθεσία: Aegaleo.
Επικοινωνία:

Re: IMC 2011

#4

Μη αναγνωσμένη δημοσίευση από S.E.Louridas » Τετ Ιούλ 27, 2011 11:27 pm

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

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


S.E.Louridas

1.Μιλώ, μόνο όταν έχω να πώ κάτι καλύτερο από την σιωπή (Πυθαγόρας).
2.Οι αξίες αντανακλώνται, Δεν επιβάλλονται.
3.Είναι Κορυφαία η κάθε στιγμή επίλυσης ενός Μαθηματικού προβλήματος.
Μπάμπης Στεργίου
Επιμελητής
Δημοσιεύσεις: 5318
Εγγραφή: Δευ Δεκ 22, 2008 2:16 pm
Τοποθεσία: Χαλκίδα - Καρδίτσα

Re: IMC 2011

#5

Μη αναγνωσμένη δημοσίευση από Μπάμπης Στεργίου » Τετ Ιούλ 27, 2011 11:31 pm

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

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

Μπάμπης


Άβαταρ μέλους
nkatsipis
Επιμελητής
Δημοσιεύσεις: 757
Εγγραφή: Κυρ Δεκ 21, 2008 10:26 am
Τοποθεσία: Σαντορίνη
Επικοινωνία:

Re: IMC 2011

#6

Μη αναγνωσμένη δημοσίευση από nkatsipis » Πέμ Ιούλ 28, 2011 12:22 am

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

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


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: IMC 2011

#7

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Πέμ Ιούλ 28, 2011 1:11 am

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


Εσύ....; Θα γίνεις κανίβαλος....;
kwstas12345
Δημοσιεύσεις: 1055
Εγγραφή: Δευ Ιαν 11, 2010 2:12 pm

Re: IMC 2011

#8

Μη αναγνωσμένη δημοσίευση από kwstas12345 » Πέμ Ιούλ 28, 2011 3:51 am

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


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

Re: IMC 2011

#9

Μη αναγνωσμένη δημοσίευση από silouan » Παρ Ιούλ 29, 2011 9:27 am

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


Σιλουανός Μπραζιτίκος
nikoszan
Δημοσιεύσεις: 951
Εγγραφή: Τρί Νοέμ 17, 2009 2:22 pm

Re: IMC 2011

#10

Μη αναγνωσμένη δημοσίευση από nikoszan » Παρ Ιούλ 29, 2011 9:34 am

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


Eukleidis
Δημοσιεύσεις: 667
Εγγραφή: Τετ Ιούλ 01, 2009 9:55 pm
Τοποθεσία: Θεσσαλονίκη

Re: IMC 2011

#11

Μη αναγνωσμένη δημοσίευση από Eukleidis » Κυρ Ιούλ 31, 2011 1:21 pm

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

Πρόβλημα 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} είναι ενδιαφέροντας.
β) Για ποιους p ο αριθμός \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
Έστω n ένας θετικός ακέραιος και έστω V ένας (2n-1)-διάστατος διανυσματικός χώρος υπέρ του σώματος των δύο στοιχείων. Να αποδειχθεί ότι για τυχόντα διανύσματα 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 με ένα νέο πολύγωνο 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/
τελευταία επεξεργασία από Eukleidis σε Κυρ Ιούλ 31, 2011 2:59 pm, έχει επεξεργασθεί 3 φορές συνολικά.


Γιώργος
Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: IMC 2011

#12

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Κυρ Ιούλ 31, 2011 2:58 pm

Κάτι δε μου παει καλά με το πρόβλημα 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.


Εσύ....; Θα γίνεις κανίβαλος....;
Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: IMC 2011

#13

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Κυρ Ιούλ 31, 2011 3:02 pm

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


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

Re: IMC 2011

#14

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιούλ 31, 2011 3:13 pm

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


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

Re: IMC 2011

#15

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιούλ 31, 2011 3:16 pm

Κοτρώνης Αναστάσιος έγραψε:Το πρόβλημα 1 της πρώτης μέρας αν θυμάμαι καλά είναι γνωστό ως Λήμμα το Ανατέλλοντος Ηλίου και υπάρχει στο βιβλίο του Απειροστικού του Spivak και του Νεγρεπόντη.
Το 1 μου φάνηκε τελείως προφανές. Δεν χρειαζόταν καν η συνέχεια. Υπάρχει όμως λάθος στην μετάφραση. Εκεί που λέει «υπάρχει y \in \mathbb{R}» πρέπει να λέει «υπάρχει y > x». Θα το διορθώσω.


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

Re: IMC 2011

#16

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιούλ 31, 2011 3:40 pm

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

Υπάρχει πραγματικός πίνακας \displaystyle{A}, \displaystyle{3 \times 3} ώστε \displaystyle{tr\left( A \right) = 0} και \displaystyle{{A^2} + {A^t} = I};
Ας υποθέσουμε πως υπάρχει. Θα συμβολίζω το A^t με B. Τότε B = I - A^2, άρα A = I - B^2 και άρα I = B + (I - B^2)^2 = B + I - 2B^2 + B^4, δηλαδή B^4 -2B^2 + B = 0. Η εξίσωση x^4 - 2x^2 + x = 0 έχει ρίζες τις 0,1 και \displaystyle{ \frac{-1 \pm \sqrt{5}}{2}}. Επειδή όμως ο B είναι 3 \times 3 πίνακας με tr(B) = tr(A) = 0 οι ιδιοτιμές του B πρέπει να είναι οι 1 και \displaystyle{ \frac{-1 \pm \sqrt{5}}{2}}. Το ίδιο πρέπει να ισχύει και για τις ιδιοτιμές του A. Επειδή οι ιδιοτιμές του A είναι διακεκριμένες, υπάρχει αντιστρέψιμος πίνακας P ώστε \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 πρέπει να είναι όμοιος με τον B και άρα να έχει τις ίδιες ιδιοτιμές, πράγμε που δεν ισχύει.


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

Re: IMC 2011

#17

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιούλ 31, 2011 10:17 pm

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 ρίχνουμε ένα νόμισμα το οποίο έχει πιθανότητα t να έρθει κορώνα. (Όλες οι ρίψεις ανεξάρτητες.) Έστω E το ενδεχόμενο τουλάχιστον σε ένα από τα από τα A_i να έρθουν όλες οι ρίψεις κορώνες. Προφανώς το \Pr(E) είναι αύξουσα συνάρτηση του t (στο [0,1]).

Για 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].


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11157
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: IMC 2011

#18

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Δευ Αύγ 01, 2011 3:15 am

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

Φιλικά,

Μιχάλης


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

Re: IMC 2011

#19

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 01, 2011 1:26 pm

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} παντρεμένες τριάδες.
Αυτό το πρόβλημα είναι ίσως λίγο άδικο μιας και είναι άμεση εφαρμογή του θεωρήματος του γάμου. Ας ελπίσουμε οι δικοί μας να το γνώριζαν. Νομίζω πως χωρίς γνώση αυτού του θεωρήματος η απόδειξη είναι αρκετά δύσκολη.


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

Re: IMC 2011

#20

Μη αναγνωσμένη δημοσίευση από silouan » Δευ Αύγ 01, 2011 2:37 pm

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

Παραθέτω τώρα τη λύση στο πρόβλημα 4 της δεύτερης μέρας.
Η λύση βασίζεται σε ένα λήμμα που το κάνουμε κατά κόρον στην προετοιμασία για την ΙΜΟ.
Αν ένα πολυώνυμο βαθμού n με πραγματικούς συντελεστές έχει n+1 ακέραιες τιμές σε ακέραια σημεία, τότε το πολυώνυμο έχει ακεραίους συντελεστές.
Η απόδειξη είναι άμεση από το Lagrange Interpolation Formula.
Στη λύση της άσκησης τώρα.
Θεωρούμε το πολυώνυμο g(x)=f(x)-f(0). Τότε g(0)=0 και 1\leq i\leq n
έχουμε από την συνθήκη (για x=0, και y=i) ότι g(i) είναι ακέραιος.
Επομένως το λήμμα εφαρμόζεται στο πολυώνυμο g, άρα το g έχει ακεραίους συντελεστές.
Τότε όμως είναι γνωστό ότι για οποιουσδήποτε ακεραίους a,b έχουμε
a-b|g(a)-g(b)=f(a)-f(b) που είναι και το ζητούμενο.
τελευταία επεξεργασία από grigkost σε Δευ Αύγ 01, 2011 3:21 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: δημιουργία συνδέσμου


Σιλουανός Μπραζιτίκος
Απάντηση

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

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

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