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

Evan Chen / USAMO Solution Notes

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

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

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

1997

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека p1,p2,p3,...p_1,p_2,p_3,... са простите числа в нарастващ ред и нека x0x_0 е реално число с 0<x0<10\lt{}x_0\lt{}1. За всяко положително цяло число kk дефинираме xkx_k така: ако xk−1=0x_{k-1}=0, то xk=0x_k=0; иначе xkx_k е дробната част на pk/xk−1p_k/x_{k-1}. Намерете всички начални стойности x0x_0, за които от някой член нататък всички xkx_k са равни на 00.
РешениеОтговорът е: точно рационалните числа в интервала (0,1)(0,1). Първо нека x0x_0 е ирационално. Ще докажем с индукция, че докато членовете са ненулеви, всички те остават ирационални. Ако xk−1x_{k-1} е ирационално, то pk/xk−1p_k/x_{k-1} също е ирационално. Ако дробната му част беше рационална, тогава pk/xk−1p_k/x_{k-1} щеше да е сума от цяло и рационално число, тоест рационално, което е невъзможно. Следователно xkx_k е ирационално и в частност не може да бъде 00. Значи ирационално начално число никога не води до нулев член. Остава да видим, че всяко рационално x0x_0 работи. Нека xk−1=a/bx_{k-1}=a/b е ненулев член, записан в несъкратим вид, където 0<a<b0\lt{}a\lt{}b. Тогава pk/xk−1=pkb/ap_k/x_{k-1}=p_kb/a. Дробната част на това число е или 00, или рационално число със знаменател най-много aa след съкращаване. Понеже a<ba\lt{}b, при всеки ненулев преход знаменателят строго намалява. Не може да има безкрайна строго намаляваща редица от положителни цели знаменатели, затова след краен брой стъпки се получава дробна част 00. Оттам нататък по дефиниция всички следващи членове са 00.
Отвори задачатаEvan Chen VONVON USAMO 1997/1Условие — източник

Задача 2

Пълен запис
Условие
Нека ABCABC е триъгълник. Точките D,E,FD,E,F лежат съответно върху симетралите на отсечките BC,CA,ABBC,CA,AB и не са колинеарни. Докажете, че правите през A,B,CA,B,C, перпендикулярни съответно на EF,FD,DEEF,FD,DE, са конкурентни.
РешениеРазглеждаме три окръжности с центрове D,E,FD,E,F. Понеже DD лежи на симетралата на BCBC, имаме DB=DCDB=DC; следователно има окръжност с център DD, която минава през BB и CC. По същия начин има окръжност с център EE, която минава през CC и AA, и окръжност с център FF, която минава през AA и BB. Радикалната ос на окръжностите с центрове EE и FF минава през AA, защото AA лежи и на двете окръжности. Тази радикална ос е перпендикулярна на правата на центровете EFEF, така че тя е точно правата през AA, перпендикулярна на EFEF. Аналогично радикалната ос на окръжностите с центрове FF и DD е правата през BB, перпендикулярна на FDFD, а радикалната ос на окръжностите с центрове DD и EE е правата през CC, перпендикулярна на DEDE. Трите центъра D,E,FD,E,F не са колинеарни, затова трите окръжности имат радикален център. По теоремата за радикалния център трите им радикални оси са конкурентни. Но това са точно трите прави от условието, което доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 1997/2Условие — източник

Задача 3

Пълен запис
Условие
Докажете, че за всяко цяло число nn съществува единствен многочлен QQ с коефициенти от множеството {0,1,…,9}\{0,1,\ldots,9\}, за който Q(−2)=Q(−5)=nQ(-2)=Q(-5)=n.
РешениеЩе опишем цифрите на QQ от свободния член нагоре. По-общо, за двойка цели числа (u,v)(u,v) ще търсим многочлен QQ с цифри от 00 до 99, за който Q(−2)=uQ(-2)=u и Q(−5)=vQ(-5)=v. Ако Q(x)=d+xR(x)Q(x)=d+xR(x), където dd е свободният член, тогава u=d−2R(−2),v=d−5R(−5).u=d-2R(-2), \qquad v=d-5R(-5). Следователно dd трябва да удовлетворява d≡u(mod2),d≡v(mod5).d \equiv u \pmod 2, \qquad d \equiv v \pmod 5. По китайската теорема за остатъците има точно една цифра d∈{0,1,…,9}d \in \{0,1,\ldots,9\} с тези две свойства. След като тази цифра е избрана, следващата двойка е принудително T(u,v)=((d−u)/2,(d−v)/5).T(u,v)=((d-u)/2,(d-v)/5). Обратно, ако за двойката T(u,v)T(u,v) вече имаме подходящ многочлен RR, то d+xR(x)d+xR(x) е подходящ многочлен за (u,v)(u,v). Така едновременно доказваме и построяването, и единствеността, стига да покажем, че започвайки от (n,n)(n,n) този процес стига до (0,0)(0,0). Забележете първо, че условието u≡v(mod3)u \equiv v \pmod 3 се запазва от прехода TT. Наистина, ако u≡v(mod3)u \equiv v \pmod 3, то ((d−u)/2)−((d−v)/5)=(3d−5u+2v)/10((d-u)/2)-((d-v)/5)=(3d-5u+2v)/10 също се дели на 33, понеже числителят се дели и на 1010, и на 33. Началната двойка (n,n)(n,n) очевидно има това свойство. Нека M=max⁡(∣u∣,∣v∣)M=\max(|u|,|v|). Понеже 0≤d≤90 \le d \le 9, ако M>9M\gt{}9, то следващата двойка има координати по абсолютна стойност най-много (M+9)/2(M+9)/2 и (M+9)/5(M+9)/5, тоест новият максимум е строго по-малък от MM. Следователно след краен брой стъпки стигаме до M≤9M \le 9. След още най-много две стъпки втората координата има абсолютна стойност най-много 22, а първата остава с абсолютна стойност най-много 99. Остава само малка крайна проверка за двойките с ∣u∣≤9|u| \le 9, ∣v∣≤2|v| \le 2 и u≡v(mod3)u \equiv v \pmod 3. Пряко от правилото за цифрата dd всяка такава двойка или е (0,0)(0,0), или след една стъпка попада в множеството {(1,1),(2,2),(3,0),(4,1),(5,2),(7,1),(8,2),(−3,0),(−2,1)}\{(1,1),(2,2),(3,0),(4,1),(5,2),(7,1),(8,2),(-3,0),(-2,1)\}. А тези двойки завършват веднага по веригите (1,1),(2,2)↦(0,0),(1,1),(2,2) \mapsto (0,0), (3,0),(4,1),(5,2)↦(1,1),(3,0),(4,1),(5,2) \mapsto (1,1), (7,1),(8,2)↦(−3,0)↦(4,1),(7,1),(8,2) \mapsto (-3,0) \mapsto (4,1), и (−2,1)↦(4,1).(-2,1) \mapsto (4,1). Значи процесът винаги спира в (0,0)(0,0). При обръщане на стъпките получаваме търсения многочлен, а понеже всяка цифра dd беше принудително определена, този многочлен е единствен.
Отвори задачатаEvan Chen VONVON USAMO 1997/3Условие — източник

Задача 4

Пълен запис
Условие
Нека отрязване на изпъкнал nn-ъгълник означава следната операция: избираме две съседни страни ABAB и BCBC и ги заменяме с трите отсечки AMAM, MNMN и NCNC, където MM е средата на ABAB, а NN е средата на BCBC. С други думи, отрязваме триъгълника MBNMBN и получаваме изпъкнал (n+1)(n+1)-ъгълник. Правилен шестоъгълник P6\mathcal P_6 с лице 11 се отрязва и се получава седмоъгълник P7\mathcal P_7. После P7\mathcal P_7 се отрязва по един от седемте възможни начини, за да се получи осмоъгълник P8\mathcal P_8, и т.н. Докажете, че независимо от избора на отрязванията лицето на Pn\mathcal P_n е по-голямо от 1/31/3 за всяко n≥6n\ge6.
РешениеНека първоначалният правилен шестоъгълник е ABCDEFABCDEF в този ред и некаK=△ACE∩△BDF.K=\triangle ACE\cap\triangle BDF.Това е централният правилен шестоъгълник в звездата, образувана от двата равностранни триъгълника ACEACE и BDFBDF. Неговото лице е точно една трета от лицето на първоначалния шестоъгълник, тоест [K]=1/3[K]=1/3. Ще докажем, че всяко отрязване оставя цялата област KK вътре в многоъгълника. За целта на всяка страна на текущия многоъгълник приписваме основа, която е множество от страни на първоначалния шестоъгълник. В началото страните AB,BC,CD,DE,EF,FAAB,BC,CD,DE,EF,FA имат за основа самите себе си. Когато отрязваме две съседни страни и се появи новата страна MNMN, за основа на MNMN вземаме обединението на основите на двете страни, които са били отрязани. Ще използваме малко по-силен инвариант: за всеки две съседни страни на текущия многоъгълник обединението на основите им съдържа най-много две съседни първоначални страни. В началото това е очевидно. При едно отрязване двете части от старите страни запазват старите си основи, а новата страна получава обединението на основите на двете отрязани съседни страни. Затова новите съседни двойки около отрязването имат същото обединение на основи като старата отрязана двойка, а всички останали съседни двойки не се променят. Инвариантът се запазва, и в частност основата на всяка отделна страна съдържа най-много две съседни първоначални страни. Сега разгледайте страна, чиято основа е например подмножество на {AB,BC}\{AB,BC\}. Тогава тази страна лежи в триъгълника ABCABC: началните страни очевидно имат това свойство, а при отрязване новата отсечка свързва точки от две такива страни и остава вътре в същия триъгълник по изпъкналост. Следователно отрязаният триъгълник при върха BB е изцяло от страната на правата ACAC, която не съдържа KK, и дори не пресича отсечката ACAC. Аналогично всяко възможно отрязване е затворено в един от шестте ъглови триъгълникаABC, BCD, CDE, DEF, EFA, FABABC,\ BCD,\ CDE,\ DEF,\ EFA,\ FABи не достига съответната страна на триъгълника ACEACE или BDFBDF, която отделя този ъгъл от областта KK. Значи никога не отрязваме точка от KK. След краен брой отрязвания многоъгълникът Pn\mathcal P_n съдържа KK и освен това има ненулева част извън KK около всяка своя страна, така че лицето му е строго по-голямо от [K]=1/3[K]=1/3. Това доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 1997/4Условие — източник

Задача 5

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа. Докажете, че 1/(a3+b3+abc)+1/(b3+c3+abc)1/(a^3+b^3+abc)+1/(b^3+c^3+abc)+1/(c3+a3+abc)≤+1/(c^3+a^3+abc) \le1/(abc). 1/(abc).
РешениеЩе оценим всеки от трите знаменателя отдолу. За положителни aa и bb имаме a3+b3−ab(a+b)=(a+b)(a−b)2≥0,a^3+b^3-ab(a+b)=(a+b)(a-b)^2 \ge 0, следователно a3+b3+abc≥ab(a+b)+abc=ab(a+b+c).a^3+b^3+abc \ge ab(a+b)+abc=ab(a+b+c). Значи 1/(a3+b3+abc)≤1/(ab(a+b+c)).1/(a^3+b^3+abc) \le 1/(ab(a+b+c)). Същото разсъждение, приложено циклично, дава 1/(b3+c3+abc)≤1/(bc(a+b+c))1/(b^3+c^3+abc) \le 1/(bc(a+b+c)) и 1/(c3+a3+abc)≤1/(ca(a+b+c)).1/(c^3+a^3+abc) \le 1/(ca(a+b+c)).Като съберем тези три неравенства, получаваме 1/(a3+b3+abc)+1/(b3+c3+abc)1/(a^3+b^3+abc)+1/(b^3+c^3+abc)+1/(c3+a3+abc)≤+1/(c^3+a^3+abc) \le(1/(a+b+c))(1/(ab)+1/(bc)+1/(ca)). (1/(a+b+c))(1/(ab)+1/(bc)+1/(ca)). Но 1/(ab)+1/(bc)+1/(ca)=(a+b+c)/(abc),1/(ab)+1/(bc)+1/(ca)=(a+b+c)/(abc), така че дясната страна е точно 1/(abc)1/(abc). Това доказва исканото неравенство.
Отвори задачатаEvan Chen VONVON USAMO 1997/5Условие — източник

Задача 6

Пълен запис
Условие
Нека редицата от неотрицателни цели числа a1,a2,…,a1997a_1,a_2,\ldots,a_{1997} удовлетворява ai+aj≤ai+j≤ai+aj+1a_i+a_j \le a_{i+j} \le a_i+a_j+1 за всички i,j≥1i,j \ge 1 с i+j≤1997i+j \le 1997. Докажете, че съществува реално число xx, такова че an=⌊nx⌋a_n=\lfloor nx\rfloor за всяко 1≤n≤19971 \le n \le 1997.
РешениеЩе докажем малко по-общо твърдение, като заменим 19971997 с произволно положително цяло число NN. За всяко nn условието an=⌊nx⌋a_n=\lfloor nx\rfloor е еквивалентно на ann≤x<an+1n.\frac{a_n}{n}\le x\lt{}\frac{a_n+1}{n}. Следователно е достатъчно да покажем, че max⁡1≤n≤Nann<min⁡1≤n≤Nan+1n.\max_{1\le n\le N}\frac{a_n}{n}\lt{}\min_{1\le n\le N}\frac{a_n+1}{n}.Ще докажем по индукция по NN следното по-силно твърдение. Нека ii е най-малкият индекс, при който се достига максимумът на дробите an/na_n/n, а jj е най-малкият индекс, при който се достига минимумът на дробите (an+1)/n(a_n+1)/n. Тогава aii<aj+1j,\frac{a_i}{i}\lt{}\frac{a_j+1}{j}, и тези две несъкратими дроби са съседни в редицата на Фарей от ред NN, тоест между тях няма друга рационална дроб със знаменател най-много NN. Базата N=1N=1 е ясна. Нека твърдението е доказано за N−1N-1 и добавим члена aNa_N. За старите крайни дроби пишем L=aii,U=aj+1j.L=\frac{a_i}{i},\qquad U=\frac{a_j+1}{j}. По индукционната хипотеза те са съседни в редицата на Фарей от ред N−1N-1, следователно i+j≥Ni+j\ge N. Първо нека i+j>Ni+j\gt{}N. Между две съседни Фарейови дроби с тези знаменатели няма дроб със знаменател NN във вътрешността на интервала (L,U)(L,U). Затова съществува цяло число bb, за което bN≤L<U≤b+1N.\frac bN\le L\lt{}U\le\frac{b+1}{N}. От левия край и от това, че UU е най-малкият стар десен край, получаваме b−aiN−i≤bN≤L<U≤aN−i+1N−i,\frac{b-a_i}{N-i}\le\frac bN\le L\lt{}U\le\frac{a_{N-i}+1}{N-i}, откъдето, понеже числата са цели, aN−i≥b−aia_{N-i}\ge b-a_i. Аналогично, от това, че LL е най-големият стар ляв край, и от десния край получаваме aN−jN−j≤L<U≤b+1N≤b−ajN−j,\frac{a_{N-j}}{N-j}\le L\lt{}U\le\frac{b+1}{N}\le\frac{b-a_j}{N-j}, откъдето aN−j<b−aja_{N-j}\lt{}b-a_j, тоест aN−j≤b−aj−1a_{N-j}\le b-a_j-1. Сега условието на задачата дава aN≥ai+aN−i≥ba_N\ge a_i+a_{N-i}\ge b и aN≤aj+aN−j+1≤b.a_N\le a_j+a_{N-j}+1\le b. Значи всъщност aN=ba_N=b. Следователно новият ляв край aN/Na_N/N не надминава LL, а новият десен край (aN+1)/N(a_N+1)/N не е по-малък от UU. Двойката i,ji,j не се променя, а понеже i+j>Ni+j\gt{}N, същите две дроби остават съседни и в редицата на Фарей от ред NN. Остава случаят i+j=Ni+j=N. Тогава медиантата ai+aj+1N\frac{a_i+a_j+1}{N} лежи строго между LL и UU. Освен това условието за aNa_N дава aN∈{ai+aj,  ai+aj+1}.a_N\in\{a_i+a_j,\;a_i+a_j+1\}. Ако aN=ai+aja_N=a_i+a_j, новият десен край е aN+1N=ai+aj+1N,\frac{a_N+1}{N}=\frac{a_i+a_j+1}{N}, така че двойката крайни дроби става (L,aN+1N)\left(L,\frac{a_N+1}{N}\right). Ако aN=ai+aj+1a_N=a_i+a_j+1, новият ляв край е aNN=ai+aj+1N,\frac{a_N}{N}=\frac{a_i+a_j+1}{N}, така че двойката става (aNN,U)\left(\frac{a_N}{N},U\right). Стандартното свойство на редиците на Фарей казва, че медиантата на две съседни дроби е несъкратима и е съседна на всяка от тях в новия ред. Следователно индукционното твърдение се запазва. Така за N=1997N=1997 имаме L<UL\lt{}U. Избираме например x=Lx=L. За всяко nn е изпълнено ann≤x<an+1n,\frac{a_n}{n}\le x\lt{}\frac{a_n+1}{n}, което е еквивалентно на an≤nx<an+1a_n\le nx\lt{}a_n+1. Следователно an=⌊nx⌋a_n=\lfloor nx\rfloor за всички 1≤n≤19971\le n\le1997.
Отвори задачатаEvan Chen VONVON USAMO 1997/6Условие — източник