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

Evan Chen / USAMO Solution Notes

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

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

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

2018

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа, за които a+b+c=4x2abc3a+b+c=4\sqrt[3]{\vphantom{x^2}abc}. Да се докаже, че2(ab+bc+ca)+4min⁡(a2,b2,c2)≥a2+b2+c2.2(ab+bc+ca)+4\min(a^2,b^2,c^2)\ge a^2+b^2+c^2.
РешениеБез ограничение нека c=min⁡(a,b,c)c=\min(a,b,c). Понеже условието и неравенството са хомогенни, можем да мащабираме така, че c=1c=1. Тогава трябва да докажем4ab+2a+2b+3≥(a+b)2,4ab+2a+2b+3\ge (a+b)^2,а условието ставаa+b+1=4x2ab3.a+b+1=4\sqrt[3]{\vphantom{x^2}ab}.Поставяме t=x2ab3t=\sqrt[3]{\vphantom{x^2}ab}. Тогава a+b=4t−1a+b=4t-1 и исканото неравенство се свежда до4t3+2(4t−1)+3≥(4t−1)2.4t^3+2(4t-1)+3\ge(4t-1)^2.След пренасяне това е точно0≤4t3−16t2+16t=4t(t−2)2,0\le4t^3-16t^2+16t=4t(t-2)^2,което е вярно за t>0t\gt{}0. Следователно първоначалното неравенство е доказано. Равенство настъпва, когато t=2t=2, тоест при нормировката c=1c=1 имаме ab=8ab=8 и a+b=7a+b=7, а след това можем да върнем мащаба. Изборът на cc като минималното число е единствената загуба на общност; ако минимумът се достига при друг член, просто преименуваме променливите.
Отвори задачатаEvan Chen VONVON USAMO 2018/1Условие — източник

Задача 2

Пълен запис
Условие
Да се намерят всички функции f:(0,∞)→(0,∞)f:(0,\infty)\to(0,\infty), за коитоf(x+1y)+f(y+1z)+f(z+1x)=1f\left(x+\frac1y\right)+f\left(y+\frac1z\right)+f\left(z+\frac1x\right)=1за всички x,y,z>0x,y,z\gt{}0 с xyz=1xyz=1.
РешениеЩе докажем, че всички решения саf(x)=kx+1+1−k3,−12≤k≤1.f(x)=\frac{k}{x+1}+\frac{1-k}{3},\qquad -\frac12\le k\le1.Тези функции се проверяват директно. Нека x=b/cx=b/c, y=c/ay=c/a, z=a/bz=a/b, където a,b,c>0a,b,c\gt{}0. Тогава уравнението е еквивалентно наf(a+bc)+f(b+ca)+f(c+ab)=1.f\left(\frac{a+b}{c}\right)+f\left(\frac{b+c}{a}\right)+f\left(\frac{c+a}{b}\right)=1.Дефинираме g:(0,1)→(0,∞)g:(0,1)\to(0,\infty) чрезg(t)=f(1t−1).g(t)=f\left(\frac1t-1\right).Получавамеg(u)+g(v)+g(w)=1g(u)+g(v)+g(w)=1за всички положителни u,v,wu,v,w с u+v+w=1u+v+w=1. Оттук следва, че gg удовлетворява уравнението на Йенсен върху интервалите, където то има смисъл: ако r+s<1r+s\lt{}1, тоg(r)+g(s)=1−g(1−r−s)=2g(r+s2).g(r)+g(s)=1-g(1-r-s)=2g\left(\frac{r+s}{2}\right).Тъй като gg е ограничена отдолу, стандартният извод за уравнението на Йенсен дава, че gg е афинна: g(t)=kt+ℓg(t)=kt+\ell. Замествайки u+v+w=1u+v+w=1, получаваме k+3ℓ=1k+3\ell=1, тоестg(t)=kt+1−k3.g(t)=kt+\frac{1-k}{3}.Понеже ff има положителни стойности върху (0,∞)(0,\infty), същото важи за gg върху (0,1)(0,1), откъдето се получава −12≤k≤1-\frac12\le k\le1. Връщането към ff дава точно посоченото семейство.
Отвори задачатаEvan Chen VONVON USAMO 2018/2Условие — източник

Задача 3

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число и нека a1,…,ama_1,\ldots,a_m са всички m=φ(n)m=\varphi(n) положителни цели числа, по-малки от nn и взаимно прости с nn. Да се предположи, че всеки прост делител на mm дели и nn. Да се докаже, че mm делиa1k+a2k+⋯+amka_1^k+a_2^k+\cdots+a_m^kза всяко положително цяло число kk.
РешениеЗа N≥2N\ge2 некаA(N)={1≤x<N:gcd⁡(x,N)=1},A(N)=\{1\le x\lt{}N:\gcd(x,N)=1\},S(N,k)=∑x∈A(N)xk.\qquad S(N,k)=\sum_{x\in A(N)}x^k.Ще докажем по-силното твърдение: ако p∣Np\mid N, тоνp(S(N,k))≥νp(φ(N))\nu_p(S(N,k))\ge\nu_p(\varphi(N))за всяко k≥1k\ge1. Прилагано към простите pp, които делят m=φ(n)m=\varphi(n), а по условие делят и nn, това веднага дава m∣S(n,k)m\mid S(n,k). Първо разглеждаме N=peN=p^e. За нечетно pp вземаме примитивен корен gg по модул pep^e и получаваме геометрична прогресияS(pe,k)≡1+gk+g2k+⋯+g(φ(pe)−1)k(modpe).S(p^e,k)\equiv1+g^k+g^{2k}+\cdots+g^{(\varphi(p^e)-1)k}\pmod{p^e}.Ако p−1∤kp-1\nmid k, знаменателят в сумата на прогресията не се дели на pp, така че сумата е 00 по модул pep^e. Ако p−1∣kp-1\mid k, лемата за повдигане на показателя дава точно поне e−1=νp(φ(pe))e-1=\nu_p(\varphi(p^e)) множителя pp. За p=2p=2 случаят с нечетно kk се получава чрез сдвояване на xx и 2e−x2^e-x, а при четно kk се използва, че 55 поражда квадратичните остатъци по модул 2e2^e. Ще използваме и следствие: за всички t,kt,k и просто pp е вярноνp(1k+2k+⋯+tk)≥νp(t)−1,\nu_p(1^k+2^k+\cdots+t^k)\ge\nu_p(t)-1,което следва от предишния абзац, като отделим членовете, делящи се на pp, и приложим индукция. Сега добавяме простите делители на NN един по един. Да предположим, че твърдението е доказано за NN, и да разгледаме NqNq. Ако q∤Nq\nmid N, тоA(Nq)={a+Nh:a∈A(N), 0≤h<q}∖qA(N).A(Nq)=\{a+Nh: a\in A(N),\ 0\le h\lt{}q\}\setminus qA(N).След разлагане с бинома получавамеS(Nq,k)=S(Nq,k)=(q−qk)S(N,k)(q-q^k)S(N,k)+∑j=1k(kj)NjS(N,k−j)∑h=1q−1hj.+\sum_{j=1}^k {k\choose j}N^jS(N,k-j)\sum_{h=1}^{q-1}h^j.Първият член носи вече наличните множители от φ(N)\varphi(N) и допълнителните от q−1q-1, а във всеки член на сумата следствието дава νp(q−1)−1\nu_p(q-1)-1 множителя, докато NjN^j добавя поне още един множител pp, когато е нужно. Ако q∣Nq\mid N, формулата е същата без изваждането на qA(N)qA(N) и няма нов множител на φ\varphi за покриване. Така индукцията доказва силното твърдение, а оттам и задачата.
Отвори задачатаEvan Chen VONVON USAMO 2018/3Условие — източник

Задача 4

Пълен запис
Условие
Нека pp е просто число и нека a1,…,apa_1,\ldots,a_p са цели числа. Да се докаже, че съществува цяло число kk, за което числатаa1+k, a2+2k, …, ap+pka_1+k,\ a_2+2k,\ \ldots,\ a_p+pkдават поне p2\frac p2 различни остатъка при деление на pp.
РешениеДостатъчно е да разгледаме k=0,1,…,p−1k=0,1,\ldots,p-1. За всяко такова kk построяваме граф GkG_k с върхове 1,2,…,p1,2,\ldots,p, като свързваме ii и jj тогава и само тогава, когатоai+ik≡aj+jk(modp).a_i+ik\equiv a_j+jk\pmod p.За фиксирана двойка i≠ji\ne j това сравнение определя единствено kk по модул pp, понежеk≡−ai−aji−j(modp).k\equiv-\frac{a_i-a_j}{i-j}\pmod p.Следователно всяко ребро {i,j}\{i,j\} се появява в точно един от графите G0,G1,…,Gp−1G_0,G_1,\ldots,G_{p-1}. Общо има (p2){p\choose2} ребра, така че по принципа на Дирихле някой граф GkG_k има най-много1p(p2)=p−12\frac1p{p\choose2}=\frac{p-1}{2}ребра. Всеки граф с pp върха и ee ребра има поне p−ep-e свързани компоненти, следователно този граф има понеp−p−12=p+12p-\frac{p-1}{2}=\frac{p+1}{2}свързани компоненти. В една свързана компонента всички съответни числа ai+ika_i+ik имат един и същ остатък, а различните компоненти могат само да увеличат броя на различните остатъци. Значи за избраното kk има поне (p+1)/2(p+1)/2, в частност поне p/2p/2, различни остатъка.
Отвори задачатаEvan Chen VONVON USAMO 2018/4Условие — източник

Задача 5

Пълен запис
Условие
Нека ABCDABCD е изпъкнал вписан четириъгълник с E=AC∩BDE=AC\cap BD, F=AB∩CDF=AB\cap CD и G=DA∩BCG=DA\cap BC. Окръжността, описана около △ABE\triangle ABE, пресича правата CBCB в точките BB и PP, а окръжността, описана около △ADE\triangle ADE, пресича правата CDCD в точките DD и QQ. Да се предположи, че C,B,P,GC,B,P,G са колинеарни в този ред, както и C,Q,D,FC,Q,D,F в този ред. Ако M=FP∩GQM=FP\cap GQ, да се докаже, че ∠MAC=90∘\angle MAC=90^\circ.
РешениеЩе използваме точка на Микел и теоремата на Пап. Първо доказваме две прости наблюдения. По степен на точката CC имамеCQ⋅CD=CA⋅CE=CB⋅CP,CQ\cdot CD=CA\cdot CE=CB\cdot CP,следователно самопресичащият се четириъгълник PQDBPQDB е вписан. Освен това EE лежи на PQPQ, защото с насочени ъгли∠AEP=∠ABP=∠ABC=∠ADC=∠ADQ=∠AEQ.\angle AEP=\angle ABP=\angle ABC=\angle ADC=\angle ADQ=\angle AEQ.Нека H=PD∩BQH=PD\cap BQ. От стандартното свойство на точката на Микел за пълния четириъгълник с върхове по правите PBPB, BQBQ, QDQD, DPDP следва, че AA е точката на Микел и че AA е петата на перпендикуляра от HH към CECE. Затова HA⊥CEHA\perp CE, а понеже EE лежи на ACAC, получаваме HA⊥ACHA\perp AC. Остава да свържем HH с дадената точка MM. Прилагаме теоремата на Пап към двете колинеарни тройки B,P,GB,P,G и D,Q,FD,Q,F. Трите пресечни точки на съответните противоположни страни лежат на една права; в нашите означения това са H=PD∩BQH=PD\cap BQ, A=BF∩DGA=BF\cap DG и M=PF∩GQM=PF\cap GQ. Следователно H,A,MH,A,M са колинеарни. Понеже HA⊥ACHA\perp AC, същото важи и за MAMA, тоест ∠MAC=90∘\angle MAC=90^\circ.ABCDEFGPQHM
Отвори задачатаEvan Chen VONVON USAMO 2018/5Условие — източник

Задача 6

Пълен запис
Условие
Нека ana_n е броят на пермутациите (x1,x2,…,xn)(x_1,x_2,\ldots,x_n) на (1,2,…,n)(1,2,\ldots,n), за които отношениятаx11,x22,…,xnn\frac{x_1}{1},\frac{x_2}{2},\ldots,\frac{x_n}{n}са две по две различни. Да се докаже, че ana_n е нечетно за всяко n≥1n\ge1.
РешениеРазглеждаме пермутациите като биекции π\pi на множеството {1,2,…,n}\{1,2,\ldots,n\}, където xk=π(k)x_k=\pi(k). Ако π\pi има исканото свойство, то и обратната пермутация π−1\pi^{-1} го има: отношенията при обратната пермутация са реципрочните на отношенията при π\pi. Следователно пермутациите, които не са равни на обратните си, се сдвояват по двойки. За паритета на ana_n остава да преброим само инволюциите, тоест пермутациите, чиито цикли са с дължина най-много 22. Една такава инволюция се състои от размени на двойки и евентуално една неподвижна точка. Не може да има две неподвижни точки, защото всяка от тях дава отношение 11. Значи при четно nn получаваме перфектно съчетание на върховете на KnK_n, а при нечетно nn - максимално съчетание с един непокрит връх. За ребро {i,j}\{i,j\}, i<ji\lt{}j, поставяме етикет i/ji/j. Инволюцията е допустима точно когато етикетите на всички ребра в съответното максимално съчетание са различни; ще наричаме такова съчетание добро. Сега въвеждаме операция върху максималните съчетания. Ако две несрещащи се ребра abab и cdcd имат един и същ етикет, където a<ba\lt{}b и c<dc\lt{}d, тогава a/b=c/da/b=c/d, откъдето a/c=b/da/c=b/d след подходящо подреждане на четирите върха. Затова можем да заменим ребрата ab,cdab,cd с ac,bdac,bd и пак получаваме две ребра с един и същ етикет. За дадено съчетание MM наричаме негови съседи всички съчетания, които се получават, като за всеки етикет изберем няколко несрещащи се двойки ребра с този етикет и извършим описаната размяна. Това отношение е симетрично и всяко съчетание е съсед на самото себе си. Да преброим броя на съседите на фиксирано MM по модул 22. Ако даден етикет се среща rr пъти сред ребрата на MM, броят начини да изберем двойки ребра с този етикет и да ги разменим е∑k(r2k)(2k−1)!!.\sum_k {r\choose 2k}(2k-1)!!.По модул 22 това е∑k(r2k)=2r−1,\sum_k {r\choose 2k}=2^{r-1},което е нечетно точно когато r=1r=1. Умножавайки по всички етикети, получаваме: броят на съседите на MM, включително самото MM, е нечетен точно за добрите съчетания. Накрая сумираме тези бройки съседи по всички максимални съчетания. Понеже съседството е симетрично, всяка двойка различни съчетания се брои два пъти, а всяко съчетание се брои веднъж като съсед на себе си. Следователно сумата по модул 22 е равна на броя на всички максимални съчетания. Този брой е(2⌈n/2⌉−1)!!,(2\lceil n/2\rceil-1)!!,следователно е нечетен. Но по предишния абзац същата сума по модул 22 е точно броят на добрите съчетания по модул 22. Значи броят на допустимите инволюции е нечетен. Тъй като всички останали допустими пермутации се сдвояват с обратните си, заключаваме, че ana_n е нечетно за всяко n≥1n\ge1.
Отвори задачатаEvan Chen VONVON USAMO 2018/6Условие — източник