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

Evan Chen / USAMO Solution Notes

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

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

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

2007

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека nn е положително цяло число. Дефинираме редица, като поставяме a1=na_1=n, а за всяко k>1k\gt{}1 избираме aka_k да бъде единственото цяло число в интервала 0≤ak≤k−10\le a_k\le k-1, за което a1+a2+⋯+aka_1+a_2+\cdots+a_k се дели на kk. Например при n=9n=9 получената редица започва с 9,1,2,0,3,3,3,…9,1,2,0,3,3,3,\ldots. Да се докаже, че за всяко nn редицата a1,a2,…a_1,a_2,\ldots е константна от някой член нататък.
РешениеЗа всяко kk поставямеbk=a1+a2+⋯+akk.b_k=\frac{a_1+a_2+\cdots+a_k}{k}.По условие bkb_k е неотрицателно цяло число. Ще докажем, че редицата (bk)(b_k) е невъзходяща. Наистина, понеже 0≤ak+1≤k0\le a_{k+1}\le k, имамеbk+1=kbk+ak+1k+1≤kbk+kk+1<bk+1.b_{k+1}=\frac{kb_k+a_{k+1}}{k+1}\le \frac{kb_k+k}{k+1}\lt{}b_k+1.Лявата страна е цяло число, следователно bk+1≤bkb_{k+1}\le b_k. Така (bk)(b_k) е невъзходяща редица от неотрицателни цели числа и затова е константна от някой член нататък. Нека bN=bN+1=⋯=bb_N=b_{N+1}=\cdots=b. Тогава за всяко k≥N+1k\ge N+1 получавамеak=kbk−(k−1)bk−1=kb−(k−1)b=b.a_k=kb_k-(k-1)b_{k-1}=kb-(k-1)b=b.Тази формула показва не само стабилизиране, а и точната стойност на всички достатъчно късни членове. Следователно и редицата a1,a2,…a_1,a_2,\ldots е константна от някой член нататък, както се искаше.
Отвори задачатаEvan Chen VONVON USAMO 2007/1Условие — източник

Задача 2

Пълен запис
Условие
Възможно ли е всички решетъчни точки в R2\mathbb R^2 да бъдат покрити от безкрайно семейство кръгове, чиито вътрешности са две по две непересичащи се, ако радиусът на всеки кръг е поне 55?
РешениеОтговорът е не. Да допуснем противното. Избираме кръг OO, който не пресича никой от дадените кръгове, и го разширяваме, докато стане максимален с това свойство. Нека радиусът му е rr. Тъй като всички решетъчни точки са покрити от дадените кръгове, нашият празен кръг OO не съдържа решетъчна точка. А всяка точка от равнината е на разстояние най-много 1/21/\sqrt2 от някоя решетъчна точка, следователно трябва да е r≤1/2r\le 1/\sqrt2. От максималността на OO той трябва да се допира до поне три от дадените кръгове; иначе центърът му може леко да се премести и радиусът да се увеличи. Нека три такива кръга имат центрове A,B,CA,B,C. Сред трите ъгъла около центъра на OO има поне един, който е най-много 120∘120^\circ; без ограничение нека това е ∠AOB\angle AOB. Нека радиусите на O,A,BO,A,B са съответно r,a,br,a,b. Тогава a,b≥5a,b\ge5, а понеже вътрешностите на дадените кръгове са непересичащи се, имаме AB≥a+bAB\ge a+b. От косинусовата теорема и ∠AOB≤120∘\angle AOB\le120^\circ следва(a+b)2≤AB2≤(a+r)2+(b+r)2+(a+r)(b+r).(a+b)^2\le AB^2\le (a+r)^2+(b+r)^2+(a+r)(b+r).След опростяване това дава12r2≥(a−3r)(b−3r).12r^2\ge (a-3r)(b-3r).Но от a,b≥5a,b\ge5 получаваме(a−3r)(b−3r)≥(5−3r)2.(a-3r)(b-3r)\ge (5-3r)^2.За 0≤r≤1/20\le r\le 1/\sqrt2 неравенството 12r2≥(5−3r)212r^2\ge(5-3r)^2 е невъзможно. Следователно всъщност r>1/2r\gt{}1/\sqrt2. Това обаче означава, че OO съдържа решетъчна точка, защото центърът му е на разстояние най-много 1/21/\sqrt2 от такава точка. Получаваме непокрита решетъчна точка, противоречие.
Отвори задачатаEvan Chen VONVON USAMO 2007/2Условие — източник

Задача 3

Пълен запис
Условие
Нека SS е множество с n2+n−1n^2+n-1 елемента. Всички nn-елементни подмножества на SS са разделени в два класа. Да се докаже, че има поне nn две по две непресичащи се множества, които принадлежат на един и същ клас.
РешениеЩе наричаме едно (n+1)(n+1)-елементно множество полезно, ако сред неговите nn-елементни подмножества има представители и от двата класа. Вземаме максимална фамилия от две по две непресичащи се полезни множества и нека броят им е pp. Нека TT е множеството от всички елементи, които не лежат в избраните полезни множества. Първо ще покажем, че всички nn-елементни подмножества на TT са от един и същ клас. Ако имаше две такива подмножества RR и R′R' от различни класове, бихме могли да заменяме елементите на RR един по един, докато получим R′R'. В някоя стъпка цветът трябва да се смени; тогава обединението на двете съседни nn-елементни множества има най-много n+1n+1 елемента и съдържа nn-елементни подмножества от двата класа. Допълвайки при нужда до точно n+1n+1 елемента в TT, получаваме полезно множество в TT, което противоречи на максималността. Следователно всички nn-елементни подмножества на TT са, без ограничение, от първия клас. От всяко избрано полезно множество можем да вземем по едно nn-елементно подмножество от първия клас, а от TT можем да извадим още ⌊∣T∣/n⌋\left\lfloor |T|/n\right\rfloor две по две непресичащи се nn-елементни подмножества от същия клас. Ако p≥np\ge n, вече сме готови. Затова нека p<np\lt{}n. Тогава∣T∣=n2+n−1−p(n+1),|T|=n^2+n-1-p(n+1),и следователно⌊∣T∣n⌋≥n−p.\left\lfloor\frac{|T|}{n}\right\rfloor\ge n-p.Така общо получаваме поне p+(n−p)=np+(n-p)=n две по две непресичащи се nn-елементни подмножества от един и същ клас, както трябваше да се докаже.
Отвори задачатаEvan Chen VONVON USAMO 2007/3Условие — източник

Задача 4

Пълен запис
Условие
Животно с nn клетки е свързана фигура, съставена от nn еднакви квадратни клетки, тоест полимино с nn клетки. Динозавър е животно с поне 20072007 клетки. Наричаме динозавър примитивен, ако клетките му не могат да бъдат разделени на два или повече динозавъра. Да се намери, с доказателство, максималният възможен брой клетки в примитивен динозавър.
РешениеОтговорът е 80258025. Ще използваме графа на съседство на клетките и ще вземем негово покриващо дърво TT. Всеки връх на това дърво има степен най-много 44, защото една квадратна клетка има най-много четири странични съседи. Ако дървото можеше да се раздели на две или повече свързани части, всяка с поне 20072007 върха, това би дало съответно разделяне на динозавъра. Затова е достатъчно да разсъждаваме върху TT. Ще докажем, че в TT има връх vv, такъв че след изтриването му всички компоненти имат най-много 20062006 върха. Да допуснем противното. Тогава за всеки връх vv има компонент на T−vT-v с поне 20072007 върха; насочваме от vv реброто към съседа, който лежи в такъв голям компонент. Получаваме ориентация, в която от всеки връх излиза една стрелка. Ако следваме стрелките, понеже дървото е крайно, в някакъв момент ще се получи повторение. Единственият възможен цикъл в дърво с такава ориентация е двуцикъл по едно ребро, да кажем u↔vu\leftrightarrow v. Но тогава компонентът на T−uT-u, който съдържа vv, има поне 20072007 върха, и компонентът на T−vT-v, който съдържа uu, също има поне 20072007 върха. Тези два компонента са точно двете части, получени при премахване на реброто uvuv, и са свързани. Това разделя динозавъра на два динозавъра, противоречие с примитивността. Следователно такъв връх vv съществува. След изтриването на vv има най-много 44 компонента и всяка има най-много 20062006 върха. Значи общият брой клетки е най-много1+4⋅2006=8025.1+4\cdot2006=8025.Остава конструкция. Вземаме една централна клетка и към всяка от четирите нейни страни залепяме права лента от 20062006 клетки. Получаваме динозавър с 1+4⋅2006=80251+4\cdot2006=8025 клетки. Всяка свързана част с поне 20072007 клетки трябва да съдържа централната клетка, защото всяка от четирите ленти без центъра има само 20062006 клетки. Следователно не могат да се отделят два динозавъра, понеже и двата биха трябвало да съдържат централната клетка. Конструкцията е примитивна и границата е точна.
Отвори задачатаEvan Chen VONVON USAMO 2007/4Условие — източник

Задача 5

Пълен запис
Условие
Да се докаже, че за всяко неотрицателно цяло число nn числото 77n+17^{7^n}+1 е произведение на поне 2n+32n+3 прости числа, които не е задължително да са различни, т.е. броят се с повторения.
РешениеЩе докажем твърдението с индукция по nn. При n=0n=0 имаме 770+1=8=2⋅2⋅27^{7^0}+1=8=2\cdot2\cdot2, така че твърдението е вярно. Да предположим, че 77n+17^{7^n}+1 вече има поне 2n+32n+3 прости множителя. ПоставямеX=77n.X=7^{7^n}.Тогава77n+1+1=X7+1=7^{7^{n+1}}+1=X^7+1=(X+1)(X6−X5+X4−X3+X2−X+1).(X+1)(X^6-X^5+X^4-X^3+X^2-X+1).Първият множител X+1X+1 е точно предишното число. Достатъчно е да покажем, че вторият множител е съставен, защото тогава при преминаване от nn към n+1n+1 се добавят поне два нови прости множителя. НекаQ=X6−X5+X4−X3+X2−X+1.Q=X^6-X^5+X^4-X^3+X^2-X+1.Имаме тъждествотоQ=(X+1)6−7X(X2+X+1)2.Q=(X+1)^6-7X(X^2+X+1)^2.Понеже X=77nX=7^{7^n}, числото 7X=77n+17X=7^{7^n+1} е квадрат, защото 7n+17^n+1 е четно. СледователноQ=(X+1)6−(7(7n+1)/2(X2+X+1))2Q=(X+1)^6-\left(7^{(7^n+1)/2}(X^2+X+1)\right)^2е разлика на два квадрата. За X≥7X\ge7 двата получени положителни множителя са по-големи от 11, затова QQ е съставно число. Така всеки индукционен преход добавя поне два прости множителя, а от трите множителя при n=0n=0 получаваме поне 2n+32n+3 прости множителя за всяко nn.
Отвори задачатаEvan Chen VONVON USAMO 2007/5Условие — източник

Задача 6

Пълен запис
Условие
Нека ABCABC е остроъгълен триъгълник, а ω\omega, SS и RR са съответно неговата вписана окръжност, описана окръжност и радиусът на описаната окръжност. Окръжността ωA\omega_A се допира вътрешно до SS в AA и външно до ω\omega. Окръжността SAS_A се допира вътрешно до SS в AA и вътрешно до ω\omega. Нека PAP_A и QAQ_A са съответно центровете на ωA\omega_A и SAS_A. Аналогично дефинираме точките PB,QB,PC,QCP_B,Q_B,P_C,Q_C. Да се докаже, че 8PAQA⋅PBQB⋅PCQC≤R3,8P_AQ_A\cdot P_BQ_B\cdot P_CQ_C\le R^3, като равенство има тогава и само тогава, когато ABCABC е равностранен.
РешениеНека a=BCa=BC, b=CAb=CA, c=ABc=AB, s=a+b+c2s=\frac{a+b+c}{2}, KK е лицето, rr е радиусът на вписаната окръжност и ha=2Kah_a=\frac{2K}{a} е височината от AA. Ще пресметнем дължината PAQAP_AQ_A. Правим инверсия с център AA и радиус s−as-a, а след това отражение спрямо ъглополовящата на ∠BAC\angle BAC. Ще означаваме образите след тези две операции със звезда и после с плюс. Инверсията е избрана така, че вписаната окръжност остава неподвижна. Окръжността ωA\omega_A, която минава през AA, се превръща в права, успоредна на образа на SS и перпендикулярна на правата PAQAP_AQ_A; освен това тази права е допирателна към ω\omega. Понеже PAQAP_AQ_A е правата AOAO, а изогоналният образ на AOAO е височината от AA, след отражението тази допирателна е точно BCBC. Следователно образът P+P^+ на второто пресичане на PAQAP_AQ_A с ωA\omega_A е петата на височината от AA към BCBC. По същия начин образът Q+Q^+ на второто пресичане на PAQAP_AQ_A с SAS_A лежи на правата AP+AP^+ и е такъв, че P+Q+=2rP^+Q^+=2r. От инверсията получавамеAPA=12AP=(s−a)22AP+=(s−a)22haAP_A=\frac12 AP=\frac{(s-a)^2}{2AP^+}=\frac{(s-a)^2}{2h_a}иAQA=12AQ=(s−a)22AQ+=(s−a)22(ha−2r).AQ_A=\frac12 AQ=\frac{(s-a)^2}{2AQ^+}=\frac{(s-a)^2}{2(h_a-2r)}.ЗатоваPAQA=12(s−a)2(1ha−2r−1ha).P_AQ_A=\frac12(s-a)^2\left(\frac1{h_a-2r}-\frac1{h_a}\right).Понеже ha=2Kah_a=\frac{2K}{a} и r=Ksr=\frac Ks, това се опростява доPAQA=a2(s−a)4K.P_AQ_A=\frac{a^2(s-a)}{4K}.Аналогично,PBQB=b2(s−b)4K,PCQC=c2(s−c)4K.P_BQ_B=\frac{b^2(s-b)}{4K},\qquad P_CQ_C=\frac{c^2(s-c)}{4K}.Следователно желаното неравенство е еквивалентно наa2b2c2(s−a)(s−b)(s−c)≤8(RK)3.a^2b^2c^2(s-a)(s-b)(s-c)\le 8(RK)^3.Използваме abc=4RKabc=4RK и формулата на Херон (s−a)(s−b)(s−c)=rK(s-a)(s-b)(s-c)=rK. Получаваме, че последното неравенство е еквивалентно на2r≤R.2r\le R.Това е точно неравенството на Ойлер за триъгълник, защото IO2=R(R−2r)≥0IO^2=R(R-2r)\ge0, където II и OO са центровете на вписаната и описаната окръжност. Равенство има тогава и само тогава, когато I=OI=O, което за остроъгълен триъгълник означава, че триъгълникът е равностранен. Така получаваме и търсеното условие за равенство.ABCOIPₐQₐHₐ
Отвори задачатаEvan Chen VONVON USAMO 2007/6Условие — източник