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

Evan Chen / USAMO Solution Notes

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

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

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

2000

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Наричаме реалнозначна функция ff силно изпъкнала, акоf(x)+f(y)2≥f(x+y2)+∣x−y∣\frac{f(x)+f(y)}2\ge f\left(\frac{x+y}{2}\right)+|x-y|за всички реални числа xx и yy. Да се докаже, че силно изпъкнала функция не съществува.
РешениеПо-общо, за C≥0C\ge0 ще казваме, че ff е CC-изпъкнала, акоf(x)+f(y)2≥f(x+y2)+C∣x−y∣\frac{f(x)+f(y)}2\ge f\left(\frac{x+y}{2}\right)+C|x-y|за всички реални x,yx,y. Ще покажем, че ако C>0C\gt{}0, от CC-изпъкналост следва 2C2C-изпъкналост; повторение на това ще даде невъзможност. Нека a<b<c<d<ea\lt{}b\lt{}c\lt{}d\lt{}e са пет последователни члена на аритметична прогресия и нека t=e−at=e-a. От CC-изпъкналостта за двойките (a,c)(a,c), (c,e)(c,e) и (b,d)(b,d) получавамеf(a)+f(c)≥2f(b)+Ct,f(a)+f(c)\ge2f(b)+Ct,f(c)+f(e)≥2f(d)+Ct,f(c)+f(e)\ge2f(d)+Ct,f(b)+f(d)≥2f(c)+Ct.f(b)+f(d)\ge2f(c)+Ct.Събирайки първите две неравенства и два пъти третото, след съкращаване получавамеf(a)+f(e)≥2f(c)+4Ct.f(a)+f(e)\ge2f(c)+4Ct.Това е точно условието за 2C2C-изпъкналост за двойката (a,e)(a,e). Следователно от CC-изпъкналост следва 2C2C-изпъкналост, оттам 4C4C-изпъкналост и т.н. При силно изпъкнала функция имаме C=1C=1. Фиксираме различни aa и ee; тогава горното повторение би принудило f(a)+f(e)2−f(a+e2)\frac{f(a)+f(e)}2-f\left(\frac{a+e}{2}\right) да е поне 2m∣a−e∣2^m|a-e| за всяко mm, което е невъзможно, защото лявата страна е фиксирано реално число. Противоречието доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 2000/1Условие — източник

Задача 2

Пълен запис
Условие
Нека SS е множеството от всички триъгълници ABCABC, за които5(1AP+1BQ+1CR)−3min⁡{AP,BQ,CR}=5\left(\frac1{AP}+\frac1{BQ}+\frac1{CR}\right)-\frac3{\min\{AP,BQ,CR\}}=6r,\frac6r,където rr е радиусът на вписаната окръжност, а P,Q,RP,Q,R са точките, в които тя се допира съответно до страните AB,BC,CAAB,BC,CA. Да се докаже, че всички триъгълници от SS са равнобедрени и подобни помежду си.
РешениеПолагаме x=APx=AP, y=BQy=BQ, z=CRz=CR. Тогава страните на триъгълника са x+yx+y, y+zy+z, z+xz+x, полупериметърът е x+y+zx+y+z, а от Хероновата формула получавамеr2=xyzx+y+z.r^2=\frac{xyz}{x+y+z}.Достатъчно е да докажем неравенството2x+5y+5z≥6r,\frac2x+\frac5y+\frac5z\ge\frac6r,като равенство има точно при x:y:z=1:4:4x:y:z=1:4:4. Наистина, ако например xx е най-малкото от x,y,zx,y,z, лявата страна в условието на задачата е точно 2/x+5/y+5/z2/x+5/y+5/z; останалите случаи са същите след преименуване. След повдигане на квадрат и замяна x=1/ax=1/a, y=4/by=4/b, z=4/cz=4/c неравенството се свежда до64a2+25(b+c)2≥64a(b+c)+36bc.64a^2+25(b+c)^2\ge64a(b+c)+36bc.Това следва от две приложения на AM-GM:16(4a2+(b+c)2)≥64a(b+c),16\big(4a^2+(b+c)^2\big)\ge64a(b+c),9(b+c)2≥36bc.9(b+c)^2\ge36bc.Равенство и в двете има точно когато 4a=b+c4a=b+c и b=cb=c, т.е. a=b=ca=b=c. В първоначалните променливи това означава x:y:z=1:4:4x:y:z=1:4:4. Следователно в условието на задачата равенство е възможно само когато най-малкият от трите допирателни отрязъка е в отношение 1:4:41:4:4 с другите два. Значи два от тях са равни, така че триъгълникът е равнобедрен, а отношението на допирателните отрязъци е фиксирано. Затова всички такива триъгълници са подобни.
Отвори задачатаEvan Chen VONVON USAMO 2000/2Условие — източник

Задача 3

Пълен запис
Условие
Пасианс се играе с RR червени, WW бели и BB сини карти. Играчът изиграва всички карти една по една и при всяко изиграване получава наказание. Ако изиграе синя карта, наказанието е броят на белите карти, които още държи. Ако изиграе бяла карта, наказанието е два пъти броят на червените карти, които още държи. Ако изиграе червена карта, наказанието е три пъти броят на сините карти, които още държи. Да се намерят, като функция на R,W,BR,W,B, най-малкото възможно общо наказание и броят на редовете на игра, с които този минимум се постига.
РешениеМинималното общо наказание еmin⁡{BW,2WR,3RB}.\min\{BW,2WR,3RB\}.Естествено е да се досетим, че е оптимално първо да се изхвърлят всички карти от един цвят; горната формула казва точно коя от трите възможности е най-добра. Доказателството е пряка индукция по B+W+RB+W+R. Нека F(B,W,R)=min⁡{BW,2WR,3RB}F(B,W,R)=\min\{BW,2WR,3RB\}. След първия ход получаваме рекурсиятаF(B,W,R)=F(B,W,R)=min⁡{F(B−1,W,R)+W,  F(B,W−1,R)+2R,  F(B,W,R−1)+3B}.\min\{F(B-1,W,R)+W,\; F(B,W-1,R)+2R,\; F(B,W,R-1)+3B\}.Проверка на трите случая показва, че дясната страна наистина е min⁡{BW,2WR,3RB}\min\{BW,2WR,3RB\}; началният случай, когато един от броевете е 00, е очевиден. Остава да преброим оптималните редове. Ако едно от числата BW,2WR,3RBBW,2WR,3RB е строго по-малко от другите две, оптималният ред е единствен. АкоBW=2WR<3RB,BW=2WR\lt{}3RB,има W+1W+1 оптимални реда: може първо да се изиграят от 00 до WW бели карти, след което да се изиграят всички сини карти. Ако2WR=3RB<BW,2WR=3RB\lt{}BW,има R+1R+1 оптимални реда: може първо да се изиграят от 00 до RR червени карти, след което да се изиграят всички бели карти. Ако3RB=BW<2WR,3RB=BW\lt{}2WR,има B+1B+1 оптимални реда: може първо да се изиграят от 00 до BB сини карти, след което да се изиграят всички червени карти. Накрая, акоBW=2WR=3RB,BW=2WR=3RB,първата карта ни поставя в един от трите предишни случая, така че общият брой оптимални редове е R+W+BR+W+B.
Отвори задачатаEvan Chen VONVON USAMO 2000/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намери най-малкото положително цяло число nn със следното свойство: ако nn квадрата от шахматна дъска 1000×10001000\times1000 са оцветени, то съществуват три оцветени квадрата, чиито центрове образуват правоъгълен триъгълник със страни, успоредни на страните на дъската.
РешениеОтговорът е n=1999n=1999. Първо ще дадем строеж с 19981998 оцветени квадрата без такава тройка. Оцветяваме всички квадрати в първата колона и всички квадрати в последния ред, но не оцветяваме общия им ъглов квадрат. Получава се пробито Г-образно множество с 999+999=1998999+999=1998 квадрата; в него няма оцветен квадрат, който едновременно да има друг оцветен квадрат в своя ред и друг оцветен квадрат в своята колона. Сега доказваме, че повече не може. Нека в някакво оцветяване няма търсения правоъгълен триъгълник. Тогава за всеки оцветен квадрат е вярно поне едно от двете: той е единственият оцветен квадрат в своя ред или е единственият оцветен квадрат в своята колона. Нека R1R_1 е множеството от редовете с точно един оцветен квадрат, а C1C_1 е множеството от колоните с точно един оцветен квадрат. Всеки оцветен квадрат се брои от някой ред в R1R_1 или от някоя колона в C1C_1, затова броят на оцветените квадрати е най-много∣R1∣+∣C1∣.|R_1|+|C_1|.Ако има повече от 10001000 оцветени квадрата, не всички редове са единични и не всички колони са единични. Следователно ∣R1∣≤999|R_1|\le999 и ∣C1∣≤999|C_1|\le999, откъдето броят на оцветените квадрати е най-много 19981998. Така при 19991999 оцветени квадрата търсената тройка задължително съществува.
Отвори задачатаEvan Chen VONVON USAMO 2000/4Условие — източник

Задача 5

Пълен запис
Условие
Нека A1A2A3A_1A_2A_3 е триъгълник и нека ω1\omega_1 е окръжност в неговата равнина, минаваща през A1A_1 и A2A_2. Да предположим, че съществуват окръжности ω2,ω3,…,ω7\omega_2,\omega_3,\ldots,\omega_7 такива, че за k=2,3,…,7k=2,3,\ldots,7 окръжността ωk\omega_k се допира външно до ωk−1\omega_{k-1} и минава през AkA_k и Ak+1A_{k+1}, където индексите се вземат по модул 33. Да се докаже, че ω7=ω1\omega_7=\omega_1.
РешениеЩе следим ъгъла, под който съответната окръжност се вижда от върха на страната. Некаα=∠A3A1A2,β=∠A1A2A3,\alpha=\angle A_3A_1A_2,\qquad \beta=\angle A_1A_2A_3,γ=∠A2A3A1.\qquad \gamma=\angle A_2A_3A_1.Нека OiO_i е центърът на ωi\omega_i и полагамеθ=∠O1A2A1.\theta=\angle O_1A_2A_1.Понеже последователните окръжности се допират външно, центровете им и точката на допиране лежат на една права. Оттук, с насочени ъгли, последователно получаваме∠O1A2A1=θ,\angle O_1A_2A_1=\theta,∠O2A3A2=−β−θ,\angle O_2A_3A_2=-\beta-\theta,∠O3A1A3=β−γ+θ,\angle O_3A_1A_3=\beta-\gamma+\theta,∠O4A2A1=(γ−β−α)−θ.\angle O_4A_2A_1=(\gamma-\beta-\alpha)-\theta.Ако положим k=γ−β−αk=\gamma-\beta-\alpha, същото пресмятане още веднъж дава∠O7A2A1=k−(k−θ)=θ.\angle O_7A_2A_1=k-(k-\theta)=\theta.Окръжност през A1A_1 и A2A_2 е определена от положението на центъра си върху перпендикулярния симетрал на A1A2A_1A_2, а този насочен ъгъл връща центъра в същата позиция. Следователно O7=O1O_7=O_1 и значи ω7=ω1\omega_7=\omega_1.A1A2A3O1O2O3
Отвори задачатаEvan Chen VONVON USAMO 2000/5Условие — източник

Задача 6

Пълен запис
Условие
Нека a1,b1,a2,b2,…,an,bna_1,b_1,a_2,b_2,\ldots,a_n,b_n са неотрицателни реални числа. Да се докаже, че∑i,j=1nmin⁡{aiaj,bibj}≤\sum_{i,j=1}^n\min\{a_ia_j,b_ib_j\}\le∑i,j=1nmin⁡{aibj,ajbi}.\sum_{i,j=1}^n\min\{a_ib_j,a_jb_i\}.
РешениеПо непрекъснатост можем да допуснем ai>0a_i\gt{}0 за всички ii и да запишем bi=riaib_i=r_i a_i. Тогава трябва да докажем∑i,jaiaj(min⁡(ri,rj)−min⁡(1,rirj))≥0.\sum_{i,j}a_ia_j\big(\min(r_i,r_j)-\min(1,r_ir_j)\big)\ge0.Нека εi=1\varepsilon_i=1, ако ri≥1r_i\ge1, и εi=−1\varepsilon_i=-1 иначе, а si=∣ri−1∣s_i=|r_i-1|. Ключовото преобразуване е2min⁡(ri,rj)−2min⁡(1,rirj)=2\min(r_i,r_j)-2\min(1,r_ir_j)=∣rirj−1∣−∣ri−rj∣−(ri−1)(rj−1).|r_ir_j-1|-|r_i-r_j|-(r_i-1)(r_j-1).То превръща двойния минимум в един отделен минимум. След стандартно опростяване получаваме, че е достатъчно да се докаже следното твърдение: за произволни реални xix_i и неотрицателни tit_i имаме∑i,jxixjmin⁡(ti,tj)≥0.\sum_{i,j}x_ix_j\min(t_i,t_j)\ge0.За доказателство на твърдението подреждаме t1≤t2≤⋯≤tnt_1\le t_2\le\cdots\le t_n. Тогава∑i,jxixjmin⁡(ti,tj)=\sum_{i,j}x_ix_j\min(t_i,t_j)=∑i(ti−ti−1)(xi+xi+1+⋯+xn)2≥\sum_i (t_i-t_{i-1})(x_i+x_{i+1}+\cdots+x_n)^2\ge0,0,където t0=0t_0=0. Това доказва желаното неравенство. Еквивалентно, може да се използва и интегралната идентичностmin⁡(ti,tj)=∫0∞1u≤ti1u≤tj du,\min(t_i,t_j)=\int_0^\infty \mathbf{1}_{u\le t_i}\mathbf{1}_{u\le t_j}\,du,след което сумата става интеграл от квадрат. И в двата варианта получаваме неотрицателност и задачата е решена.
Отвори задачатаEvan Chen VONVON USAMO 2000/6Условие — източник