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

Evan Chen / USA TST Solutions

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

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

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

2017

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
В спортна лига всеки отбор използва множество от най-много tt отличителни цвята. Множество SS от отбори се нарича цветово разпознаваемо, ако на всеки отбор в SS може да се присвои един от неговите отличителни цветове така, че никой отбор в SS да не получи цвят, който е отличителен за друг отбор от SS. За всички положителни цели числа nn и tt определете най-голямото цяло число g(n,t)g(n,t) със следното свойство: във всяка спортна лига, в която общо се срещат точно nn различни цвята, винаги може да се намери цветово разпознаваемо множество с поне g(n,t)g(n,t) отбора.
РешениеОтговорът еg(n,t)=⌈nt⌉.g(n,t)=\left\lceil\frac nt\right\rceil.Първо това е горна граница. Разделяме nn-те цвята на ⌈n/t⌉\left\lceil n/t\right\rceil групи, всяка с най-много tt цвята, и правим по един отбор за всяка група, чиито отличителни цветове са точно цветовете в тази група. В такава лига няма повече от ⌈n/t⌉\left\lceil n/t\right\rceil отбора, така че не може да се гарантира по-голямо цветово разпознаваемо множество. Остава да докажем, че толкова винаги може да се намери. Започваме с множеството SS от всички отбори. Докато съществува отбор, всички чиито отличителни цветове вече се срещат като отличителни цветове на други отбори от SS, изтриваме този отбор от SS. Това изтриване не премахва нито един цвят от общата колекция цветове, защото всеки негов цвят остава представен от някой друг отбор. Когато процесът спре, всички nn цвята още се срещат в оставащите отбори. Понеже всеки отбор има най-много tt отличителни цвята, остават поне ⌈n/t⌉\left\lceil n/t\right\rceil отбора. Ще видим, че оставащото множество SS е цветово разпознаваемо. За всеки отбор T∈ST\in S вече не е вярно, че всички негови цветове се споделят с други отбори в SS. Следователно TT има поне един отличителен цвят, който не е отличителен за никой друг отбор от SS. Присвояваме на всеки отбор такъв негов собствен цвят. Получаваме точно изискваното цветово разпознаваемо множество, с размер поне ⌈n/t⌉\left\lceil n/t\right\rceil.
Отвори задачатаEvan Chen VONVON TST 2017/1Условие — източник

Задача 3

Пълен запис
Условие
Нека P,Q∈R[x]P,Q\in\mathbb R[x] са взаимно прости неконстантни полиноми. Докажете, че съществуват най-много три реални числа λ\lambda, за които P+λQP+\lambda Q е квадрат на полином.
РешениеЩе докажем по-силно твърдение над C\mathbb C. Да предположим противното: има четири различни числа λ1,λ2,λ3,λ4∈C\lambda_1,\lambda_2,\lambda_3,\lambda_4\in\mathbb C и полиноми Ri∈C[x]R_i\in\mathbb C[x], за коитоP+λiQ=Ri2(i=1,2,3,4).P+\lambda_iQ=R_i^2\qquad (i=1,2,3,4).Можем да приемем, че deg⁡P≠deg⁡Q\deg P\ne\deg Q. Ако степените са равни, заменяме PP с P+cQP+cQ за подходяща константа cc; това само преименува параметъра λ\lambda и не променя взаимната простота. Диференцираме равенството и получавамеP′+λiQ′=2RiRi′.P'+\lambda_iQ'=2R_iR_i'.Умножаваме първоначалното равенство по Q′Q' и последното по QQ, след което изваждаме. ТакаQ′(P+λiQ)−Q(P′+λiQ′)=Q′P−QP′.Q'(P+\lambda_iQ)-Q(P'+\lambda_iQ')=Q'P-QP'.Лявата страна се дели на RiR_i, защото P+λiQ=Ri2P+\lambda_iQ=R_i^2 и P′+λiQ′P'+\lambda_iQ' се дели на RiR_i. СледователноRi∣Q′P−QP′R_i\mid Q'P-QP'за всяко ii. Полиномите RiR_i са два по два взаимно прости. Наистина, ако някой неконстантен полином дели и RiR_i, и RjR_j при i≠ji\ne j, той дели разликата(P+λiQ)−(P+λjQ)=(λi−λj)Q,(P+\lambda_iQ)-(P+\lambda_jQ)=(\lambda_i-\lambda_j)Q,а също дели P+λiQP+\lambda_iQ; оттук дели и PP, и QQ, което противоречи на взаимната простота. Значи произведението R1R2R3R4R_1R_2R_3R_4 дели Q′P−QP′Q'P-QP'. Ако d=max⁡(deg⁡P,deg⁡Q)d=\max(\deg P, \deg Q), понеже deg⁡P≠deg⁡Q\deg P\ne\deg Q, всеки полином P+λiQP+\lambda_iQ има степен dd. Такаdeg⁡(R1R2R3R4)=4⋅d2=2d.\deg(R_1R_2R_3R_4)=4\cdot\frac d2=2d.От друга странаdeg⁡(Q′P−QP′)≤deg⁡P+deg⁡Q−1<2d.\deg(Q'P-QP')\le \deg P+\deg Q-1\lt{}2d.Това е невъзможно, освен ако Q′P−QP′=0Q'P-QP'=0. Но тогава по правилото за производна на частно имаме (P/Q)′=0(P/Q)'=0, следователно P/QP/Q е константа, което противоречи на това, че PP и QQ са взаимно прости неконстантни полиноми. Противоречието доказва, че такива четири стойности на λ\lambda няма.
Отвори задачатаEvan Chen VONVON TST 2017/3Условие — източник

Задача 4

Пълен запис
Условие
Мамите на викторина. За всеки въпрос можете да погледнете отговорите на другите n>1n\gt{}1 участници, преди да запишете своя отговор. След като всички отговори бъдат предадени, водещият обявява верния отговор. Верен отговор носи 00 точки. Грешен отговор носи −2-2 точки за останалите участници, но само −1-1 точка за вас, понеже сте хакнали системата за оценяване. След обявяването на верния отговор водещият преминава към следващия въпрос. Докажете, че ако в някакъв момент водите с 2n−12^{n-1} точки, то със сигурност можете да завършите на първо място.
РешениеЩе докажем дори по-силното твърдение, че е достатъчен аванс 2n−2+12^{n-2}+1. Първо пренормираме точките спрямо вашия резултат. Това не променя въпроса кой е пред вас: можем да мислим, че при всеки въпрос участниците с верен отговор печелят 11 точка, участниците с отговора, който копирате и който се оказва грешен, губят 11 точка, а вашият резултат остава фиксиран. Кръговете, в които всички дават един и същ отговор, не са важни. Също така, ако копираният от вас отговор е верен, положението само се подобрява за вас; затова гледаме само кръговете, в които избрана от вас група губи 11 точка, а някаква друга група печели 11 точка. Ключовото наблюдение е следното. Ако в някой по-ранен кръг множеството SS от участници е спечелило точка, а в по-късен кръг всички участници от SS дават един и същ отговор, тогава можем да копираме този отговор. Ако той е грешен, всички от SS губят точка и ефектът на двата кръга за тях се занулява; ако е верен, положението за вас е още по-добро. Значи такъв по-ранен кръг може да бъде заличен от сметката. Поддържаме списък L\mathcal L от подмножества на множеството на другите nn участници. Първоначално списъкът е празен. Във всеки кръг действаме така. Ако има група участници SS, които са дали един и същ отговор, и S∈LS\in\mathcal L, копираме техния отговор и изтриваме SS от L\mathcal L. В този кръг не добавяме ново множество в списъка. Ако такава група няма, копираме отговор на група TT с възможно най-голям размер, като при възможност вземаме ∣T∣≥n/2|T|\ge n/2. Нека SS е множеството на участниците с верен отговор. Тогава SS е непресичащо се с TT, така че ∣S∣≤n/2|S|\le n/2, и добавяме SS в списъка L\mathcal L. По построение в L\mathcal L никога няма повторение: ако някое множество от списъка се появи като група с общ отговор, ние го изтриваме вместо да позволим то да бъде добавено отново. Затова резултатът на всеки участник е най-много броят множества от текущия списък, които го съдържат. Всички добавяни множества имат размер най-много n/2n/2. За фиксиран участник броят на подмножествата на {1,2,…,n}\{1,2,\ldots,n\} с размер най-много n/2n/2, които го съдържат, е най-много 2n−22^{n-2}. Следователно никой от останалите участници не може да натрупа преднина повече от 2n−22^{n-2} спрямо фиксирания ви резултат. Ако първоначално водите с 2n−2+12^{n-2}+1, вие неизбежно завършвате строго пред всички. Това доказва и исканото по-слабо твърдение с аванс 2n−12^{n-1}.
Отвори задачатаEvan Chen VONVON TST 2017/4Условие — източник

Задача 6

Пълен запис
Условие
Докажете, че съществуват безкрайно много тройки (a,b,p)(a,b,p) от цели числа, където pp е просто число и 0<a≤b<p0\lt{}a\le b\lt{}p, за които p5p^5 дели(a+b)p−ap−bp.(a+b)^p-a^p-b^p.
РешениеЩе използваме следното стандартно твърдение: за всяко просто число p≡1(mod3)p\equiv1\pmod3 съществуват цели числа a,ba,b с 0<a≤b<p0\lt{}a\le b\lt{}p, за коитоp2∣a2+ab+b2.p^2\mid a^2+ab+b^2.Например това следва от лемата на Туе, приложена към корен на x2+x+1≡0(modp2)x^2+x+1\equiv0\pmod{p^2}; еквивалентно, теорията на формата x2+xy+y2x^2+xy+y^2 дава представяне p2=a2+ab+b2p^2=a^2+ab+b^2. Сега ще докажем ключовата полиномиална делимост. Ако p≡1(mod3)p\equiv1\pmod3, тогаваp(x2+xy+y2)2∣(x+y)p−xp−ypp(x^2+xy+y^2)^2\mid (x+y)^p-x^p-y^pкато полиноми с цели коефициенти. Първо всички вътрешни биномиални коефициенти (pk)\binom pk се делят на pp, така че целият полином (x+y)p−xp−yp(x+y)^p-x^p-y^p се дели на pp. Остава да видим двойния множител x2+xy+y2x^2+xy+y^2. След хомогенизация е достатъчно да докажем, че(x2+x+1)2∣F(x),F(x)=(x+1)p−xp−1.(x^2+x+1)^2\mid F(x),\qquad F(x)=(x+1)^p-x^p-1.Нека ζ\zeta е примитивен трети корен на единицата. Понеже p≡1(mod3)p\equiv1\pmod3, имаме ζp=ζ\zeta^p=\zeta, а също 1+ζ=−ζ21+\zeta=-\zeta^2. ТогаваF(ζ)=(1+ζ)p−ζp−1=F(\zeta)=(1+\zeta)^p-\zeta^p-1=(−ζ2)p−ζ−1=−ζ2−ζ−1=0.(-\zeta^2)^p-\zeta-1=-\zeta^2-\zeta-1=0.Освен товаF′(x)=p(x+1)p−1−pxp−1,F'(x)=p(x+1)^{p-1}-px^{p-1},и при x=ζx=\zeta получаваме F′(ζ)=p−p=0F'(\zeta)=p-p=0, защото p−1p-1 се дели на 33. Значи ζ\zeta е двоен корен на FF, а същото важи и за спрегнатия корен ζ2\zeta^2. Следователно (x2+x+1)2(x^2+x+1)^2 дели F(x)F(x). Избираме произволно просто p≡1(mod3)p\equiv1\pmod3 и съответните a,ba,b от стандартното твърдение. Тогаваp(a2+ab+b2)2∣(a+b)p−ap−bp.p(a^2+ab+b^2)^2\mid (a+b)^p-a^p-b^p.Понеже p2∣a2+ab+b2p^2\mid a^2+ab+b^2, дясната страна се дели на p⋅p4=p5p\cdot p^4=p^5. Има безкрайно много прости числа p≡1(mod3)p\equiv1\pmod3, така че получаваме безкрайно много искани тройки.
Отвори задачатаEvan Chen VONVON TST 2017/6Условие — източник