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

Evan Chen / USAMO Solution Notes

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

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

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

2015

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Да се реши в цели числа уравнението x2+xy+y2=(x+y3+1)3x^2+xy+y^2=\left(\frac{x+y}{3}+1\right)^3.
РешениеПоставяме a=x+y,b=x−y.a=x+y,\qquad b=x-y. Тогава a,b∈Za,b\in\mathbb Z са с еднаква четност и x=(a+b)/2x=(a+b)/2, y=(a−b)/2y=(a-b)/2. Уравнението става 3a2+b24=(a3+1)3.\frac{3a^2+b^2}{4}=\left(\frac a3+1\right)^3. Тъй като лявата страна е цяло число, от ((a+3)/3)3∈Z\left((a+3)/3\right)^3\in\mathbb Z следва 3∣a3\mid a. Нека a=3ca=3c. След умножение и опростяване получаваме b2=(c−2)2(4c+1).b^2=(c-2)^2(4c+1). Следователно 4c+14c+1 трябва да е квадрат на нечетно число, да кажем 4c+1=m24c+1=m^2. Обратно, всеки такъв избор на нечетно mm дава c=(m2−1)/4c=(m^2-1)/4 и b=±m(m2−9)4,b=\pm\frac{m(m^2-9)}4, откъдето x=3(m2−1)±(m3−9m)8,x=\frac{3(m^2-1)\pm(m^3-9m)}8,y=3(m2−1)∓(m3−9m)8.\qquad y=\frac{3(m^2-1)\mp(m^3-9m)}8. За нечетно mm тези числа са цели, така че получаваме всички решения. Ако запишем m=2n+1m=2n+1, по-чистата форма е x=n3+3n2−1,y=−n3+3n+1,x=n^3+3n^2-1,\qquad y=-n^3+3n+1, за произволно n∈Zn\in\mathbb Z, както и двойката с разменени координати. Това са точно всички целочислени решения.
Отвори задачатаEvan Chen VONVON USAMO 2015/1Условие — източник

Задача 3

Пълен запис
Условие
Нека S={1,2,…,n}S=\{1,2,\ldots,n\}, където n≥1n\ge1. Всяко от 2n2^n-те подмножества на SS се оцветява в червено или синьо; оцветява се самото подмножество, а не отделните му елементи. За всяко T⊆ST\subseteq S означаваме с f(T)f(T) броя на сините подмножества на TT. Да се намери броят на оцветяванията, за които за всеки две подмножества T1,T2⊆ST_1,T_2\subseteq S е изпълнено f(T1)f(T2)=f(T1∪T2)f(T1∩T2).f(T_1)f(T_2)=f(T_1\cup T_2)f(T_1\cap T_2).
РешениеОтговорът е 1+3n1+3^n. Нека за дадено оцветяване разгледаме носителя supp⁡={T⊆S:f(T)≠0}.\operatorname{supp}=\{T\subseteq S:f(T)\ne0\}. Едното оцветяване, при което всички подмножества са червени, очевидно работи. За всяко друго оцветяване носителят не е празен. Ако T1,T2T_1,T_2 са в него, то лявата страна в условието е положителна, следователно и T1∪T2T_1\cup T_2, и T1∩T2T_1\cap T_2 са в носителя. Освен това носителят е нагоре затворен: ако TT е в него и T⊆UT\subseteq U, то всяко синьо подмножество на TT е синьо подмножество и на UU, така че f(U)>0f(U)\gt{}0. Затова носителят има вид [X,S]={T:X⊆T⊆S}[X,S]=\{T:X\subseteq T\subseteq S\} за някое фиксирано X⊆SX\subseteq S. Остава да преброим оцветяванията с такъв носител. Първо разглеждаме случая X=∅X=\varnothing, тоест ∅\varnothing е синьо. Тогава изборът кои едноелементни множества са сини определя всичко: ако тези елементи образуват множество BB, единствената възможност е сини да са точно подмножествата на BB. Тогава f(T)=2∣T∩B∣f(T)=2^{|T\cap B|} и условието следва от тъждеството ∣T1∩B∣+∣T2∩B∣=∣(T1∪T2)∩B∣+∣(T1∩T2)∩B∣|T_1\cap B|+|T_2\cap B|=|(T_1\cup T_2)\cap B|+|(T_1\cap T_2)\cap B|. Единствеността се доказва индуктивно, защото от стойностите на ff за по-малки множества се възстановява цветът на следващото множество. Следователно при пълен носител има 2n2^n оцветявания. В общия случай, ако носителят е [X,S][X,S], след премахване на задължителните елементи на XX получаваме оцветяване с пълен носител върху S∖XS\setminus X. Ако ∣X∣=r|X|=r, тези оцветявания са 2n−r2^{n-r}, а изборите на XX са (nr)\binom nr. Следователно броят на нетривиалните оцветявания е ∑r=0n(nr)2n−r=3n.\sum_{r=0}^n\binom nr2^{n-r}=3^n. Заедно с изцяло червеното оцветяване получаваме 1+3n1+3^n.
Отвори задачатаEvan Chen VONVON USAMO 2015/3Условие — източник

Задача 4

Пълен запис
Условие
Стив поставя m≥1m\ge1 неразличими камъчета върху квадратчетата на решетка n×nn\times n. Върху едно квадратче може да има произволно голяма купчина. След това той може да прави ходове с камъчета по следния начин. Избират се четири квадратчета, които са върхове на правоъгълник, тоест имат координати (i,k)(i,k), (i,l)(i,l), (j,k)(j,k), (j,l)(j,l) за 1≤i,j,k,l≤n1\le i,j,k,l\le n, i<ji\lt{}j, k<lk\lt{}l. Един ход премахва по едно камъче от (i,k)(i,k) и (j,l)(j,l) и ги премества съответно в (i,l)(i,l) и (j,k)(j,k), или обратно. Две разположения са еквивалентни, ако едното може да се получи от другото чрез поредица от такива ходове. Колко различни нееквивалентни начина има Стив да постави камъчетата?
РешениеОтговорът е (m+n−1n−1)2.\binom{m+n-1}{n-1}^2. За всяко разположение записваме броя камъчета във всеки ред и във всеки стълб. Един ход само разменя две камъчета по диагоналите на правоъгълник, затова тези 2n2n числа не се променят. Значи двойката от редови и стълбови суми е инвариант. Броят на възможните редови суми е броят на слабите композиции на mm в nn части, тоест (m+n−1n−1)\binom{m+n-1}{n-1}; същото важи и за стълбовите суми. Така получаваме най-много (m+n−1n−1)2\binom{m+n-1}{n-1}^2 класа. Остава да докажем, че този инвариант е пълен и че всяка такава двойка суми се реализира. Мислим за камъчетата като за мултимножество от наредени двойки (x,y)(x,y), където xx е редът, а yy е стълбът. Фиксираните редови и стълбови суми са точно две мултимножества XX и YY от координати. Дадено разположение е получено, като съчетаем елементите на XX с елементите на YY по някакъв ред. Един ход с камъчета просто разменя две различни yy-координати между две камъчета с различни xx-координати; такива размени пораждат всяка пермутация на YY спрямо XX (ако редовете съвпадат, размяната не променя разположението). Следователно всички разположения с една и съща сигнатура са еквивалентни. Накрая, всяка сигнатура се реализира: подреждаме елементите на XX и YY в произволен ред и поставяме камъче в (Xi,Yi)(X_i,Y_i) за всяко i=1,…,mi=1,\ldots,m. Така класовете са точно колкото двойките редови и стълбови суми.
Отвори задачатаEvan Chen VONVON USAMO 2015/4Условие — източник

Задача 5

Пълен запис
Условие
Нека a,b,c,d,ea,b,c,d,e са различни положителни цели числа, за които a4+b4=c4+d4=e5.a^4+b^4=c^4+d^4=e^5. Да се докаже, че ac+bdac+bd е съставно число.
РешениеДа допуснем противното: p=ac+bdp=ac+bd е просто число. От ac≡−bd(modp)ac\equiv-bd\pmod p получаваме a4c4≡b4d4(modp).a^4c^4\equiv b^4d^4\pmod p. Понеже c4=e5−d4c^4=e^5-d^4 и b4=e5−a4b^4=e^5-a^4, след заместване следва a4(e5−d4)≡(e5−a4)d4(modp),a^4(e^5-d^4)\equiv(e^5-a^4)d^4\pmod p, тоест e5(a4−d4)≡0(modp).e^5(a^4-d^4)\equiv0\pmod p. Имаме p>ep\gt{}e: наистина, e5=a4+b4≤a5+b5<(ac+bd)5=p5e^5=a^4+b^4\le a^5+b^5\lt{}(ac+bd)^5=p^5. Значи p∤ep\nmid e, откъдето p∣a4−d4p\mid a^4-d^4. Следователно p≤a2+d2.p\le a^2+d^2. Аналогично, разменяйки ролите по симетричния начин, получаваме и p≤b2+c2.p\le b^2+c^2.Така ac+bd≤a2+d2,ac+bd≤b2+c2.ac+bd\le a^2+d^2,\qquad ac+bd\le b^2+c^2. Първото неравенство дава 0≤a(a−c)+d(d−b),0\le a(a-c)+d(d-b), а второто дава 0≤b(b−d)+c(c−a),0\le b(b-d)+c(c-a), или еквивалентно b(d−b)+c(a−c)≤0.b(d-b)+c(a-c)\le0. От равенството a4+b4=c4+d4a^4+b^4=c^4+d^4 следва, че a−ca-c и d−bd-b имат един и същи знак, защото функцията x4x^4 е строго растяща за положителни xx. Ако и двете са положителни, последното неравенство е невъзможно; ако и двете са отрицателни, първото е невъзможно. Случаят и двете да са нули би дал a=ca=c и b=db=d, противоречие с различността. Полученото противоречие показва, че ac+bdac+bd не е просто, а понеже е по-голямо от 11, то е съставно.
Отвори задачатаEvan Chen VONVON USAMO 2015/5Условие — източник

Задача 6

Пълен запис
Условие
Фиксираме 0<λ<10\lt{}\lambda\lt{}1 и нека AA е мултимножество от положителни цели числа. Нека An={a∈A:a≤n}A_n=\{a\in A: a\le n\}, като елементите се броят с кратност. Да предположим, че за всяко n∈Nn\in\mathbb N мултимножеството AnA_n съдържа най-много nλn\lambda числа. Докажете, че съществуват безкрайно много n∈Nn\in\mathbb N, за които сумата на елементите на AnA_n е най-много n(n+1)2λ\frac{n(n+1)}2\lambda.
РешениеЗа краткост #S\#S ще означава броя на елементите на мултимножеството SS, с кратности. Полагаме xn=nλ−#An≥0.x_n=n\lambda-\#A_n\ge0. Ще допуснем противното, а именно че твърдението е невярно за всички достатъчно големи nn. Тогава за тези nn имамеn(n+1)2λ<∑a∈Ana=1(#A1−#A0)+2(#A2−#A1)+⋯+n(#An−#An−1)=n#An−(#A1+⋯+#An−1)=n(nλ−xn)−((λ−x1)+(2λ−x2)+⋯+((n−1)λ−xn−1))=n(n+1)2λ−nxn+(x1+⋯+xn−1).\begin{aligned} \frac{n(n+1)}2\lambda &\lt{}\sum_{a\in A_n}a\\ &=1(\#A_1-\#A_0)+2(\#A_2-\#A_1)+\cdots+n(\#A_n-\#A_{n-1})\\ &=n\#A_n-(\#A_1+\cdots+\#A_{n-1})\\ &=n(n\lambda-x_n)-\big((\lambda-x_1)+(2\lambda-x_2)+\cdots+((n-1)\lambda-x_{n-1})\big)\\ &=\frac{n(n+1)}2\lambda-nx_n+(x_1+\cdots+x_{n-1}). \end{aligned}Следователно за всички достатъчно големи nn, да кажем за n≥N0n\ge N_0, е изпълнено xn<x1+x2+⋯+xn−1n.x_n\lt{}\frac{x_1+x_2+\cdots+x_{n-1}}{n}. С други думи, всеки достатъчно късен член е по-малък от средното аритметично на всички предишни членове. Остава да използваме целочисленото условие. За всяко n≥2n\ge2 разликата xn−xn−1=λ−(#An−#An−1)x_n-x_{n-1}=\lambda-(\#A_n-\#A_{n-1}) се различава от 00 на разстояние поне ε=min⁡{λ,1−λ}>0,\varepsilon=\min\{\lambda,1-\lambda\}\gt{}0, защото #An−#An−1\#A_n-\#A_{n-1} е цяло неотрицателно число. Значи всеки два съседни члена на редицата (xn)(x_n) се различават по абсолютна стойност поне с ε\varepsilon. Нека MM е средното аритметично на числата x1,x2,…,xN0x_1,x_2,\ldots,x_{N_0}. От предишното неравенство веднага следва по индукция, че xn<Mx_n\lt{}M за всяко n>N0n\gt{}N_0: ако всички предишни членове са по-малки от MM, тогава и средното им е по-малко от MM. Но щом съседните членове се различават поне с ε\varepsilon, за n>N0n\gt{}N_0 имаме xn+xn+1<2M−ε.x_n+x_{n+1}\lt{}2M-\varepsilon. Следователно средното аритметично на достатъчно дълга начална част на редицата пада под M−ε/3M-\varepsilon/3; крайните първи членове вече не могат да компенсират безкрайната опашка от двойки със средно под M−ε/2M-\varepsilon/2. Отново от неравенството xn<x1+x2+⋯+xn−1nx_n\lt{}\frac{x_1+x_2+\cdots+x_{n-1}}{n} получаваме, че за някое N1>N0N_1\gt{}N_0 е вярно xn<M−ε3(n>N1).x_n\lt{}M-\frac{\varepsilon}{3}\qquad(n\gt{}N_1).Повтаряме същия аргумент. След достатъчно далечен индекс всички xnx_n са по-малки от M−2ε/3M-2\varepsilon/3, после от M−εM-\varepsilon, и така нататък. След краен брой повторения получаваме xn<0x_n\lt{}0 за всички достатъчно големи nn, което противоречи на xn≥0x_n\ge0. Следователно допускането е невярно и желаното неравенство за сумата на елементите на AnA_n е изпълнено за безкрайно много стойности на nn. Забележка. Условието 0<λ<10\lt{}\lambda\lt{}1 е съществено; при λ=1\lambda=1 например мултимножеството {2,2,3,4,5,…}\{2,2,3,4,5,\ldots\} показва, че заключението може да се провали.
Отвори задачатаEvan Chen VONVON USAMO 2015/6Условие — източник