maths.bgmaths.bg
Всички колекции
IMO

Evan Chen / IMO Solution Notes

159 задачи от базата, подредени за бързо решаване по година или клас. Показаните източници са тези, записани към самите задачи.

29 години1 класаИма видими липси
По годинаПо клас

Избрана година

2017

Назад към папките

Открити липси за попълване от източника

  • 2017 · 11-12: липсва задача 3, 4

11-12

4 задачи

Задача 1

Пълен запис
Условие
За всяко цяло число a0>1a_0\gt{}1 дефинираме редицата a0,a1,a2,…a_0,a_1,a_2,\ldots чрезan+1={x2an,ако x2an е цяло число,an+3,иначеa_{n+1}=\begin{cases}\sqrt{\vphantom{x^2}a_n},&\text{ако }\sqrt{\vphantom{x^2}a_n}\text{ е цяло число},\\a_n+3,&\text{иначе}\end{cases}за всяко n≥0n\ge0. Определете всички стойности на a0a_0, за които съществува число AA, такова че an=Aa_n=A за безкрайно много стойности на nn.
РешениеОтговорът еa0≡0(mod3).a_0\equiv0\pmod3.Ще използваме следната лема. **Лема.** Нека cc е най-малкият член на редицата. Тогава или c≡2(mod3)c\equiv2\pmod3, или c=3c=3. Доказателство на лемата. Ясно е, че c≠1,4c\ne1,4. Ако cc беше точен квадрат, следващият член щеше да бъде c<c\sqrt c\lt{}c, невъзможно. Да допуснем, че c≢2(mod3)c\not\equiv2\pmod3. След като редицата стигне до cc, тя прибавя 33, докато достигне следващ точен квадрат. Този квадрат трябва да е един от(⌊c⌋+1)2,(⌊c⌋+2)2,(⌊c⌋+3)2.\left(\lfloor\sqrt c\rfloor+1\right)^2,\quad\left(\lfloor\sqrt c\rfloor+2\right)^2,\quad\left(\lfloor\sqrt c\rfloor+3\right)^2.След вземане на корен следва, чеc≤⌊c⌋+3≤c+3,c\le \lfloor\sqrt c\rfloor+3\le \sqrt c+3,откъдето c≤5c\le5. Тъй като c≠1,2,4,5c\ne1,2,4,5 в разглеждания случай, получаваме c=3c=3. Лемата е доказана. Ако a0≡0(mod3)a_0\equiv0\pmod3, тогава всички членове са кратни на 33. По лемата най-малкият член е 33, а3→6→9→3,3\to6\to9\to3,така че A=3A=3 се среща безкрайно много пъти. Ако a0≢0(mod3)a_0\not\equiv0\pmod3, тогава нито един член не е кратен на 33, в частност 33 не се среща. По лемата най-малкият член е 22 по модул 33. Но точен квадрат не може да бъде 22 по модул 33, така че след този момент редицата само нараства с по 33 и не може да има стойност, която се среща безкрайно много пъти. Следователно точно търсените начални стойности са кратните на 33.
Отвори задачатаEvan Chen VONVON IMO 2017/1Условие — източник

Задача 2

Пълен запис
Условие
Решете над R\mathbb R функционалното уравнениеf(f(x)f(y))+f(x+y)=f(xy).f(f(x)f(y))+f(x+y)=f(xy).
РешениеЕдинствените решения саf(x)≡0,f(x)=x−1,f(x)=1−x,f(x)\equiv0,\qquad f(x)=x-1,\qquad f(x)=1-x,и директна проверка показва, че те наистина работят. Ако ff е решение, то −f-f също е решение. Освен това, ако f(0)=0f(0)=0, поставянето на y=0y=0 веднага дава f≡0f\equiv0. Затова занапред можем да приемем, че f(0)>0f(0)\gt{}0. Първо ще докажем, чеf(z)=0⟺z=1,f(z)=0\quad\Longleftrightarrow\quad z=1,както и че f(0)=1f(0)=1 и f(1)=0f(1)=0. Ако f(z)=0f(z)=0 и z≠1z\ne1, поставямеx=z,y=zz−1,x=z,\qquad y=\frac{z}{z-1},така че x+y=xyx+y=xy. От уравнението следва f(0)=0f(0)=0, противоречие. Обратно, при x=y=0x=y=0 получаваме f(f(0)2)=0f(f(0)^2)=0, следователно по вече доказаното f(0)2=1f(0)^2=1. Понеже f(0)>0f(0)\gt{}0, имаме f(0)=1f(0)=1, а оттук и f(1)=0f(1)=0. Сега ще покажем, че ff е инективна. При y=1y=1 уравнението даваf(x+1)=f(x)−1,f(x+1)=f(x)-1,следователно по индукцияf(x+n)=f(x)−n(1)f(x+n)=f(x)-n\tag{1}за всяко цяло n≥0n\ge0. Да допуснем, че f(a)=f(b)f(a)=f(b). Използвайки (1), можем да прибавим към aa и bb един и същ достатъчно голям цял брой, така че да съществуват реални x,yx,y сx+y=a+1,xy=b.x+y=a+1,\qquad xy=b.За тези x,yx,y получавамеf(f(x)f(y))=f(xy)−f(x+y)=f(f(x)f(y))=f(xy)-f(x+y)=f(b)−f(a+1)=f(b)+1−f(a)=1.f(b)-f(a+1)=f(b)+1-f(a)=1.С помощта на (1) това даваf(f(x)f(y)+1)=0.f(f(x)f(y)+1)=0.Значи f(x)f(y)+1=1f(x)f(y)+1=1, тоест f(x)f(y)=0f(x)f(y)=0. От първата част следва 1∈{x,y}1\in\{x,y\}, а това заедно с x+y=a+1x+y=a+1 и xy=bxy=b принуждава a=ba=b. Следователно ff е инективна. Остава финалната стъпка. При y=0y=0 имамеf(f(x))+f(x)=1.f(f(x))+f(x)=1.Прилагайки същото към f(x)f(x), получавамеf(f(f(x)))=1−f(f(x))=f(x).f(f(f(x)))=1-f(f(x))=f(x).От друга страна f(f(x))=1−f(x)f(f(x))=1-f(x), така чеf(1−f(x))=f(x).f(1-f(x))=f(x).Понеже ff е инективна, 1−f(x)=x1-f(x)=x, тоест f(x)=1−xf(x)=1-x. Със симетрията f↦−ff\mapsto -f получаваме и f(x)=x−1f(x)=x-1, а нулевото решение вече беше отделено.
Отвори задачатаEvan Chen VONVON IMO 2017/2Условие — източник

Задача 5

Пълен запис
Условие
Нека N≥1N\ge1 е фиксирано. В редица стоят N(N+1)N(N+1) футболисти с различни ръстове. Сър Алекс Сонг иска да премахне N(N−1)N(N-1) футболисти, така че да остане нова редица от 2N2N футболисти, в която са изпълнени следните NN условия: между двамата най-високи няма никого, между третия и четвъртия най-висок няма никого, …\ldots, между двамата най-ниски няма никого. Докажете, че това е възможно.
РешениеЩе докажем твърдението с индукция по NN. Подреждаме футболистите по ръст и ги разделяме на NN групи от по N+1N+1 души:G1={1,2,…,N+1},G_1=\{1,2,\ldots,N+1\},G2={N+2,…,2N+2},…\quad G_2=\{N+2,\ldots,2N+2\},\quad\ldotsкъдето номерата означават поредност по ръст. Накрая ще изберем по двама души от всяка група. Сканираме редицата отляво надясно, докато за първи път срещнем двама футболисти от една и съща група, да речем GkG_k. Запазваме тези двама, а всички сканирани дотук футболисти, както и цялата група GkG_k, изключваме от по-нататъшното разглеждане. Запазената двойка ще бъде най-лявата двойка в крайния избор и между двамата няма да остане никой. Във всяка от останалите групи са премахнати най-много по един вече сканиран футболист, така че във всяка остават поне NN души. След като махнем групата GkG_k, остават N−1N-1 групи, всяка с поне NN души, и можем да приложим индукционното предположение. Получаваме по две избрани лица от всяка останала група, като съответните двойки са съседни в окончателната редица. Така общо остават 2N2N футболисти, по двама от всяка група по ръст. Понеже групите са последователни по ръст, тези двойки са точно двойката на двамата най-високи, после третия и четвъртия най-висок, и така нататък до двамата най-ниски. Условието е изпълнено.711251091216843
Отвори задачатаEvan Chen VONVON IMO 2017/5Условие — източник

Задача 6

Пълен запис
Условие
Примитивна решетъчна точка е наредена двойка цели числа (x,y)(x,y), за която gcd⁡(x,y)=1\gcd(x,y)=1. Докажете, че ако SS е крайно множество от примитивни решетъчни точки, то съществува неконстантен хомогенен полином f(x,y)f(x,y) с цели коефициенти, такъв че f(x,y)=1f(x,y)=1 за всяка точка (x,y)∈S(x,y)\in S.
РешениеЩе докажем твърдението с индукция по ∣S∣|S|. При една точка (a,b)(a,b) то е точно лемата на Безу: избираме цели u,vu,v с ua+vb=1ua+vb=1 и вземаме f(x,y)=ux+vyf(x,y)=ux+vy. За индукционната стъпка нека вече имаме точки (ai,bi)(a_i,b_i) за i=1,…,mi=1,\ldots,m, и искаме да добавим още една примитивна точка (am+1,bm+1)(a_{m+1},b_{m+1}). Чрез подходяща линейна замяна с целочислена матрица с детерминанта 11 можем да приемем, че новата точка е (1,0)(1,0). Наистина, избираме u,vu,v така, чеuam+1+vbm+1=1,ua_{m+1}+vb_{m+1}=1,и използваме матрицатаT=(uv−bm+1am+1).T=\begin{pmatrix}u&v\\-b_{m+1}&a_{m+1}\end{pmatrix}.Тя изпраща (am+1,bm+1)(a_{m+1},b_{m+1}) в (1,0)(1,0) и има детерминанта 11. След такава замяна хомогенността и целочислеността на коефициентите се запазват. По индукционно предположение има хомогенен полином g(x,y)g(x,y) с цели коефициенти, който е равен на 11 върху старите mm точки. Нека d=deg⁡gd=\deg g. Ще търсим новия полином във видаf(x,y)=g(x,y)M−CxdM−m∏i=1m(bix−aiy),f(x,y)=g(x,y)^M-Cx^{dM-m}\prod_{i=1}^m(b_i x-a_i y),където MM е достатъчно голямо цяло число, а CC също ще бъде цяло число. За всяка стара точка (ai,bi)(a_i,b_i) произведението има нулев множител, така че f(ai,bi)=1f(a_i,b_i)=1. Остава да осигурим f(1,0)=1f(1,0)=1, тоест1=g(1,0)M−C∏i=1mbi.1=g(1,0)^M-C\prod_{i=1}^m b_i.Ако ∏ibi=0\prod_i b_i=0, тогава за някое ii имаме bi=0b_i=0, откъдето ai=±1a_i=\pm1. Понеже g(ai,0)=1g(a_i,0)=1 и gg е хомогенен, получаваме g(1,0)=±1g(1,0)=\pm1; вземаме четно MM и условието е изпълнено. Остава случаят ∏ibi≠0\prod_i b_i\ne0. Ще покажем, че g(1,0)g(1,0) е взаимнопросто с всяко bib_i. Понеже gg е хомогенен и g(ai,bi)=1g(a_i,b_i)=1, по модул bib_i имаме1=g(ai,bi)≡g(ai,0)=aidg(1,0)(modbi).1=g(a_i,b_i)\equiv g(a_i,0)=a_i^d g(1,0)\pmod{b_i}.А тъй като gcd⁡(ai,bi)=1\gcd(a_i,b_i)=1, това означава, че g(1,0)g(1,0) е обратимо по модул bib_i. Следователно g(1,0)g(1,0) е взаимнопросто с ∏ibi\prod_i b_i. Избираме MM достатъчно голямо и кратно на φ(∣∏ibi∣)\varphi\left(\left|\prod_i b_i\right|\right). Тогаваg(1,0)M≡1(mod∏ibi),g(1,0)^M\equiv1\pmod{\prod_i b_i},така чеC=g(1,0)M−1∏ibiC=\frac{g(1,0)^M-1}{\prod_i b_i}е цяло число. С този избор f(1,0)=1f(1,0)=1, а вече проверихме старите точки. Индукцията е завършена.
Отвори задачатаEvan Chen VONVON IMO 2017/6Условие — източник