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

Evan Chen / USAMO Solution Notes

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

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

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

2012

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

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

  • 2012 · 11-12: липсва задача 5

11-12

5 задачи

Задача 1

Пълен запис
Условие
Да се намерят всички цели числа n≥3n\ge3 със следното свойство: измежду всеки nn положителни реални числа a1,a2,…,ana_1,a_2,\ldots,a_n, за които max⁡(a1,a2,…,an)≤n⋅min⁡(a1,a2,…,an),\max(a_1,a_2,\ldots,a_n)\le n\cdot\min(a_1,a_2,\ldots,a_n), съществуват три, които са дължини на страни на остроъгълен триъгълник.
РешениеОтговорът е: всички n≥13n\ge13. Нека F1=F2=1F_1=F_2=1 и Fm+1=Fm+Fm−1F_{m+1}=F_m+F_{m-1} са числата на Фибоначи. Ще използваме простия факт, че Fm≤m2F_m\le m^2 тогава и само тогава, когато m≤12m\le12. Това се проверява директно за първите стойности: F12=144=122F_{12}=144=12^2, а F13=233>132F_{13}=233\gt{}13^2 и F14=377>142F_{14}=377\gt{}14^2; за m≥15m\ge15 индукцията дава Fm=Fm−1+Fm−2>(m−1)2+(m−2)2>m2.F_m=F_{m-1}+F_{m-2}\gt{}(m-1)^2+(m-2)^2\gt{}m^2.Нека първо n≥13n\ge13 и да допуснем противното: няма три от числата, които да са страни на остроъгълен триъгълник. Подреждаме ги така, че a1≤a2≤⋯≤ana_1\le a_2\le\cdots\le a_n. Тогава за всяко i≥2i\ge2 тройката ai−1,ai,ai+1a_{i-1},a_i,a_{i+1} не е остроъгълна, следователно ai+12≥ai2+ai−12.a_{i+1}^2\ge a_i^2+a_{i-1}^2. Оттук по индукция получаваме ai2≥Fia12a_i^2\ge F_i a_1^2 за всички ii. В частност an2≥Fna12a_n^2\ge F_n a_1^2. От условието на задачата обаче an≤na1a_n\le n a_1, затова Fn≤n2F_n\le n^2, което противоречи на n≥13n\ge13. Остава да покажем, че за n≤12n\le12 свойството не е вярно. Вземаме ai=x2Fi,i=1,2,…,n.a_i=\sqrt{\vphantom{x^2}F_i},\qquad i=1,2,\ldots,n. Тогава min⁡ai=1\min a_i=1 и max⁡ai=x2Fn≤n\max a_i=\sqrt{\vphantom{x^2}F_n}\le n, така че условието е изпълнено. Но ако i<j<ki\lt{}j\lt{}k, то ak2=Fk=Fk−1+Fk−2≥Fj+Fi=aj2+ai2,a_k^2=F_k=F_{k-1}+F_{k-2}\ge F_j+F_i=a_j^2+a_i^2, следователно тези три числа не могат да бъдат страни на остроъгълен триъгълник. Значи точно n≥13n\ge13 работят.
Отвори задачатаEvan Chen VONVON USAMO 2012/1Условие — източник

Задача 2

Пълен запис
Условие
Окръжност е разделена на равни дъги от 432432 точки. Точките са оцветени в четири цвята така, че 108108 точки са червени, 108108 са зелени, 108108 са сини, а останалите 108108 са жълти. Да се докаже, че могат да се изберат по три точки от всеки цвят така, че четирите триъгълника, образувани от избраните точки с един и същи цвят, да са конгруентни.
РешениеЩе използваме ротации и осредняване. Разглеждаме 431431-те нетъждествени ротации на окръжността и броим колко червени точки попадат върху зелени. При случайно избрана такава ротация всяка фиксирана червена точка попада върху зелена с вероятност 108/431108/431. Следователно математическото очакване на броя съвпадения е 108⋅108431>27.108\cdot\frac{108}{431}\gt{}27. По принципа на Дирихле съществува ротация, при която поне 2828 червени точки попадат върху зелени точки. Така намираме червен 2828-ъгълник и зелен 2828-ъгълник, които са образи един на друг при ротация. Сега вземаме този червен 2828-ъгълник и го сравняваме със сините точки. Изключваме двете ротации, които дават вече намерените червена и зелена конфигурация, и разглеждаме останалите 430430 ротации. По същата сметка очакваният брой попадения върху сини точки е 28⋅108430>7.28\cdot\frac{108}{430}\gt{}7. Следователно можем да изберем червен, зелен и син 88-ъгълник, които са ротационни образи един на друг. Накрая повтаряме аргумента с жълтите точки. От 429429-те допустими ротации очакваният брой попадения е 8⋅108429>2,8\cdot\frac{108}{429}\gt{}2, затова съществуват поне 33 попадения. Получаваме по три точки от всеки от четирите цвята, като четирите тройки са ротационни образи на една и съща тройка. Следователно образуваните четири триъгълника са конгруентни.
Отвори задачатаEvan Chen VONVON USAMO 2012/2Условие — източник

Задача 3

Пълен запис
Условие
Определете за кои цели числа n>1n\gt{}1 съществува безкрайна редица a1,a2,a3,…a_1,a_2,a_3,\ldots от ненулеви цели числа, такава че за всяко положително цяло число kk е изпълненоak+2a2k+⋯+nank=0.a_k+2a_{2k}+\cdots+na_{nk}=0.
РешениеОтговорът е: всички n>2n\gt{}2. За n=2n=2 равенството става ak+2a2k=0a_k+2a_{2k}=0. Оттук рекурентно получавамеa2t=(−1)ta12t(t≥1),a_{2^t}=(-1)^t\frac{a_1}{2^t}\qquad(t\ge1),което е невъзможно за ненулеви цели числа a2ta_{2^t} при всички tt: числото a1a_1 би трябвало да се дели на произволно големи степени на 22. Нека сега n≥3n\ge3. Ще построим напълно мултипликативна редица, тоест aij=aiaja_{ij}=a_i a_j за всички положителни цели i,ji,j. Тогава a1=1a_1=1, а условието за всяко kk ще следва от едно-единствено равенство:ak+2a2k+⋯+nank=ak(1a1+2a2+⋯+nan),a_k+2a_{2k}+\cdots+na_{nk}=a_k(1a_1+2a_2+\cdots+na_n),така че е достатъчно да изберем стойностите върху простите числа така, че1a1+2a2+⋯+nan=0.1a_1+2a_2+\cdots+na_n=0.Първо разглеждаме n≥9n\ge9. По постулата на Бертран съществуват прости числа pp и qq, за които⌈n2⌉<q<2⌈n2⌉,q−12<p<q−1.\left\lceil\frac n2\right\rceil\lt{}q\lt{}2\left\lceil\frac n2\right\rceil,\qquad \frac{q-1}{2}\lt{}p\lt{}q-1.Тогава p≠qp\ne q, q≥7q\ge7, p>3p\gt{}3, p<q<np\lt{}q\lt{}n, 2q>n2q\gt{}n и 4p>n4p\gt{}n. Полагаме ar=1a_r=1 за всяко просто число r≠p,qr\ne p,q. Остава да изберем ненулеви цели стойности за apa_p и aqa_q. В сумата 1a1+2a2+⋯+nan1a_1+2a_2+\cdots+na_n единствените членове, които могат да се различават от обикновената сума 1+2+⋯+n1+2+\cdots+n, са кратните на pp и кратното qq. Понеже 4p>n4p\gt{}n, кратните на pp сред 1,2,…,n1,2,\ldots,n са само pp, евентуално 2p2p, евентуално 3p3p. Съответно трябва да решим едно от трите линейни уравнения6p⋅ap+q⋅aq=6p+q−n(n+1)2,6p\cdot a_p+q\cdot a_q=6p+q-\frac{n(n+1)}2,3p⋅ap+q⋅aq=3p+q−n(n+1)2,3p\cdot a_p+q\cdot a_q=3p+q-\frac{n(n+1)}2,илиp⋅ap+q⋅aq=p+q−n(n+1)2,p\cdot a_p+q\cdot a_q=p+q-\frac{n(n+1)}2,според това дали 3p≤n3p\le n, само 2p≤n2p\le n, или само p≤np\le n. Във всеки случай коефициентът пред apa_p е взаимнопрост с qq, тъй като qq е просто и е различно от 22, 33, pp. По лемата на Безу има цели решения; понеже решенията образуват безкрайна аритметична прогресия, можем да изберем решение, при което и apa_p, и aqa_q са ненулеви. Това дава търсената напълно мултипликативна редица за всички n≥9n\ge9. Остават малките стойности 3≤n≤83\le n\le8. Те се проверяват с явни напълно мултипликативни редици. За n=3n=3 вземаме am=(−1)ν3(m)a_m=(-1)^{\nu_3(m)}. За n=4n=4 вземаме am=(−1)ν2(m)+ν3(m)a_m=(-1)^{\nu_2(m)+\nu_3(m)}. За n=5n=5 вземаме am=(−2)ν5(m)a_m=(-2)^{\nu_5(m)}. За n=6n=6 вземаме am=5ν2(m)3ν3(m)(−42)ν5(m)a_m=5^{\nu_2(m)}3^{\nu_3(m)}(-42)^{\nu_5(m)}. За n=7n=7 вземаме am=(−3)ν7(m)a_m=(-3)^{\nu_7(m)}. За n=8n=8 можем да използваме предишната конструкция с (p,q)=(5,7)(p,q)=(5,7); например изборът a5=a7=−2a_5=a_7=-2 и ar=1a_r=1 за останалите прости rr дава 1a1+⋯+8a8=01a_1+\cdots+8a_8=0. Лесна проверка показва, че във всеки от изброените случаи сумата 1a1+2a2+⋯+nan1a_1+2a_2+\cdots+na_n е нула. Следователно нужната редица съществува точно за n>2n\gt{}2.
Отвори задачатаEvan Chen VONVON USAMO 2012/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички функции f:N→Nf:\mathbb N\to\mathbb N, за които f(n!)=f(n)!f(n!)=f(n)! за всяко положително цяло число nn и m−nm-n дели f(m)−f(n)f(m)-f(n) за всички различни положителни цели числа m,nm,n.
РешениеОтговорът е: f≡1f\equiv1, f≡2f\equiv2 и тъждествената функция f(n)=nf(n)=n. Те очевидно удовлетворяват условията; ще докажем, че други няма. От f(1!)=f(1)!f(1!)=f(1)! и f(2!)=f(2)!f(2!)=f(2)! следва f(1),f(2)∈{1,2}f(1),f(2)\in\{1,2\}. Освен това, прилагайки делимостта към m!m! и n!n!, получаваме m!−n!∣f(m)!−f(n)!.m!-n!\mid f(m)!-f(n)!.Разглеждаме случаите според f(1)f(1) и f(2)f(2). Ако f(2)=1f(2)=1, то за m≥3m\ge3 имаме m!−2∣f(m)!−1.m!-2\mid f(m)!-1. Числото m!−2m!-2 е четно, а ако f(m)≥2f(m)\ge2, тогава f(m)!−1f(m)!-1 е нечетно, което е невъзможно. Значи f(m)=1f(m)=1 за всички m≥3m\ge3, а от 3−1∣f(3)−f(1)3-1\mid f(3)-f(1) следва и f(1)=1f(1)=1. Получаваме f≡1f\equiv1. Ако f(1)=f(2)=2f(1)=f(2)=2, то от 3!−1∣f(3)!−23!-1\mid f(3)!-2 следва f(3)=2f(3)=2. После за m≥4m\ge4 имаме m!−6∣f(m)!−2.m!-6\mid f(m)!-2. Делителят се дели на 33, а ако f(m)≥3f(m)\ge3, то f(m)!−2≡1(mod3)f(m)!-2\equiv1\pmod3, невъзможно. Така f(m)=2f(m)=2 за всички mm, тоест f≡2f\equiv2. Остава случаят f(1)=1f(1)=1 и f(2)=2f(2)=2. От 3!−1∣f(3)!−1,3!−2∣f(3)!−23!-1\mid f(3)!-1,\qquad 3!-2\mid f(3)!-2 лесно се получава f(3)=3f(3)=3. Ще докажем по индукция, че f(k)=kf(k)=k за всички kk. Да приемем, че f(1)=1,…,f(k)=kf(1)=1,\ldots,f(k)=k. Тогава k⋅k≠(k+1)!−k!∣f(k+1)!−k!,k\cdot k\neq{}(k+1)!-k!\mid f(k+1)!-k!, откъдето f(k+1)≥kf(k+1)\ge k и k∣f(k+1)!k!−1.k\mid \frac{f(k+1)!}{k!}-1. Последното изключва f(k+1)≥2k+1f(k+1)\ge2k+1, защото произведението (k+1)(k+2)⋯f(k+1)(k+1)(k+2)\cdots f(k+1) би се деляло на kk. Значи f(k+1)≤2kf(k+1)\le2k. От първоначалната делимост с n=1n=1 получаваме k∣f(k+1)−1k\mid f(k+1)-1. Единственото число между kk и 2k2k, което е 11 по модул kk, е k+1k+1. Следователно f(k+1)=k+1f(k+1)=k+1 и индукцията е завършена.
Отвори задачатаEvan Chen VONVON USAMO 2012/4Условие — източник

Задача 6

Пълен запис
Условие
За цяло число n≥2n\ge2 нека x1,x2,…,xnx_1,x_2,\ldots,x_n са реални числа, за които x1+x2+⋯+xn=0,x12+x22+⋯+xn2=1.x_1+x_2+\cdots+x_n=0,\qquad x_1^2+x_2^2+\cdots+x_n^2=1. За всяко подмножество A⊆{1,2,…,n}A\subseteq\{1,2,\ldots,n\} дефинираме SA=∑i∈AxiS_A=\sum_{i\in A}x_i; ако A=∅A=\emptyset, то SA=0S_A=0. Да се докаже, че за всяко положително число λ\lambda броят на множествата AA, за които SA≥λS_A\ge\lambda, е най-много 2n−3/λ22^{n-3}/\lambda^2. Да се намерят случаите на равенство.
РешениеИзбираме случайно подмножество AA чрез независими случайни величини εi∈{0,1}\varepsilon_i\in\{0,1\}, където P(εi=1)=1/2\mathbb P(\varepsilon_i=1)=1/2, и пишем SA=∑iεixi.S_A=\sum_i\varepsilon_i x_i. Тогава E(SA2)=\mathbb E(S_A^2)=∑iE(εi2)xi2+2∑i<jE(εiεj)xixj.\sum_i\mathbb E(\varepsilon_i^2)x_i^2+2\sum_{i\lt{}j}\mathbb E(\varepsilon_i\varepsilon_j)x_ix_j. Понеже E(εi2)=1/2\mathbb E(\varepsilon_i^2)=1/2 и E(εiεj)=1/4\mathbb E(\varepsilon_i\varepsilon_j)=1/4, получаваме E(SA2)=12∑ixi2+12∑i<jxixj.\mathbb E(S_A^2)=\frac12\sum_i x_i^2+\frac12\sum_{i\lt{}j}x_ix_j. От ∑ixi=0\sum_i x_i=0 следва ∑i<jxixj=−1/2\sum_{i\lt{}j}x_ix_j=-1/2, а от ∑ixi2=1\sum_i x_i^2=1 получаваме E(SA2)=12+12⋅(−12)=14.\mathbb E(S_A^2)=\frac12+\frac12\cdot\left(-\frac12\right)=\frac14. Следователно ∑ASA2=2n⋅14=2n−2.\sum_A S_A^2=2^n\cdot\frac14=2^{n-2}.Всяко множество AA се сдвоява с допълнението си, като SAc=−SAS_{A^c}=-S_A. Затова сумата на SA2S_A^2 само по множествата с SA>0S_A\gt{}0 е точно половината от общата сума, тоест ∑SA>0SA2=2n−3.\sum_{S_A\gt{}0}S_A^2=2^{n-3}. Ако NN е броят на множествата с SA≥λS_A\ge\lambda, то всяко от тях дава принос поне λ2\lambda^2, следователно Nλ2≤2n−3,N\lambda^2\le2^{n-3}, което е търсената оценка. Да разгледаме равенството. То изисква всяка положителна стойност на SAS_A да е точно λ\lambda; иначе или ще има положителна стойност под λ\lambda, която не се брои, или някоя броена стойност ще дава принос по-голям от λ2\lambda^2. Значи всички суми SAS_A принадлежат на множеството {−λ,0,λ}\{-\lambda,0,\lambda\}. В частност всяко xi=S{i}x_i=S_{\{i\}} е едно от тези три числа. Не може да има две положителни xix_i, защото сумата им би била 2λ2\lambda, и аналогично не може да има две отрицателни. Понеже общата сума е 00 и сумата от квадратите е 11, трябва, след пермутация, x1=12,x2=−12,x3=⋯=xn=0,x_1=\frac1{\sqrt2},\qquad x_2=-\frac1{\sqrt2},\qquad x_3=\cdots=x_n=0, и тогава λ=1/2\lambda=1/\sqrt2. Лесно се проверява, че точно тези случаи наистина дават равенство.
Отвори задачатаEvan Chen VONVON USAMO 2012/6Условие — източник