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

Evan Chen / USAMO Solution Notes

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

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

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

2017

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

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

  • 2017 · 11-12: липсва задача 3, 4, 5

11-12

3 задачи

Задача 1

Пълен запис
Условие
Да се докаже, че съществуват безкрайно много двойки взаимно прости положителни цели числа a,b>1a,b\gt{}1, за които a+ba+b дели ab+baa^b+b^a.
РешениеЩе дадем явно безкрайно семейство. За всяко цяло n≥2n\ge2 поставяме a=2n−1,b=2n+1.a=2n-1,\qquad b=2n+1. Тогава a,b>1a,b\gt{}1 и gcd⁡(a,b)=gcd⁡(2n−1,2)=1,\gcd(a,b)=\gcd(2n-1,2)=1, така че числата са взаимно прости. Нека m=a+b=4nm=a+b=4n. Понеже b≡−a(modm)b\equiv -a\pmod m, получаваме ab+ba≡ab+(−a)a=ab−aa=aa(ab−a−1)(modm),a^b+b^a\equiv a^b+(-a)^a=a^b-a^a=a^a(a^{b-a}-1)\pmod m, защото aa е нечетно. Но b−a=2b-a=2, а a2−1=(2n−1)2−1=4n(n−1),a^2-1=(2n-1)^2-1=4n(n-1), което се дели на 4n=m4n=m. Следователно ab−a−1=a2−1≡0(modm)a^{b-a}-1=a^2-1\equiv0\pmod m, откъдето m∣ab+bam\mid a^b+b^a. Така всяко n≥2n\ge2 дава допустима двойка (2n−1,2n+1)(2n-1,2n+1), а тези двойки са безкрайно много.
Отвори задачатаEvan Chen VONVON USAMO 2017/1Условие — източник

Задача 2

Пълен запис
Условие
Нека m1,m2,…,mnm_1,m_2,\ldots,m_n е колекция от nn положителни цели числа, не непременно различни. За всяка последователност от цели числа A=(a1,…,an)A=(a_1,\ldots,a_n) и всяка пермутация w=(w1,…,wn)w=(w_1,\ldots,w_n) на m1,m2,…,mnm_1,m_2,\ldots,m_n наричаме AA-инверсия на ww двойка членове wi,wjw_i,w_j с i<ji\lt{}j, за която е изпълнено едно от условията ai≥wi>wj,wj>ai≥wi,wi>wj>ai.a_i\ge w_i\gt{}w_j,\qquad w_j\gt{}a_i\ge w_i,\qquad w_i\gt{}w_j\gt{}a_i. Да се докаже, че за всеки две последователности от цели числа A=(a1,…,an)A=(a_1,\ldots,a_n) и B=(b1,…,bn)B=(b_1,\ldots,b_n) и за всяко положително цяло число kk броят на пермутациите на m1,m2,…,mnm_1,m_2,\ldots,m_n с точно kk AA-инверсии е равен на броя на пермутациите с точно kk BB-инверсии.
РешениеЩе докажем, че за фиксиран избор на AA генериращата функция FA(q)=∑wqIA(w),F_A(q)=\sum_w q^{I_A(w)}, където IA(w)I_A(w) е броят AA-инверсии, всъщност не зависи от AA. Броим пермутациите с кратност: ако например мултимножеството е {1,1,2}\{1,1,2\}, то имаме 3!3! пермутации на трите дадени позиции. Нека различните стойности в мултимножеството са θ1<θ2<⋯<θm,\theta_1\lt{}\theta_2\lt{}\cdots\lt{}\theta_m, а eie_i е броят появявания на θi\theta_i, така че e1+⋯+em=ne_1+\cdots+e_m=n. За обикновените инверсии wi>wjw_i\gt{}w_j е стандартно, че генериращата функция е F(e1,…,em)=[n]q!∏i=1mei![ei]q!,F(e_1,\ldots,e_m)=[n]_q!\prod_{i=1}^m\frac{e_i!}{[e_i]_q!}, където [r]q≠(1)(1+q)⋯(1+q+⋯+qr−1)[r]_q\neq{}(1)(1+q)\cdots(1+q+\cdots+q^{r-1}). Това се вижда, като първо разграничим леко равните елементи и получим [n]q![n]_q!, а после за всяка група от равни елементи премахнем вътрешните инверсии, което дели на [ei]q![e_i]_q! и умножава по ei!e_i!. Сега доказваме по индукция по nn, че същата формула важи за всеки избор на AA. Нека първият праг a1a_1 лежи между θk\theta_k и θk+1\theta_{k+1}, тоест θk≤a1<θk+1\theta_k\le a_1\lt{}\theta_{k+1}, като допускаме k=0k=0 или k=mk=m. Ако първият член на пермутацията е θi\theta_i с i≤ki\le k, тогава AA-инверсиите, които използват този първи член, са точно e1+⋯+ei−1+ek+1+⋯+em.e_1+\cdots+e_{i-1}+e_{k+1}+\cdots+e_m. Ако i>ki\gt{}k, броят им е ek+1+⋯+ei−1.e_{k+1}+\cdots+e_{i-1}. След избора на първия член остава същата задача с едно по-малко появяване на θi\theta_i, затова по индукционното предположение получаваме рекурсията FA(e1,…,em)=F_A(e_1,\ldots,e_m)=∑i=1kqe1+⋯+ei−1+ek+1+⋯+emeiF(e1,…,ei−1,…,em)\sum_{i=1}^k q^{e_1+\cdots+e_{i-1}+e_{k+1}+\cdots+e_m}e_iF(e_1,\ldots,e_i-1,\ldots,e_m)+∑i=k+1mqek+1+⋯+ei−1eiF(e1,…,ei−1,…,em).+\sum_{i=k+1}^m q^{e_{k+1}+\cdots+e_{i-1}}e_iF(e_1,\ldots,e_i-1,\ldots,e_m). Делим тази рекурсия на явната формула за F(e1,…,em)F(e_1,\ldots,e_m). От eiF(e1,…,ei−1,…,em)F(e1,…,em)=\frac{e_iF(e_1,\ldots,e_i-1,\ldots,e_m)}{F(e_1,\ldots,e_m)}=1−qei1−qn\frac{1-q^{e_i}}{1-q^n} остава да се провери тъждеството 1−qn=1-q^n=qek+1+⋯+em∑i=1kqe1+⋯+ei−1(1−qei)q^{e_{k+1}+\cdots+e_m}\sum_{i=1}^k q^{e_1+\cdots+e_{i-1}}(1-q^{e_i})+∑i=k+1mqek+1+⋯+ei−1(1−qei).+\sum_{i=k+1}^m q^{e_{k+1}+\cdots+e_{i-1}}(1-q^{e_i}). Двете суми телескопират съответно до qek+1+⋯+em−qnq^{e_{k+1}+\cdots+e_m}-q^n и 1−qek+1+⋯+em1-q^{e_{k+1}+\cdots+e_m}, така че тъждеството е вярно. Следователно FA(q)=F(e1,…,em)F_A(q)=F(e_1,\ldots,e_m) за всяко AA, а коефициентът пред qkq^k е независим от AA. Това доказва твърдението и за всяка друга последователност BB.
Отвори задачатаEvan Chen VONVON USAMO 2017/2Условие — източник

Задача 6

Пълен запис
Условие
Да се намери най-малката възможна стойност на ab3+4+bc3+4+cd3+4+da3+4,\frac{a}{b^3+4}+\frac{b}{c^3+4}+\frac{c}{d^3+4}+\frac{d}{a^3+4}, ако a,b,c,da,b,c,d са неотрицателни реални числа и a+b+c+d=4a+b+c+d=4.
РешениеОтговорът е 23\frac23. Тази стойност се достига например при (a,b,c,d)=(2,2,0,0)(a,b,c,d)=(2,2,0,0) и при цикличните му размествания. Основната оценка е допирателната права към функцията 1/(x3+4)1/(x^3+4) при x=2x=2: за всяко x≥0x\ge0 имаме 1x3+4≥14−x12,\frac1{x^3+4}\ge\frac14-\frac{x}{12}, защото след умножение с положителното x3+4x^3+4 това е еквивалентно на 12−(3−x)(x3+4)=x(x+1)(x−2)2≥0.12-(3-x)(x^3+4)=x(x+1)(x-2)^2\ge0. Прилагаме тази оценка циклично и получаваме ∑cycab3+4≥a+b+c+d4−ab+bc+cd+da12.\sum_{\rm cyc}\frac{a}{b^3+4}\ge\frac{a+b+c+d}{4}-\frac{ab+bc+cd+da}{12}. Но ab+bc+cd+da=(a+c)(b+d)≤ab+bc+cd+da=(a+c)(b+d)\le((a+c)+(b+d)2)2=4,\left(\frac{(a+c)+(b+d)}2\right)^2=4, тъй като a+b+c+d=4a+b+c+d=4. Следователно ∑cycab3+4≥1−412=23.\sum_{\rm cyc}\frac{a}{b^3+4}\ge1-\frac{4}{12}=\frac23. Равенство има при (2,2,0,0)(2,2,0,0): тогава ненулевите членове дават 223+4+203+4=16+12=23.\frac{2}{2^3+4}+\frac{2}{0^3+4}=\frac16+\frac12=\frac23. Значи най-малката възможна стойност е точно 23\frac23.
Отвори задачатаEvan Chen VONVON USAMO 2017/6Условие — източник