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

Evan Chen / EGMO Twitch Solution

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

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

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

2020

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Нека a0,a1,a2,…,a3030a_0,a_1,a_2,\ldots,a_{3030} е редица от положителни цели числа, за която2an+2=an+1+4an2a_{n+2}=a_{n+1}+4a_nза n=0,1,…,3028n=0,1,\ldots,3028. Докажете, че поне един от членовете на редицата се дели на 220202^{2020}.
РешениеЩе докажем по-силното твърдение: за всяко N≥1N\ge1, ако положителни цели числаa0,a1,…,a3Na_0,a_1,\ldots,a_{3N}удовлетворяват 2an+2=an+1+4an2a_{n+2}=a_{n+1}+4a_n, то някой от тези членове се дели на 4N4^N. При N=1010N=1010 това е точно делимост на 220202^{2020}. За N=1N=1 имаме a2=2a3−4a1a_2=2a_3-4a_1, следователно a2a_2 е четно. Тогава a1=2a2−4a0a_1=2a_2-4a_0 се дели на 44, което доказва базата. Нека N≥2N\ge2 и приемем твърдението за N−1N-1. Отak=2ak+1−4ak−1a_{k}=2a_{k+1}-4a_{k-1}следва първо, че a1,a2,…,a3N−1a_1,a_2,\ldots,a_{3N-1} са четни, а после, за 1≤k≤3N−21\le k\le 3N-2, че aka_k се дели на 44. Следователноb0=a14,b1=a24,…,b3N−3=a3N−24b_0=\frac{a_1}{4},\quad b_1=\frac{a_2}{4},\quad \ldots,\quad b_{3N-3}=\frac{a_{3N-2}}4са положителни цели числа и удовлетворяват същата рекурентна връзка. По индукционното предположение някое bib_i се дели на 4N−14^{N-1}, така че съответният ai+1a_{i+1} се дели на 4N4^N. Индукцията е завършена.
Отвори задачатаEvan Chen VONVON EGMO 2020/1Условие — източник

Задача 2

Пълен запис
Условие
Намерете всички списъци (x1,x2,…,x2020)(x_1,x_2,\ldots,x_{2020}) от неотрицателни реални числа, които удовлетворяват следните три условия:x1≤x2≤⋯≤x2020,x_1\le x_2\le \cdots\le x_{2020},x2020≤x1+1,x_{2020}\le x_1+1,и съществува пермутация (y1,y2,…,y2020)(y_1,y_2,\ldots,y_{2020}) на (x1,x2,…,x2020)(x_1,x_2,\ldots,x_{2020}), такава че∑i=12020((xi+1)(yi+1))2=\sum_{i=1}^{2020}\big((x_i+1)(y_i+1)\big)^2=8∑i=12020xi3.8\sum_{i=1}^{2020}x_i^3.
РешениеОтговорът е един от двата списъка0,…,0⏟1010,1,…,1⏟1010\underbrace{0,\ldots,0}_{1010},\underbrace{1,\ldots,1}_{1010}или1,…,1⏟1010,2,…,2⏟1010.\underbrace{1,\ldots,1}_{1010},\underbrace{2,\ldots,2}_{1010}.И в двата случая равенството се получава, като пермутацията сдвоява всяка по-малка стойност със съответната по-голяма стойност. Ще използваме следното неравенство за неотрицателни реални числа. Ако a,b≥0a,b\ge0 и ∣a−b∣≤1|a-b|\le1, то((a+1)(b+1))2≥4(a3+b3),\big((a+1)(b+1)\big)^2\ge4(a^3+b^3),като равенство има само когато {a,b}={0,1}\{a,b\}=\{0,1\} или {a,b}={1,2}\{a,b\}=\{1,2\}. Наистина,a3+b3=(a+b)((a−b)2+ab)≤(a+b)(1+ab)≤a^3+b^3=(a+b)((a-b)^2+ab)\le(a+b)(1+ab)\le(a+b+1+ab2)2=((a+1)(b+1))24.\left(\frac{a+b+1+ab}{2}\right)^2=\frac{\big((a+1)(b+1)\big)^2}{4}.Условията x1≤⋯≤x2020≤x1+1x_1\le\cdots\le x_{2020}\le x_1+1 показват, че всеки два члена на списъка се различават с най-много 11; затова неравенството може да се приложи към всяка двойка (xi,yi)(x_i,y_i). Получаваме∑i((xi+1)(yi+1))2≥\sum_i\big((x_i+1)(y_i+1)\big)^2\ge4∑i(xi3+yi3)=8∑ixi3,4\sum_i(x_i^3+y_i^3)=8\sum_i x_i^3,понеже (yi)(y_i) е пермутация на (xi)(x_i). В условието има равенство, следователно във всяка отделна двойка има равенство. Значи всяка двойка (xi,yi)(x_i,y_i) е от вида 0,10,1 или от вида 1,21,2. Поради x2020≤x1+1x_{2020}\le x_1+1 в списъка не могат едновременно да присъстват 00 и 22. Ако стойностите са 00 и 11, всяка нула трябва да бъде сдвоена с единица и всяка единица с нула, така че броевете им са равни: по 10101010. Аналогично, ако стойностите са 11 и 22, те също са по 10101010. Това дава точно двата списъка по-горе.
Отвори задачатаEvan Chen VONVON EGMO 2020/2Условие — източник

Задача 4

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число. Една пермутация на числата 1,2,…,m1,2,\ldots,m се нарича свежа, ако не съществува положително цяло число k<mk\lt{}m, за което първите kk числа в пермутацията са точно 1,2,…,k1,2,\ldots,k в някакъв ред. Нека fmf_m е броят на свежите пермутации на 1,2,…,m1,2,\ldots,m. Докажете, че fn≥n⋅fn−1f_n\ge n\cdot f_{n-1}.
РешениеЗа всяка свежа пермутация b1,b2,…,bn−1b_1,b_2,\ldots,b_{n-1} на 1,2,…,n−11,2,\ldots,n-1 ще построим nn различни свежи пермутации на 1,2,…,n1,2,\ldots,n. Първите n−1n-1 от тях се получават, като вмъкнем nn на kk-та позиция за k=1,2,…,n−1k=1,2,\ldots,n-1. Последната се получава по друг начин: заменяме числото n−1n-1 с nn и добавяме n−1n-1 в края. Например от 31423142 получаваме 53142,35142,31542,3145253142,35142,31542,31452 и 3152431524. Тези пермутации са свежи. При вмъкване на nn всяка забранена начална част с дължина k<nk\lt{}n или съдържа nn, което е невъзможно за множеството {1,2,…,k}\{1,2,\ldots,k\}, или не го съдържа и тогава би дала забранена начална част в старата пермутация. При последната конструкция краят е n−1n-1, а преди него стои nn на мястото на n−1n-1; отново всяка забранена начална част или съдържа nn, или би нарушила свежестта на началната пермутация. Освен това всички построени пермутации са различни. Ако изтрием nn от пермутация от първите n−1n-1 вида, получаваме обратно свежата пермутация b1,…,bn−1b_1,\ldots,b_{n-1}. При последния вид обаче изтриването на nn оставя n−1n-1 в края, така че получената пермутация на n−1n-1 е несвежа, защото първите n−2n-2 позиции са точно числата 1,2,…,n−21,2,\ldots,n-2. Следователно построението е инективно и дава поне nfn−1n f_{n-1} свежи пермутации.
Отвори задачатаEvan Chen VONVON EGMO 2020/4Условие — източник

Задача 6

Пълен запис
Условие
Намерете всички цели числа m>1m\gt{}1, за които редицата (an)n≥1(a_n)_{n\ge1}, зададена с a1=a2=1a_1=a_2=1, a3=4a_3=4 иan+2=m(an+1+an)−an−1a_{n+2}=m(a_{n+1}+a_n)-a_{n-1}за n≥2n\ge2, съдържа само точни квадрати.
РешениеОтговорът еm=2илиm=10.m=2\quad\text{или}\quad m=10.Първо проверяваме, че тези стойности работят. При m=2m=2 имаме an=Fn2a_n=F_n^2, където F1=F2=1F_1=F_2=1 са числата на Фибоначи; тъждеството следва от Fn+2=Fn+1+FnF_{n+2}=F_{n+1}+F_n. При m=10m=10 дефинираме u1=u2=1u_1=u_2=1, u3=2u_3=2 и un+2=3un+1+unu_{n+2}=3u_{n+1}+u_n за n≥2n\ge2. Тогаваun+32=10(un+22+un+12)−un2,u_{n+3}^2=10(u_{n+2}^2+u_{n+1}^2)-u_n^2,така че an=un2a_n=u_n^2 за всички nn. Остава да докажем, че няма други стойности. Първите членове саa1=1,a2=1,a3=4,a_1=1,\quad a_2=1,\quad a_3=4,a4=5m−1,a5=5m2+3m−1,a_4=5m-1,\quad a_5=5m^2+3m-1,a6=5m3+8m2−2m−4.\quad a_6=5m^3+8m^2-2m-4.Ако всички членове са точни квадрати, то a4a6a_4a_6 също е точен квадрат. Директно пресмятане дава16a4a6=400m4+560m3−288m2−288m+64=16a_4a_6=400m^4+560m^3-288m^2-288m+64=(20m2+14m−12110)2+50810m−8241100.\left(20m^2+14m-\frac{121}{10}\right)^2+\frac{508}{10}m-\frac{8241}{100}.НекаA=200m2+140m−121.A=200m^2+140m-121.Тогава A≡−1(mod20)A\equiv-1\pmod{20} и1600a4a6=A2+5080m−8241.1600a_4a_6=A^2+5080m-8241.За всяко цяло m>1m\gt{}1 имаме 5080m−8241>05080m-8241\gt{}0 и 42A+441>5080m−824142A+441\gt{}5080m-8241, следователноA2<1600a4a6<(A+21)2.A^2\lt{}1600a_4a_6\lt{}(A+21)^2.Но 1600a4a61600a_4a_6 е квадрат, чийто корен се дели на 2020. Тъй като A≡−1(mod20)A\equiv-1\pmod{20}, единствената възможност между AA и A+21A+21 е коренът да бъде A+1A+1. Значи1600a4a6=(A+1)2,1600a_4a_6=(A+1)^2,откъдето 5080m−8241=2A+15080m-8241=2A+1. След заместване на AA получаваме400m2−4800m+8000=0,400m^2-4800m+8000=0,тоест m=2m=2 или m=10m=10.
Отвори задачатаEvan Chen VONVON EGMO 2020/6Условие — източник