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

Evan Chen / IMO Solution Notes

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

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

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

2023

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

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

  • 2023 · 11-12: липсва задача 2

11-12

4 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички съставни цели числа n>1n\gt{}1 със следното свойство: ако d1<d2<⋯<dkd_1\lt{}d_2\lt{}\cdots\lt{}d_k са всички положителни делители на nn, то did_i дели di+1+di+2d_{i+1}+d_{i+2} за всяко 1≤i≤k−21\le i\le k-2.
РешениеОтговорът е: всички степени на прости числа pep^e с e≥2e\ge2. Първо проверяваме, че те работят. Ако n=pen=p^e, положителните делители са1,p,p2,…,pe.1,p,p^2,\ldots,p^e.Тогава условието ставаpi−1∣pi+pi+1,p^{i-1}\mid p^i+p^{i+1},което е очевидно вярно за всяко допустимо ii. Остава да докажем, че други примери няма. Нека nn има поне два различни прости делителя и нека p<qp\lt{}q са двата най-малки. Нека pep^e е най-голямата степен на pp, която дели nn и е по-малка от qq. Тогава най-малките делители на nn започват с1,p,p2,…,pe,q.1,p,p^2,\ldots,p^e,q.Следователно сред най-големите делители, в нарастващ ред, се срещат последователноnq,npe,npe−1.\frac nq,\qquad \frac n{p^e},\qquad \frac n{p^{e-1}}.Условието на задачата изискваnq∣npe+npe−1=(p+1)npe.\frac nq\mid \frac n{p^e}+\frac n{p^{e-1}}=\frac{(p+1)n}{p^e}.След съкращаване това означава, чеq(p+1)pe\frac{q(p+1)}{p^e}е цяло число. Но pp не дели нито qq, нито p+1p+1, което е невъзможно. Значи nn има само един прост делител, т.е. nn е степен на просто число. Понеже nn е съставно, степента е поне 22.
Отвори задачатаEvan Chen VONVON IMO 2023/1Условие — източник

Задача 3

Пълен запис
Условие
За всяко цяло число k≥2k\ge2 да се намерят всички безкрайни редици от положителни цели числа a1,a2,…a_1,a_2,\ldots, за които съществува полиномP(x)=xk+ck−1xk−1+⋯+c1x+c0,P(x)=x^k+c_{k-1}x^{k-1}+\cdots+c_1x+c_0,където c0,c1,…,ck−1c_0,c_1,\ldots,c_{k-1} са неотрицателни цели числа, такъв чеP(an)=an+1an+2⋯an+kP(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}за всяко цяло число n≥1n\ge1.
РешениеОтговорът е: точно аритметичните прогресии от положителни цели числа. Първо проверяваме, че всяка такава редица работи. Ако an=a1+d(n−1)a_n=a_1+d(n-1) за някое цяло d≥0d\ge0, тогаваan+1an+2⋯an+k=(an+d)(an+2d)⋯(an+kd),a_{n+1}a_{n+2}\cdots a_{n+k}=(a_n+d)(a_n+2d)\cdots(a_n+kd),затова можем да вземемP(x)=(x+d)(x+2d)⋯(x+kd).P(x)=(x+d)(x+2d)\cdots(x+kd).Този полином е моничен от степен kk и има неотрицателни цели коефициенти. Остава обратната посока. Първо ще покажем, че редицата е или строго растяща, или константна. От равенствата за n−1n-1 и nn получавамеan+k=P(an)P(an−1) an.a_{n+k}=\frac{P(a_n)}{P(a_{n-1})}\,a_n.Полиномът PP е строго растящ върху положителните цели числа. Ако за някое nn имаме an<an−1a_n\lt{}a_{n-1}, тогава формулата дава an+k<ana_{n+k}\lt{}a_n. Между индексите n+1,n+2,…,n+kn+1,n+2,\ldots,n+k има член, който е по-малък от предишния си член и е по-малък от ana_n; повтаряйки това, получаваме безкрайна строго намаляваща подпоследователност от положителни цели числа, което е невъзможно. Следователно a1≤a2≤⋯a_1\le a_2\le\cdots. Ако някъде има равенство an=an−1a_n=a_{n-1}, тогава горната формула дава an+k=ana_{n+k}=a_n. Заедно с монотонността това принуждава an−1=an=an+1=⋯=an+ka_{n-1}=a_n=a_{n+1}=\cdots=a_{n+k}, а после с индукция надолу и нагоре цялата редица е константна. Така занапред можем да считаме, че редицата е строго растяща. Нека CC е константа, за която P(x)<xk+Cxk−1P(x)\lt{}x^k+Cx^{k-1} за всяко положително цяло xx; например можем да вземем C=c0+c1+⋯+ck−1+1C=c_0+c_1+\cdots+c_{k-1}+1. Понеже редицата е строго растяща,an+k=P(an)an+1an+2⋯an+k−1<a_{n+k}=\frac{P(a_n)}{a_{n+1}a_{n+2}\cdots a_{n+k-1}}\lt{}ank+Cank−1(an+1)(an+2)⋯(an+k−1)<\frac{a_n^k+Ca_n^{k-1}}{(a_n+1)(a_n+2)\cdots(a_n+k-1)}\lt{}an+C+1.a_n+C+1.Значи разликите между съседни членове са ограничени. За всеки nn разглеждаме вектора от разликиΔ(n)=\Delta(n)=(an+1−an,an+2−an+1,…,an+k−an+k−1).(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k}-a_{n+k-1}).Той приема само краен брой стойности. Някакъв вектор (d1,…,dk)(d_1,\ldots,d_k) се среща за безкрайно много индекси NN. За тези NN имамеP(aN)=P(a_N)=(aN+d1)(aN+d1+d2)⋯(aN+d1+⋯+dk).(a_N+d_1)(a_N+d_1+d_2)\cdots(a_N+d_1+\cdots+d_k).Тъй като това равенство е вярно за безкрайно много стойности на aNa_N, следва тъждествотоP(X)=(X+d1)(X+d1+d2)⋯(X+d1+⋯+dk).P(X)=(X+d_1)(X+d_1+d_2)\cdots(X+d_1+\cdots+d_k).Следователно векторът на разликите, който може да се среща безкрайно често, е единствено определен от PP. Значи от някой момент нататък Δ(n)\Delta(n) е константен, а редицата съвпада с аритметична прогресия. Накрая същото равенство за PP връща разликите една стъпка назад, така че с низходяща индукция редицата е аритметична прогресия от самото начало.
Отвори задачатаEvan Chen VONVON IMO 2023/3Условие — източник

Задача 4

Пълен запис
Условие
Нека x1,x2,…,x2023x_1,x_2,\ldots,x_{2023} са две по две различни положителни реални числа, за коитоan=a_n=x2(x1+x2+⋯+xn)(1x1+1x2+⋯+1xn)\sqrt{\vphantom{x^2}(x_1+x_2+\cdots+x_n)\left(\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_n}\right)}е цяло число за всяко n=1,2,…,2023n=1,2,\ldots,2023. Да се докаже, че a2023≥3034a_{2023}\ge3034.
РешениеПърво, от неравенството на Коши-Шварц следва, че an≥na_n\ge n, а по-важното тук е, че редицата ana_n е строго растяща. Наистина, при добавяне на ново положително число произведението(x1+⋯+xn)(1x1+⋯+1xn)(x_1+\cdots+x_n)\left(\frac1{x_1}+\cdots+\frac1{x_n}\right)се увеличава строго. Понеже всички ana_n са цели числа и a1=1a_1=1, имаме an+1≥an+1a_{n+1}\ge a_n+1. Ще докажем по-силното твърдениеa2m+1≥3m+1a_{2m+1}\ge3m+1за всяко m≥0m\ge0. При m=0m=0 това е a1=1a_1=1. Нека nn е произволен и поставимu=x2xn+1xn+2.u=\sqrt{\vphantom{x^2}\frac{x_{n+1}}{x_{n+2}}}.Понеже xn+1≠xn+2x_{n+1}\ne x_{n+2}, имаме u≠1u\ne1. Прилагаме Коши-Шварц в следния вид към трите групи от членове: първите nn числа, числото xn+1x_{n+1} и числото xn+2x_{n+2}. Получавамеan+22=((x1+⋯+xn)+xn+1+xn+2)(1x1+⋯+1xn+1xn+1+1xn+2)≥(an+x2xn+1xn+2+x2xn+2xn+1)2=(an+u+1u)2.\begin{align*} a_{n+2}^2&=\left((x_1+\cdots+x_n)+x_{n+1}+x_{n+2}\right)\left(\frac1{x_1}+\cdots+\frac1{x_n}+\frac1{x_{n+1}}+\frac1{x_{n+2}}\right)\\ &\ge\left(a_n+\sqrt{\vphantom{x^2}\frac{x_{n+1}}{x_{n+2}}}+\sqrt{\vphantom{x^2}\frac{x_{n+2}}{x_{n+1}}}\right)^2 =\left(a_n+u+\frac1u\right)^2. \end{align*}Следователноan+2≥an+u+1u>an+2,a_{n+2}\ge a_n+u+\frac1u\gt{}a_n+2,като последното неравенство е строго поради u≠1u\ne1. Тъй като an+2a_{n+2} и ana_n са цели числа, получавамеan+2≥an+3.a_{n+2}\ge a_n+3.Прилагайки това през една стъпка, получавамеa2m+1≥a1+3m=3m+1.a_{2m+1}\ge a_1+3m=3m+1.За 2023=2⋅1011+12023=2\cdot1011+1 следваa2023≥3⋅1011+1=3034,a_{2023}\ge3\cdot1011+1=3034,както трябваше да се докаже.
Отвори задачатаEvan Chen VONVON IMO 2023/4Условие — източник

Задача 5

Пълен запис
Условие
Нека nn е положително цяло число. Японски триъгълник се състои от 1+2+⋯+n1+2+\cdots+n кръгчета, подредени в равностранна триъгълна форма така, че за всяко 1≤i≤n1\le i\le n в ii-тия ред има точно ii кръгчета, точно едно от които е оцветено в червено. Нинджа път в японския триъгълник е редица от nn кръгчета, която започва от горния ред, после на всяка стъпка преминава към едно от двете кръгчета непосредствено под текущото и завършва в долния ред. В зависимост от nn да се намери най-голямото kk, за което във всеки японски триъгълник съществува нинджа път, съдържащ поне kk червени кръгчета.
РешениеОтговорът еk=⌊log⁡2n⌋+1.k=\lfloor\log_2 n\rfloor+1.Първо даваме конструкция, която показва, че не можем да гарантираме повече. Разделяме редовете на блокове{1},{2,3},{4,5,6,7},…,\{1\},\quad \{2,3\},\quad \{4,5,6,7\},\quad\ldots,т.е. блокът с номер tt е 2t−1≤r≤2t−12^{t-1}\le r\le2^t-1. В ред rr от този блок поставяме червеното кръгче на позиция 2t−r2^t-r, броено отляво надясно. В рамките на един блок тези позиции строго намаляват, а по нинджа път позицията никога не намалява. Следователно един път може да срещне най-много едно червено кръгче от всеки блок. До ред nn има точно ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1 блока, така че има пример, в който никой нинджа път не съдържа повече от толкова червени кръгчета. Остава да докажем, че толкова червени кръгчета винаги могат да се намерят. За кръгчето на позиция jj в ред rr нека f(r,j)f(r,j) е най-големият възможен брой червени кръгчета по част от нинджа път, която завършва в това кръгче. За невалидни позиции поставяме f(r,j)=0f(r,j)=0. Тогаваf(r,j)=f(r,j)=max⁡(f(r−1,j−1),f(r−1,j))+ε(r,j),\max(f(r-1,j-1),f(r-1,j))+\varepsilon(r,j),където ε(r,j)=1\varepsilon(r,j)=1, ако кръгчето е червено, и 00 иначе. НекаSr=f(r,1)+f(r,2)+⋯+f(r,r).S_r=f(r,1)+f(r,2)+\cdots+f(r,r).Ще докажем рекурсиятаSr+1≥Sr+⌈Srr⌉+1.S_{r+1}\ge S_r+\left\lceil\frac{S_r}{r}\right\rceil+1.Избираме индекс mm, за който f(r,m)f(r,m) е максимално. В следващия ред има точно едно червено кръгче, следователно сумата на добавките ε\varepsilon е 11. Освен товаSr+1=∑j=1r+1max⁡(f(r,j−1),f(r,j))+1≥∑j=1mf(r,j)+∑j=m+1r+1f(r,j−1)+1=Sr+f(r,m)+1≥Sr+⌈Srr⌉+1.\begin{align*} S_{r+1}&=\sum_{j=1}^{r+1}\max(f(r,j-1),f(r,j))+1\\ &\ge\sum_{j=1}^{m} f(r,j)+\sum_{j=m+1}^{r+1} f(r,j-1)+1\\ &=S_r+f(r,m)+1\ge S_r+\left\lceil\frac{S_r}{r}\right\rceil+1. \end{align*}Сега ще покажем по индукция, че ако r=2c+sr=2^c+s, където 0≤s≤2c−10\le s\le2^c-1, тоSr≥cr+2s+1.S_r\ge cr+2s+1.При r=1r=1 това е ясно. Ако твърдението е вярно за rr, тогава от рекурсията и от ⌈Sr/r⌉≥c+1\lceil S_r/r\rceil\ge c+1 получавамеSr+1≥cr+2s+1+c+1+1=c(r+1)+2(s+1)+1.S_{r+1}\ge cr+2s+1+c+1+1=c(r+1)+2(s+1)+1.Ако s+1<2cs+1\lt{}2^c, това е точно нужната оценка за r+1r+1. Ако s+1=2cs+1=2^c, тогава r+1=2c+1r+1=2^{c+1} и дясната страна става (c+1)(r+1)+1(c+1)(r+1)+1, което отново е нужната оценка. За последния ред n=2c+sn=2^c+s имамеmax⁡jf(n,j)≥⌈Snn⌉≥c+1=⌊log⁡2n⌋+1.\max_j f(n,j)\ge\left\lceil\frac{S_n}{n}\right\rceil\ge c+1=\lfloor\log_2 n\rfloor+1.Това означава, че съществува нинджа път с поне ⌊log⁡2n⌋+1\lfloor\log_2 n\rfloor+1 червени кръгчета. Заедно с конструкцията това дава точната стойност.
Отвори задачатаEvan Chen VONVON IMO 2023/5Условие — източник