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

Evan Chen / USAMO Solution Notes

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

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

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

2008

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Да се докаже, че за всяко положително цяло число nn съществуват взаимно прости две по две цели числа k0,k1,…,knk_0,k_1,\ldots,k_n, всички строго по-големи от 11, такива че k0k1⋯kn−1k_0k_1\cdots k_n-1 е произведение на две последователни цели числа.
РешениеЩе построим една безкрайна редица, от която после вземаме първите n+1n+1 члена. Използваме тъждеството(x2+x+1)(x2−x+1)=x2(x2+1)+1.(x^2+x+1)(x^2-x+1)=x^2(x^2+1)+1.Поставяме x0=2x_0=2 и k0=x02+x0+1=7k_0=x_0^2+x_0+1=7. Ще дефинираме рекурсивно xmx_m и kmk_m така, чеk0k1⋯km=xm(xm+1)+1=xm2+xm+1.k_0k_1\cdots k_m=x_m(x_m+1)+1=x_m^2+x_m+1.Ако това е вярно за някое mm, поставямеkm+1=xm2−xm+1,xm+1=xm2.k_{m+1}=x_m^2-x_m+1,\qquad x_{m+1}=x_m^2.Тогава горното тъждество даваk0k1⋯kmkm+1=(xm2+xm+1)(xm2−xm+1)=k_0k_1\cdots k_mk_{m+1}=(x_m^2+x_m+1)(x_m^2-x_m+1)=xm2(xm2+1)+1=xm+1(xm+1+1)+1.x_m^2(x_m^2+1)+1=x_{m+1}(x_{m+1}+1)+1.Следователно за всяко mm имамеk0k1⋯km−1=xm(xm+1),k_0k_1\cdots k_m-1=x_m(x_m+1),което е произведение на две последователни цели числа. Остава да проверим взаимната простота. При построението xmx_m винаги е четно и поне 22, така че km+1=xm2−xm+1k_{m+1}=x_m^2-x_m+1 е нечетно и по-голямо от 11. Освен товаgcd⁡(k0k1⋯km,km+1)=\gcd(k_0k_1\cdots k_m,k_{m+1})=gcd⁡(xm2+xm+1,xm2−xm+1).\gcd(x_m^2+x_m+1,x_m^2-x_m+1).Разликата на двата аргумента е 2xm2x_m, затова този най-голям общ делител дели 2xm2x_m. Но km+1k_{m+1} е нечетно и е взаимно просто с xmx_m, понеже xm2−xm+1≡1(modxm)x_m^2-x_m+1\equiv1\pmod{x_m}. Следователно делителят е 11. Така всеки нов член е взаимно прост с произведението на предишните, което доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 2008/1Условие — източник

Задача 2

Пълен запис
Условие
Нека ABCABC е остроъгълен разностранен триъгълник, а M,N,PM,N,P са съответно средите на BC,CA,ABBC,CA,AB, като симетралите на ABAB и ACAC пресичат лъча AMAM съответно в точките DD и EE. Правите BDBD и CECE се пресичат в точка FF вътре в триъгълника ABCABC. Да се докаже, че точките A,N,F,PA,N,F,P лежат на една окръжност.
РешениеНека a=BCa=BC, b=CAb=CA, c=ABc=AB и работим с барицентрични координати спрямо ABCABC. Ще използваме стандартното означение SA=12(b2+c2−a2)S_A=\frac{1}{2}(b^2+c^2-a^2). Понеже DD лежи на медианата AMAM, имаме D=(t:1:1)D=(t:1:1) за някакво tt. Условието DA=DBDA=DB, тъй като DD е върху симетралата на ABAB, дава 0=b2(t−1)+(a2−c2),0=b^2(t-1)+(a^2-c^2), следователно D=(2SA:c2:c2).D=(2S_A:c^2:c^2). Аналогично E=(2SA:b2:b2).E=(2S_A:b^2:b^2). От пресичането на правите BDBD и CECE получаваме F=(2SA:b2:c2).F=(2S_A:b^2:c^2). Нека F′F' е образът на AA при централна симетрия с център FF, тоест FF е средата на AF′AF'. Сумата на барицентричните координати на FF е 2SA+b2+c2=2b2+2c2−a2.2S_A+b^2+c^2=2b^2+2c^2-a^2. Затова F′=2F−A=(−a2:2b2:2c2).F'=2F-A=(-a^2:2b^2:2c^2). Точката F′F' лежи на описаната окръжност на ABCABC, защото уравнението ѝ в барицентрични координати е a2yz+b2zx+c2xy=0,a^2yz+b^2zx+c^2xy=0, а координатите на F′F' го удовлетворяват. Сега при хомотетия с център AA и коефициент 12\frac12 описаната окръжност на ABCABC се превръща в окръжността през AA, средата PP на ABAB и средата NN на ACAC. Тъй като FF е средата на AF′AF', от F′∈(ABC)F'\in(ABC) следва F∈(APN)F\in(APN). Следователно A,N,F,PA,N,F,P лежат на една окръжност.ABCMNPDEF
Отвори задачатаEvan Chen VONVON USAMO 2008/2Условие — източник

Задача 3

Пълен запис
Условие
Нека nn е положително цяло число. Нека SnS_n е множеството от точките (x,y)(x,y) с цели координати, за които ∣x∣+∣y+12∣<n.|x|+|y+\frac{1}{2}|\lt{}n. Път е редица от различни точки (x1,y1),(x2,y2),…,(xℓ,yℓ)(x_1,y_1),(x_2,y_2),\ldots,(x_\ell,y_\ell) от SnS_n, такава че за всяко i=2,…,ℓi=2,\ldots,\ell разстоянието между (xi,yi)(x_i,y_i) и (xi−1,yi−1)(x_{i-1},y_{i-1}) е 11. Да се докаже, че точките от SnS_n не могат да бъдат разделени на по-малко от nn пътя.
РешениеЩе използваме оцветяване в два цвята. Разделяме фигурата SnS_n на горна и долна половина спрямо хоризонталната ос между редовете y=0y=0 и y=−1y=-1. В горната половина оцветяваме точките шахматно в синьо и червено така, че крайната точка (n−1,0)(n-1,0) да е синя, а долната половина оцветяваме като огледален образ на горната. При това оцветяване съседни точки почти винаги имат различни цветове. Единственото изключение е по хоризонталната ос на симетрия: там може да се появи ребро между две сини точки. Освен това сините точки са точно с 2n2n повече от червените. Да допуснем, че SnS_n е разделено на mm пътя. Разрязваме всеки път по всяко ребро, което свързва две сини точки. Такива ребра има само по оста на симетрия, и там има най-много nn възможни разреза. Следователно след разрязването получаваме най-много m+nm+n пътя. От друга страна, след тези разрези всеки получен път редува цветовете си, освен че може да съдържа двойки от две червени съседни точки. Във всеки такъв път броят на сините точки надвишава броя на червените с най-много 11. Понеже общо сините точки са с 2n2n повече от червените, трябва да има поне 2n2n пътя след разрязването. Значи m+n≥2n,m+n\ge2n, откъдето m≥nm\ge n. Това доказва твърдението.
Отвори задачатаEvan Chen VONVON USAMO 2008/3Условие — източник

Задача 4

Пълен запис
Условие
За кои цели числа n≥3n\ge3 може да се намери триангулация на правилен nn-ъгълник, съставена само от равнобедрени триъгълници? Тук триангулация означава разрязване чрез непресичащи се диагонали на триъгълници, чието обединение е целият многоъгълник.
РешениеОтговорът е: точно за числата n=2a(2b+1),n=2^a(2^b+1), където a,ba,b са неотрицателни цели числа, не и двете нули. Нека правилният многоъгълник е A1A2…AnA_1A_2\ldots A_n с индекси по модул nn. Ще наричаме страните AiAi+1A_iA_{i+1} къси. Всяка къса страна участва в точно един триъгълник от триангулацията. Ако nn е четно, единствените равнобедрени триъгълници, които могат да използват дадена къса страна AiAi+1A_iA_{i+1} без пресичане, са малките триъгълници с трети връх Ai−1A_{i-1} или Ai+2A_{i+2}. Следователно за n>4n\gt{}4 всички къси страни трябва да се групират по двойки в такива малки триъгълници; след премахването им остава правилен n/2n/2-ъгълник. Значи за четно n>4n\gt{}4 числото nn работи тогава и само тогава, когато n/2n/2 работи. Понеже n=4n=4 очевидно работи, това свежда четния случай до нечетния, като позволява произволен множител степен на 22. Нека сега n>1n\gt{}1 е нечетно. Поради паритет не всички къси страни могат да участват в малки триъгълници. Следователно поне една къса страна участва в голям равнобедрен триъгълник. Такъв голям триъгълник съдържа центъра на многоъгълника, затова в триангулацията може да има най-много един такъв триъгълник. След премахването му останалите къси страни трябва да се сдвоят чрез малки триъгълници, а същият аргумент се повтаря рекурсивно в двете получени половини. Това е възможно точно когато n−1n-1 е степен на 22, тоест когато n=2b+1n=2^b+1 за някое положително цяло число bb. Комбинирайки нечетния случай с многократното делене на две в четния случай, получаваме точно числата n=2a(2b+1)n=2^a(2^b+1) с a,b≥0a,b\ge0 и не едновременно нули. Конструкциите се получават, като обръщаме описаните редукции: за нечетното ядро вземаме един голям триъгълник и запълваме двете половини симетрично, а при умножаване по 22 добавяме външен слой от малки равнобедрени триъгълници.
Отвори задачатаEvan Chen VONVON USAMO 2008/4Условие — източник

Задача 5

Пълен запис
Условие
На дъската са записани три неотрицателни реални числа r1,r2,r3r_1,r_2,r_3. Известно е, че съществуват цели числа a1,a2,a3a_1,a_2,a_3, не всички нулеви, за които a1r1+a2r2+a3r3=0.a_1r_1+a_2r_2+a_3r_3=0. Разрешена е следната операция: избират се две числа x,yx,y на дъската с x≤yx\le y, изтрива се yy и на негово място се записва y−xy-x. Да се докаже, че след краен брой такива операции можем да получим поне една нула на дъската.
РешениеАко на дъската вече има нула, няма какво да доказваме. Затова предполагаме, че всички rir_i са положителни. Ще използваме дадената целочислена зависимост и ще намаляваме величинатаW=∣a1∣+∣a2∣+∣a3∣.W=|a_1|+|a_2|+|a_3|.Ако някой от коефициентите вече е нула, например a3=0a_3=0, тогава a1r1+a2r2=0a_1r_1+a_2r_2=0, така че r1/r2r_1/r_2 е рационално число. Пишем r1=uqr_1=uq и r2=vqr_2=vq с положителни цели u,vu,v и реално q>0q\gt{}0. Обикновеният алгоритъм на Евклид, приложен чрез разрешената операция върху r1r_1 и r2r_2, за краен брой стъпки дава нула. Остава да покажем, че докато всички коефициенти са ненулеви, можем да намалим WW. След пренареждане некаr1>r2>r3>0;r_1\gt{}r_2\gt{}r_3\gt{}0;ако две от числата са равни, една операция веднага дава нула. Умножавайки зависимостта по −1-1 при нужда, можем да считаме, че a1>0a_1\gt{}0. Първо нека поне един от a2,a3a_2,a_3 е положителен. Те не могат и двата да са положителни, защото тогава всички членове с положителни коефициенти не могат да се компенсират. Ако a2>0a_2\gt{}0, то a3<0a_3\lt{}0 и0=a1r1+a2r2+a3r3>a1r3+a3r3=(a1+a3)r3.0=a_1r_1+a_2r_2+a_3r_3\gt{}a_1r_3+a_3r_3=(a_1+a_3)r_3.Следователно a1+a3<0a_1+a_3\lt{}0, откъдето ∣a1+a3∣<∣a3∣|a_1+a_3|\lt{}|a_3|. Извършваме операцията r1↦r1−r3r_1\mapsto r_1-r_3. Новата зависимост еa1(r1−r3)+a2r2+(a1+a3)r3=0,a_1(r_1-r_3)+a_2r_2+(a_1+a_3)r_3=0,и сумата на абсолютните стойности на коефициентите намалява. Случаят a3>0a_3\gt{}0 е същият, като вместо това използваме операцията r1↦r1−r2r_1\mapsto r_1-r_2. Остава случаят a2<0a_2\lt{}0 и a3<0a_3\lt{}0. Ако ∣a1+a2∣<∣a2∣|a_1+a_2|\lt{}|a_2|, използваме операцията r1↦r1−r2r_1\mapsto r_1-r_2 и намаляваме WW; ако ∣a1+a3∣<∣a3∣|a_1+a_3|\lt{}|a_3|, използваме r1↦r1−r3r_1\mapsto r_1-r_3. Да допуснем, че нито едно от тези две неравенства не е вярно. Тогава от a2,a3<0a_2,a_3\lt{}0 следва, че a1+a2a_1+a_2 и a1+a3a_1+a_3 са неотрицателни, а дориa1+2a2≥0,a1+2a3≥0.a_1+2a_2\ge0,\qquad a_1+2a_3\ge0.Като съберем, получаваме a1+a2+a3≥0a_1+a_2+a_3\ge0. От друга страна, понеже a1>0a_1\gt{}0, a2<0a_2\lt{}0, a3<0a_3\lt{}0 и r1>r2>r3r_1\gt{}r_2\gt{}r_3, имаме0=a1r1+a2r2+a3r3>r2(a1+a2+a3),0=a_1r_1+a_2r_2+a_3r_3\gt{}r_2(a_1+a_2+a_3),което дава a1+a2+a3<0a_1+a_2+a_3\lt{}0. Това е противоречие. Следователно, докато няма нулев коефициент, можем с разрешена операция да получим нова ненулева целочислена зависимост с по-малка стойност на WW. Това не може да продължава безкрайно, защото WW е положително цяло число. След краен брой стъпки някой коефициент става нула, а тогава, както видяхме, алгоритъмът на Евклид довършва доказателството.
Отвори задачатаEvan Chen VONVON USAMO 2008/5Условие — източник

Задача 6

Пълен запис
Условие
На една математическа конференция всеки двама математици са или приятели, или непознати. По време на хранене всеки участник яде в една от две големи зали. Всеки математик настоява да бъде в зала, в която има четен брой негови приятели. Да се докаже, че броят на начините участниците да бъдат разпределени между двете зали е степен на 22, тоест има вида 2k2^k за някое положително цяло число kk.
РешениеРазглеждаме граф, чиито върхове са математиците, а ребрата свързват двойките приятели. Разпределение между двете зали е същото като оцветяване на върховете с два цвята. Нека върховете са 1,2,…,m1,2,\ldots,m и работим над полето F2\mathbb F_2. Ако viv_i е цветът на върха ii, условието за върха ii казва, че броят на съседите jj, за които vj=viv_j=v_i, е четен. Понеже над F2\mathbb F_2 индикаторът на равенството vj=viv_j=v_i е 1+vi+vj1+v_i+v_j, това условие може да се запише като линейно уравнение. Нека AA е матрицата, която извън диагонала има матрицата на съседство на графа, а на диагонала в ред ii има степента на върха ii по модул 22. Ако dd е векторът от тези диагонални елементи, всички добри оцветявания са точно решенията наAv=dAv=dнад F2\mathbb F_2. Следователно множеството от решения е или празно, или е транслация на ker⁡A\ker A, така че броят му е степен на 22. Остава само да докажем, че поне едно добро оцветяване винаги съществува. Ще го докажем с минимален контрапример. Нека GG е граф с най-малък брой върхове, за който добро оцветяване не съществува. Ако всички върхове имат четна степен, оцветяването, при което всички са в една и съща зала, е добро. Значи има връх uu с нечетна степен. Премахваме uu и сред неговите съседи обръщаме съседството: всяка двойка съседи на uu, която е била свързана, става несвързана, а всяка несвързана двойка става свързана. Получаваме по-малък граф, следователно той има добро оцветяване. Ще го продължим до добро оцветяване на GG. Сред съседите на uu броим колко са от първия и колко от втория цвят. Тъй като степента на uu е нечетна, точно един от тези два броя е четен. Даваме на uu цвета, за който броят на съседите с този цвят е четен. Тогава условието за uu е изпълнено. За връх, който не е съсед на uu, нищо не се променя. За съсед ww на uu промяната в паритета идва от обръщането на ребрата към другите съседи на uu със същия цвят като ww, а ако ww има цвета на uu, и от новия съсед uu. Изборът на цвета на uu прави тази обща промяна четна, така че условието за ww също остава изпълнено. Получихме добро оцветяване на GG, противоречие с минималността. Значи добро оцветяване винаги има. Понеже допълнителната размяна на двете зали също дава добро разпределение, броят е степен 2k2^k с положително kk.
Отвори задачатаEvan Chen VONVON USAMO 2008/6Условие — източник