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

Evan Chen / USA TSTST Solutions

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

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

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

2016

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

Открити липси за попълване от източника

  • 2016 · 11-12: липсва задача 2

11-12

4 задачи

Задача 1

Пълен запис
Условие
Нека A=A(x,y)A=A(x,y) и B=B(x,y)B=B(x,y) са полиноми на две променливи с реални коефициенти. Да предположим, че A(x,y)/B(x,y)A(x,y)/B(x,y) е полином по xx за безбройно много стойности на yy и е полином по yy за безбройно много стойности на xx. Докажете, че BB дели AA, т.е. съществува полином CC с реални коефициенти, за койтоA=B⋅C.A=B\cdot C.
РешениеТова е приложение на алгоритъма за деление, но трябва да внимаваме със специализациите. Първо ще докажем, че A/BA/B може да се запише като полином по xx, чиито коефициенти са рационални функции по yy. Работим в пръстена (R(y))[x](\mathbb R(y))[x], тоест разглеждаме полиноми по xx с коефициенти от полето R(y)\mathbb R(y). По алгоритъма за деление имамеA=QB+R,Q,R∈(R(y))[x],A=QB+R,\qquad Q,R\in(\mathbb R(y))[x],където deg⁡xR<deg⁡xB\deg_x R\lt{}\deg_x B. Твърдим, че R≡0R\equiv0. По условие за безбройно много стойности y0y_0 полиномът B(x,y0)B(x,y_0) дели A(x,y0)A(x,y_0) в R[x]\mathbb R[x]. За всички такива y0y_0, освен крайно много изключения, специализацията е допустима за коефициентите на Q,RQ,R и степенното неравенствоdeg⁡xR(x,y0)<deg⁡xB(x,y0)\deg_x R(x,y_0)\lt{}\deg_x B(x,y_0)се запазва. Но от A=QB+RA=QB+R следва, че B(x,y0)B(x,y_0) дели R(x,y0)R(x,y_0). Това е възможно при горното степенно неравенство само ако R(x,y0)≡0R(x,y_0)\equiv0. Така получаваме безбройно много стойности y0y_0, за които всеки коефициент на RR се занулява. Следователно всички тези рационални функции са нулеви, т.е. R≡0R\equiv0. ЗначиAB=Q(x,y)\frac AB=Q(x,y)като полином по xx с рационални функции по yy. След умножение с общ знаменател можем да запишемAB=F(x,y)M(y),\frac AB=\frac{F(x,y)}{M(y)},където F∈R[x,y]F\in\mathbb R[x,y] и M∈R[y]M\in\mathbb R[y]. Повтаряйки същия аргумент, но с разменени роли на xx и yy, получаваме и представянеAB=G(x,y)N(x),\frac AB=\frac{G(x,y)}{N(x)},където G∈R[x,y]G\in\mathbb R[x,y] и N∈R[x]N\in\mathbb R[x]. Съкращаваме дробите така, че gcd⁡(F,M)=1\gcd(F,M)=1 и gcd⁡(G,N)=1\gcd(G,N)=1 в R[x,y]\mathbb R[x,y]. Освен това gcd⁡(M,N)=1\gcd(M,N)=1, защото единият полином зависи само от yy, а другият само от xx. От равенствотоF(x,y)N(x)=G(x,y)M(y)F(x,y)N(x)=G(x,y)M(y)следва, че MM дели F⋅NF\cdot N. Понеже MM е взаимнопрост с FF и с NN, получаваме, че MM е константен полином. Следователно A/BA/B всъщност е полином от R[x,y]\mathbb R[x,y], което точно означава, че BB дели AA.
Отвори задачатаEvan Chen VONVON TSTST 2016/1Условие — източник

Задача 3

Пълен запис
Условие
Съществува ли неконстантен полином Q(x)Q(x) с цели коефициенти със следното свойство: за всяко положително цяло число n>2n\gt{}2 числатаQ(0),Q(1),Q(2),…,Q(n−1)Q(0),Q(1),Q(2),\ldots,Q(n-1)да дават най-много 0.499n0.499n различни остатъка по модул nn?
РешениеДа, такъв полином съществува. Ще покажем, чеQ(x)=420(x2−1)2Q(x)=420(x^2-1)^2работи. Достатъчно е да проверим случая n=4n=4 и случая, когато n=pn=p е нечетно просто число. Наистина, ако свойството е вярно по модул някой делител dd на nn, то всеки остатък по модул dd идва от най-много n/dn/d остатъка по модул nn, така че броят на остатъците по модул nn е най-много 0.499n0.499n. Всяко n>2n\gt{}2 има делител 44 или нечетен прост делител. При n=4n=4 е тривиално, понеже 420≡0(mod4)420\equiv0\pmod4. Нека сега pp е нечетно просто число. Ако pp дели 420420, всички стойности са еднакви по модул pp, така че няма какво да се доказва. Затова приемаме p≥11p\ge11 и разглеждамеF(x)=(x2−1)2,F(x)=(x^2-1)^2,защото умножаването по ненулевата константа 420420 не променя броя на стойностите по модул pp. Първо ще използваме следния факт: за поне 12(p−3)\frac12(p-3) стойности на aa числото 1−a21-a^2 е ненулев квадратичен остатък по модул pp. Действително, ако k≠0k\ne0 и k2≠−1k^2\ne-1, тогаваa=1−k21+k2a=\frac{1-k^2}{1+k^2}дава1−a2=4k2(1+k2)2,1-a^2=\frac{4k^2}{(1+k^2)^2},което е квадрат. Различните допустими стойности на k2k^2 дават различни aa, а те са поне 12(p−3)\frac12(p-3). Стойностите на FF са квадратични остатъци, така че образът му е подмножество на най-много 12(p+1)\frac12(p+1) остатъка. Ще покажем, че много от тези квадратични остатъци всъщност липсват. Наричаме остатък tt полезен, ако нито 1−t1-t, нито 1+t1+t е квадратичен остатък по модул pp. Ако tt е полезен, тогава t2t^2 не е стойност на FF, защото равенството (x2−1)2=t2(x^2-1)^2=t^2 би дало x2=1+tx^2=1+t или x2=1−tx^2=1-t. Нека χ(u)=(up)\chi(u)=\left(\frac{u}{p}\right) е символът на Лежандр и нека NN е броят на полезните остатъци tt. Сумирайки по всички остатъци tt по модул pp, получаваме оценкатаN≥14∑t(1−χ(1−t))(1−χ(1+t))−1=14(p+∑tχ(1−t2))−1.\begin{align*} N&\ge \frac14\sum_t\left(1-\chi(1-t)\right)\left(1-\chi(1+t)\right)-1\\ &=\frac14\left(p+\sum_t\chi(1-t^2)\right)-1. \end{align*}В последната сума има поне 12(p−3)\frac12(p-3) члена, равни на +1+1, двата члена при t=±1t=\pm1 са 00, а останалите са най-малко −1-1. СледователноN≥14(p−5).N\ge\frac14(p-5).Понеже полезните остатъци tt и −t-t могат да изключат един и същ квадрат t2t^2, от образа на FF липсват поне N/2N/2 квадратични остатъка. Значи броят на стойностите на FF по модул pp е най-много12(p+1)−12N≤38(p+3).\frac12(p+1)-\frac12N\le\frac38(p+3).За p≥11p\ge11 имаме 38(p+3)<0.499p\frac38(p+3)\lt{}0.499p. Следователно Q(x)=420(x2−1)2Q(x)=420(x^2-1)^2 удовлетворява условието за всяко n>2n\gt{}2.
Отвори задачатаEvan Chen VONVON TSTST 2016/3Условие — източник

Задача 4

Пълен запис
Условие
Докажете, че ако nn и kk са положителни цели числа, за които φk(n)=1\varphi^k(n)=1, то n≤3kn\le3^k. Тук φk\varphi^k означава kk последователни приложения на функцията на Ойлер.
РешениеОсновната идея е да следим колко степени на 22 неизбежно ще се появят при многократно прилагане на φ\varphi. Дефинираме адитивна тежест ww върху положителните цели числа чрезw(ab)=w(a)+w(b),w(2)=1,w(ab)=w(a)+w(b),\qquad w(2)=1,и за всяко нечетно просто число pp полагамеw(p)=w(p−1).w(p)=w(p-1).Тази дефиниция е коректна, защото при p>2p\gt{}2 числото p−1p-1 има само прости делители, по-малки от pp, така че можем да дефинираме ww индуктивно по простите числа. Нека n=∏pepn=\prod p^{e_p}. От формулатаφ(n)=∏p∣npep−1(p−1)\varphi(n)=\prod_{p\mid n}p^{e_p-1}(p-1)следва, че ако nn е четно, тогава w(φ(n))=w(n)−1w(\varphi(n))=w(n)-1, а ако nn е нечетно и n>1n\gt{}1, тогава w(φ(n))=w(n)w(\varphi(n))=w(n). Следователно всяко приложение на φ\varphi намалява ww с най-много 11. Понеже w(1)=0w(1)=0 и φk(n)=1\varphi^k(n)=1, непременноk≥w(n).k\ge w(n).Остава да свържем w(n)w(n) с размера на nn. Ще докажем, чеw(q)≥log⁡3qw(q)\ge\log_3 qза всяко просто число qq. За q=2q=2 това е ясно, защото w(2)=1>log⁡32w(2)=1\gt{}\log_3 2. Нека q>2q\gt{}2 и да използваме силна индукция. Тогаваw(q)=w(q−1)=w(2)+w(q−12)≥1+log⁡3(q−12).w(q)=w(q-1)=w(2)+w\left(\frac{q-1}{2}\right)\ge1+\log_3\left(\frac{q-1}{2}\right).А понеже q≥3q\ge3, имаме1+log⁡3(q−12)=log⁡3(3(q−1)2)≥log⁡3q.1+\log_3\left(\frac{q-1}{2}\right)=\log_3\left(\frac{3(q-1)}{2}\right)\ge\log_3 q.Така неравенството е доказано за простите числа, а от адитивността следва за всяко nn:w(n)≥log⁡3n.w(n)\ge\log_3 n.Комбинирайки това с k≥w(n)k\ge w(n), получаваме k≥log⁡3nk\ge\log_3 n, т.е. n≤3kn\le3^k.
Отвори задачатаEvan Chen VONVON TSTST 2016/4Условие — източник

Задача 5

Пълен запис
Условие
В координатната равнина са дадени краен брой стени, които са непресичащи се отсечки, никоя от които не е успоредна на някоя от координатните оси. Булдозер започва от произволна точка и се движи в посока на положителната xx-ос. Всеки път, когато удари стена, той завива под прав ъгъл спрямо пътя си, в посока от стената навън, и продължава да се движи. Така булдозерът винаги се движи успоредно на координатните оси. Докажете, че е невъзможно булдозерът да удари и двете страни на всяка стена.
РешениеЩе казваме, че стена vv е над стена ww, ако някоя точка от vv се намира точно над някоя точка от ww. Тази релация е антисиметрична, понеже стените не се пресичат. Ключовото твърдение е, че съществува най-ниска стена, тоест стена, която не е над никоя друга стена. Да допуснем противното. Тогава получаваме насочен цикъл с дължина n≥3n\ge3: можем да построим точки Pi,QiP_i,Q_i за i=1,2,…,ni=1,2,\ldots,n (индексите се вземат по модул nn), така че QiQ_i да е точно над Pi+1P_{i+1} за всяко ii, отсечката QiPi+1Q_iP_{i+1} да не пресича вътрешността на никоя стена, а всяка отсечка PiQiP_iQ_i да лежи върху стена. Получаваме начупена линия с 2n2n върха, която няма самопресичания. Нека QiPi+1Q_iP_{i+1} е най-лявата вертикална отсечка от тази начупена линия, а QjPj+1Q_jP_{j+1} е най-дясната вертикална отсечка. Самата начупена линия дава път от Pi+1P_{i+1} до QjQ_j, както и път от Pj+1P_{j+1} до QiQ_i. Понеже тези два пътя трябва да преминат от лявата вертикална отсечка към дясната и обратно, те неизбежно се пресичат. Това противоречи на липсата на самопресичания и доказва съществуването на най-ниска стена. По същия начин съществува и най-висока стена. Ако след някакъв момент булдозерът се движи нагоре безкрайно, той никога не може да удари долната страна на най-ниската стена. Ако след някакъв момент се движи надолу безкрайно, той никога не може да удари горната страна на най-високата стена. Остава само да отбележим, че хоризонтален последен лъч се покрива със същия аргумент след размяна на ролите на координатните оси: тогава съществуват най-лява и най-дясна стена, и булдозерът пропуска съответната им странична страна. Ако пък движението приключи с последен удар преди да бъдат ударени всички страни, твърдението е вече ясно. Следователно в никой случай не може да бъдат ударени и двете страни на всяка стена.
Отвори задачатаEvan Chen VONVON TSTST 2016/5Условие — източник