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

Evan Chen / USAMO Solution Notes

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

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

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

2011

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа, за които a2+b2+c2+(a+b+c)2≤4.a^2+b^2+c^2+(a+b+c)^2\le4. Да се докаже, че ab+1(a+b)2+bc+1(b+c)2+ca+1(c+a)2≥3.\frac{ab+1}{(a+b)^2}+\frac{bc+1}{(b+c)^2}+\frac{ca+1}{(c+a)^2}\ge3.
РешениеУсловието е еквивалентно на a2+b2+c2+ab+bc+ca≤2.a^2+b^2+c^2+ab+bc+ca\le2. Затова∑cyc2ab+2(a+b)2≥\sum_{\mathrm{cyc}}\frac{2ab+2}{(a+b)^2}\ge∑cyc2ab+a2+b2+c2+ab+bc+ca(a+b)2.\sum_{\mathrm{cyc}}\frac{2ab+a^2+b^2+c^2+ab+bc+ca}{(a+b)^2}.Във всяка циклична дроб числителят вдясно се преобразува като2ab+a2+b2+c2+ab+bc+ca=2ab+a^2+b^2+c^2+ab+bc+ca=(a+b)2+(c+a)(c+b).(a+b)^2+(c+a)(c+b).Следователно2∑cycab+1(a+b)2≥2\sum_{\mathrm{cyc}}\frac{ab+1}{(a+b)^2}\ge3+∑cyc(c+a)(c+b)(a+b)2.3+\sum_{\mathrm{cyc}}\frac{(c+a)(c+b)}{(a+b)^2}.По AM-GM за трите положителни члена имаме∑cyc(c+a)(c+b)(a+b)2≥\sum_{\mathrm{cyc}}\frac{(c+a)(c+b)}{(a+b)^2}\ge3x2∏cyc(c+a)(c+b)(a+b)23=3,3\sqrt[3]{\vphantom{x^2}\prod_{\mathrm{cyc}}\frac{(c+a)(c+b)}{(a+b)^2}}=3,защото произведението под корена е 11. Така дясната страна е поне 66, откъдето след деление на 22 получаваме исканото неравенство.
Отвори задачатаEvan Chen VONVON USAMO 2011/1Условие — източник

Задача 2

Пълен запис
Условие
На всеки връх на правилен петоъгълник е записано цяло число така, че сумата на петте числа е 20112011. Един ход в играта се състои в това да се избере цяло число mm, не непременно положително, да се извади mm от числата в два съседни върха и да се прибави 2m2m към противоположния връх, който не е съседен на нито един от първите два. Числото mm и избраните върхове могат да се променят от ход на ход. Казваме, че играта се печели във връх, ако след краен брой ходове в този връх стои числото 20112011, а в останалите четири върха стоят нули. Да се докаже, че при всяко начално разпределение има точно един връх, в който играта може да се спечели.
РешениеНомерираме върховете последователно с 0,1,2,3,40,1,2,3,4 и нека текущите числа са N0,N1,N2,N3,N4N_0,N_1,N_2,N_3,N_4. ВеличинатаS=N1+2N2+3N3+4N4(mod5)S=N_1+2N_2+3N_3+4N_4\pmod5е инвариант. Наистина, ако в един ход противоположният връх е ii, тогава промяната в претеглената сума е 2im−(i+2)m−(i+3)m≡0(mod5)2im-(i+2)m-(i+3)m\equiv0\pmod5, където индексите са по модул 55. Това веднага показва, че може да има най-много един печеливш връх: ако накрая единственото ненулево число е 20112011 във връх jj, то S≡2011j≡j(mod5)S\equiv2011j\equiv j\pmod5. Остава да докажем, че този единствен възможен връх наистина е достижим. Без ограничение нека той е връх 00, тоест началните числа a0,a1,a2,a3,a4a_0,a_1,a_2,a_3,a_4 удовлетворяватa1+2a2+3a3+4a4≡0(mod5).a_1+2a_2+3a_3+4a_4\equiv0\pmod5.Нека xix_i е сумата на всички избрани стойности mm в ходовете, при които връх ii е противоположният връх и получава 2m2m. Търсим цели xix_i, за които крайното състояние да е печелившо във връх 00. Това дава системата2011=a0+2x0−x2−x3,2011=a_0+2x_0-x_2-x_3,0=a1+2x1−x3−x4,0=a_1+2x_1-x_3-x_4,0=a2+2x2−x4−x0,0=a_2+2x_2-x_4-x_0,0=a3+2x3−x0−x1,0=a_3+2x_3-x_0-x_1,0=a4+2x4−x1−x2.0=a_4+2x_4-x_1-x_2.Първото уравнение следва от останалите четири и от запазването на общата сума. Освен това можем да прибавим една и съща константа към всички xix_i, без да променим нито едно от крайните числа; затова поставяме x0=0x_0=0. От третото и четвъртото уравнение получавамеx4=2x2+a2,x1=2x3+a3.x_4=2x_2+a_2,\qquad x_1=2x_3+a_3.След заместване във второто и петото остават2x2−3x3=2a3+a1−a2,2x3−3x2=2a2+a4−a3.2x_2-3x_3=2a_3+a_1-a_2,\qquad 2x_3-3x_2=2a_2+a_4-a_3.Изваждайки, намирамеx2−x3=a1−3a2+3a3−a45.x_2-x_3=\frac{a_1-3a_2+3a_3-a_4}{5}.Дробта е цяло число, защото числителят е сравним с a1+2a2+3a3+4a4a_1+2a_2+3a_3+4a_4 по модул 55. Ако го означим с kk, една целочислена система решения еx2=3k−(2a3+a1−a2),x3=2k−(2a3+a1−a2),x_2=3k-(2a_3+a_1-a_2),\qquad x_3=2k-(2a_3+a_1-a_2),x1=2x3+a3,x4=2x2+a2,x0=0.x_1=2x_3+a_3,\qquad x_4=2x_2+a_2,\qquad x_0=0.Понеже mm може да е отрицателно, всяка такава целочислена петорка xix_i се реализира чрез съответните ходове. Следователно печалбата в единствения връх, определен от инварианта, винаги е възможна.
Отвори задачатаEvan Chen VONVON USAMO 2011/2Условие — източник

Задача 4

Пълен запис
Условие
Да се разгледа твърдението: за всяко положително цяло число n≥2n\ge2 остатъкът при деление на 22n2^{2^n} на 2n−12^n-1 е степен на 44. Да се докаже твърдението или да се намери контрапример с доказателство.
РешениеЩе покажем, че n=25n=25 е контрапример. По модул 225−12^{25}-1 имаме 225≡12^{25}\equiv1, затова степените на 22 имат период, който дели 2525. Следователно показателят може да се намали по модул 2525:2225≡2225 mod 25≡27(mod225−1),2^{2^{25}}\equiv2^{2^{25}\bmod 25}\equiv2^7\pmod{2^{25}-1},понеже 225≡7(mod25)2^{25}\equiv7\pmod{25}. Числото 272^7 наистина е остатъкът, защото 0<27<225−10\lt{}2^7\lt{}2^{25}-1. Но 272^7 не е степен на 44, тъй като всяка степен на 44 има вида 22t2^{2t} с четен показател. Значи твърдението е невярно.
Отвори задачатаEvan Chen VONVON USAMO 2011/4Условие — източник

Задача 6

Пълен запис
Условие
Нека AA е множество с ∣A∣=225|A|=225. Да предположим, че съществуват единадесет подмножества A1,A2,…,A11A_1,A_2,\ldots,A_{11} на AA, за които ∣Ai∣=45|A_i|=45 за 1≤i≤111\le i\le11 и ∣Ai∩Aj∣=9|A_i\cap A_j|=9 за 1≤i<j≤111\le i\lt{}j\le11. Да се докаже, че ∣A1∪A2∪⋯∪A11∣≥165,|A_1\cup A_2\cup\cdots\cup A_{11}|\ge165, и да се даде пример, при който има равенство.
РешениеЧислото 225225 почти не играе роля в оценката. Да означим елементите на обединението A1∪⋯∪A11A_1\cup\cdots\cup A_{11} с a1,a2,…,ana_1,a_2,\ldots,a_n, и нека xix_i е броят на множествата AjA_j, в които участва aia_i. Тогава∑i=1nxi=45⋅11=495.\sum_{i=1}^n x_i=45\cdot11=495.От друга страна, ако броим по двойки множествата Ap,AqA_p,A_q, в които се среща един и същ елемент, получаваме∑i=1n(xi2)=(112)⋅9.\sum_{i=1}^n\binom{x_i}{2}=\binom{11}{2}\cdot9.Понеже (xi2)=(xi2−xi)/2\binom{x_i}{2}=(x_i^2-x_i)/2, оттук следва∑i=1nxi2=2(112)⋅9+495=1485.\sum_{i=1}^n x_i^2=2\binom{11}{2}\cdot9+495=1485.По неравенството на Коши-Шварцn∑i=1nxi2≥(∑i=1nxi)2,n\sum_{i=1}^n x_i^2\ge\left(\sum_{i=1}^n x_i\right)^2,следователноn≥49521485=165.n\ge\frac{495^2}{1485}=165.Точно това е исканото, защото nn е размерът на обединението. За пример с равенство вземаме като обединение всички триелементни подмножества на {1,2,…,11}\{1,2,\ldots,11\}; те са (113)=165\binom{11}{3}=165. Ако държим самото множество AA да има точно 225225 елемента, добавяме още 6060 произволни елемента, които не участват в нито едно AiA_i. Нека AiA_i е множеството от всички триелементни подмножества, които съдържат ii. Тогава∣Ai∣=(102)=45,|A_i|=\binom{10}{2}=45,а за i≠ji\ne j множеството Ai∩AjA_i\cap A_j се състои от триелементните подмножества, съдържащи едновременно ii и jj, така че третият елемент може да се избере по (91)=9\binom{9}{1}=9 начина. Получаваме равенство.
Отвори задачатаEvan Chen VONVON USAMO 2011/6Условие — източник