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

Evan Chen / USA TST Solutions

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

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

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

2014

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

11-12

5 задачи

Задача 2

Пълен запис
Условие
Нека a1,a2,a3,…a_1,a_2,a_3,\ldots е редица от цели числа със свойството, че средното аритметично на всяка група от последователни нейни членове е точен квадрат. По-точно, за всички положителни цели числа nn и kk числотоan+an+1+⋯+an+k−1k\frac{a_n+a_{n+1}+\cdots+a_{n+k-1}}{k}е квадрат на цяло число. Докажете, че редицата е константна, тоест всички aia_i са равни на един и същ точен квадрат.
РешениеНека νp(n)\nu_p(n) означава най-големия показател, с който простото число pp дели nn. Ще докажем следното по-силно твърдение. Твърдение. Нека (an)(a_n) е редица от цели числа и нека pp е просто число. Да предположим, че средното аритметично на всяка последователна група от членове с дължина най-много pp е точен квадрат. Тогава νp(ai)\nu_p(a_i) не зависи от ii. Ако това твърдение е вярно за всяко просто pp, то всички членове aia_i имат еднакви pp-адични валуации за всяко pp. Понеже при k=1k=1 всеки aia_i сам по себе си е точен квадрат, получаваме, че всички aia_i са един и същ точен квадрат. Значи остава да докажем твърдението. Доказателството е с индукция по най-малката стойност на νp(ai)\nu_p(a_i). Тази стойност е четна, защото всяко aia_i е квадрат. Първо ще използваме две леми. Първа лема. Ако j≡k(modp)j\equiv k\pmod p, то aj≡ak(modp)a_j\equiv a_k\pmod p. Действително, от условието за групи с дължина pp имамеp∣aj+aj+1+⋯+aj+p−1p\mid a_j+a_{j+1}+\cdots+a_{j+p-1}иp∣aj+1+aj+2+⋯+aj+p.p\mid a_{j+1}+a_{j+2}+\cdots+a_{j+p}.След изваждане получаваме aj≡aj+p(modp)a_j\equiv a_{j+p}\pmod p, а оттук следва твърдението за всички индекси, еднакви по модул pp. Втора лема. Ако някой член aia_i се дели на pp, то всички членове се делят на pp. За p=2p=2 това е непосредствено от първата лема, така че нека p≥3p\ge3. След преместване на индексите можем да приемем, че a1≡0(modp)a_1\equiv0\pmod p. НекаSn=a1+a2+⋯+an≡a2+a3+⋯+an(modp).S_n=a_1+a_2+\cdots+a_n\equiv a_2+a_3+\cdots+a_n\pmod p.Ще наричаме число kk с 2≤k<p2\le k\lt{}p пивот, ако 1−k−11-k^{-1} е квадратичен неостатък по модул pp. Твърдим, че за всеки пивот kk е изпълнено Sk≡0(modp)S_k\equiv0\pmod p. Ако не е така, то числатаa1+a2+⋯+akkиa2+a3+⋯+akk−1\frac{a_1+a_2+\cdots+a_k}{k}\qquad\text{и}\qquad\frac{a_2+a_3+\cdots+a_k}{k-1}са ненулеви квадратични остатъци по модул pp, защото са точни квадрати като цели числа. Делението им дава, чеk−1k=1−k−1\frac{k-1}{k}=1-k^{-1}е квадратичен остатък, противоречие с избора на пивот. Сега ще намерим две последователни нулеви частични суми. Ако 22 е пивот, вземаме m=1m=1, защото S1≡0S_1\equiv0 и току-що доказахме S2≡0S_2\equiv0. Ако 22 не е пивот, тогава пивотите са точно p−12\frac{p-1}{2} на брой: по един за всеки квадратичен неостатък, различен от 00 и 11. Всички те лежат сред числата 3,4,…,p−13,4,\ldots,p-1, така че по принципа на Дирихле два от тях са последователни. Следователно съществува mm сSm≡Sm+1≡0(modp),S_m\equiv S_{m+1}\equiv0\pmod p,откъдето p∣am+1p\mid a_{m+1}. Повтаряйки същата процедура, започвайки от am+1a_{m+1} вместо от a1a_1, получаваме, чеa2m+1,a3m+1,a4m+1,…a_{2m+1},a_{3m+1},a_{4m+1},\ldotsсъщо се делят на pp. Тъй като m<pm\lt{}p, числата 1,m+1,2m+1,…1,m+1,2m+1,\ldots обхождат всички остатъци по модул pp. Първата лема тогава показва, че всеки член aia_i се дели на pp. Втората лема е доказана. Втората лема дава базата на индукцията. Ако най-малката pp-адична валуация е 00, нито един член не може да се дели на pp, иначе всички биха се делили; следователно всички валуации са 00. Нека сега всички aia_i се делят на pp. Понеже са квадрати, те всъщност се делят на p2p^2. Освен това всяко допустимо средно аритметично също е квадрат; когато то се дели на pp, то се дели на p2p^2. Значи след замянатаai⟼aip2a_i\longmapsto \frac{a_i}{p^2}получаваме нова редица, която пак удовлетворява условието на твърдението за всички дължини най-много pp. По индукционното предположение νp(ai/p2)\nu_p(a_i/p^2) е независимо от ii, а оттук и νp(ai)\nu_p(a_i) е независимо от ii. Това доказва твърдението за произволно просто pp и завършва решението. Забележката в доказателството е важна: условието за дължини най-много pp не може просто да се махне в индукционната стъпка, защото средното на p2p^2 члена, всички делящи се на pp, не е задължително да се дели на pp.
Отвори задачатаEvan Chen VONVON TST 2014/2Условие — източник

Задача 3

Пълен запис
Условие
Нека nn е четно положително цяло число и нека GG е прост граф с nn върха и точно n24\frac{n^2}{4} ребра. Неподредена двойка различни върхове {x,y}\{x,y\} ще наричаме приятелска, ако двата върха имат общ съсед, тоест ако съществува връх zz, за който xzxz и yzyz са ребра. Докажете, че в GG има поне2(n/22)2\binom{n/2}{2}приятелски двойки върхове.
РешениеЩе използваме графовата форма на парадокса на приятелството: средно вашите приятели имат поне толкова приятели, колкото имате вие. Лема. За връх vv нека a(v)a(v) е средната степен на съседите на vv, като при изолиран връх полагаме a(v)=0a(v)=0. Тогава∑va(v)≥∑vdeg⁡v=2#E,\sum_v a(v)\ge \sum_v \deg v=2\#E,където #E\#E е броят на ребрата. Доказателство. Пренебрегваме изолираните върхове, защото те нямат принос. Тогава∑va(v)=∑v∑w∼vdeg⁡wdeg⁡v=∑v∑w∼vdeg⁡wdeg⁡v=∑ребра vw(deg⁡wdeg⁡v+deg⁡vdeg⁡w)≥∑ребра vw2=2#E.\begin{align*} \sum_v a(v) &=\sum_v\frac{\sum_{w\sim v}\deg w}{\deg v}\\ &=\sum_v\sum_{w\sim v}\frac{\deg w}{\deg v}\\ &=\sum_{\text{ребра }vw}\left(\frac{\deg w}{\deg v}+\frac{\deg v}{\deg w}\right)\\ &\ge\sum_{\text{ребра }vw}2=2\#E. \end{align*}Последното неравенство е неравенството между средно аритметично и средно геометрично, приложено към двете положителни числа deg⁡w/deg⁡v\deg w/\deg v и deg⁡v/deg⁡w\deg v/\deg w. Следствие. За връх vv нека m(v)m(v) е максималната степен на съсед на vv, като отново полагаме m(v)=0m(v)=0, ако vv е изолиран. Тогава∑vm(v)≥2#E.\sum_v m(v)\ge2\#E.Наистина, за всеки връх имаме m(v)≥a(v)m(v)\ge a(v). Сега броим приятелските двойки. Фиксираме връх vv и избираме негов съсед ww с максимална възможна степен m(v)m(v). Всеки друг съсед на ww образува с vv приятелска двойка, защото общият им съсед е ww. Така върхът vv участва в поне m(v)−1m(v)-1 приятелски двойки; за изолиран връх това е само тривиална отрицателна долна оценка, която не вреди. Когато сумираме по всички върхове, всяка действителна приятелска двойка има два края и затова участва точно два пъти в общия брой инцидентности. Следователно броят на приятелските двойки е поне12∑v(m(v)−1)≥#E−12#V.\frac12\sum_v(m(v)-1)\ge \#E-\frac12\#V.Тук #V=n\#V=n и по условие #E=n2/4\#E=n^2/4, следователно получаваме#E−12#V=n24−n2=n(n−2)4=2(n/22),\#E-\frac12\#V=\frac{n^2}{4}-\frac n2=\frac{n(n-2)}4=2\binom{n/2}{2},което е точно исканата оценка. Равенство се достига например за пълния двуделен граф Kn/2,n/2K_{n/2,n/2}.
Отвори задачатаEvan Chen VONVON TST 2014/3Условие — източник

Задача 4

Пълен запис
Условие
Нека nn е четно положително цяло число и нека c1,c2,…,cn−1c_1,c_2,\ldots,c_{n-1} са реални числа, за които∑i=1n−1∣ci−1∣<1.\sum_{i=1}^{n-1}|c_i-1|\lt{}1.Докажете, че полиномът2xn−cn−1xn−1+cn−2xn−2−⋯−c1x+22x^n-c_{n-1}x^{n-1}+c_{n-2}x^{n-2}-\cdots-c_1x+2няма реални корени.
РешениеЩе докажем по-силното твърдение, че даденият полином е положителен за всяко реално xx. Първо, от∑i=1n−1∣ci−1∣<1\sum_{i=1}^{n-1}|c_i-1|\lt{}1следва ∣ci−1∣<1|c_i-1|\lt{}1 за всяко ii, тоест ci>0c_i\gt{}0. Ако x≤0x\le0, тогава nn е четно и всеки член в средната редуваща се сума е неотрицателен: коефициентът пред xix^i има знак (−1)i(-1)^i, а самото xix^i също има знак (−1)i(-1)^i при x<0x\lt{}0. Следователно целият полином е положителен за x≤0x\le0. Остава случаят x>0x\gt{}0. Пишемci=1−di,c_i=1-d_i,така че∑i=1n−1∣di∣<1.\sum_{i=1}^{n-1}|d_i|\lt{}1.Нека P(x)P(x) е даденият полином. Понеже nn е четно, имамеP(x)=2xn+2+∑i=1n−1(−1)i(1−di)xi=(xn+1+∑i=0n(−1)ixi)−∑i=1n−1(−1)idixi=xn+1+xn+1+1x+1−∑i=1n−1(−1)idixi.\begin{align*} P(x) &=2x^n+2+\sum_{i=1}^{n-1}(-1)^i(1-d_i)x^i\\ &=\left(x^n+1+\sum_{i=0}^n(-1)^ix^i\right)-\sum_{i=1}^{n-1}(-1)^id_ix^i\\ &=x^n+1+\frac{x^{n+1}+1}{x+1}-\sum_{i=1}^{n-1}(-1)^id_ix^i. \end{align*}Затова е достатъчно да докажемxn+1>∑i=1n−1∣di∣xi,x^n+1\gt{}\sum_{i=1}^{n-1}|d_i|x^i,защото добавката xn+1+1x+1\frac{x^{n+1}+1}{x+1} е положителна. Но за x>0x\gt{}0 и всяко 1≤i≤n−11\le i\le n-1 е вярноxn+1>xi.x^n+1\gt{}x^i.Наистина, ако 0<x≤10\lt{}x\le1, дясната страна е най-много 11, а лявата е по-голяма от 11; ако x>1x\gt{}1, тогава xn>xix^n\gt{}x^i. Умножаваме тези оценки с неотрицателните числа ∣di∣|d_i| и сумираме. Получаваме∑i=1n−1∣di∣xi<\sum_{i=1}^{n-1}|d_i|x^i\lt{}(∑i=1n−1∣di∣)(xn+1)<xn+1.\left(\sum_{i=1}^{n-1}|d_i|\right)(x^n+1)\lt{}x^n+1.Следователно P(x)>0P(x)\gt{}0 и за x>0x\gt{}0. Полиномът е положителен за всяко реално xx, така че няма реални корени.
Отвори задачатаEvan Chen VONVON TST 2014/4Условие — източник

Задача 5

Пълен запис
Условие
Нека ABCDABCD е вписан четириъгълник, а E,F,G,HE,F,G,H са съответно средите на AB,BC,CD,DAAB,BC,CD,DA. Нека W,X,Y,ZW,X,Y,Z са ортоцентровете съответно на триъгълниците AHEAHE, BEFBEF, CFGCFG и DGHDGH. Докажете, че четириъгълниците ABCDABCD и WXYZWXYZ имат равни лица.
РешениеЩе използваме комплексни координати. Чрез директна подобност можем да приемем, че описаната окръжност на ABCDABCD е единичната окръжност с център 00. Нека комплексните координати на точките A,B,C,DA,B,C,D са съответно a,b,c,da,b,c,d, а тези на W,X,Y,ZW,X,Y,Z са w,x,y,zw,x,y,z. Първо ще намерим ww. В триъгълника с върхове D,A,BD,A,B, лежащи върху единичната окръжност, ортоцентърът има координатаd+a+b.d+a+b.От друга страна, EE и HH са средите на ABAB и ADAD, затова триъгълникът AHEAHE е хомотетичен на DABDAB с център AA и коефициент 12\frac12. Следователно неговият ортоцентър е образът на ортоцентъра на DABDAB при тази хомотетия, тоестw=a+12((d+a+b)−a)=12(2a+b+d).w=a+\frac12\big((d+a+b)-a\big)=\frac12(2a+b+d).По същия начин получаваме цикличноw=12(2a+b+d),x=12(2b+c+a),y=12(2c+d+b),z=12(2d+a+c).\begin{align*} w&=\frac12(2a+b+d),\\ x&=\frac12(2b+c+a),\\ y&=\frac12(2c+d+b),\\ z&=\frac12(2d+a+c). \end{align*}Оттукw−y=a−c,x−z=b−d.w-y=a-c,\qquad x-z=b-d.С други думи, диагоналите на WXYZWXYZ са равни като вектори, с евентуално сменена посока, на диагоналите на ABCDABCD. Лицето на произволен четириъгълник е половината от абсолютната стойност на векторното произведение на неговите диагонали. Понеже двете двойки диагонали имат същите дължини и същия насочен ъгъл помежду си, получаваме[WXYZ]=[ABCD].[WXYZ]=[ABCD].Това доказва твърдението.
Отвори задачатаEvan Chen VONVON TST 2014/5Условие — източник

Задача 6

Пълен запис
Условие
За просто число pp подмножество SS от остатъци по модул pp се нарича безсумна мултипликативна подгрупа на Fp\mathbb F_p, ако са изпълнени следните две условия: - съществува ненулев остатък α\alpha по модул pp, такъв чеS={1,α1,α2,…}S=\{1,\alpha^1,\alpha^2,\ldots\}където всички елементи се разглеждат по модул pp; - не съществуват a,b,c∈Sa,b,c\in S, не непременно различни, такива чеa+b≡c(modp).a+b\equiv c\pmod p.Докажете, че за всяко цяло число NN съществуват просто число pp и безсумна мултипликативна подгрупа SS на Fp\mathbb F_p, за които ∣S∣≥N|S|\ge N.
РешениеПърво доказваме обща лема за полиноми. Лема. Ако f,g∈Z[X]f,g\in\mathbb Z[X] са взаимнопрости неконстантни полиноми, то за всички достатъчно големи прости числа pp те нямат общ корен по модул pp. Доказателство. По теоремата на Безу, след евентуално умножение с общ знаменател, съществуват полиноми A(X),B(X)∈Z[X]A(X),B(X)\in\mathbb Z[X] и ненулево цяло число cc, за коитоA(X)f(X)+B(X)g(X)=c.A(X)f(X)+B(X)g(X)=c.Ако rr е общ корен на ff и gg по модул pp, след заместване X=rX=r получаваме p∣cp\mid c. Това е възможно само за крайно много прости числа pp, което доказва лемата. Сега даваме конструкцията. Избираме цяло число n≥Nn\ge N, за което 3∤n3\nmid n. По теоремата на Дирихле има произволно големи прости числа p≡1(modn)p\equiv1\pmod n. Ще изберем такова pp достатъчно голямо. Тъй като Fp×\mathbb F_p^\times е циклична група с ред p−1p-1, в нея има примитивен nn-ти корен на единицата; нека това бъде α\alpha. ПоставямеS={1,α,α2,…,αn−1}.S=\{1,\alpha,\alpha^2,\ldots,\alpha^{n-1}\}.Тогава SS е мултипликативна подгрупа и ∣S∣=n≥N|S|=n\ge N. Остава да покажем, че при достатъчно голям избор на pp множеството SS е безсумно. Да допуснем противното. Ако a+b≡c(modp)a+b\equiv c\pmod p за някакви a,b,c∈Sa,b,c\in S, делим на aa и получаваме1+αk≡αm(modp)1+\alpha^k\equiv\alpha^m\pmod pза подходящи цели числа kk и mm. Оттук X=αkX=\alpha^k е общ корен по модул pp на двата полинома(X+1)n−1иXn−1.(X+1)^n-1\qquad\text{и}\qquad X^n-1.Ще проверим, че тези два полинома са взаимнопрости в Z[X]\mathbb Z[X], когато 3∤n3\nmid n. Достатъчно е да видим, че нямат общ комплексен корен. Ако ω\omega е такъв корен, тоωn=1и(1+ω)n=1.\omega^n=1\qquad\text{и}\qquad(1+\omega)^n=1.Следователно ∣ω∣=1|\omega|=1 и ∣1+ω∣=1|1+\omega|=1. Единствените комплексни числа с тези две свойства саω=−12±32i,\omega=-\frac12\pm\frac{\sqrt3}{2}i,които са примитивни трети корени на единицата. Но тогава ωn=1\omega^n=1 би наложило 3∣n3\mid n, противоречие. Значи полиномите (X+1)n−1(X+1)^n-1 и Xn−1X^n-1 са взаимнопрости. По лемата те не могат да имат общ корен по модул всички достатъчно големи прости числа pp. Избираме нашето просто число p≡1(modn)p\equiv1\pmod n по-голямо от крайното множество изключения. Тогава такова сравнение 1+αk≡αm(modp)1+\alpha^k\equiv\alpha^m\pmod p е невъзможно, следователно SS е безсумна мултипликативна подгрупа на Fp\mathbb F_p с ∣S∣=n≥N|S|=n\ge N.
Отвори задачатаEvan Chen VONVON TST 2014/6Условие — източник