Προκριματικός Διαγωνισμός 2016

#1

Μιας και έκλεισε χτες η ημερομηνία για την δήλωση των ομάδων στην ΙΜΟ, βάζω τα προβλήματα του φετινού προκριματικού των μεγάλων.
Τα θέματα 3 και 4 είναι τα Α2 και C3 από τη περσινή λίστα της ΙΜΟ.

1. Δίνεται η ακολουθία a_n

που ορίζεται αναδρομικά ως εξής:
a_0=3

και $\displaystyle a_{n+1}-a_n=n(a_n-1)$ , για κάθε $n\geq 0$ .
Να βρεθούν όλοι οι θετικοί ακέραιοι

, για τους οποίους ισχύει (m,a_n)=1

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

.

2. Δίνεται τρίγωνο $AB\Gamma$ εγγεγραμμένο σε κύκλο C(O,R)

με $AB<A\Gamma<B \Gamma$ . Έστω $\Delta, E, Z$ τα μέσα των πλευρών των $B\Gamma, A\Gamma, AB$ αντίστοιχα και

το ίχνος του ύψους από τη κορυφή

. Με διαμέτρους τις πλευρές $AB, A\Gamma$ και εξωτερικά του τριγώνου, κατασκευάζουμε ημικύκλια c_1

και

αντίστοιχα. Οι ευθείες $\Delta Z$ και

τέμνουν το ημικύκλιο c_1

στα σημεία $\Pi$ , $\Sigma$ αντίστοιχα, και οι $\Delta E$ ,

τέμνουν το ημικύκλιο c_2

στα σημεία P, T

αντίστοιχα. Οι ευθείες $\Pi\Sigma$ και

τέμνονται στο σημείο

. Να αποδείξετε ότι :
(α) οι ευθείες $\Pi P$ και $\Sigma T$ τέμνονται στο σημείο

(β) οι ευθείες $\Pi P$ και $M \Delta$ τέμνονται επάνω στο κύκλο C(O,R)

.

3. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την

f(x-f(y))=f(f(x))-f(y)-1

για κάθε $x,y\in\mathbb{Z}$ .

4. Σε ένα πεπερασμένο σύνολο

με στοιχεία θετικούς ακέραιους, ονομάζουμε μία διαμέριση του

σε δύο μη κενά ξένα μεταξύ τους υποσύνολά του A_1, A_2

καλή, αν το ελάχιστο κοινό πολλαπλάσιο των στοιχείων του A_1

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

. Να προσδιορίσετε την ελάχιστη τιμή του

για την οποία υπάρχει σύνολο με στοιχεία

θετικούς ακέραιους που έχει ακριβώς 2015

καλές διαμερίσεις.

simantiris j. · #2

: Προκριματικός; b.png (17.21 KiB) Προβλήθηκε 4056 φορές

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

περνούν από το

αφού έχουν ως κέντρα τα μέσα των AB,AC

αντίστοιχα.Επιπλέον ο κύκλος των εννιά σημείων του ABC

περνά από τα σημεία Z,E,D,K

άρα το

είναι εγγράψιμο.

Επιπλέον χρησιμοποιώντας την εγγραψιμότητα των ARTK

και

έχουμε $\hat{RTK}=\hat{PAK}=\hat{PSK}$ οπότε το τετράπλευρο MTKS

είναι εγγράψιμο, άρα $\hat{SKT}+\hat{SMT}=180^{\circ}$ .
Όμως και το ZEDK

είναι εγγράψιμο, άρα $\hat{ZKE}=\hat{ZDE}$ οπότε $\hat{PDR}+\hat{SMT}=180^{\circ}$ δηλαδή το τετράπλευρο PDRM

είναι εγγράψιμο.

Έτσι παίρνουμε $\hat{MDR}=\hat{MPR}=\hat{SKA}$ .Επίσης $\hat{ZKB}=\hat{B}=\hat{EDC}$ (αφού $ZK=ZB,DE\parallel AB$ ) οπότε $\hat{MDC}=\hat{MDR}+\hat{EDC}=\hat{SKA}+\hat{SKB}=\hat{AKB}=90^{\circ}$ δηλαδή η

μεσοκάθετος της

, άρα κόβει τον C(O,R)

στο μέσο του τόξου BAC

.

Για να τελειώσει το πρόβλημα αρκεί να δείξουμε ότι και η

περνά από εκεί.Έστω ότι κόβει τον κύκλο στο

.Τότε έχουμε με κυνηγι γωνιών ότι $\hat{NCB}=\hat{PAB}=\hat{ZPA}=\hat{NAE}=\hat{NBC}\Rightarrow NB=NC$ (όπου κυρίως χρησιμοποιήσαμε ότι $ZP=PA,ZD\parallel AC$ ).Άρα το

είναι το μέσο του τόξου BAC

και η απόδειξη ολοκληρώθηκε.

simantiris j. · #3

Για λόγους πληρότητας, βάζω μια λύση και για το α), εργαζόμενος στο παραπάνω σχήμα.
Αρχικά όπως είπαμε τα τερτάπλευρα SAKB,ATCK

είναι εγγράψιμα, άρα $\hat{SAB}+\hat{A}+\hat{TAC}=\hat{KZB}+\hat{A}+\hat{TKC}=\hat{B}+\hat{A}+\hat{C}=180^{\circ}$ , δηλαδή τα S,A,T

συνευθειακά.
Επιπλέον το ZEDK

είναι εγγράψιμο συνεπώς $\hat{DZK}=\hat{ZDE}\Rightarrow \hat{PZS}=\hat{RET}\Rightarrow 2\hat{PKZ}=2\hat{RKE}\Rightarrow \hat{PKZ}=\hat{RKE}\Rightarrow \hat{SAP}=\hat{RAT}$ (όπου χρησιμοποιήσαμε ότι οι $\hat{SZP},\hat{RET}$ είναι εξωτερικές των ισοσκελών τριγώνων PZK,REK

αντίστοιχα, καθώς και την εγγραψιμότητα των SAKP,ARTK

) που επειδή ήδη έχουμε αποδείξει ότι S,A,T

συνευθειακά, δίνει ότι και P,A,R

έιναι συνευθειακά.

Marios V. · #4

silouan έγραψε: 1. Δίνεται η ακολουθία που ορίζεται αναδρομικά ως εξής:
και $\displaystyle a_{n+1}-a_n=n(a_n-1)$ , για κάθε $n\geq 0$ .
Να βρεθούν όλοι οι θετικοί ακέραιοι , για τους οποίους ισχύει για κάθε θετικό ακέραιο .

$a_{n+1}-a_{n}=n(a_n-1)$ οπότε $a_{n+1}-1=(n+1)(a_{n}-1)$ για κάθε $n\geq 0$ .
Επαγωγικά λοιπόν, $a_{n+1}-1=(n+1)!(a_0-1)=2(n+1)!$ και άρα $a_{n}=2(n!)+1$ για κάθε $n\geq 1$ .
Ελέγχουμε και την περίπτωση n=0

και πράγματι $a_{n}=2(n!)+1$ για κάθε $n\geq 0$ .

Θέτουμε τώρα n=p-3

όπου

πρώτος μεγαλύτερος του

. Έχουμε $a_{p-3}=2(p-3)!+1$ που από Wilson δίνει $a_{p-3} \equiv 2(p-3)!+1 \equiv (p-1)(p-2)(p-3)!+1 \equiv 0 (modp)$ για κάθε πρώτο

μεγαλύτερο του

.

Επομένως, αν

έχει πρώτο διαιρέτη

μεγαλύτερο του

θα έχουμε $p|a_{p-3}$ επομένως το

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

δουλεύουν.

Έτσι, τα ζητούμενα

είναι αυτά στην μορφή 2^t

όπου

μη-αρνητικός ακέραιος.

Αξίζει να αναφερθεί η ομοιότητα με τo φετινό 3 της BMO καθώς και με τo 4 της IMO του 2005.

#5

Φερμά_96 έγραψε: Αξίζει να αναφερθεί η ομοιότητα με τo φετινό 3 της BMO καθώς και με τo 4 της IMO του 2005.

Η όποια ομοιότητα με το 3ο της ΒΜΟ έγγυται στο γεγονός ότι κατασκευάστηκαν από τον ίδιο άνθρωπο

Την ομοιότητα (πέραν του ζητουμένου) με την άσκηση της ΙΜΟ δεν τη βλέπω! Θέλω να πω, ότι αν κάποιος ξέρει πώς λύνεται το πρόβλημα της ΙΜΟ, δεν ξέρει πώς να λύσει αυτό. Κάνω λάθος;

simantiris j. · #6

Εν αναμονεί των λύσεων των υπόλοιπων προβλημάτων βάζω άλλο ένα τρόπο εύρεσης της ακολουθίας (μακροσκελή)
Έχουμε ότι $a_{n+1}-(n+1)a_{n}+n=0$ .Θέτοντας όπου

το

έχουμε $a_{n}-na_{n-1}+n-1=0$ .
Αφαιρόντας κατά μέλη είναι $a_{n+1}-a_{n}-n(a_{n}-a_{n-1})=a_{n}-1=\frac{a_{n+1}-a_{n}}{n}$ .Θεωρούμε την ακολουθία $b_{n}=a_{n}-a_{n-1}$ και η σχέση γίνεται $b_{n+1}-nb_{n}=\frac{b_{n+1}}{n}\Rightarrow (n-1)b_{n+1}=n^2b_{n}\Rightarrow \frac{b_{n+1}}{b_{n}}=\frac{n^2}{n-1}$ οπότε τηλεσκοπικά $\frac{b_{n+1}}{b_{2}}=\frac{b_{n+1}}{b_{n}}\cdot \frac{b_{n}}{b_{n-1}}\cdot \cdot \cdot \frac{b_{3}}{b_{2}}=n^2(n-1)!\Rightarrow b_{n+1}=2nn!$ άρα $a_{n+1}-a_{n}=2nn!$
Αυτή τη φορά με τηλεσκοπικά αθροίσματα παίρνουμε $a_{n+1}-a_{1}=(a_{n+1}-a_{n})+...+(a_{2}-a_{1})=2(nn!+(n-1)(n-1)!+...+2)\Rightarrow a_{n+1}=2(nn!+(n-1)(n-1)!+...+2)+3\Rightarrow a_{n}=2((n-1)(n-1)!+...+2)+3$
Θα αποδείξουμε ότι το άθροισμα της παρένθεσης είναι απλά ίσο με n!-1

.Όντως όμως έχουμε
$(n-1)(n-1)!+(n-2)(n-2)!+...+2\cdot 2!-1=(n!-(n-1)!)+((n-1)!-(n-2)!)+...+2\cdot 2!-1=n!-1$
συνεπώς $a_{n}=2(n!-1)+3=2(n!)+1$ .
Το κακό με αυτό τον τρόπο είναι ότι εκτός από το ότι δεν είναι δυο γραμμές όπως του Φερμά_96, κάποιος μπορεί να μην υποψιαστεί ότι το μεγάλο άθροισμα είναι απλά ίσο με n!-1

και να χάσει το πρόβλημα.

gavrilos · #7

silouan έγραψε:3. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την

για κάθε $x,y\in\mathbb{Z}$ .

Γεια σε όλους.

Έστω $\displaystyle{P(x,y):f(x-f(y))=f(f(x))-f(y)-1 \ \forall x,y\in \mathbb{Z}}$ .

$\displaystyle{P(x,f(x)):f(x-f(f(x)))=-1 \ \forall x\in \mathbb{Z} \ (1)}$ .

$\displaystyle{P(x,x-f(f(x)))\overset{(1)}:f(x+1)=f(f(x)) \ \forall x\in \mathbb{Z} \ (2)}$ .

$\displaystyle{(P(f(x),x):f(0)=f(f(f(x)))-f(x)-1\overset{(2)}\Leftrightarrow f(x+2)-f(x)=f(0)+1 \ \forall x\in \mathbb{Z} \ (3)}$ .Άρα $\displaystyle{f(-2)=-1}$ .

Έστω $\displaystyle{k\in \mathbb{N}}$ .Έχουμε $\displaystyle{\begin{cases} f(2)-f(0)=f(0)+1\\ f(4)-f(2)=f(0)+1\\ \ldots \\ f(2k)-f(2k-2)=f(0)+1 \end{cases}\Rightarrow f(2k)-f(0)=k(f(0)+1)\Rightarrow \boxed{f(2k)=k(f(0)+1)+f(0)}}$ .

Επίσης, $\displaystyle{\begin{cases} f(0)-f(-2)=f(0)+1\\ f(-2)-f(-4)=f(0)+1\\ \ldots \\ f(-2k+2)-f(-2k)=f(0)+1 \end{cases}\Rightarrow \boxed{f(-2k)=-k(f(0)+1)+f(0)}}$ .

Ακόμη, $\displaystyle{\begin{cases} f(3)-f(1)=f(0)+1\\ f(5)-f(3)=f(0)+1\\ \ldots \\ f(2k+1)-f(2k-1)=f(0)+1 \end{cases}\Rightarrow \boxed{f(2k+1)=k(f(0)+1)+f(1)}}$ .

Τέλος $\displaystyle{\begin{cases} f(1)-f(-1)=f(0)+1\\ f(-1)-f(-3)=f(0)+1\\ \ldots \\ f(-2k+3)-f(-2k+1)=f(0)+1 \end{cases}\Rightarrow \boxed{f(-2k+1)=-k(f(0)+1)+f(1)}}$ .

Γενικότερα, $\displaystyle{f(x)=\begin{cases} \frac{x}{2}(f(0)+1)+f(0) \ , \ if \ x \ is \ even \\ \\ \frac{x-1}{2}(f(0)+1)+f(1) \ , \ if \ x \ is \ odd \end{cases}}$

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

$\bullet$ Ας υποθέσουμε ότι ο $\displaystyle{f(0)}$ είναι άρτιος.

$\displaystyle{P(0,0):f(-f(0))=f(f(0))-f(0)-1\Rightarrow \frac{-f(0)}{2}(f(0)+1)+f(0)=\frac{f(0)}{2}(f(0)+1)+f(0)-f(0)-1\Rightarrow }$

$\displaystyle{\Rightarrow f(0)(f(0)+1)=(f(0)+1)\Rightarrow f(0)=-1 \vee f(0)=1}$ ,δηλαδή ο $\displaystyle{f(0)}$ είναι περιττός,άτοπο.

$\bullet$ Έστω πως ο $\displaystyle{f(0)}$ είναι περιττός.

$\displaystyle{(2)\Rightarrow f(f(0))=f(1)\Rightarrow \frac{f(0)-1}{2}(f(0)+1)+f(1)=f(1)\Leftrightarrow f(0)=1 \vee f(0)=-1}$ .

Έστω πως $\displaystyle{f(0)=-1}$ .Τότε $\displaystyle{f(x)=\begin{cases} -1 \ , \ if \ x \ is \ even\\ f(1) \ , \ if \ x \ is \ odd \end{cases}}$

$\displaystyle{P(1,1):f(1-f(1))=f(f(1))-f(1)-1}$ .

$\displaystyle{P(0,1):f(-f(1))=f(-1)-f(1)-1=-1}$ .Προφανώς η $\displaystyle{f}$ είναι άρτια,άρα από τις δύο αυτές σχέσεις προκύπτει $\displaystyle{f(1-f(1))=-2-f(1)}$ .

Άρα,είτε $\displaystyle{-2-f(1)=-1\Leftrightarrow f(1)=-1\Leftrightarrow \boxed{f(x)=-1 \ \forall x\in \mathbb{Z}}}$ που είναι μια λύση,

είτε $\displaystyle{-2-f(1)=f(1)\Leftrightarrow f(1)=-1}$ που δίνει πάλι την ίδια λύση.

Έστω τώρα ότι $\displaystyle{f(0)=1}$ .Τότε $\displaystyle{f(x)=\begin{cases} x+1 \ , \ if \ x \ is \ even \\ x+f(1)-1 \ , \ if \ x \ is \ odd \end{cases}}$

$\displaystyle{P(1,1):f(1-f(1))=f(f(1))-f(1)-1}$ .Αν $\displaystyle{f(1)}$ περιττός,τότε $\displaystyle{1-f(1)}$ άρτιος,άρα $\displaystyle{2-f(1)=f(1)+f(1)-1-f(1)-1\Rightarrow f(1)=2}$ ,άτοπο.

Άρα ο $\displaystyle{f(1)}$ πρέπει να είναι άρτιος. $\displaystyle{P(0,1):f(-f(1))=f(f(0))-f(1)-1=f(1)-f(1)-1=-1\Leftrightarrow -f(1)+1=-1\Leftrightarrow f(1)=2}$ .

Άρα $\displaystyle{\boxed{f(x)=x+1 \ \forall x\in \mathbb{Z}}}$ ,που επαληθεύει,άρα είναι η δεύτερη λύση.

$\rule{430pt}{1pt}$

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

Marios V. · #8

silouan έγραψε:
Η όποια ομοιότητα με το 3ο της ΒΜΟ έγγυται στο γεγονός ότι κατασκευάστηκαν από τον ίδιο άνθρωπο

Το φαντάστηκα

silouan έγραψε:
Την ομοιότητα (πέραν του ζητουμένου) με την άσκηση της ΙΜΟ δεν τη βλέπω! Θέλω να πω, ότι αν κάποιος ξέρει πώς λύνεται το πρόβλημα της ΙΜΟ, δεν ξέρει πώς να λύσει αυτό. Κάνω λάθος;

Η ομοιότητα με την IMO είναι στην γενική στρατηγική (δεν είναι τόσο μεγάλη, αλλά υπάρχει):
Στο πρόβλημα του 05, αποδεικνύουμε ότι για κάθε αρκετά μεγάλο πρώτο ( p>3

) υπάρχει όρος της ακολουθίας που να είναι πολλαπλάσιο του

. Συγεκριμένα ο αντίστοιχος όρος είναι ο $a_{p-2}$ και το αποδεικνύουμε χρησιμοποιόντας Fermat.

Στο φετινό αποδεικνύουμε το ίδιο (για p>2

) αλλά με τον όρο $a_{p-3}$ και χρησιμοποιόντας το Wilson.

(Και θα μπορούσε να πει κανείς πως χονδρικά το $a^{p-2} \equiv 1/a (modp)$ είναι για το Fermat ό,τι είναι το 2(p-3)!+1= 0 (modp)

για το Wilson. Αν και το δεύτερο είναι σαφώς πιο δύσκολο να το σκεφτείς: καλύτερη αναλογία θα ήταν το (p-2)!-1= 0 (modp)

)

Αλλά ναι, το να λύσει κανείς αυτό της IMO σε καμία περίπτωση δεν σημαίνει πως ξέρει να λύσε κ'αυτό. Χρειάζονται και άλλες ιδέες όπως το 2(p-3)!+1= 0 (modp)

(και η επίλυση της αναδρομικής).

silouan έγραψε: 3. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την
για κάθε $x,y\in\mathbb{Z}$ .

Βάζω και μια λύση γ' αυτό (πιθανό να γίνεται και πιο σύντομα):

f(x-f(y))=f(f(x))-f(y)-1

για κάθε $x,y\in\mathbb{Z}$ (1).
Για x=f(y)

στην (1) έχουμε fff(y)=f(y)+f(0)+1

για κάθε $y\in\mathbb{Z}$ (2).

Για y=f(x)

στην (1) έχουμε f(x-ff(x))=-1

για κάθε $x\in\mathbb{Z}$ (3).

Για y=x-ff(x)

στην (1) και χρησιμοποιώντας την (3) έχουμε f(x+1)=ff(x)

(4).
Για

όπου

στην (3) έχουμε f(x+2)=ff(x+1)=fff(x)

(5).
Από (5) και (2) έχουμε f(x+2)=f(x)+f(0)+1

.

Από αυτό το σημείο πιθανό να υπάρχει και αρκετά πιο γρήγορος τρόπος.

Συνεχίζω ως εξής:

Επαγωγικά f(2k)=kc+f(0)

και

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

, όπου

. (6)

Από (4) για χ=2k

έχουμε

οπότε από (6), $ck+f(1)=f(ck+f(0))= \frac{c(ck+f(0)}{2}+f(0)$ ή $\frac{c(ck+f(0)-1)}{2}+f(1)$ Ανάλογα με την αρτιότητα του ck+f(0)

.

Επομένως, $\frac{c(2-c)}{2}k=\frac{c(f(0)-1)}{2}$ ή $\frac{cf(0)}{2}+f(0)-f(1)$ . Όμως το

διατρέχει τους ακεραίους οπότε c=0

ή

.

A) Για c=0

:

και

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

.
Θέτοντας x=f(1)+1

και

στην (1) έχουμε f(f(1)+1-f(1))=f(f(f(1)+1))-f(1)-1

Δηλαδή:

.
Όμως

ή

οπότε

.
Επομένως f(x)=-1

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

.

B) Για c=2

:

και

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

(όπου

).

Η (2) για y=0

δίνει

οπότε

οπότε:

ή

και άρα

ή

οπότε

.
Άρα

για κάθε

ακέραιο.

Μοναδικές λύσεις λοιπόν οι $f(x)\equiv -1$ και $f(x) \equiv x+1$ (οι οποίες, με αντικατάσταση, όντως επαληθεύουν την αρχική).

Edit: Με πρόλαβαν αλλά το αφήνω για τον κόπο μου

#9

silouan έγραψε: 4. Σε ένα πεπερασμένο σύνολο με στοιχεία θετικούς ακέραιους, ονομάζουμε μία διαμέριση του σε δύο μη κενά ξένα μεταξύ τους υποσύνολά του καλή, αν το ελάχιστο κοινό πολλαπλάσιο των στοιχείων του ισούται με το μέγιστο κοινό διαιρέτη των στοιχείων του . Να προσδιορίσετε την ελάχιστη τιμή του για την οποία υπάρχει σύνολο με στοιχεία θετικούς ακέραιους που έχει ακριβώς καλές διαμερίσεις.

Έστω μια καλή διαμέριση και έστω ότι $\mathrm{lcm}(A_1) = \mathrm{gcd}(A_2) = k$ . Αυτό σημαίνει ότι κάθε στοιχείο του A_1

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

και κάθε στοιχείο του A_2

διαιρεί το

.

Σε κάθε καλή διαμέριση $A = A_1 \cup A_2$ αντιστοιχούμε τον αριθμό $\mathrm{lcm}(A_1) = \mathrm{gcd}(A_2)$ .

Αν σε μια καλή διαμέριση $A_1 \cup A_2$ αντιστοιχίσουμε τον αριθμό

αυτό σημαίνει ότι κάθε στοιχείο του A_1

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

και κάθε στοιχείο του A_2

διαιρεί το

. Τότε κάθε στοιχείο του

είναι είτε πολλαπλάσιο, είτε διαιρέτης του

. Επιπλέον αν μας δοθεί το

τότε γνωρίζουμε όλες τις καλές διαμερίσεις που δίνουν το

αφού το

πρέπει να περιέχει όλα τα πολλαπλάσια, το δε A_2

πρέπει να περιέχει όλους τους διαιρέτες. Οπότε η διαμέριση καθορίζεται εκτός και αν $k \in A$ αφού τότε πιθανώς να έχουμε δύο επιλογές. Μια για $k \in A_1$ και μια για $k \in A_2$ .

Έστω $k_1 <k_2 < \cdots < k_m$ όλοι οι αριθμοί που αντιστοιχούν σε κάποια καλή διαμέριση. Ισχυρίζομαι ότι $k_i | k_{i+1}$ . Πράγματι σε αντίθετη περίπτωση ας υποθέσουμε ότι $d = (k_i,k_{i+1}) < k_i$ . Ας πάρουμε μια διαμέριση που μας δίνει το k_i

. Κάθε αριθμός που βάζουμε στο A_2

διαιρεί το k_i

. Άρα όλοι οι αριθμοί του A_2

είναι μικρότεροι ή ίσοι του k_i

και άρα είναι μικρότεροι του $k_{i+1}$ . Σίγουρα λοιπόν δεν είναι πολλαπλάσια του $k_{i+1}$ και άρα από τα προηγούμενα πρέπει να διαιρούν και τον $k_{i+1}$ . Τότε όμως έχουμε $\mathrm{gcd}(A_2) \leqslant d < k_i$ , άτοπο.

Έστω τώρα a_i

για $1 \leqslant i \leqslant m-1$ το πλήθος των στοιχείων του

που βρίσκονται στο διάστημα $(k_i,k_{i+1})$ . Έστω επίσης a_0

το πλήθος των στοιχείων που είναι μικρότερα του k_1

και

το πλήθος των στοιχείων που είναι μεγαλύτερα του k_m

.

Για $1 \leqslant i \leqslant m$ έστω b_i = 1

αν $k_i \in A$ και b_i=0

αν $k_i \notin A$ .

Για $1 \leqslant i \leqslant m$ έστω c_i

ο αριθμός των διαφορετικών διαμερίσεων που αντιστοιχούν στο k_i

. (Έχουμε ήδη δει ότι c_i=1

ή

.)

Αν c_i=2

αναγκαστικά πρέπει b_i = 1

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

να ισούται με k_i

. Πρέπει λοιπόν $a_i \geqslant 2$ . Ομοίως πρέπει $a_{i-1} \geqslant 2$ .

Αν c_i=1

τότε έχουμε τα εξής:
Αν b_i = 0

πρέπει $a_i \geqslant 2$ και $a_{i-1} \geqslant 2$ .
Αν b_1 = 1

πρέπει $a_i \geqslant 2$ ή $a_{i-1} \geqslant 2$ .

Από τα πιο πάνω λαμβάνω ότι
$\displaystyle{ \frac{a_{i-1}}{2} + b_i + \frac{a_i}{2} - c_i \geqslant 1}$
για κάθε $1 \leqslant i \leqslant m$ .

Για τις περιπτώσεις i=1

και

θα χρησιμοποιήσω επίσης τα εξής: Αν c_1 = 2

τότε
$\displaystyle{ a_0 + b_1 + \frac{a_1}{2} - c_1 \geqslant 2}$
και ομοίως αν c_m = 2

τότε
$\displaystyle{ a_{m-1} + b_m + \frac{a_m}{2} - c_m \geqslant 2}$

Προσθέτοντας, και λαμβάνοντας υπόψη ότι $c_1 + \cdots + c_m = 2015$ , καταλήγω στα εξής ανάλογα με τις τιμές των c_1,c_m

:

Αν

τότε
$\displaystyle{ (a_0 + \cdots + a_m) + (b_1 + \cdots + b_m) \geqslant (2 + (m-2) + 2) + 2015 = m + 2017 \geqslant 1008 + 2017 = 3025}$
[Είναι $m \geqslant 1008$ αφού $c_1 + \cdots + c_m = 2015$ με $c_i \leqslant 2$ για κάθε

.]

Αν

(ή

) τότε
$\displaystyle{ (a_0 + \cdots + a_m) + (b_1 + \cdots + b_m) \geqslant (1 + (m-2) + 2) + 2015 = m + 2016 \geqslant 1008 + 2016 = 3024}$

Αν c_1=c_m=1

τότε
$\displaystyle{ (a_0 + \cdots + a_m) + (b_1 + \cdots + b_m) \geqslant (1 + (m-2) + 1) + 2015 = m + 2015 \geqslant 1009 + 2015 = 3024}$
[Σε αυτήν την περίπτωση είναι $m-2 \geqslant 1007$ και άρα $m \geqslant 1009$ αφού $c_2 + \cdots + c_{m-1} = 2013$ με $c_i \leqslant 2$ για κάθε

.]

Άρα το

έχει τουλάχιστον 3024

στοιχεία.

Αυτό μπορεί να επιτευχθεί παίρνοντας όλους τους αριθμούς της μορφής 2^a3^b

όπου $(a,b) \in \{(0,0),(0,1),(1,0), (1,1),(1,2),(2,1) , \ldots, (1007,1007),(1007,1008),(1008,1007)\}$ .

Έχουμε ακριβώς $3 \times 1008 = 3024$ αριθμούς. Ο αριθμός

αντιστοιχεί σε μία καλή διάταξη, ενώ οι αριθμοί $6,6^2,\ldots,6^{1007}$ αντιστοιχούν σε δύο καλές διατάξεις ο κάθε ένας.

[Με τους πιο πάνω συμβολισμούς είναι $k_1 = 1, k_2 = 6, \ldots, k_{1008} = 6^{1007}$ , $a_0 = 0, a_1 = a_2 = \cdots = a_{1008} = 2$ , $b_1 = \cdots = b_{1008} = 1$ και $c_1=1, c_2 = \cdots = c_{1008} = 2$ .

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #10

silouan έγραψε: ↑
Τετ Ιουν 01, 2016 2:33 pm

3. Να βρεθούν όλες οι συναρτήσεις $f:\mathbb{Z}\rightarrow\mathbb{Z}$ που ικανοποιούν την

για κάθε $x,y\in\mathbb{Z}$ .

Μία λύση κάπως διαφορετική

Συμβολίζω με P(x,y)

την δοσμένη
P(x,f(x)): f(x-f(f(x)))=-1

.

Γενικά για x>0

θα έχω

έτσι αν $f(0)\neq -1$ τότε $f(2x_1)=f(2x_2)\Leftrightarrow x_1=x_2$ για $x_1,x_2\geq 1$
Αν πάλι f(2x_1+1)=f(2x_2+1)

τότε $f(f(2x_1+1))=f(f(2x_2+1))\Leftrightarrow 2(x_1+1)=2(x_2+1)$ άρα x_1=x_2

για $x_1,x_2\geq 1$
Έχω λοιπόν ότι αν x,y

φυσικοί με 2|x+y

τότε $f(x)=f(y)\Leftrightarrow x=y$ . Υποθέτω τώρα ότι για $x,y\in \mathbb{Z}$ είναι

Τότε $f(f(x))=f(f(y))\Leftrightarrow f(x+1)=f(y+1)$ και επαγωγικά f(x+n)=f(y+n)

για

φυσικό .Για

αρκετά μεγάλο οι x+n=x_1,y+n=χ_2

είναι θετικοί με f(x_1)=f(x_2)

και

για κάθε

φυσικό.Αν $x_2\geq x_1$ θέτω m=x_2-x_1

οπότε έχω

.Όμως

και έτσι

.Είναι

άρα $x_1=2x_2-x_1\Leftrightarrow x_2=x_1\Leftrightarrow x=y$ .Άρα η

είναι

.
Έτσι $f(x+1)=f(f(x))\Leftrightarrow f(x)=x+1,\forall x\in \mathbb{Z}$ .Έμεινε μόνο η περίπτωση f(0)=-1

.Σε αυτή την περίπτωση f(x+2)=f(x)

.
Άρα

για κάθε

άρτιο.Έστω f(x)=c,x

περιττός.Στην f(x-f(y))=f(x+1)-f(y)-1

θέτω

περιττό και παίρνω $f(c-c)=f(artios)-c-c1\Leftrightarrow -1=-1-c-1\Leftrightarrow c=-1$ .Άρα $f(x)=-1\forall x\in \mathbb{Z}$
Έχω λοιπόν $f(x)=x+1,\forall x\in \mathbb{Z}$ και $f(x)\equiv -1$ οι λύσεις.

Προκριματικός Διαγωνισμός 2016

Προκριματικός Διαγωνισμός 2016

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

Re: Προκριματικός 2015 (Μεγάλοι)

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