IMO 2017

simantiris j. · #1

Πριν λίγο τελείωσε η 1η μέρα του διαγωνισμού.Ας συζητήσουμε τα θέματα,όταν αυτά δημοσιευτούν,εδώ.
Καλή επιτυχία στους διαγωνιζόμενους και στην εθνική μας ομάδα!

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #2

Το πρόβλημα 2 είναι

Να βρεθούν όλες οι $f:\mathbb{R}\rightarrow \mathbb{R}$

που ικανοποιούν την $f(f(x)f(y))+f(x+y)=f(xy),x,y\in \mathbb{R}$

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #3

Το πρόβλημα 1 είναι

Για κάθε ακέραιο $a_{0}> 1$ , ορίζουμε την ακολουθία $a_0,a_1,a_2,\ldots$ ως εξής:

$\displaystyle{ a_{n+1} = \begin{cases} \sqrt{a_n} & \text{\gr αν } \sqrt{a_n} \text{ \gr ακέραιος} \\ a_n+3 & \text{\gr διαφορετικά} \end{cases} \quad \text{\gr για κάθε } n \geqslant 0.}$

Να προσδιορίσετε όλες τις τιμές του $a_{0}$ για τις οποίες υπάρχει αριθμός

τέτοιος ώστε $a_{n}=A$ για άπειρες τιμές του

.

Επεξεργασία από Demetres: Βελτίωση εκφώνησης.
συμπλήρωμα. Διόρθωσα καραμπινάτο τυπογραφικό.
συμπλήρωμα2.Το τυπογραφικό είχε γίνει από τον Demetres όταν βελτίωσε την εκφώνηση.

#4

Πρόβλημα 3

Ένας κυνηγός και ένα αόρατο κουνέλι παίζουν ένα παιγνίδι στο Ευκλείδειο επίπεδο. Το σημείο εκκίνησης A_0

του κουνελιού και το σημείο εκκίνησης B_0

του κυνηγού είναι τα ίδια. Μετά από n-1

γύρους του παιγνιδιού, το κουνέλι βρίσκεται στο σημείο $A_{n-1}$ και ο κυνηγός στο σημείο $B_{n-1}$ . Στον

-οστό γύρο του παιγνιδιού, τρία πράγματα συμβαίνουν κατά σειρά:

(α) Το κουνέλι κινείται αόρατα σε ένα σημείο $A_{n}$ τέτοιο ώστε η απόσταση μεταξύ των σημείων $A_{n-1}$ και $A_{n}$ να είναι ακριβώς ίση με

.

(β) Μια συσκευή παρακολούθησης αναφέρει ένα σημείο $P_{n}$ στον κυνηγό. Η μόνη εγγυημένη πληροφορία είναι ότι η απόσταση μεταξύ των σημείων $P_{n}$ και $A_{n}$ είναι το πολύ

.

(γ) Ο κυνηγός κινείται ορατά σε ένα σημείο $B_{n}$ τέτοιο ώστε η απόσταση μεταξύ των σημείων $B_{n-1}$ και $B_{n}$ να είναι ακριβώς ίση με

.

Είναι πάντοτε δυνατόν, ανεξάρτητα από το πως κινείται το κουνέλι και ανεξάρτητα από το ποια σημεία αναφέρονται από την συσκευή παρακολούθησης , για τον κυνηγό να επιλέξει τις κινήσεις του έτσι ώστε μετά από 10^9

γύρους να είναι σίγουρος ότι η απόσταση μεταξύ αυτού και του κουνελιού είναι το πολύ 100

;

Γιάννης Μπόρμπας · #5

Η απάντηση στο πρόβλημα 1 είναι:
$a_0\equiv 0(\mod 3)$ . Θα ανεβάσω την λύση μου σε λίγο.

harrisp · #6

Γιάννης Μπόρμπας έγραψε:Η απάντηση στο πρόβλημα 1 είναι:
$a_0\equiv 0(\mod 3)$ . Θα ανεβάσω την λύση μου σε λίγο.

Να σε βγάλω από τον κόπο (

) να γράψεις την εύκολη περίπτωση του $a_0\equiv 2 \mod 3$ αφού δεν έχω ολοκληρωμένη λύση παρά μόνο μερικά πορίσματα. Η άσκηση ουσιαστικά ξετυλίγεται μέσα από τις απλές δοκιμές.

Λοιπόν, έχουμε: a_1=a_0+3

αφού κανένα τέλειο τετράγωνο δεν αφήνει υπόλοιπο $2 \mod 3$ . Πάλι έχουμε ότι a_2=a_1+6

για τον ίδιο λόγο.

Συνεχίζοντας βλέπουμε ότι η ακολουθία λοιπόν είναι γνησίως αύξουσα άρα είναι αδύνατον να ισχύει a_n=A

για άπειρα

.

Η συνέχεια δική σου...

knm2608 · #7

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:Το πρόβλημα 2 είναι

Να βρεθούν όλες οι $f:\mathbb{R}\rightarrow \mathbb{R}$

που ικανοποιούν την $f(f(x)f(y))+f(x+y)=f(xy),x,y\in \mathbb{R}$

Κάποιες λύσεις για το 2 υπάρχουν εδώ https://artofproblemsolving.com/communi ... _problem_2

Γιάννης Μπόρμπας · #8

Πρόβλημα 1
Το πρόβλημα είναι ισοδύναμο με το εξής:
Αρχικά έχουμε έναν ακέραιο k>1

. Μπορούμε να κάνουμε τις εξής κινήσεις:
Κίνηση 1: Αν ο

είναι το τετράγωνο ενός ακεραίου, τότε τον σβήνουμε και στην θέση του γράφουμε τον $\sqrt{k}$ .
Κίνηση 2Αν ο

δεν είναι το τετράγωνο ενός ακεραίου, τότε τον σβήνουμε και στην θέση του γράφουμε τον k+3

.
Για ποιους θετικούς ακέραιους k>1

υπάρχει ακέραιος

τέτοιος ώστε σε οποιαδήποτε κίνηση ο αριθμός που υπάρχει στον πίνακα είναι μικρότερος
ή ίσος του

;
Λήμμα 1
Αν κάποια στιγμή ο αριθμός που υπάρχει στον πίνακα (έστω

) αφήνει υπόλοιπο

διαιρούμενος με το

τότε ο αριθμός

δεν είναι λύση.
Απόδειξη
Ας υποθέσουμε ότι $t\equiv 2(\mod 3)$ . Τότε αφού το

δεν είναι τετραγωνικό κατάλοιπο $(\mod 3)$ μπορούμε να εκτελούμε διαδοχικά μόνο
την δεύτερη κίνηση. Όμως κάθε αριθμός που προκύπτει αφήνει υπόλοιπο

διαιρούμενος με το

, οπότε εκτελώντας συνεχώς την δεύτερη
κίνηση δεν μπορούμε να βρούμε ακέραιο

καθώς ο αριθμός που υπάρχει στον πίνακα, συνεχώς μεγαλώνει.

Στην συνέχεια θα δείξουμε επαγωγικά πως:
Αν οι αριθμοί: 3,6,9, ..., 3n

αποτελούν λύση, τότε και ο 3n+3

αποτελεί λύση.
Φυσικά για n=1

ο αριθμός

είναι λύση διότι οι κινήσεις είναι οι εξής: $3\rightarrow 6\rightarrow 9\rightarrow 3...$ οπότε για m=10

έχουμε λύση.
Στην συνέχεια λαμβάνουμε 2 περιπτώσεις:
(1) Αν ο αριθμός

δεν είναι τέλειο τετράγωνο: Τότε μέσω της δεύτερης κίνησης προκύπτει ο 3n+3

και αφού ο αριθμός

είναι λύση τότε
φυσικά και ο 3n+3

πρέπει να είναι αναγκαστικά.
(2) Αν ο αριθμός

είναι τέλειο τετράγωνο: Έστω 3n=(3l)^2

. σε οποιαδήποτε κίνηση ο αριθμός που προκύπτει διαιρείται με το

, οπότε
το αμέσως επόμενο τέλειο τετράγωνο μετά το (3l)^2

το οποίο είναι πολλαπλάσιο του

είναι το

. Αφού όμως (3l+3)^2>3n+3>(3l)^2

τότε οι κινήσεις είναι οι εξής: $3n+3\rightarrow 3n+6\rightarrow 3n+9\rightarrow ... \rightarrow (3l+3)^2\rightarrow 3l+3$ . Όμως 3l+3<(3l)^2=3n

οπότε ο αριθμός 3l+3

αποτελεί λύση λόγω της υπόθεσης, άρα και ο 3n+3

είναι λύση.
Οπότε προκύπτει η λύση: $a_0\equiv 0(\mod 3)$ .

Επαγωγικά θα δείξουμε πως αν οι αριθμοί 4,7,10, ..., 3n+1

δεν είναι λύση τότε και ο 3n+4

δεν είναι λύση.
Για n=1

έχουμε ότι: $4\rightarrow 2$ , όμως με βάση το λήμμα 1 ο αριθμός

δεν είναι λύση.
Στην συνέχεια λαμβάνουμε τις περιπτώσεις:
(1) Αν ο αριθμός 3n+1

δεν είναι τέλειο τετράγωνο: Όμοια με πριν με βάση την δεύτερη κίνηση προκύπτει ο 3n+4

ο οποίος δεν μπορεί να αποτελεί λύση αφού ο 3n+1

δεν αποτελεί και αυτός.
(2) Αν ο αριθμός 3n+1

είναι τέλειο τετράγωνο: Λαμβάνουμε 2 υποπεριπτώσεις:
(2.1) Αν 3n+1=(3l+2)^2

. Τότε το αμέσως επόμενο τέλειο τετράγωνο που δεν είναι πολλαπλάσιο του

είναι το

.
Με όμοιο τρόπο οι κινήσεις είναι οι εξής: $3n+4\rightarrow 3n+7\rightarrow ...\rightarrow (3l+4)^2\rightarrow 3l+4$ .
Όμως 3l+4<(3l+2)^2=3n+1

άρα ο αριθμός 3l+4

δεν αποτελεί λύση λόγω της υπόθεσης
επομένως ούτε και ο 3n+4

αποτελεί.
(2.2) Αν 3n+1=(3l+1)^2

. Τότε το αμέσως επόμενο τέλειο τετράγωνο που δεν είναι πολλαπλάσιο του

είναι το

.
Πάλι, οι κινήσεις είναι οι εξής: $3n+4\rightarrow 3n+7\rightarrow ...\rightarrow (3l+2)^2\rightarrow 3l+2$ που με βάση το λήμμα 1
δεν αποτελεί λύση ο 3l+2

άρα ούτε και ο 3n+4

.
Ανακεφαλαιώνοντας η αναγκαία και ικανή συνθήκη είναι: $\boxed{a_0\equiv 0(\mod 3)}$

Panagiotis11 · #9

Πρόβλημα 4

Έστω

και

διαφορετικά σημεία ενός κύκλου $\Omega$ τέτοια, ώστε το
ευθύγραμμο τμήμα

να μην είναι διάμετρός του. Έστω $\ell$ η εφαπτομένη του
κύκλου $\Omega$ στο σημείο

. Σημείο

είναι τέτοιο, ώστε το

να είναι το μέσον του
ευθυγράμμου τμήματος

. Στο μικρότερο τόξο

του $\Omega$ επιλέγουμε σημείο

, ώστε
ο περιγεγραμμένος κύκλος $\Gamma$ του τριγώνου JST

να τέμνει την εφαπτομένη $\ell$ σε δύο
διαφορετικά σημεία. Έστω

το κοινό σημείο του $\Gamma$ και της $\ell$ , που βρίσκεται
πλησιέστερα στο

. H ευθεία

τέμνει ξανά τον κύκλο $\Omega$ στο σημείο

. Να
αποδείξετε ότι η ευθεία

εφάπτεται του κύκλου $\Gamma$ .

Πρόβλημα 5

Δίνεται ακέραιος N > 2

. Ένα σύνολο N(N + 1)

ποδοσφαιριστών,
μεταξύ των οποίων δεν υπάρχουν δύο με το ίδιο ύψος, στέκονται σε μια γραμμή. Ο
προπονητής θέλει να απομακρύνει N(N - 1)

ποδοσφαιριστές από αυτή τη
γραμμή, έτσι ώστε να απομείνει μία νέα γραμμή από

ποδοσφαιριστές, στην
οποία να ικανοποιούνται οι ακόλουθες

συνθήκες:
(

) Κανένας δε στέκεται μεταξύ των δύο πιο ψηλών ποδοσφαιριστών,
(

) Κανένας δε στέκεται μεταξύ του τρίτου και τέταρτου ψηλότερων
ποδοσφαιριστών,
⋮
(

) Κανένας δε στέκεται μεταξύ των δύο πιο κοντών ποδοσφαιριστών.

Να αποδείξετε ότι αυτό είναι πάντοτε δυνατόν.

Πρόβλημα 6

Ένα διατεταγμένο ζεύγος ακεραίων (x, y)

είναι ένα πρωταρχικό
σημείο, αν ο μέγιστος κοινός διαιρέτης των

και

είναι

.Αν

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

και ακέραιοι $a_0, a_1, \ldots , a_n$ τέτοιοι, ώστε για κάθε ζεύγος (x, y)

του

, να έχουμε:

$\displaystyle{a_0x^n + a_1x^{n-1} y + a_2x^{n-2}y^2 + \cdots + a_{n-1}xy^{n-1} + a_ny^n = 1.}$

Γιάννης Μπόρμπας · #10

Τελικά το πρόβλημα 3 αποδείχθηκε (όπως περίμενα) το πιο δύσκολο πρόβλημα στην φετινή IMO.

harrisp · #11

Panagiotis11 έγραψε:Πρόβλημα 4
Έστω και διαφορετικά σημεία ενός κύκλου $\Omega$ τέτοια, ώστε το
ευθύγραμμο τμήμα να μην είναι διάμετρός του. Έστω $\ell$ η εφαπτομένη του
κύκλου $\Omega$ στο σημείο . Σημείο είναι τέτοιο, ώστε το να είναι το μέσον του
ευθυγράμμου τμήματος . Στο μικρότερο τόξο του $\Omega$ επιλέγουμε σημείο , ώστε
ο περιγεγραμμένος κύκλος $\Gamma$ του τριγώνου να τέμνει την εφαπτομένη $\ell$ σε δύο
διαφορετικά σημεία. Έστω το κοινό σημείο του $\Gamma$ και της $\ell$ , που βρίσκεται
πλησιέστερα στο . H ευθεία τέμνει ξανά τον κύκλο $\Omega$ στο σημείο . Να
αποδείξετε ότι η ευθεία εφάπτεται του κύκλου $\Gamma$ .

Θα βάλω πλήρη λύση και σχήμα αύριο λόγω της ώρας.

• KR//AT

• Αφού έχουμε το μεσο ενός τμήματος θα θεωρήσουμε το συμμετρικό του

ως προς το

,

. Τότε το

είναι παραλληλόγραμμο άρα A'R//AT

συνεπώς τα A'KR

είναι συνευθειακά
• Το A'KST

είναι εγγράψιμο και εύκολα έπεται το ζητούμενο,

#12

Panagiotis11 έγραψε: Πρόβλημα 5

Δίνεται ακέραιος . Ένα σύνολο ποδοσφαιριστών,
μεταξύ των οποίων δεν υπάρχουν δύο με το ίδιο ύψος, στέκονται σε μια γραμμή. Ο
προπονητής θέλει να απομακρύνει ποδοσφαιριστές από αυτή τη
γραμμή, έτσι ώστε να απομείνει μία νέα γραμμή από ποδοσφαιριστές, στην
οποία να ικανοποιούνται οι ακόλουθες συνθήκες:
() Κανένας δε στέκεται μεταξύ των δύο πιο ψηλών ποδοσφαιριστών,
() Κανένας δε στέκεται μεταξύ του τρίτου και τέταρτου ψηλότερων
ποδοσφαιριστών,
⋮
() Κανένας δε στέκεται μεταξύ των δύο πιο κοντών ποδοσφαιριστών.

Να αποδείξετε ότι αυτό είναι πάντοτε δυνατόν.

Καλό! Έχω μια σύντομη απόδειξη αλλά νομίζω ότι είναι δύσκολο πρόβλημα. Δηλαδή αρκετά κατάλληλο για πρόβλημα 5.

Θα αποδείξω επαγωγικά κάτι ισχυρότερο.

Χωρίζω τους N(N+1)

ποδοσφαιριστές σε

ομάδες των N+1

ατόμων. Θα δείξω ότι μπορώ να επιτύχω το ζητούμενο παίρνοντας δύο ποδοσφαιριστές από κάθε ομάδα.

Η περίπτωση N=1

είναι άμεση.

Τώρα, ξεκινώντας από τον ψηλότερο, ένας ένας από κάθε ομάδα κάνει ένα βήμα μπροστά. Αυτό συνεχίζεται μέχρι δύο άτομα από κάποια ομάδα να κάνουν ένα βήμα μπροστά. Παίρνω αυτούς τους δύο από αυτήν την ομάδα. Διώχνω όλους τους υπόλοιπους παίκτες της ομάδας. Διώχνω επίσης όσους παίκτες έχουν κάνει βήμα μπροστά. Τώρα μου έμειναν N-1

ομάδες από

ποδοσφαριστές, όλοι χαμηλότεροι από τους δύο που επέλεξα. Από την επαγωγική υπόθεση μπορώ να επιλέξω τα υπόλοιπα N-1

ζεύγη.

Ορέστης Λιγνός · #13

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

Έστω και διαφορετικά σημεία ενός κύκλου $\Omega$ τέτοια, ώστε το
ευθύγραμμο τμήμα να μην είναι διάμετρός του. Έστω $\ell$ η εφαπτομένη του
κύκλου $\Omega$ στο σημείο . Σημείο είναι τέτοιο, ώστε το να είναι το μέσον του
ευθυγράμμου τμήματος . Στο μικρότερο τόξο του $\Omega$ επιλέγουμε σημείο , ώστε
ο περιγεγραμμένος κύκλος $\Gamma$ του τριγώνου να τέμνει την εφαπτομένη $\ell$ σε δύο
διαφορετικά σημεία. Έστω το κοινό σημείο του $\Gamma$ και της $\ell$ , που βρίσκεται
πλησιέστερα στο . H ευθεία τέμνει ξανά τον κύκλο $\Omega$ στο σημείο . Να
αποδείξετε ότι η ευθεία εφάπτεται του κύκλου $\Gamma$ .

Έστω $Q \equiv RK \cap AS$ .

Θα δείξουμε πρώτα πως $RK \parallel AT$ .

Είναι $\widehat{KRT}=\widehat{KRS}=\widehat{KJS}=\widehat{STA}=\widehat{RTA} \Rightarrow \widehat{KRT}=\widehat{RTA} \Rightarrow RK \parallel AT$ .

Έτσι, τα τρίγωνα $\vartriangle RSQ,\vartriangle STA$ έχουν $\widehat{QRS}=\widehat{STA},\widehat{RQS}=\widehat{SAT}, RS=ST$ , οπότε είναι ίσα (έμμεσο κριτήριο).

Έτσι, $QS=SA, RS=ST \Rightarrow RQTA$ παραλληλόγραμμο.

Επίσης, $\widehat{RKS}=\widehat{SRA}=\widehat{TRA}=\widehat{RTQ}=\widehat{STQ} \Rightarrow \widehat{RKS}=\widehat{STQ} \Rightarrow SKQT$ εγγράψιμο.

Οπότε, $\widehat{KTS}=\widehat{KQS}=\widehat{RQA}=\widehat{QAT}=\widehat{SAT} \Rightarrow \widehat{KTS}=\widehat{SAT}$ , και το ζητούμενο γίνεται άμεσο.

: IMO4-2017.png (29.19 KiB) Προβλήθηκε 3235 φορές

Γιάννης Μπόρμπας · #14

Panagiotis11 έγραψε: Πρόβλημα 6

Ένα διατεταγμένο ζεύγος ακεραίων είναι ένα πρωταρχικό
σημείο, αν ο μέγιστος κοινός διαιρέτης των και είναι .Αν είναι ένα
πεπερασμένο σύνολο πρωταρχικών σημείων, να αποδείξετε ότι υπάρχουν ένας
θετικός ακέραιος και ακέραιοι $a_0, a_1, \ldots , a_n$ τέτοιοι, ώστε για κάθε ζεύγος
του , να έχουμε:

$\displaystyle{a_0x^n + a_1x^{n-1} y + a_2x^{n-2}y^2 + \cdots + a_{n-1}xy^{n-1} + a_ny^n = 1.}$

Πολύ καλό πρόβλημα!
Θα αποδείξουμε με ισχυρή επαγωγή την ύπαρξη ομογενοποιημένου πολυωνύμου ως προς το πλήθος των πρωταρχικών σημείων.

Αν |S|=1

και $(x_0,y_0)\in S$ τότε μπορούμε να βρούμε a,b

τέτοια ώστε ax_o+by_o=1

. Οπότε επιλέγοντας
f(x,y)=ax+by

καταλήγουμε στο ζητούμενο.

Αν υπάρχει πολυώνυμο ομογενοποιημένο πολυώνυμο g(x,y)

τέτοιο ώστε $g(x_i,y_i)=1 \forall i=1,2,...,n-1$ με

να είναι
πρωταρχικό σημείο $\forall i=1,2,...,n-1$ αρκεί να βρούμε ένα πολυώνυμο f(x,y)

τέτοιο ώστε $f(x_i,y_i)=1 \forall i=1,2,...,n$
όπου (x_n,y_n)

είναι το καινούργιο πρωταρχικό σημείο που προσθέτουμε στο

.

Βήμα 1
Αφού $\gcd(x_n,y_n)=1$ τότε μπορούμε να βρούμε a,b

τέτοια ώστε ax_n+by_n=1

. Μπορούμε να αξιοποιήσουμε το παραπάνω
θεωρώντας το πολυώνυμο r(x,y)=t(ax+by)^u

το οποίο μπορεί να πάρει οποιαδήποτε τιμή

θελήσουμε την οποία μαζί με το

θα την προσδιορίσουμε αργότερα.

Βήμα 2
Με όμοιο τρόπο παρατηρούμε ότι g(x_i,y_i)^l=1

οπότε μπορούμε να χρησιμοποιήσουμε το πολυώνυμο h(x)=g(x,y)^l

για κάποιο

που θα προσδιορίσουμε αργότερα, στην κατασκευή του f(x,y)

.

Βήμα 3
Παίρνουμε f(x,y)=h(x,y)+d(x,y)r(x,y)

. Αφού

επιλέγουμε

$\displaystyle{d(x,y)=\prod_{i=1}^{n-1}(y_ix-x_iy)}$ .

Οπότε έχουμε: 1=g(x_n,y_n)^l+d(x_n,y_n)r(x_n,y_n)

Βήμα 4
Έπειτα παρατηρούμε ότι αν $\exist p\in P : p|g(x_n,y_n) , p|x_iy_n-y_ix_n$ (1)για κάποιο

τότε θα είχαμε:

Έστω $\displaystyle{\sum_{j=0}^p c_jx^{p-j}y^p=g(x,y)}$

$0\equiv g(x_n,y_n)\equiv x_i^pg(x_n,y_n)\equiv x_i^p\displaystyle{\sum_{j=0}^p c_jx_n^{p-j}y_n^j}$ .

$\equiv \displaystyle{\sum_{j=0}^p c_j(x_ix_n)^{p-j}(x_iy_n)^j}\equiv \displaystyle{\sum_{j=0}^p c_j(x_ix_n)^{p-j}(y_ix_n)^j}=$ .
$x_n^lg(x_i,y_i)=x_n^l (\mod p)$ οπότε θα είχαμε p|x_n

. Με όμοιο τρόπο δείχνουμε ότι p|y_n

που είναι άτοπο αφού
$\gcd(x_n,y_n)=1$ .

Βήμα 5

Από το βήμα 4 γνωρίζουμε ότι: $\gcd( g(x_n,y_n),d(x_n,y_n))=1$ οπότε μπορούμε να επιλέξουμε $l=c\phi(d(x_n,y_n))$ για να εξασφαλίσουμε την ακεραιότητα του r(x_n,y_n)

.

Βήμα 6
Έπειτα, πρέπει να εξισώσουμε τους βαθμούς των πολυωνύμων.
Θέλουμε deg h=deg r +deg d

.
Οπότε επιλέγουμε u=deg h-n+1

.

Βήμα 7
Τέλος επειδή εμείς χειριζόμαστε την τιμή του

επιλέγουμε $t=\frac{1-h(x_n,y_n)}{d(x_n,y_n)}$ .

Και έτσι εξασφαλίζουμε την ύπαρξη του f(x,y)

.

#15

Demetres έγραψε:Πρόβλημα 3

Ένας κυνηγός και ένα αόρατο κουνέλι παίζουν ένα παιγνίδι στο Ευκλείδειο επίπεδο. Το σημείο εκκίνησης του κουνελιού και το σημείο εκκίνησης του κυνηγού είναι τα ίδια. Μετά από γύρους του παιγνιδιού, το κουνέλι βρίσκεται στο σημείο $A_{n-1}$ και ο κυνηγός στο σημείο $B_{n-1}$ . Στον -οστό γύρο του παιγνιδιού, τρία πράγματα συμβαίνουν κατά σειρά:

(α) Το κουνέλι κινείται αόρατα σε ένα σημείο $A_{n}$ τέτοιο ώστε η απόσταση μεταξύ των σημείων $A_{n-1}$ και $A_{n}$ να είναι ακριβώς ίση με .

(β) Μια συσκευή παρακολούθησης αναφέρει ένα σημείο $P_{n}$ στον κυνηγό. Η μόνη εγγυημένη πληροφορία είναι ότι η απόσταση μεταξύ των σημείων $P_{n}$ και $A_{n}$ είναι το πολύ .

(γ) Ο κυνηγός κινείται ορατά σε ένα σημείο $B_{n}$ τέτοιο ώστε η απόσταση μεταξύ των σημείων $B_{n-1}$ και $B_{n}$ να είναι ακριβώς ίση με .

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

Προτού βάλω την λύση μου, αλλά και ενδιάμεσα της λύσης, βάζω κάποια σχόλια. Δεν χρειάζονται για την απόδειξη αλλά πιστεύω βοηθούν αρκετά στην κατανόηση και στον τρόπο σκέψης για να καταλήξουμε στην λύση.

Σχόλιο 1: Η προφανής στρατηγική του κυνηγού είναι να κινείται προς τα P_n

. Αν δείξουμε πως η απόσταση d_n

του κυνηγού από τα P_n

είναι πάντα το πολύ

, τότε η απόσταση από τον λαγό είναι πάντα το πολύ 100

. Δεν είναι δύσκολο να δείξουμε ότι σε κάθε βήμα το d_n

μπορεί να αυξηθεί το πολύ κατά 2. Αυτό ασφαλώς δεν μας κάνει. Όσο όμως πιο κοντά στο

είναι η αύξηση, τόσες περισσότερες πληροφορίες έχουμε για την ακριβή θέση του λαγού, κάτι που επιτρέπει στο επόμενο βήμα τουλάχιστον είτε να μειώσουμε το d_n

είτε να αυξηθεί ελάχιστα. Για να δείξουμε ότι τέτοια στρατηγική δουλεύει, πιθανώς με κάποιες τροποποιήσεις, θα πρέπει να λαμβάνουμε υπόψη περισσότερο τις πληροφορίες που παίρνουμε από τις διαδοχικές θέσεις των P_n

.

Σχόλιο 2: Πως μπορούμε να δείξουμε ότι ο λαγός αποτυγχάνει; Μια «αφελής» στρατηγική για τον λαγό της μορφής «αν ο κυνηγός είναι εκεί, τότε θα κινηθώ έτσι» είναι καταδικασμένη να αποτύχει. Και αυτό διότι ο κυνηγός μπορεί να είναι τυχεράκιας και να κινείται πάντα προς τον λαγό. Ο μόνος τρόπος για να αποφύγουμε κάτι τέτοιο είναι να έχουμε πολλούς λαγούς! Σε κάθε στιγμή της διαδικασίας μπορεί να έχουμε πολλούς, ίσως και άπειρους λαγούς, οι οποίοι θα ικανοποιούν ότι με βάση το προηγούμενο ιστορικό μπορούν όντως να βρίσκονται σε συγκεκριμένη θέση. Μπορούμε στο τέλος να επιλέξουμε ποιος είναι ο πραγματικός λαγός και ποιοι οι ψεύτικοι.

Σχόλιο 3: Ο κυνηγός μπορεί επίσης να είναι τυχεράκιας και σε σχέση με το τι εμφανίζει η συσκευή παρακολούθησης. Μπορεί π.χ. να έχει εσωτερική πληροφόρηση ότι πάντα η συσκευή δίνει απόσταση 1 βόρεια του λαγού. Για να αποτρέψουμε κάτι τέτοιο θα ελέγχουμε πλήρως εμείς την συσκευή.

Σχόλιο 4: Συνοψίζοντας μια καλή στρατηγική για το κουνέλι θα είναι η εξής: Πρώτα ανακοινώνουμε την ένδειξη της συσκευής. Μετά τοποθετούμε άπειρους λαγούς στις θέσεις που είναι δυνατόν να εμφανίζονται σε σχέση και με το προηγούμενο ιστορικό. Μετά κινείται ο κυνηγός. Τέλος αποφασίζουμε ποιος από τους άπειρους λαγούς είναι ο πραγματικός και συνεχίζουμε.

Πριν το επόμενο σχόλιο, ξεκινώ εισάγοντας κάποιους συμβολισμούς. Γράφω d_n

για την απόσταση του κυνηγού από το κουνέλι μετά από

γύρους. Αρχικά d_0=0

. Στον πρώτο γύρο, ανακοινώνουμε το σημείο P_1 = A_0

. Όπου και αν μετακινηθεί ο κυνηγός, εμείς ως κουνέλι μετακινούμαστε στο αντιδιαμετρικό του σημείο πάνω στον κύκλος ακτίνας

και κέντρο P_1 = A_0 = B_0

. Έτσι έχουμε d_1 = 2

.

Σχόλιο 5: Θα θέλαμε να δείξουμε ότι αν $d_n \geqslant N$ , τότε $d_{n+1} \geqslant N +f(N)$ όπου f(N)

είναι μια μικρή αλλά όχι αμελητέα αύξηση. Αν μπορούμε να δείξουμε κάτι τέτοιο τότε είμαστε κοντά στην επίλυση. Αν μάλιστα δεν είναι τόσο καλό το φράγμα αλλά δείξουμε ότι μπορούμε να το πετύχουμε με $10^{10}$ κινήσεις τότε ίσως πάρουμε και αρκετές μονάδες. Δυστυχώς κάτι τέτοιο είναι αδύνατο αν N > 1

. Αν π.χ. ο κυνηγός γνωρίζει την ακριβή θέση του λαγού στο προηγούμενο βήμα και κινηθεί προς τον λαγό τότε το d_n

δεν μπορεί να αυξηθεί.

Η δυσκολία του σχολίου 5 είναι και η σημαντικότερη δυσκολία που πρέπει να παρακαμφθεί. Το κόλπο για να την παρακάμψουμε είναι να δείξουμε ότι $d_{n+g(N)} \geqslant N + f(N)$ . Γιατί μπορούμε να το επιτύχουμε αυτό θα το δούμε αργότερα. Προς το παρόν γράφω το σημαντικότερο λήμμα για την λύση της άσκησης:

Λήμμα 1: Έστω φυσικός

. Αν μπορώ να πετύχω $d_n \in [N,N+1)$ , τότε μπορώ να πετύχω και $d_{n+(N+2)}^2 \geqslant d_n^2 + \frac{1}{2N+3}$ .

Πρωτού αποδείξω το λήμμα, θα δείξω γιατί αυτό είναι αρκετό για την επίλυση της άσκησης.

Λήμμα 2: Έστω φυσικός

. Αν μπορώ να πετύχω $d_n \in [N,N+1)$ , τότε μπορώ να πετύχω και $d_{n+(N+2)(2N+3)(2N+1)} \geqslant N+1}$ .

Απόδειξη λήμματος 2: Απλά επαναλαμβάνω το Λήμμα 1 το πολύ

φορές. Αν σε κάποια φάση πετύχω $d_r \geqslant N+1$ τότε χρησιμοποιώ το Λήμμα 3 πιο κάτω.

Λήμμα 3: Αν μπορώ να πετύχω $d_r \geqslant d$ , τότε μπορώ να πετύχω και $d_{r+1} \geqslant d$

Απόδειξη λήμματος 3: Άμεσο αν κινηθώ στην ευθεία που ενώνει τον κυνηγό με το κουνέλι απομακρυνόμενος από τον κυνηγό.

Από το Λήμμα 2 έχουμε $d_{1 + 4\cdot 7 \cdot 5} \geqslant 3$ , $d_{1+4\cdot7\cdot 5 + 5 \cdot 9 \cdot 7} \geqslant 4$ κ.τ.λ. μέχρι το $d_r \geqslant 101$ , όπου

$\displaystyle{\begin{aligned} r &= 1 + \sum_{k=2}^{101} (k+2)(2k+3)(2k+1) \\ &\leqslant 1 + \sum_{k=2}^{101} (2k)(2k + 3k/2)(2k + k/2) \\ &\leqslant 18\sum_{k=1}^{101} k^3 \\ &= 18 \cdot \frac{101^2 \cdot 102^2}{4} \\ &\leqslant 5 \cdot 10^8 \cdot (1.01 \times 1.02)^2 < 10^9 \end{aligned}}$

Άρα μπορώ να πετύχω και $d_{10^9} \geqslant 101$ .

Μένει να δείξουμε το Λήμμα 1 που είναι και το ζουμί της άσκησης. Πριν την απόδειξη βάζω ακόμη ένα σχόλιο.

Σχόλιο 6: Σε ένα βήμα η τριγωνική ανισότητα δουλεύει εναντίον μας. Για να την κάνουμε να δουλέψει υπέρ μας πρέπει ο κυνηγός να ξεπεράσει το σημείο που βρισκόμασταν στον γύρο

και μετά να μην γνωρίζει πολλά για το που βρισκόμαστε. Σε αυτήν την περίπτωση η τριγωνική ανισότητα δουλεύει ανάποδα. Ας δούμε και τις τεχνικές λεπτομέρειες:

Απόδειξη Λήμματος 1: Χωρίς βλάβη της γενικότητας, ο κυνηγός βρίσκεται στην θέση (0,0)

και ο λαγός στην θέση (m,0)

με $m \in [N,N+1)$ . Θα υποθέσουμε ακόμη ότι ο λαγός ανακοινώνει πλήρως την θέση του στον κυνηγό. Κλωνοποιούμε τον λαγό σε δύο λαγούς. Για τα επόμενα (N+2)

βήματα, ο ένας λαγός κινείται ευθεία προς το σημείο $(m+\sqrt{(N+2)^2-1},1)$ και ο άλλος προς το σημείο $(m+\sqrt{(N+2)^2-1},-1)$ . Σε κάθε βήμα ανακοινώνουμε το σημείο (x,0)

όπου το

είναι η κοινή τετμημένη των δύο λαγών. Στο τέλος των N+2

γύρων ο κυνηγός θα βρίσκεται σε ένα σημείο (x,y)

με $x \leqslant N+2$ . Οπότε η απόσταση

του κυνηγού από ένα από τους δύο λαγούς (αυτόν που θα ονομάσουμε πραγματικό) θα ικανοποιεί

$\displaystyle{ d^2 = (m + \sqrt{(N+2)^2-1} - x)^2 + 1 \geqslant [(m - (N+2 - \sqrt{(N+2)^2-1})]^2 + 1}$

Αλλά

$\displaystyle{ N+2 - \sqrt{(N+2)^2-1} = \frac{1}{N+2 + \sqrt{(N+2)^2-1}} \leqslant \frac{1}{2N+3}}$

Οπότε

$\displaystyle{ d^2 \geqslant \left(m - \frac{1}{2N+3}\right)^2 + 1 \geqslant m^2 - \frac{2m}{2N+3} + 1 \geqslant m^2 + \frac{1}{2N+3}}$

όπως θέλαμε να δείξουμε.

simantiris j. · #16

Έστω και καθυστερημένα,βρίσκοντας τώρα λίγο χρόνο για να ασχοληθώ,βάζω τη λύση μου για το 2,ώστε να έχουμε λύσεις όλων των προβλημάτων (και ρίχνοντας μια ματιά στο παραπάνω σύνδεσμο δεν υπάρχει ίδια η παρακάτω λύση).

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:Το πρόβλημα 2 είναι

Να βρεθούν όλες οι $f:\mathbb{R}\rightarrow \mathbb{R}$

που ικανοποιούν την $f(f(x)f(y))+f(x+y)=f(xy),x,y\in \mathbb{R}$

Έστω

η δοσμένη πρόταση.Έχουμε:
$P(0,0)\Rightarrow f(f^2(0))=0$
$P(x,f^2(0))\Rightarrow f(0)+f(x+f^2(0))=f(xf^2(0))$ .Έστω $f^2(0)\neq 1$ .Τότε σε αυτήν για $x=\frac{f^2(0)}{f^2(0)-1}$ (η λύση της x+f^2(0)=xf^2(0)

) έχουμε ότι f(0)=0

οπότε από αυτή προκύπτει ότι $f(x)=0,\forall x\in \mathbb{R}$ που προφανώς είναι λύση.
Έστω τώρα f^2(0)=1

.Παρατηρούμε από τη δοσμένη σχέση ότι αν η

είναι λύση της τότε και η

είναι λύση της,άρα χωρίς βλάβη της γενικότητας υποθέτουμε ότι f(0)=1

και έχουμε:
$P(x,0)\Rightarrow f(f(x))+f(x)=1$ (1) άρα f(f(f(x)))=1-f(f(x))=f(x)

(2).
$P(x,1)\Rightarrow f(x)=f(x+1)+1$ (3), από όπου εύκολα έχουμε ότι f(2)=-1

και

(και γενικά ότι f(n)=1-n

για κάθε ακέραιο

που δε μας ενδιαφέρει εδώ,αλλά μας δείχνει τη συνάρτηση που ψάχνουμε).
Επίσης είναι f(f(x))=1-f(x)=-f(x+1)

(1 και 3) άρα $f(-f(x+1))=f(f(f(x)))=f(x)=f(x+1)+1\Rightarrow f(-f(x))=f(x)+1$ (από 2 και 3).
$P(x,2)\Rightarrow f(-f(x))+f(x+2)=f(2x)\Rightarrow f(2x)=f(x)+1+f(x)-2\Rightarrow f(2x)=2f(x)-1$ άρα και f(2f(x))=2f(f(x))-1=2(1-f(x))-1=1-2f(x)

(4).
$P(x,-1)\Rightarrow f(2f(x))+f(x-1)=f(-x)\Rightarrow 1-2f(x)+f(x)+1=f(-x)\Rightarrow f(x)+f(-x)=2$ (5),όπου χρησιμοποιήσαμε τις 3 και 4.
Τώρα έχουμε 2 επιλογές:Είτε να συνεχίσουμε τη λογική των αντικατάστασεων στην αρχική με την ελπίδα να πάρουμε κάτι καλό,είτε να αρχίσουμε να εξετάζουμε τη σχέση δυο αριθμών με ίδιες εικόνες (υπό μια έννοια το 1-1 της

).Λόγω της (2) θα κινηθούμε προς τη 2η επιλογή.Αξιοποιώντας την (5) και θέλοντας να "σπάσουμε" τη συμμετρία της αρχικής είναι:
$P(x,-y)\Rightarrow f(f(x)(2-f(y)))+f(x-y)=f(-xy)\Rightarrow 2-f(f(x)f(y)-2f(x))+f(x-y)=2-f(xy)\Rightarrow f(x-y)=f(f(x)f(y)-2f(x))-f(xy)$ (6).
Η (6) είναι σημαντική και πετυχαίνει αυτό που θέλαμε.Πράγματι έστω $x,y\in R$ με f(x)=f(y)

.Εναλλάσοντας τα x,y

αυτά στην 6 έχουμε f(y-x)=f(f(y)f(x)-2f(y))-f(yx)

.Όμως

άρα είναι f(x-y)=f(y-x)

.
Από την 5 όμως $f(x-y)+f(y-x)=2\Rightarrow f(x-y)=f(y-x)=1$
Αποδείξαμε λοιπόν ότι αν $f(x)=f(y)\Rightarrow f(x-y)=1$ .
Επιστρέφοντας λοιπόν στην 2 είναι $f((f(f(x)))=f(x)\Rightarrow f(x-f(f(x)))=1\Rightarrow f(x+f(x)-1)=1\Rightarrow f(x+f(x))+1=1\Rightarrow f(x+f(x))=0$ (7).
Έχουμε σχεδόν τελειώσει.Πράγματι έστω $a\neq 1$ τέτοιο ώστε f(a)=0

.Είναι:
$P(x,a)\Rightarrow 1+f(x+a)=f(ax)$ όπου για $x=\frac{a}{a-1}$ έχουμε 1=0

,άτοπο.Συνεπώς $f(a)=0\Leftrightarrow a=1$ .
Αυτό για την 7 όμως σημαίνει ότι $x+f(x)=1\Rightarrow f(x)=1-x,\forall x\in \mathbb{R}$ που επαληθεύει την αρχική.
Άρα όπως εξηγήσαμε οι λύσεις είναι η μηδενική καθώς και οι συναρτήσεις 1-x,x-1

.

#17

Έχω κάνει ένα αρχείο με τις λύσεις που συζητήθηκαν στην ΙΜΟ. Άλλες είναι των παιδιών, άλλες είναι οι επίσημες, άλλες δικές μου.
Καλή ανάγνωση!

IMO_2017_solutions.pdf: (240.75 KiB) Μεταφορτώθηκε 326 φορές

#18

Πολύ ωραία Σιλουανέ, ευχαριστούμε.

IMO 2017

IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

Re: IMO 2017

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