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

Evan Chen / USAMO Solution Notes

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

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

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

2002

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека SS е множество с 20022002 елемента и нека NN е цяло число с 0≤N≤220020\le N\le 2^{2002}. Да се докаже, че е възможно всяко подмножество на SS да се оцвети в черно или бяло така, че: (a) обединението на всеки две бели подмножества е бяло; (b) обединението на всеки две черни подмножества е черно; (c) има точно NN бели подмножества.
РешениеЩе докажем малко по-общото твърдение: ако n≥0n\ge0 и 0≤N≤2n0\le N\le 2^n, то подмножествата на {1,2,…,n}\{1,2,\ldots,n\} могат да се оцветят по желания начин с точно NN бели множества. Доказателството е с индукция по nn. При n=0n=0 има само едно подмножество и случаите N=0,1N=0,1 са очевидни. Нека твърдението е доказано за n−1n-1. Ако N≤2n−1N\le 2^{n-1}, оцветяваме подмножествата на {1,…,n−1}\{1,\ldots,n-1\} с точно NN бели множества според индукционното предположение, а всички подмножества, които съдържат nn, оцветяваме в черно. Тогава обединение на две бели множества пак не съдържа nn и остава бяло, а обединение, в което участва черно множество със nn, автоматично е черно. Останалите случаи следват от индукционното оцветяване. Ако N>2n−1N\gt{}2^{n-1}, оцветяваме подмножествата на {1,…,n−1}\{1,\ldots,n-1\} така, че белите да са N−2n−1N-2^{n-1}, а всички подмножества, които съдържат nn, правим бели. Същата проверка показва, че условията за обединение са запазени. Така индукцията завършва доказателството.
Отвори задачатаEvan Chen VONVON USAMO 2002/1Условие — източник

Задача 2

Пълен запис
Условие
Нека ABCABC е триъгълник, за който(cot⁡A2)2+(2cot⁡B2)2+(3cot⁡C2)2=(6s7r)2,\left(\cot\frac{A}{2}\right)^2+\left(2\cot\frac{B}{2}\right)^2+\left(3\cot\frac{C}{2}\right)^2=\left(\frac{6s}{7r}\right)^2,където ss е полупериметърът, а rr е радиусът на вписаната окръжност. Да се докаже, че ABCABC е подобен на триъгълник TT, чиито страни са положителни цели числа без общ делител, и да се намерят тези числа.
РешениеНека страните срещу A,B,CA,B,C са съответно a,b,ca,b,c и положим по обичайния начинx=s−a,y=s−b,z=s−c.x=s-a,\qquad y=s-b,\qquad z=s-c.Понеже cot⁡(A/2)=x/r\cot(A/2)=x/r и аналогично за другите два ъгъла, даденото равенство ставаx2+4y2+9z2=(67(x+y+z))2.x^2+4y^2+9z^2=\left(\frac67(x+y+z)\right)^2.От неравенството на Коши-Шварц имаме(1+14+19)(x2+4y2+9z2)≥(x+y+z)2.\left(1+\frac14+\frac19\right)(x^2+4y^2+9z^2)\ge (x+y+z)^2.Но 1+14+19=49361+\frac14+\frac19=\frac{49}{36}, а даденото равенство прави това неравенство равенство. Следователно е изпълнено условието за равенство в Коши-Шварц:x:2y:3z=1:12:13.x:2y:3z=1:\frac12:\frac13.Затоваx:y:z=36:9:4.x:y:z=36:9:4.Страните на триъгълника саa:b:c=(y+z):(z+x):(x+y)=13:40:45.a:b:c=(y+z):(z+x):(x+y)=13:40:45.Тези три числа са взаимно прости като тройка, така че търсеният триъгълник TT има страни 13,40,4513,40,45.
Отвори задачатаEvan Chen VONVON USAMO 2002/2Условие — източник

Задача 3

Пълен запис
Условие
Да се докаже, че всеки моничен многочлен от степен nn с реални коефициенти може да се представи като средно аритметично на два монични многочлена от степен nn, всеки от които има nn реални корена.
РешениеПърво ще използваме следната лема. Ако pp е моничен многочлен от степен nn иp(1)p(2)<0,p(2)p(3)<0,p(1)p(2)\lt{}0,\quad p(2)p(3)\lt{}0,…,p(n−1)p(n)<0,\quad \ldots,\quad p(n-1)p(n)\lt{}0,то pp има nn реални корена. Наистина, теоремата за междинните стойности дава по един корен във всеки интервал (1,2),(2,3),…,(n−1,n)(1,2),(2,3),\ldots,(n-1,n). Последният корен се намира извън този отрязък: ако nn е четно, p(x)→+∞p(x)\to +\infty при x→±∞x\to\pm\infty, а p(1)p(1) и p(n)p(n) са с противоположни знаци; ако nn е нечетно, крайните граници при −∞-\infty и +∞+\infty са с противоположни знаци, докато p(1)p(1) и p(n)p(n) са с един и същи знак. Нека сега ff е даденият моничен многочлен. Избираме число MM толкова голямо, че M>1000max⁡1≤t≤n∣f(t)∣+1000M\gt{}1000\max_{1\le t\le n}|f(t)|+1000. За всяко k=1,2,…,nk=1,2,\ldots,n избираме реални числа ak,bka_k,b_k, за коитоak+bk=2f(k),(−1)kak>M,(−1)k+1bk>M.a_k+b_k=2f(k),\qquad (-1)^k a_k\gt{}M,\qquad (-1)^{k+1}b_k\gt{}M.Това е възможно, като първо изберем aka_k с достатъчно голяма абсолютна стойност и нужния знак, а после положим bk=2f(k)−akb_k=2f(k)-a_k. Съществуват единствени монични многочлени gg и hh от степен nn със стойности g(k)=akg(k)=a_k и h(k)=bkh(k)=b_k за k=1,…,nk=1,\ldots,n. По избора на знаците и лемата и двата многочлена имат nn реални корена. Освен това многочленът 12(g+h)\frac12(g+h) и ff са монични от степен nn и съвпадат в точките 1,2,…,n1,2,\ldots,n. Разликата им има степен най-много n−1n-1 и има nn корена, следователно е нулевият многочлен. Значи f=12(g+h)f=\frac12(g+h), както се искаше.
Отвори задачатаEvan Chen VONVON USAMO 2002/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb{R}\to\mathbb{R}, за коитоf(x2−y2)=xf(x)−yf(y)f(x^2-y^2)=xf(x)-yf(y)за всички реални числа xx и yy.
РешениеОтговорът еf(x)=cx(c∈R),f(x)=cx\qquad(c\in\mathbb{R}),и тези функции очевидно удовлетворяват условието. Поставяйки съответно y=0y=0 и x=0x=0, получавамеf(x2)=xf(x),f(−y2)=−yf(y).f(x^2)=xf(x),\qquad f(-y^2)=-yf(y).Оттук ff е нечетна функция и в частност f(0)=0f(0)=0. Първоначалното равенство може да се запише катоf(x2−y2)+f(y2)=f(x2).f(x^2-y^2)+f(y^2)=f(x^2).Понеже всяко неотрицателно число е квадрат и ff е нечетна, следва, че ff е адитивна: f(u+v)=f(u)+f(v)f(u+v)=f(u)+f(v) за всички реални u,vu,v. Сега използваме едновременно адитивността и равенството f(x2)=xf(x)f(x^2)=xf(x). Имамеf((x+1)2)=(x+1)f(x+1).f((x+1)^2)=(x+1)f(x+1).Лявата страна еf(x2+2x+1)=f(x2)+2f(x)+f(1)=f(x^2+2x+1)=f(x^2)+2f(x)+f(1)=xf(x)+2f(x)+f(1),xf(x)+2f(x)+f(1),а дясната страна е(x+1)(f(x)+f(1)).(x+1)(f(x)+f(1)).След съкращаване получаваме f(x)=xf(1)f(x)=xf(1) за всяко реално xx. Това дава точно посочените линейни решения.
Отвори задачатаEvan Chen VONVON USAMO 2002/4Условие — източник

Задача 5

Пълен запис
Условие
Нека a,ba,b са цели числа, по-големи от 22. Да се докаже, че съществуват положително цяло число kk и крайна редица n1,n2,…,nkn_1,n_2,\ldots,n_k от положителни цели числа такива, че n1=an_1=a, nk=bn_k=b и ni+ni+1n_i+n_{i+1} дели nini+1n_i n_{i+1} за всяко 1≤i<k1\le i\lt{}k.
РешениеРазглеждаме граф GG с върхове 3,4,5,…3,4,5,\ldots, като два върха v,wv,w са свързани с ребро точно когато v+wv+w дели vwvw. Задачата е еквивалентна на това да докажем, че този граф е свързан. Първо, всяко n>2n\gt{}2 е свързано последователно сn(n−1),n(n−1)(n−2),…,n!.n(n-1),\quad n(n-1)(n-2),\quad \ldots,\quad n!.Например nn е свързано с n(n−1)n(n-1), защото сумата им е n2n^2, а произведението им е кратно на n2n^2; същата проверка работи на всяка следваща стъпка, тъй като вече натрупаното произведение съдържа нужния нов делител. Остава да видим, че факториелите са в една компонента. За n>2n\gt{}2 числото n!n! е свързано с (n+1)!(n+1)! така: ако nn е четно, тогава n!+(n+1)≠(n+2)n!n!+(n+1)\neq{}(n+2)n!, а n+2n+2 дели n!n!, така че има ребро n!∼(n+1)!n!\sim (n+1)!; ако nn е нечетно, използваме пътяn!∼2n!∼(n+1)!.n!\sim 2n!\sim (n+1)!.Първото ребро е валидно, понеже 3n!3n! дели 2(n!)22(n!)^2, а второто следва от 2n!+(n+1)≠(n+3)n!2n!+(n+1)\neq{}(n+3)n! и факта, че n+3n+3 дели 2n!2n!. Следователно всеки връх е свързан с някой факториел, а факториелите са свързани помежду си. Графът е свързан и исканата редица съществува.
Отвори задачатаEvan Chen VONVON USAMO 2002/5Условие — източник

Задача 6

Пълен запис
Условие
Имам лист с марки с размер n×nn\times n, от който трябва да откъсвам блокове от три съседни марки в един ред или в една колона. Мога да късам само по перфорациите между съседни марки и всеки блок трябва да излезе от листа цял. Нека b(n)b(n) е най-малкият брой блокове, които мога да откъсна така, че след това да е невъзможно да се откъсне още един блок. Да се докаже, че съществуват реални константи cc и dd, за които17n2−cn≤b(n)≤15n2+dn\frac17 n^2-cn\le b(n)\le \frac15 n^2+dnза всички n>0n\gt{}0.
РешениеЗа долната оценка броим всички възможни места, на които би могъл да стои един блок. Те са 2n(n−2)2n(n-2): по n(n−2)n(n-2) хоризонтални и вертикални. След като вече не може да се откъсне нов блок, всяко такова място трябва да пресича поне един откъснат блок. Един фиксиран откъснат блок пресича най-много 55 възможни блока със същата ориентация и най-много 99 възможни блока с другата ориентация, общо най-много 1414. Следователно14b(n)≥2n(n−2),14b(n)\ge 2n(n-2),тоестb(n)≥17n2−27n.b(n)\ge \frac17n^2-\frac27n.Това дава лявото неравенство. За горната оценка използваме периодичен строеж с период 55. Номерираме редовете и колоните и във всяка колона jj късаме вертикални блокове от три марки с начални редове r≡j(mod5)r\equiv j\pmod 5. В безкрайната периодична картина във всяка колона се редуват три откъснати и две останали клетки, така че няма три последователни останали клетки вертикално. Във всеки фиксиран ред откъснатите клетки заемат три последователни класа колони по модул 55, така че няма три последователни останали клетки и хоризонтално. В краен квадрат n×nn\times n вземаме всички цели вертикални блокове от тази периодична схема, които се побират в листа. Те са най-много 15n2+O(n)\frac15n^2+O(n). Възможните проблеми са само в няколко гранични реда и колони; там можем да добавим още O(n)O(n) вертикални блока и да унищожим всички останали възможни тройки. Следователно за някоя абсолютна константа dd имаме b(n)≤15n2+dnb(n)\le \frac15n^2+dn, което завършва доказателството.период 5
Отвори задачатаEvan Chen VONVON USAMO 2002/6Условие — източник