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

Evan Chen / USAMO Solution Notes

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

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

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

2023

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
В остроъгълен триъгълник ABCABC нека MM е средата на BCBC. Нека PP е петата на перпендикуляра от CC към AMAM. Да предположим, че описаната окръжност на триъгълника ABPABP пресича правата BCBC в две различни точки BB и QQ. Нека NN е средата на AQAQ. Да се докаже, че NB=NCNB=NC.
РешениеНека DD е петата на височината от AA към BCBC. Ще докажем, че QQ е образът на DD при централна симетрия спрямо MM. Понеже ∠ADC=∠APC=90∘\angle ADC=\angle APC=90^\circ, четириъгълникът ADPCADPC е вписан. Прилагаме степен на точката MM спрямо окръжностите (ADPC)(ADPC) и (ABPQ)(ABPQ), като дължините по правата BCBC се вземат насочено: MB⋅MQ=MA⋅MP=MC⋅MD.MB\cdot MQ=MA\cdot MP=MC\cdot MD. Тъй като MM е среда на BCBC, имаме MB=MCMB=MC, следователно MQ=MDMQ=MD с правилна посока по правата BCBC. Значи MM е среда на DQDQ. Сега в триъгълника ADQADQ точките MM и NN са среди съответно на DQDQ и AQAQ, затова MN∥ADMN\parallel AD. Но AD⊥BCAD\perp BC, следователно MN⊥BCMN\perp BC. Понеже MM е средата на BCBC, правата през MM, перпендикулярна на BCBC, е симетралата на BCBC. Точката NN лежи на нея, откъдето NB=NCNB=NC.ABCMDPQN
Отвори задачатаEvan Chen VONVON USAMO 2023/1Условие — източник

Задача 2

Пълен запис
Условие
Да се реши в положителните реални числа функционалното уравнениеf(xy+f(x))=xf(y)+2f(xy+f(x))=xf(y)+2за всички положителни реални числа xx и yy.
РешениеОтговорът еf(x)=x+1.f(x)=x+1.Проверката е непосредствена: ако f(t)=t+1f(t)=t+1, тогаваf(xy+f(x))=f(xy+x+1)=xy+x+2=xf(y)+2.f(xy+f(x))=f(xy+x+1)=xy+x+2=xf(y)+2.Нека P(x,y)P(x,y) означава даденото равенство. Първо ще докажем, че ff не намалява. Да допуснем противното: нека a>b>0a\gt{}b\gt{}0, но f(a)<f(b)f(a)\lt{}f(b). Избирамеy=f(b)−f(a)a−b>0.y=\frac{f(b)-f(a)}{a-b}\gt{}0.Тогава ay+f(a)=by+f(b)ay+f(a)=by+f(b). От P(a,y)P(a,y) и P(b,y)P(b,y) левите страни са равни, следователноaf(y)+2=bf(y)+2,af(y)+2=bf(y)+2,което е невъзможно, понеже a≠ba\ne b и f(y)>0f(y)\gt{}0. Значи ff е ненамаляваща. Поставяме c=f(1)>0c=f(1)\gt{}0. От P(1,y)P(1,y) получавамеf(y+c)=f(y)+2f(y+c)=f(y)+2за всяко y>0y\gt{}0. Следователно стойностите на ff върху аритметичните прогресии със стъпка cc растат с точно 22. Заедно с ненамаляването това дава линейна оценка с ограничена грешка:f(x)=Kx+O(1)(x→∞),f(x)=Kx+O(1)\qquad(x\to\infty),където K=2/cK=2/c. Наистина, ако mc≤x≤(m+1)cmc\le x\le (m+1)c, то f(mc)≤f(x)≤f((m+1)c)f(mc)\le f(x)\le f((m+1)c), а двете крайни стойности се различават само с 22. По-точно същото разсъждение може да се приложи след преместване с достатъчно голямо кратно на cc, така че грешката в оценката остава ограничена с абсолютна константа, която не зависи от xx. Тази равномерност е важна: тя позволява да сравняваме главните линейни членове в уравнението, без неизвестната ограничена част да влияе след деление на xx. Сега фиксираме произволно y>0y\gt{}0 и пускаме x→∞x\to\infty в P(x,y)P(x,y). От вече получената оценка имамеf(xy+f(x))=K(xy+f(x))+O(1)=f(xy+f(x))=K(xy+f(x))+O(1)=Kxy+K2x+O(1),Kxy+K^2x+O(1),докато дясната страна е xf(y)+2xf(y)+2. Следователноx(Ky+K2−f(y))=O(1).x\bigl(Ky+K^2-f(y)\bigr)=O(1).Тъй като yy е фиксирано, това е възможно при неограничено големи xx само акоf(y)=Ky+K2.f(y)=Ky+K^2.Значи ff е линейна на цялата положителна полуос. Остава да намерим KK. Замествайки f(t)=Kt+K2f(t)=Kt+K^2 в първоначалното уравнение, получавамеK(xy+Kx+K2)+K2=x(Ky+K2)+2.K(xy+Kx+K^2)+K^2=x(Ky+K^2)+2.След съкращаване оставаK3+K2=2.K^3+K^2=2.Понеже K>0K\gt{}0, а функцията K2(K+1)K^2(K+1) е строго растяща за K>0K\gt{}0, единственото решение е K=1K=1. Следователно f(y)=y+1f(y)=y+1 за всяко y>0y\gt{}0, което вече проверихме.
Отвори задачатаEvan Chen VONVON USAMO 2023/2Условие — източник

Задача 3

Пълен запис
Условие
Разглеждаме дъска n×nn\times n от единични квадратчета, където nn е нечетно положително цяло число. Казваме, че колекция C\mathcal C от еднакви домина е максимална конфигурация, подравнена по мрежата, ако C\mathcal C се състои от n2−12\frac{n^2-1}{2} домина, всяко от които покрива точно две съседни квадратчета и домината не се застъпват; тогава C\mathcal C покрива всички квадратчета освен едно. Позволено е да плъзнем, без да завъртаме, едно домино така, че то да покрие непокритото квадратче; получава се нова максимална конфигурация с друго непокрито квадратче. Нека k(C)k(\mathcal C) е броят на различните максимални конфигурации, които могат да се получат от C\mathcal C чрез последователни плъзгания на домина. Да се намерят всички възможни стойности на k(C)k(\mathcal C) като функция на nn.
РешениеОтговорът еk(C)∈{1,2,…,(n−12)2}∪{(n+12)2}.k(\mathcal C)\in \left\{1,2,\ldots,\left(\frac{n-1}{2}\right)^2\right\}\cup\left\{\left(\frac{n+1}{2}\right)^2\right\}.Номерираме квадратчетата с координати (x,y)(x,y), където 1≤x,y≤n1\le x,y\le n. Наричаме квадратче специално, ако е празното квадратче или ако двете му координати имат същата четност като координатите на празното квадратче. При всяко допустимо плъзгане празното квадратче се премества от едно специално квадратче в друго, а паритетният клас на специалните квадратчета не се променя. Построяваме насочен граф GG върху специалните квадратчета. Ако едно домино лежи върху специално квадратче ss, насочваме ребро от ss към специалното квадратче, към което това домино сочи; празното квадратче няма изходящо ребро. В свързаната компонента TT, която съдържа празното квадратче, всички стрелки сочат към него. Плъзгането на домино точно обръща едно ребро по пътя в тази компонента. Следователно достижимите конфигурации са точно изборите на връх на TT, който да бъде новото празно квадратче, и затоваk(C)=∣V(T)∣.k(\mathcal C)=|V(T)|.Остава да разберем какви размери може да има TT. Ако специалните квадратчета са с две нечетни координати, те са (n+12)2\left(\frac{n+1}{2}\right)^2. В този случай всеки цикъл в ненасочения граф GG огражда нечетен брой квадратчета от дъската: това следва от теоремата на Пик, приложена към центровете на квадратчетата по и вътре в цикъла, заедно с паритетното броене на домината по границата. Затова компонентата на празното квадратче е дърво, освен ако е затворена от цикъл. Ако тя не е цялото множество от специални квадратчета, такъв ограждащ цикъл я отделя от най-външния ред и най-външната колона, откъдето ∣V(T)∣≤(n−12)2|V(T)|\le \left(\frac{n-1}{2}\right)^2. Ако обаче TT е обхващащо дърво, получаваме единствената голяма стойност (n+12)2\left(\frac{n+1}{2}\right)^2; тя се реализира от змиевидна конфигурация, която минава през всички специални квадратчета. Ако специалните квадратчета са с две четни координати, те са (n−12)2\left(\frac{n-1}{2}\right)^2. Същото графово описание дава k(C)=∣V(T)∣k(\mathcal C)=|V(T)|, този път без възможност за по-голяма стойност. За всяко 1≤k≤(n−12)21\le k\le \left(\frac{n-1}{2}\right)^2 вземаме змиевиден път от kk специални квадратчета и ориентираме съответните домина към избраното празно квадратче; останалите специални квадратчета се затварят в малки локални блокове, които не са достижими от празното квадратче. Това дава конфигурация с точно kk достижими положения. Така получаваме всички стойности от първия интервал и единствената допълнителна голяма стойност, както беше твърдяно.
Отвори задачатаEvan Chen VONVON USAMO 2023/3Условие — източник

Задача 4

Пълен запис
Условие
Фиксирани са положителни цели числа aa и NN, а на дъска са написани NN положителни цели числа. Алиса и Боб играят следната игра. На ход Алиса трябва да замени някое число nn на дъската с n+an+a, а на ход Боб трябва да замени някое четно число nn на дъската с n/2n/2. Алиса започва и двамата се редуват. Ако на свой ход Боб няма валиден ход, играта приключва. След като разглежда NN-те числа на дъската, Боб разбира, че независимо какви ходове прави Алиса, той може да наложи играта в крайна сметка да приключи. Да се докаже, че всъщност за това aa и тези NN числа играта гарантирано приключва независимо от ходовете и на Алиса, и на Боб.
РешениеНека ν2(t)\nu_2(t) означава показателя на 22 в разлагането на положителното цяло число tt. При N=1N=1 няма какво да се доказва: във всеки момент всеки играч има най-много един възможен ход, така че няма избор на стратегия. Нека оттук нататък N≥2N\ge2, а SS е множеството от числата на дъската, броени с кратности. Първо, ако ν2(x)<ν2(a)\nu_2(x)\lt{}\nu_2(a) за всяко x∈Sx\in S, играта приключва независимо от ходовете. Наистина, при такова xx имаме ν2(x+a)=ν2(x)\nu_2(x+a)=\nu_2(x), така че ходът на Алиса не променя този показател. Всеки ход на Боб, когато е възможен, намалява сумата на всички показатели ν2\nu_2 точно с 11. Играта приключва точно когато всички тези показатели станат нула, така че в този случай броят на ходовете на Боб е предварително определен. Сега да допуснем, че на дъската има число xx с ν2(x)≥ν2(a)\nu_2(x)\ge\nu_2(a). Тогава Алиса може да направи играта безкрайна. Следим първото число на дъската и пак го означаваме с xx. Ако ν2(x)=ν2(a)\nu_2(x)=\nu_2(a), Алиса играе върху първото число; тогава новото първо число е x+ax+a и има ν2(x+a)>ν2(a)\nu_2(x+a)\gt{}\nu_2(a). Ако пък ν2(x)>ν2(a)\nu_2(x)\gt{}\nu_2(a), Алиса играе върху някое друго число, което е възможно понеже N≥2N\ge2. С двустъпкова индукция получаваме, че непосредствено преди всеки ход на Боб е изпълнено ν2(x)>ν2(a)\nu_2(x)\gt{}\nu_2(a), а непосредствено след всеки ход на Боб е изпълнено ν2(x)≥ν2(a)\nu_2(x)\ge\nu_2(a). Значи Боб никога не остава без валиден ход, защото първото число винаги е четно преди неговия ход. Но по условие Боб може да наложи край независимо от ходовете на Алиса. Следователно този втори случай е невъзможен, така че първоначално ν2(x)<ν2(a)\nu_2(x)\lt{}\nu_2(a) за всички числа xx на дъската. По първата част играта тогава приключва независимо от ходовете и на двамата играчи.
Отвори задачатаEvan Chen VONVON USAMO 2023/4Условие — източник

Задача 5

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число. Да наречем разполагане на числата 1,2,…,n21,2,\ldots,n^2 в таблица n×nn\times n валидно по редове, ако числата във всеки ред могат да се пренаредят така, че да образуват аритметична прогресия. Аналогично, да го наречем валидно по стълбове, ако числата във всеки стълб могат да се пренаредят така, че да образуват аритметична прогресия. За кои стойности на nn е вярно, че всяко валидно по редове разполагане може да се превърне във валидно по стълбове чрез пренареждане на числата във всеки ред?
РешениеОтговорът е: точно за простите nn. Първо нека n=pn=p е просто. В аритметична прогресия с pp члена остатъците по модул pp са или всички различни, ако разликата не се дели на pp, или всички са еднакви, ако разликата се дели на pp. Да разгледаме кратните на pp в дадена валидна по редове таблица. Във всеки ред има или точно едно такова число, или точно pp такива числа. Понеже общо кратните на pp са pp, има два случая. Ако всички кратни на pp са в един ред, тогава всеки ред се състои от числата с един и същ остатък по модул pp. Следователно можем да пренаредим числата във всеки ред така, че kk-тият стълб да съдържа точно числата от (k−1)p+1(k-1)p+1 до kpkp, които образуват аритметична прогресия. Ако кратните на pp са в различни редове, тогава всеки ред съдържа всеки остатък по модул pp точно по веднъж. Пренареждаме числата във всеки ред така, че kk-тият стълб да съдържа всички числа, които дават остатък kk по модул pp (с остатък 00 за последния стълб). Тези числа образуват аритметична прогресия с разлика pp. Значи при просто nn желаното винаги е възможно. Остава да покажем, че при съставно nn свойството не е вярно. Нека pp е прост делител на nn. Построяваме валидна по редове таблица така: първият ред съдържа числата 1,2,…,n1,2,\ldots,n; следващите pp реда съдържат числата от n+1n+1 до np+nnp+n, разбити на аритметични прогресии с разлика pp; останалите редове съдържат оставащите числа в естествения им ред. Така всеки ред е аритметична прогресия след евентуално пренареждане. Да допуснем, че чрез пренареждане във всеки ред сме получили валидна по стълбове таблица. Всеки стълб тогава съдържа аритметична прогресия от nn члена, чийто най-малък член е в интервала [1,n][1,n], а най-големият е в интервала [n2−n+1,n2][n^2-n+1,n^2]: това следва от числото в първия ред и числото в последния ред на съответния стълб. Тези два крайни члена трябва да са сравними по модул n−1n-1. Разглеждаме стълба, който съдържа числото 22. В него най-малкият член е точно 22, защото числото 11 е в същия ред и не може да е в същия стълб. Единственото число в интервала [n2−n+1,n2][n^2-n+1,n^2], което е сравнимо с 22 по модул n−1n-1, е n2−n+2n^2-n+2. Следователно най-големият член на този стълб е n2−n+2n^2-n+2, а общата разлика на прогресията е ((n2−n+2)−2)/(n−1)=n((n^2-n+2)-2)/(n-1)=n. Значи същият стълб трябва да съдържа и числата n+2n+2 и 2n+22n+2. Но в построената таблица тези две числа лежат в един и същ ред: понеже pp дели nn, те имат един и същ остатък по модул pp, а следващите pp реда бяха точно прогресии с разлика pp. Невъзможно е две числа от един ред да попаднат в един и същ стълб след пренареждане само вътре в редовете. Получихме противоречие, така че при съставно nn исканото свойство не може да важи.
Отвори задачатаEvan Chen VONVON USAMO 2023/5Условие — източник

Задача 6

Пълен запис
Условие
Нека ABCABC е триъгълник с инцентър II и ексцентрове IaI_a, IbI_b, IcI_c съответно срещу върховете AA, BB и CC. Дадена е произволна точка DD върху описаната окръжност на △ABC\triangle ABC, която не лежи върху нито една от правите IIaII_a, IbIcI_bI_c или BCBC. Описаните окръжности на △DIIa\triangle DII_a и △DIbIc\triangle DI_bI_c се пресичат в две различни точки DD и FF. Ако E=DF∩BCE=DF\cap BC, да се докаже, че ∠BAD=∠EAC\angle BAD=\angle EAC.
РешениеНека MM е средата на малката дъга BCBC на описаната окръжност на ABCABC, а PP е втората пресечна точка на окръжностите (DIIa)(DII_a) и (ABC)(ABC). Понеже II и IaI_a лежат на правата AMAM, от теоремата за радикалните оси следва, че правите AMAM, DPDP и BCBC се пресичат в една точка; да я означим с KK. Нека E0=PM∩BCE_0=PM\cap BC. Първо ще докажем, че ∠BAD=∠E0AC\angle BAD=\angle E_0AC, тоест че правите ADAD и AE0AE_0 са изогонални спрямо ъгъла при AA. По лемата за изстрелването четириъгълникът AKE0PAKE_0P е вписан. Следователно∠KAE0=∠KPE0=∠DPM=∠DAM.\angle KAE_0=\angle KPE_0=\angle DPM=\angle DAM.Тъй като K,A,MK,A,M са колинеарни, това е точно равенството ∠BAD=∠E0AC\angle BAD=\angle E_0AC. Остава да покажем, че E0E_0 съвпада с дадената точка EE. Ще сравним степени към двете окръжности. Построяваме успоредник IE0IaXIE_0I_aX. От стандартното равенство за дъговата среда MM имаме MI2=ME0⋅MPMI^2=ME_0\cdot MP. Получаваме∠XIaI=∠IaIE0=∠MIE0=∠MPI=∠XPI,\angle XI_aI=\angle I_aIE_0=\angle MIE_0=\angle MPI=\angle XPI,така че XX лежи на окръжността (DIIa)(DII_a). Освен товаE0X⋅E0P=2E0M⋅E0P=2E0B⋅E0C.E_0X\cdot E_0P=2E_0M\cdot E_0P=2E_0B\cdot E_0C.Значи степента на E0E_0 спрямо (DIIa)(DII_a) е 2E0B⋅E0C2E_0B\cdot E_0C. Същият аргумент, приложен към окръжността (DIbIc)(DI_bI_c), дава същата степен на E0E_0 спрямо нея. Следователно E0E_0 лежи на радикалната ос на двете окръжности, тоест на правата DFDF. Понеже E0E_0 лежи и на BCBC, получаваме E0=DF∩BC=EE_0=DF\cap BC=E. От първата част следва ∠BAD=∠EAC\angle BAD=\angle EAC, както се искаше.
Отвори задачатаEvan Chen VONVON USAMO 2023/6Условие — източник