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

Evan Chen / USAMO Solution Notes

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

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

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

2022

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека aa и bb са положителни цели числа. Всяка клетка на таблица (a+b+1)×(a+b+1)(a+b+1)\times(a+b+1) е оцветена или в кехлибарено, или в бронзово, като има поне a2+ab−ba^2+ab-b кехлибарени клетки и поне b2+ab−ab^2+ab-a бронзови клетки. Да се докаже, че могат да се изберат aa кехлибарени клетки и bb бронзови клетки така, че никои две от избраните a+ba+b клетки да не лежат в един и същ ред или в един и същ стълб.
РешениеЩе наричаме трансверсал избор на a+b+1a+b+1 клетки, по една от всеки ред и по една от всеки стълб. Първо ще докажем, че съществува трансверсал TaT_a с поне aa кехлибарени клетки. Ако изберем трансверсал равновероятно, всяка клетка попада в него с вероятност 1/(a+b+1)1/(a+b+1), затова очакваният брой кехлибарени клетки е поне a2+ab−ba+b+1=a−1+1a+b+1>a−1.\frac{a^2+ab-b}{a+b+1}=a-1+\frac{1}{a+b+1}\gt{}a-1. Следователно някой трансверсал има поне aa кехлибарени клетки. По същия начин съществува трансверсал TbT_b с поне bb бронзови клетки, тоест с най-много a+1a+1 кехлибарени клетки. Остава да преминем от TaT_a към TbT_b. Всеки два трансверсала могат да се свържат чрез последователност от стандартни размени: избираме две избрани клетки в различни редове и стълбове и ги заменяме с другите два върха на определения от тях правоъгълник. Това запазва свойството да имаме трансверсал. При една такава размяна броят на кехлибарените клетки се изменя с най-много 22. В началото този брой е поне aa, а в края е най-много a+1a+1; следователно в някой момент по пътя той е равен на aa или на a+1a+1. Ако е равен на aa, избраният трансверсал съдържа b+1b+1 бронзови клетки и изхвърляме една от тях. Ако е равен на a+1a+1, той съдържа bb бронзови клетки и изхвърляме една кехлибарена клетка. И в двата случая остават точно aa кехлибарени и bb бронзови клетки, без две от тях да са в един ред или стълб.
Отвори задачатаEvan Chen VONVON USAMO 2022/1Условие — източник

Задача 2

Пълен запис
Условие
Нека b≥2b\ge2 и w≥2w\ge2 са фиксирани цели числа и нека n=b+wn=b+w. Дадени са 2b2b еднакви черни пръчки и 2w2w еднакви бели пръчки, всяка с дължина 11. От тях сглобяваме правилен 2n2n-ъгълник така, че успоредните страни да имат един и същ цвят. След това чрез пренасяне на черните пръчки се образува изпъкнал 2b2b-ъгълник BB, а чрез пренасяне на белите пръчки - изпъкнал 2w2w-ъгълник WW. Да се докаже, че разликата между лицата на BB и WW зависи само от числата bb и ww, а не от начина, по който е сглобен правилният 2n2n-ъгълник.
РешениеЩе докажем, че може да се разменят съседна черна и бяла пръчка, заедно със срещуположните им успоредни пръчки, без да се променя величината [B]−[W][B]-[W], където [P][P] означава лицето на многоъгълника PP. Такива съседни размени свързват всички допустими сглобявания с даден брой черни и бели двойки страни, така че това ще докаже инвариантността. Нека u⃗\vec u и v⃗\vec v са съответно черният и белият вектор на двете съседни страни, които ще разменяме. Нека x⃗\vec x е сумата на всички други черни вектори между u⃗\vec u и −u⃗-\vec u по обиколката, а y⃗\vec y - аналогичната сума за белите вектори между v⃗\vec v и −v⃗-\vec v. Единствената промяна в лицата идва от съответните успоредници. С означението ∧\wedge за ориентирано лице на успоредник трябва да проверимu⃗∧x⃗−v⃗∧y⃗=v⃗∧x⃗−u⃗∧y⃗.\vec u\wedge\vec x-\vec v\wedge\vec y=\vec v\wedge\vec x-\vec u\wedge\vec y.Това е еквивалентно на(u⃗−v⃗)∧(x⃗+y⃗)=0,(\vec u-\vec v)\wedge(\vec x+\vec y)=0,тоест на това u⃗−v⃗\vec u-\vec v и x⃗+y⃗\vec x+\vec y да са успоредни. Двата вектора наистина са успоредни, защото и двата са перпендикулярни на u⃗+v⃗\vec u+\vec v. Първо, u⃗−v⃗⊥u⃗+v⃗\vec u-\vec v\perp\vec u+\vec v, понеже u⃗\vec u и v⃗\vec v имат една и съща дължина. Второ, векторът u⃗+v⃗+x⃗+y⃗\vec u+\vec v+\vec x+\vec y свързва две срещуположни точки на описаната окръжност на правилния 2n2n-ъгълник, т.е. описва диаметър. Точката, получена след изминаване на u⃗+v⃗\vec u+\vec v, лежи върху същата полуокръжност, затова по теоремата за вписания ъгъл имаме (u⃗+v⃗)⊥(x⃗+y⃗)(\vec u+\vec v)\perp(\vec x+\vec y). Следователно u⃗−v⃗\vec u-\vec v и x⃗+y⃗\vec x+\vec y са успоредни, равенството за лицата е вярно и разликата [B]−[W][B]-[W] не се изменя при размяната. Понеже всяка подредба на цветовете с bb черни и ww бели двойки страни може да се получи от всяка друга чрез такива съседни размени, разликата между лицата зависи само от bb и ww.
Отвори задачатаEvan Chen VONVON USAMO 2022/2Условие — източник

Задача 3

Пълен запис
Условие
Да се реши в положителните реални числа функционалното уравнениеf(x)=f(f(f(x))+y)+f(xf(y))f(x+y)f(x)=f(f(f(x))+y)+f(xf(y))f(x+y)за всички положителни реални числа xx и yy.
РешениеОтговорът еf(x)=cx(c>0).f(x)=\frac{c}{x}\qquad(c\gt{}0).Тези функции се проверяват непосредствено. Ще докажем, че други решения няма. Нека P(x,y)P(x,y) означава даденото равенство, а fmf^m - mm-кратната итерация на ff. Първо въвеждаме помощното твърдениеQ(a,b):f(a)≥f(b)⟹f(f(b))≥a.Q(a,b): f(a)\ge f(b)\Longrightarrow f(f(b))\ge a.Наистина, ако a>f(f(b))a\gt{}f(f(b)), поставяме y=a−f(f(b))>0y=a-f(f(b))\gt{}0 в P(b,y)P(b,y). Тогава първият член вдясно е f(a)f(a), а вторият е положителен, така че получаваме f(b)>f(a)f(b)\gt{}f(a), противоречие. От Q(t,t)Q(t,t) следва f2(t)≥tf^2(t)\ge t за всяко t>0t\gt{}0. При t=f2(x)t=f^2(x) получаваме f4(x)≥f2(x)f^4(x)\ge f^2(x). Освен това при t=f(x)t=f(x) и t=f3(x)t=f^3(x) имаме f(x)≤f3(x)≤f5(x)f(x)\le f^3(x)\le f^5(x). Затова можем да приложим Q(f4(x),x)Q(f^4(x),x) и получаваме обратното неравенство f2(x)≥f4(x)f^2(x)\ge f^4(x). Следователноf2(x)=f4(x)f^2(x)=f^4(x)за всяко x>0x\gt{}0. Следващата стъпка е инективност. Да допуснем, че f(u)=f(v)f(u)=f(v) за някои u>vu\gt{}v. От Q(u,v)Q(u,v) и Q(v,u)Q(v,u) следва f2(v)≥uf^2(v)\ge u и f2(u)≥vf^2(u)\ge v. Сравнявайки равенствата P(z,u)P(z,u) и P(z,v)P(z,v) за z=f2(x)z=f^2(x) и използвайки f2=f4f^2=f^4 и f(u)=f(v)f(u)=f(v), получавамеf(f2(x)+u)=f(f2(x)+v)f(f^2(x)+u)=f(f^2(x)+v)за всяко x>0x\gt{}0. Сега сравняваме P(x,u)P(x,u) и P(x,v)P(x,v); отново понеже f(u)=f(v)f(u)=f(v), следваf(x+u)=f(x+v)f(x+u)=f(x+v)за всяко x>0x\gt{}0. Значи ff е периодична с период T=u−v>0T=u-v\gt{}0. Но тогава твърдението Q(1+nT,1)Q(1+nT,1) за произволно големи nn би изисквало f(f(1))≥1+nTf(f(1))\ge1+nT, което е невъзможно. Следователно ff е инективна. От f2=f4f^2=f^4 и инективността получаваме f2(x)=xf^2(x)=x. Тогава първоначалното уравнение се опростява доf(x)=f(x+y)(1+f(xf(y))).f(x)=f(x+y)\bigl(1+f(xf(y))\bigr).При x=1x=1 това даваf(1+y)=f(1)1+yf(1+y)=\frac{f(1)}{1+y}за всяко y>0y\gt{}0, така че f(t)=f(1)/tf(t)=f(1)/t за всички t>1t\gt{}1. Нека c=f(1)c=f(1). Ако a,b>1a,b\gt{}1, от последното опростено равенство получавамеca=ca+b(1+f(acb)),\frac ca=\frac{c}{a+b}\left(1+f\left(\frac{ac}{b}\right)\right),следователно f(ac/b)=b/af(ac/b)=b/a. Като оставим отношението a/ba/b да пробягва всички положителни стойности, получаваме f(t)=c/tf(t)=c/t за всяко t>0t\gt{}0.
Отвори задачатаEvan Chen VONVON USAMO 2022/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички наредени двойки прости числа (p,q)(p,q), за които p−qp-q и pq−qpq-q са точни квадрати.
РешениеОтговорът е единствено (p,q)=(3,2)(p,q)=(3,2), което очевидно работи: 3−2=13-2=1 и 3⋅2−2=43\cdot2-2=4. Ще докажем, че други двойки няма. Случаят p=qp=q не дава решение, затова можем да пишем a2=p−q,b2=pq−q=q(p−1)a^2=p-q,\qquad b^2=pq-q=q(p-1) с положителни цели числа aa и bb. Имаме 0<a<p0\lt{}a\lt{}p и 0<b<p0\lt{}b\lt{}p. Изваждаме двете равенства и получаваме (b−a)(b+a)=b2−a2=p(q−1).(b-a)(b+a)=b^2-a^2=p(q-1). Понеже 0<b−a<p0\lt{}b-a\lt{}p и 0<b+a<2p0\lt{}b+a\lt{}2p, простото число pp не може да дели b−ab-a и затова трябва да дели b+ab+a. Единствената възможност е b+a=p,b+a=p, а от горното равенство следва b−a=q−1.b-a=q-1. Тогава pp и q−1q-1 имат една и съща четност. Това е възможно само при q=2q=2. При q=2q=2 условията стават a2=p−2a^2=p-2 и b2=2p−2b^2=2p-2. Ако p≡1(mod3)p\equiv1\pmod3, тогава a2≡2(mod3)a^2\equiv2\pmod3, невъзможно. Ако p≡2(mod3)p\equiv2\pmod3, тогава b2≡2(mod3)b^2\equiv2\pmod3, също невъзможно. Следователно pp се дели на 33, а понеже pp е просто, p=3p=3. Получаваме единственото решение (3,2)(3,2).
Отвори задачатаEvan Chen VONVON USAMO 2022/4Условие — източник

Задача 5

Пълен запис
Условие
Една функция f:R→Rf:\mathbb R\to\mathbb R ще наричаме съществено растяща, ако f(s)≤f(t)f(s)\le f(t) винаги когато s≤ts\le t са реални числа, за които f(s)≠0f(s)\ne0 и f(t)≠0f(t)\ne0. Да се намери най-малкото цяло число kk със следното свойство: за произволни 20222022 реални числа x1,x2,…,x2022x_1,x_2,\ldots,x_{2022} съществуват kk съществено растящи функции f1,…,fkf_1,\ldots,f_k, такива чеf1(n)+f2(n)+⋯+fk(n)=xnf_1(n)+f_2(n)+\cdots+f_k(n)=x_nза всяко n=1,2,…,2022n=1,2,\ldots,2022.
РешениеОтговорът е 1111. По-общо, ако 20222022 се замени с NN, отговорът е ⌊log⁡2N⌋+1\lfloor\log_2 N\rfloor+1. Тъй като 210≤2022<2112^{10}\le2022\lt{}2^{11}, това дава 1111. Първо доказваме долната оценка. Да предположим, че N>2k−1N\gt{}2^k-1, и избираме xn=−nx_n=-n за n=1,2,…,Nn=1,2,\ldots,N. За всяко nn некаS(n)={i∈{1,2,…,k}:fi(n)≠0}.S(n)=\{i\in\{1,2,\ldots,k\}: f_i(n)\ne0\}.Множеството S(n)S(n) е непразно, защото сумата е −n≠0-n\ne0. Има само 2k−12^k-1 непразни подмножества на {1,2,…,k}\{1,2,\ldots,k\}, затова по принципа на Дирихле съществуват n<mn\lt{}m с S(n)=S(m)S(n)=S(m). За всеки индекс от това общо множество условието за съществено растене дава fi(n)≤fi(m)f_i(n)\le f_i(m), а за останалите индекси и двете стойности са нула. Следователно xn≤xmx_n\le x_m, което противоречи на −n>−m-n\gt{}-m. Значи непременно N≤2k−1N\le2^k-1. Остава конструкцията при N=2k−1N=2^k-1; по-малките NN следват, като просто пренебрегнем излишните места. Подреждаме непразните подмножества на {1,2,…,k}\{1,2,\ldots,k\} в стандартния рекурсивен ред, получен от двоичния отразен код на Грей. На позиция nn ще бъдат ненулеви точно функциите с индекси от съответното множество S(n)S(n). Този ред има важната особеност, че конструкцията за k−1k-1 функции се появява първо с малки стойности, после се обръща с добавен нов индекс kk и с много по-големи стойности. Избираме число BB толкова голямо, че всички дадени xnx_n да са пренебрежимо малки в сравнение с последователните степени на BB. В първата половина използваме по индукция вече построените k−1k-1 функции. В средната позиция даваме на първите k−1k-1 функции много големи положителни стойности B,B2,…,Bk−1B,B^2,\ldots,B^{k-1}, а стойността на fkf_k избираме така, че сумата да стане нужното xnx_n. В последната половина повтаряме обърнатата конструкция за първите k−1k-1 функции, но всички нейни ненулеви стойности са изместени в диапазон от много големи положителни числа; остатъкът отново се поема от fkf_k. Понеже BB е избрано достатъчно голямо, ненулевите стойности на всяка от функциите се появяват в нарастващ ред. Така на всяко от числата 1,2,…,2k−11,2,\ldots,2^k-1 сумата е точно предписаното xnx_n, а всяка функция е съществено растяща върху ненулевите си стойности. Извън тези цели точки дефинираме функциите да са нула. Това не нарушава условието, понеже то сравнява само двойки точки, в които и двете стойности са ненулеви. Конструкцията завършва доказателството.
Отвори задачатаEvan Chen VONVON USAMO 2022/5Условие — източник

Задача 6

Пълен запис
Условие
В социалната мрежа Mathbook има 20222022 потребители, като някои двойки от тях са приятели. В Mathbook приятелството е взаимно и веднъж възникнало, остава валидно. От този момент нататък Mathbook позволява ново приятелство между двама потребители само ако те имат поне двама общи приятели. Кой е най-малкият брой приятелства, които трябва вече да съществуват, така че да е възможно в крайна сметка всеки потребител да стане приятел с всеки друг?
РешениеЩе решим по-общата задача за nn потребители. Отговорът е⌈3n2⌉−2,\left\lceil\frac{3n}{2}\right\rceil-2,а за n=2022n=2022 това е 30313031. В езика на графите започваме с граф GG върху nn върха. Разрешената операция е: ако имаме цикъл C4C_4, можем да добавим двата му диагонала, т.е. да допълним този C4C_4 до K4K_4. Търсим най-малкия брой начални ребра, при който чрез такива операции може да се стигне до KnK_n. Първо даваме конструкция. Ако nn е четно, започваме с ребро abab и построяваме n/2−1n/2-1 копия на C4C_4, всяко от които използва реброто abab. Всяко копие добавя две нови върхови точки и три нови ребра, така че общият брой ребра е 1+3(n/2−1)=3n/2−21+3(n/2-1)=3n/2-2. Допълваме първо всички тези четириъгълници до K4K_4. След това всеки два върха, които не са aa и bb, вече имат общи приятели aa и bb, така че можем да добавим ребрата между тях и да завършим до KnK_n. Ако nn е нечетно, правим същата конструкция за n−1n-1 върха и добавяме още един връх, свързан с aa и bb; броят на ребрата става ⌈3n/2⌉−2\lceil3n/2\rceil-2, а допълването е аналогично. Остава долната оценка. Ще опишем алгоритъм, който добавя всички ребра, които могат да бъдат принудени, докато повече няма възможна операция. Поддържаме списък C\mathcal C от клики и етикетиране LL на ребрата: всяко ребро носи етикета на една клика от C\mathcal C, която го съдържа. В началото всяко начално ребро е отделна клика K2K_2 и носи собствения си етикет. Когато има цикъл C4=abcdC_4=abcd, чиито четири страни не всички имат един и същ етикет, вземаме всички клики, чиито етикети се появяват по тези четири страни, и нека VV е обединението на върховете им. Добавяме всички ребра, нужни за да стане VV клика, и сливаме тези клики в една нова клика KVK_V. Ребрата с използваните етикети, както и новите ребра, получават етикета KVK_V. Спираме, когато всеки C4C_4 има един и същ етикет по четирите си страни; тогава вече няма операция, която да създаде нова информация. Ако началният граф изобщо може да се допълни до KnK_n, този алгоритъм трябва накрая да има една единствена клика KnK_n. За клика K∈CK\in\mathcal C нека θ(K)\theta(K) е броят на началните ребра, които в момента носят етикета KK. Твърдим, че през целия алгоритъмθ(K)≥3∣K∣2−2.\theta(K)\ge\frac{3|K|}{2}-2.В началото това е вярно, защото всяка клика е едно ребро: θ(K2)=1\theta(K_2)=1. При сливане на две, три или четири клики стойността на θ\theta е сумата от старите стойности. От друга страна, при сливането върховете a,b,c,da,b,c,d от избрания C4C_4 вече се срещат в старите клики с припокриване: при четири слети клики има поне четири повторения на върхове, при три слети клики - поне три, а при две слети клики - поне две. Следователно размерът на новата клика е достатъчно по-малък от сумата на старите размери, за да се запази неравенството θ(K)≥3∣K∣/2−2\theta(K)\ge3|K|/2-2; в случаите с две или три клики дори получаваме запас. Ако графът е допълним до KnK_n, накрая алгоритъмът дава клика KnK_n. Тогава броят на началните ребра е поне θ(Kn)≥3n/2−2\theta(K_n)\ge3n/2-2. Понеже броят на ребрата е цяло число, получаваме долната оценка ⌈3n/2⌉−2\lceil3n/2\rceil-2. Заедно с конструкцията това доказва формулата, а при n=2022n=2022 отговорът е 30313031.
Отвори задачатаEvan Chen VONVON USAMO 2022/6Условие — източник