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

Evan Chen / IMO Solution Notes

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

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

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

2003

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека AA е 101-елементно подмножество на S={1,2,…,106}S=\{1,2,\ldots,10^6\}. Докажете, че съществуват числа t1,t2,…,t100t_1,t_2,\ldots,t_{100} от SS, за които множествата Aj={x+tj:x∈A},j=1,2,…,100,A_j=\{x+t_j:x\in A\},\quad j=1,2,\ldots,100, са две по две несечащи се.
РешениеЩе изберем преместванията жадно. Нека T={t1,t2,…,tr}⊂ST=\{t_1,t_2,\ldots,t_r\}\subset S е максимално по включване множество от премествания, за което множествата A+tiA+t_i са две по две несечащи се. Ще докажем, че r≥100r\ge100. По максималността, всяко t∈St\in S или вече принадлежи на TT, или не може да бъде добавено към TT. Във втория случай A+tA+t се пресича с някое A+tiA+t_i, тоест съществуват a,b∈Aa,b\in A с a≠ba\ne b и a+t=b+ti.a+t=b+t_i. Следователно t=ti+b−a.t=t_i+b-a.За фиксирано tit_i има най-много 101⋅100101\cdot100 стойности от вида ti+b−at_i+b-a с различни a,b∈Aa,b\in A. Значи всички числа от SS са покрити от най-много r+r⋅101⋅100r+r\cdot101\cdot100 възможности: самите избрани премествания и забранените нови премествания. Получаваме 106≤r(1+101⋅100)=10101r.10^6\le r(1+101\cdot100)=10101r. Но 10101⋅99=999999<10610101\cdot99=999999\lt{}10^6, следователно r>99r\gt{}99. Така в TT има поне 100 елемента и можем да вземем кои да е 100 от тях.
Отвори задачатаEvan Chen VONVON IMO 2003/1Условие — източник

Задача 2

Пълен запис
Условие
Определете всички двойки положителни цели числа (a,b)(a,b), за които a22ab2−b3+1\frac{a^2}{2ab^2-b^3+1} е положително цяло число.
РешениеОтговорът е (a,b)=(2ℓ,1),(a,b)=(ℓ,2ℓ),(a,b)=(2\ell,1),\quad (a,b)=(\ell,2\ell),(a,b)=(8ℓ4−ℓ,2ℓ),\quad (a,b)=(8\ell^4-\ell,2\ell), където ℓ\ell е произволно положително цяло число. Тези двойки се проверяват директно. Ако b=1b=1, получаваме a2/(2a)=a/2a^2/(2a)=a/2, откъдето точно a=2ℓa=2\ell. Оттук нататък нека b>1b\gt{}1 и нека k=a22ab2−b3+1k=\frac{a^2}{2ab^2-b^3+1} е положително цяло число. Тогава aa е корен на квадратно уравнение по XX: X2−2kb2X+k(b3−1)=0.X^2-2kb^2X+k(b^3-1)=0. Другият корен е a′=2kb2−a=k(b3−1)a.a'=2kb^2-a=\frac{k(b^3-1)}{a}. Първата формула показва, че a′a' е цяло число, а втората, заедно с b>1b\gt{}1, показва, че a′>0a'\gt{}0. Следователно решенията с фиксирано bb и kk идват по двойки (a,b)↔(a′,b)(a,b)\leftrightarrow(a',b). Ще използваме следното просто наблюдение: за всяко решение или 2a=b2a=b, или a>ba\gt{}b. Наистина знаменателят е положителен, затова 2a−b≥02a-b\ge0. Ако 2a−b>02a-b\gt{}0, то от k≥1k\ge1 следва a2≥2ab2−b3+1=b2(2a−b)+1>b2,a^2\ge2ab^2-b^3+1=b^2(2a-b)+1\gt{}b^2, следователно a>ba\gt{}b. Сега вземаме двойка взаимно спрегнати корени a1,a2a_1,a_2 за едни и същи b,kb,k. Ако нито един от тях не удовлетворява 2ai=b2a_i=b, то и двата са по-големи от bb. Нека a1>a2>ba_1\gt{}a_2\gt{}b. По формулите на Виет a1+a2=2kb2,a1a2=k(b3−1).a_1+a_2=2kb^2,\qquad a_1a_2=k(b^3-1). От a1>(a1+a2)/2=kb2a_1\gt{}(a_1+a_2)/2=kb^2 и a2>ba_2\gt{}b получаваме a1a2>kb3a_1a_2\gt{}kb^3, което противоречи на a1a2=k(b3−1)a_1a_2=k(b^3-1). Значи във всяка такава двойка един корен има вид a=b/2a=b/2. Пишем a=ℓa=\ell и b=2ℓb=2\ell. Тогава знаменателят е 11, така че k=ℓ2k=\ell^2. Спрегнатият корен е 2kb2−a=2ℓ2⋅(2ℓ)2−ℓ=8ℓ4−ℓ.2kb^2-a=2\ell^2\cdot(2\ell)^2-\ell=8\ell^4-\ell. Така получаваме точно двете фамилии с b>1b\gt{}1, а заедно със случая b=1b=1 списъкът е пълен.
Отвори задачатаEvan Chen VONVON IMO 2003/2Условие — източник

Задача 3

Пълен запис
Условие
Всяка двойка срещуположни страни на изпъкнал шестоъгълник има следното свойство: разстоянието между средите им е 32\frac{\sqrt3}{2} пъти сбора на дължините им. Докажете, че шестоъгълникът е равноъгълен.
РешениеОзначаваме шестоъгълника с ABCDEFABCDEF и работим с радиус-векторите на върховете. За срещуположните страни ABAB и DEDE условието дава∣D⃗+E⃗2−A⃗+B⃗2∣=\left\lvert\frac{\vec D+\vec E}{2}-\frac{\vec A+\vec B}{2}\right\rvert=3⋅∣B⃗−A⃗∣+∣E⃗−D⃗∣2≥\sqrt3\cdot\frac{\lvert\vec B-\vec A\rvert+\lvert\vec E-\vec D\rvert}{2}\ge3⋅∣(B⃗−A⃗)−(E⃗−D⃗)2∣,\sqrt3\cdot\left\lvert\frac{(\vec B-\vec A)-(\vec E-\vec D)}{2}\right\rvert,където последната стъпка е неравенството на триъгълника. Ще използваме и двете циклични аналогични неравенства. Полагамеx⃗=(B⃗−A⃗)−(E⃗−D⃗),y⃗=(D⃗−C⃗)−(A⃗−F⃗),z⃗=(F⃗−E⃗)−(C⃗−B⃗).\begin{aligned} \vec x&=(\vec B-\vec A)-(\vec E-\vec D),\\ \vec y&=(\vec D-\vec C)-(\vec A-\vec F),\\ \vec z&=(\vec F-\vec E)-(\vec C-\vec B). \end{aligned}Тогава векторите между съответните среди са 12(y⃗−z⃗)\frac12(\vec y-\vec z), 12(z⃗−x⃗)\frac12(\vec z-\vec x) и 12(x⃗−y⃗)\frac12(\vec x-\vec y), откъдето получаваме∣y⃗−z⃗∣≥3∣x⃗∣,\lvert\vec y-\vec z\rvert\ge\sqrt3\lvert\vec x\rvert,∣z⃗−x⃗∣≥3∣y⃗∣,\qquad \lvert\vec z-\vec x\rvert\ge\sqrt3\lvert\vec y\rvert,∣x⃗−y⃗∣≥3∣z⃗∣.\qquad \lvert\vec x-\vec y\rvert\ge\sqrt3\lvert\vec z\rvert.Повдигаме на квадрат и събираме. Понеже ∣v⃗∣2=v⃗⋅v⃗\lvert\vec v\rvert^2=\vec v\cdot\vec v, получаваме∑cyc(y⃗−z⃗)⋅(y⃗−z⃗)≥\sum_{\mathrm{cyc}}(\vec y-\vec z)\cdot(\vec y-\vec z)\ge3∑cycx⃗⋅x⃗,3\sum_{\mathrm{cyc}}\vec x\cdot\vec x,което след прегрупиране е точно−∣x⃗+y⃗+z⃗∣2≥0.-\lvert\vec x+\vec y+\vec z\rvert^2\ge0.Следователно x⃗+y⃗+z⃗=0\vec x+\vec y+\vec z=0. Освен това всички три неравенства по-горе всъщност са равенства. В частност в началните приложения на неравенството на триъгълника също има равенство, така чеAB∥DE,BC∥EF,CD∥FA.AB\parallel DE,\qquad BC\parallel EF,\qquad CD\parallel FA.Остава да определим ъглите. От z⃗=−x⃗−y⃗\vec z=-\vec x-\vec y и първите две равенства следва3∣x⃗∣2=∣x⃗+2y⃗∣2=∣x⃗∣2+4x⃗⋅y⃗+4∣y⃗∣2,3∣y⃗∣2=∣2x⃗+y⃗∣2=4∣x⃗∣2+4x⃗⋅y⃗+∣y⃗∣2.\begin{aligned} 3\lvert\vec x\rvert^2&=\lvert\vec x+2\vec y\rvert^2=\lvert\vec x\rvert^2+4\vec x\cdot\vec y+4\lvert\vec y\rvert^2,\\ 3\lvert\vec y\rvert^2&=\lvert2\vec x+\vec y\rvert^2=4\lvert\vec x\rvert^2+4\vec x\cdot\vec y+\lvert\vec y\rvert^2. \end{aligned}След изваждане получаваме ∣x⃗∣=∣y⃗∣\lvert\vec x\rvert=\lvert\vec y\rvert, а после и x⃗⋅y⃗=−12∣x⃗∣2\vec x\cdot\vec y=-\frac12\lvert\vec x\rvert^2. Циклично същото важи за всяка двойка от x⃗,y⃗,z⃗\vec x,\vec y,\vec z: те имат еднакви дължини и посоките им се различават с 120∘120^\circ. Тези вектори не могат всички да са нулеви, защото тогава от определенията и затвореността на шестоъгълника би следвало D⃗=A⃗\vec D=\vec A, невъзможно за изпъкнал шестоъгълник. Така ABAB, CDCD и EFEF са успоредни съответно на три посоки, раздалечени с 120∘120^\circ, а BCBC, DEDE и FAFA са успоредни на противоположните им посоки. Поради изпъкналостта външният ъгъл при всяка двойка съседни страни е 60∘60^\circ, следователно всеки вътрешен ъгъл е 120∘120^\circ. Значи шестоъгълникът е равноъгълен.
Отвори задачатаEvan Chen VONVON IMO 2003/3Условие — източник

Задача 4

Пълен запис
Условие
Нека ABCDABCD е вписан четириъгълник. Нека PP, QQ и RR са петите на перпендикулярите, спуснати от DD съответно към правите BCBC, CACA и ABAB. Докажете, че PQ=QRPQ=QR тогава и само тогава, когато ъглополовящите на ∠ABC\angle ABC и ∠ADC\angle ADC се пресичат върху отсечката ACAC.
РешениеНека γ\gamma е описаната окръжност на ABCDABCD. Ще използваме насочени ъгли и двойно отношение; за четири точки върху права или върху окръжност пишем например (AC;BD)γ(AC;BD)_\gamma. Условието за ъглополовящите е еквивалентно на(AC;BD)γ=−1.(AC;BD)_\gamma=-1.Наистина, по теоремата за ъглополовящата двете ъглополовящи се срещат в една и съща точка от ACAC точно когатоABBC=ADDC,\frac{AB}{BC}=\frac{AD}{DC},а за четири точки върху една окръжност това е точно хармоничността (AC;BD)γ=−1(AC;BD)_\gamma=-1. От друга страна, понеже DD лежи на описаната окръжност на триъгълника ABCABC, точките P,Q,RP,Q,R са колинеарни по теоремата за правата на Симсон. Нека ∞\infty е безкрайната точка на правата PQRPQR. Тогава PQ=QRPQ=QR е еквивалентно на това QQ да е средата на PRPR, тоест(PR;Q∞)=−1.(PR;Q\infty)=-1.Нека лъчите BQBQ и DQDQ пресичат отново γ\gamma съответно в FF и EE.ABCDPQREFЩе ни трябва, че BE∥PQRBE\parallel PQR. Понеже DQ⊥ACDQ\perp AC и DR⊥ABDR\perp AB, точките D,Q,A,RD,Q,A,R лежат на една окръжност, откъдето∠DQR=∠DAR=∠DAB.\angle DQR=\angle DAR=\angle DAB.Но A,B,D,EA,B,D,E също лежат на γ\gamma, следователно∠DAB=∠DEB.\angle DAB=\angle DEB.Понеже D,Q,ED,Q,E са колинеарни, равенството ∠DQR=∠DEB\angle DQR=\angle DEB дава QR∥BEQR\parallel BE, както искахме. Сега проектираме от точката BB. При тази проекция от правата PQRPQR върху γ\gamma имаме P↦CP\mapsto C, R↦AR\mapsto A, Q↦FQ\mapsto F, а безкрайната точка ∞\infty отива в EE, защото BE∥PQRBE\parallel PQR. Затова(PR;Q∞)=(CA;FE)γ.(PR;Q\infty)=(CA;FE)_\gamma.След това проектираме от точката QQ: правата QC=QAQC=QA дава размяната на C,AC,A, правата QF=QBQF=QB дава F↦BF\mapsto B, а правата QE=QDQE=QD дава E↦DE\mapsto D. Получаваме(CA;FE)γ=(AC;BD)γ.(CA;FE)_\gamma=(AC;BD)_\gamma.Следователно(PR;Q∞)=(AC;BD)γ,(PR;Q\infty)=(AC;BD)_\gamma,и двете разглеждани условия са еквивалентни на това общото двойно отношение да бъде −1-1. Това доказва твърдението.
Отвори задачатаEvan Chen VONVON IMO 2003/4Условие — източник

Задача 5

Пълен запис
Условие
Нека nn е положително цяло число и нека x1≤x2≤⋯≤xnx_1\le x_2\le\cdots\le x_n са реални числа. Докажете, че (∑i=1n∑j=1n∣xi−xj∣)2≤\left(\sum_{i=1}^n\sum_{j=1}^n |x_i-x_j|\right)^2\le2(n2−1)3∑i=1n∑j=1n(xi−xj)2, \frac{2(n^2-1)}{3}\sum_{i=1}^n\sum_{j=1}^n (x_i-x_j)^2, като равенство има тогава и само тогава, когато x1,x2,…,xnx_1,x_2,\ldots,x_n образуват аритметична прогресия.
РешениеЗа n≤2n\le2 твърдението е непосредствено, затова нека n≥3n\ge3. Полагаме di=xi+1−xi(i=1,2,…,n−1).d_i=x_{i+1}-x_i\quad (i=1,2,\ldots,n-1). Тогава di≥0d_i\ge0 и след събиране по интервалите, които съдържат did_i, получаваме ∑i=1n∑j=1n∣xi−xj∣=2∑i=1n−1i(n−i)di,\sum_{i=1}^n\sum_{j=1}^n |x_i-x_j|=2\sum_{i=1}^{n-1} i(n-i)d_i, както и ∑i=1n∑j=1n(xi−xj)2=\sum_{i=1}^n\sum_{j=1}^n (x_i-x_j)^2=2(∑i=1n−1i(n−i)di2+2∑1≤i<j≤n−1i(n−j)didj).2\left(\sum_{i=1}^{n-1} i(n-i)d_i^2+2\sum_{1\le i\lt{}j\le n-1} i(n-j)d_i d_j\right). Следователно е достатъчно да докажем (∑ii(n−i)di)2≤\left(\sum_i i(n-i)d_i\right)^2\len2−13(∑ii(n−i)di2+2∑i<ji(n−j)didj).\frac{n^2-1}{3}\left(\sum_i i(n-i)d_i^2+2\sum_{i\lt{}j} i(n-j)d_i d_j\right).След умножение по 33 и пренасяне това се свежда до ∑i<j(3ij(n−i)(n−j)−(n2−1)i(n−j))2didj≤\sum_{i\lt{}j}\left(3ij(n-i)(n-j)-(n^2-1)i(n-j)\right)2d_i d_j\le∑i(n2−1−3i(n−i))i(n−i)di2.\sum_i (n^2-1-3i(n-i))i(n-i)d_i^2. Прилагаме AM-GM във вида 2didj≤di2+dj22d_i d_j\le d_i^2+d_j^2. Остава само да проверим, че коефициентите пред всяко dk2d_k^2 съвпадат. За фиксирано 1≤k≤n−11\le k\le n-1 трябва да имаме ∑i<k(3ik(n−i)(n−k)−(n2−1)i(n−k))\sum_{i\lt{}k}\left(3ik(n-i)(n-k)-(n^2-1)i(n-k)\right)+∑j>k(3kj(n−k)(n−j)−(n2−1)k(n−j))+\sum_{j\gt{}k}\left(3kj(n-k)(n-j)-(n^2-1)k(n-j)\right) =(n2−1−3k(n−k))k(n−k).=(n^2-1-3k(n-k))k(n-k). Това е директна сметка. Ако означим C=n2−1C=n^2-1 и K=k(n−k)K=k(n-k), лявата страна е 3K(∑i=1n−1i(n−i)−K)3K\left(\sum_{i=1}^{n-1}i(n-i)-K\right)−C((n−k)∑i<ki+k∑j>k(n−j)).-C\left((n-k)\sum_{i\lt{}k}i+k\sum_{j\gt{}k}(n-j)\right). Използваме ∑i=1n−1i(n−i)=(n−1)n(n+1)6=Cn6\sum_{i=1}^{n-1} i(n-i)=\frac{(n-1)n(n+1)}{6}=\frac{Cn}{6} и (n−k)∑i<ki+k∑j>k(n−j)=K(n−2)2.(n-k)\sum_{i\lt{}k}i+k\sum_{j\gt{}k}(n-j)=\frac{K(n-2)}{2}. Получаваме CK−3K2CK-3K^2, което е точно дясната страна. Така неравенството е доказано. За равенство трябва да има равенство във всички използвани AM-GM оценки с ненулев коефициент. Коефициентът пред didjd_i d_j е ненулев за всяко i≤n/2i\le n/2 и j≥n/2j\ge n/2 с i<ji\lt{}j, следователно всички did_i са равни. Това означава точно, че x1,x2,…,xnx_1,x_2,\ldots,x_n образуват аритметична прогресия. Обратно, ако всички did_i са равни, директното заместване в горните формули дава равенство.
Отвори задачатаEvan Chen VONVON IMO 2003/5Условие — източник

Задача 6

Пълен запис
Условие
Нека pp е просто число. Докажете, че съществува просто число qq, такова че за всяко цяло число nn числото np−pn^p-p не се дели на qq.
РешениеЩе намерим просто число q=pk+1q=pk+1, за което pk≢1(modq)p^k\not\equiv1\pmod q. Тогава няма как да съществува nn с np≡p(modq)n^p\equiv p\pmod q: ако такова nn съществува, то q∤nq\nmid n и повдигането на степен k=(q−1)/pk=(q-1)/p дава 1≡nq−1≡pk(modq),1\equiv n^{q-1}\equiv p^k\pmod q, противоречие. Използваме циклотомичния полином Φp(X)=1+X+X2+⋯+Xp−1.\Phi_p(X)=1+X+X^2+\cdots+X^{p-1}. Ще ни трябва стандартната лема: ако qq е прост делител на Φp(a)\Phi_p(a) и q≠pq\ne p, то остатъкът на aa по модул qq има ред pp. Наистина от q∣Φp(a)q\mid\Phi_p(a) следва ap≡1(modq)a^p\equiv1\pmod q. Редът е 11 или pp; ако е 11, то a≡1(modq)a\equiv1\pmod q, откъдето q∣Φp(1)=pq\mid\Phi_p(1)=p, противоречие с q≠pq\ne p. Сега разглеждаме Φp(p)=1+p+p2+⋯+pp−1≡1+p(modp2).\Phi_p(p)=1+p+p^2+\cdots+p^{p-1}\equiv1+p\pmod{p^2}. Числото Φp(p)\Phi_p(p) е по-голямо от 11 и не се дели на pp, понеже е конгруентно на 11 по модул pp. Избираме прост делител qq на Φp(p)\Phi_p(p), за който q≢1(modp2).q\not\equiv1\pmod{p^2}. Такъв делител съществува: ако всички прости делители на Φp(p)\Phi_p(p) бяха конгруентни на 11 по модул p2p^2, тогава и произведението им с кратностите, тоест Φp(p)\Phi_p(p), щеше да е конгруентно на 11 по модул p2p^2, в противоречие с Φp(p)≡1+p(modp2)\Phi_p(p)\equiv1+p\pmod{p^2}. По лемата редът на pp по модул qq е pp, следователно q≡1(modp)q\equiv1\pmod p. Пишем q=pk+1q=pk+1. От избора на qq имаме p∤kp\nmid k, а понеже редът на pp е точно pp, получаваме pk≢1(modq)p^k\not\equiv1\pmod q. Както видяхме в началото, това точно изключва делимостта q∣np−pq\mid n^p-p за всяко цяло nn.
Отвори задачатаEvan Chen VONVON IMO 2003/6Условие — източник