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

Evan Chen / USA TSTST Solutions

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

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

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

2014

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Нека ←\leftarrow означава клавиша със стрелка наляво на стандартна клавиатура. Ако отворим текстов редактор и натиснем клавишитеab←cd←←e←←f,\texttt{ab}\leftarrow\texttt{cd}\leftarrow\leftarrow\texttt{e}\leftarrow\leftarrow\texttt{f},получаваме текста faecdb\texttt{faecdb}. Казваме, че низът BB е достижим от низ AA, ако е възможно да вмъкнем някакъв брой символи ←\leftarrow в AA така, че при натискане на получените клавиши да се получи BB. Така примерът показва, че faecdb\texttt{faecdb} е достижим от abcdef\texttt{abcdef}. Докажете, че за всеки два низа AA и BB низът AA е достижим от BB тогава и само тогава, когато BB е достижим от AA.
РешениеОчевидно AA и BB трябва да имат едно и също мултимножество от символи; занапред разглеждаме само този случай. Първо ще използваме стандартна характеристика. Нека A=123…nA=123\ldots n, а B=σ(1)σ(2)…σ(n)B=\sigma(1)\sigma(2)\ldots\sigma(n) е пермутация на символите на AA. Тогава BB е достижим от AA точно когато пермутацията σ\sigma избягва шаблона 213213, тоест няма индекси i<j<ki\lt{}j\lt{}k такива, чеσ(j)<σ(i)<σ(k).\sigma(j)\lt{}\sigma(i)\lt{}\sigma(k).Необходимостта е ясна: ако първо е изписан символът ii, после курсорът не може да прескочи вече изписан символ така, че да се появи забраненият ред. За достатъчността можем да пишем символите на BB индуктивно. След като сме поставили 1,2,…,k1,2,\ldots,k, единственият начин да заседнем при поставянето на k+1k+1 е той да стои вдясно от kk в целевия низ, а между тях да има още непоставен символ; това точно дава шаблон 213213. Следващото наблюдение е, че една пермутация избягва 213213 тогава и само тогава, когато обратната пермутация също избягва 213213. Наистина, ако i<j<ki\lt{}j\lt{}k и σ(j)<σ(i)<σ(k)\sigma(j)\lt{}\sigma(i)\lt{}\sigma(k), поставямеi′=σ(j),j′=σ(i),k′=σ(k).i'=\sigma(j),\qquad j'=\sigma(i),\qquad k'=\sigma(k).Тогава i′<j′<k′i'\lt{}j'\lt{}k' иσ−1(j′)<σ−1(i′)<σ−1(k′),\sigma^{-1}(j')\lt{}\sigma^{-1}(i')\lt{}\sigma^{-1}(k'),което е същият забранен шаблон за σ−1\sigma^{-1}. Обратната посока е симетрична. Сега задачата следва веднага. Ако BB е достижим от AA, избраният начин на писане задава някаква 213213-избягваща пермутация σ\sigma, която казва на коя позиция в BB отива всеки символ на AA. Ако символите се повтарят, такава пермутация може да не е единствена, но съществува. Понеже σ−1\sigma^{-1} също избягва 213213, същата характеристика дава начин да получим AA от BB. Следователно достижимостта е симетрична.
Отвори задачатаEvan Chen VONVON TSTST 2014/1Условие — източник

Задача 3

Пълен запис
Условие
Да се намерят всички полиноми P(x)P(x) с реални коефициенти, за коитоP(x2)=P(x+x21−x2)P(x\sqrt2)=P\left(x+\sqrt{\vphantom{x^2}1-x^2}\right)за всички реални числа xx с ∣x∣≤1|x|\le1.
РешениеОтговорът е: всички полиноми от видаP(x)=g(U(x2)),P(x)=g\left(U\left(\frac{x}{\sqrt2}\right)\right),където g∈R[x]g\in\mathbb R[x], а UU е единственият полином, за койтоU(cos⁡θ)=cos⁡(8θ).U(\cos\theta)=\cos(8\theta).Това е полиномът на Чебишев T8T_8. Поставяме Q(x)=P(x2)Q(x)=P(x\sqrt2). Условието ставаQ(cos⁡θ)=Q(cos⁡θ+sin⁡θ2)=Q(cos⁡(θ−45∘))Q(\cos\theta)=Q\left(\frac{\cos\theta+\sin\theta}{\sqrt2}\right)=Q(\cos(\theta-45^\circ))за всяко 0≤θ≤180∘0\le\theta\le180^\circ. Ще наричаме такъв полином QQ добър. Полиномът UU е добър, защото смяната θ↦θ−45∘\theta\mapsto\theta-45^\circ променя 8θ8\theta с 360∘360^\circ. Следователно всеки полином g(U(x))g(U(x)) също е добър. Остава да докажем обратното. Ще правим индукция по deg⁡Q\deg Q. Случаят на константен QQ е очевиден. За неконстантен добър QQ имаме веригатаQ(cos⁡136∘)=Q(cos⁡91∘)=Q(cos⁡46∘)=Q(cos⁡1∘)=Q(cos⁡(−44∘))=Q(cos⁡44∘)=Q(cos⁡89∘)=Q(cos⁡134∘)=Q(cos⁡179∘).\begin{align*} Q(\cos136^\circ)&=Q(\cos91^\circ)=Q(\cos46^\circ)=Q(\cos1^\circ)\\ &=Q(\cos(-44^\circ))=Q(\cos44^\circ)=Q(\cos89^\circ)=Q(\cos134^\circ)=Q(\cos179^\circ). \end{align*}Тук има осем различни стойности на xx; двете стойности cos⁡(−44∘)\cos(-44^\circ) и cos⁡44∘\cos44^\circ съвпадат. Точно тези осем стойности са корени на полиномаU(x)−U(cos⁡1∘),U(x)-U(\cos1^\circ),който е от степен 88. СледователноQ~(x)=Q(x)−Q(cos⁡1∘)U(x)−U(cos⁡1∘)\widetilde Q(x)=\frac{Q(x)-Q(\cos1^\circ)}{U(x)-U(\cos1^\circ)}е полином. Освен това Q~\widetilde Q пак е добър: числителят и знаменателят не се променят при замяната x=cos⁡θx=\cos\theta с cos⁡(θ−45∘)\cos(\theta-45^\circ). Ако QQ не е константен, това показва, че степента му е поне 88, и имамеQ(x)=(U(x)−U(cos⁡1∘))Q~(x)+Q(cos⁡1∘).Q(x)=\bigl(U(x)-U(\cos1^\circ)\bigr)\widetilde Q(x)+Q(\cos1^\circ).По индукционната хипотеза Q~\widetilde Q е полином от U(x)U(x), значи и QQ е полином от U(x)U(x). Връщайки Q(x)=P(x2)Q(x)=P(x\sqrt2), получаваме точно описаните по-горе решения.
Отвори задачатаEvan Chen VONVON TSTST 2014/3Условие — източник

Задача 4

Пълен запис
Условие
Нека P(x)P(x) и Q(x)Q(x) са произволни полиноми с реални коефициенти, като P≠0P\ne0, и нека d=deg⁡Pd=\deg P. Докажете, че съществуват полиноми A(x)A(x) и B(x)B(x), не и двата нулеви, такива чеmax⁡{deg⁡A,deg⁡B}≤d2\max\{\deg A,\deg B\}\le \frac d2иP(x)∣A(x)+Q(x)B(x).P(x)\mid A(x)+Q(x)B(x).
РешениеНека VV е векторното пространство на реалните полиноми със степен най-много ⌊d/2⌋\lfloor d/2\rfloor. Разглеждаме линейното изображениеV⊕V⟶R[x]/(P(x)),(A,B)⟼A+QB(modP).\begin{align*} V\oplus V&\longrightarrow \mathbb R[x]/(P(x)),\\ (A,B)&\longmapsto A+QB \pmod{P}. \end{align*}Областта има размерност2(⌊d2⌋+1),2\left(\left\lfloor\frac d2\right\rfloor+1\right),а пространството R[x]/(P(x))\mathbb R[x]/(P(x)) има размерност dd, защото всеки остатък по модул PP има единствен представител със степен по-малка от dd. За всяко цяло d≥0d\ge0 имаме2(⌊d2⌋+1)>d.2\left(\left\lfloor\frac d2\right\rfloor+1\right)\gt{}d.Следователно линейното изображение от по-горе има ненулево ядро. Избираме ненулева двойка (A,B)(A,B) от това ядро. Тогава AA и BB не са едновременно нулеви, степените им са най-много ⌊d/2⌋≤d/2\lfloor d/2\rfloor\le d/2, иA+QB≡0(modP),A+QB\equiv0\pmod P,което е точно исканата делимост.
Отвори задачатаEvan Chen VONVON TSTST 2014/4Условие — източник

Задача 5

Пълен запис
Условие
Да се намери най-голямото число EE със следното свойство: съществува граф с 6060 върха и EE ребра, всяко оцветено в червено или синьо, така че в това оцветяване няма едноцветен цикъл с дължина 33 и няма едноцветен цикъл с дължина 55.
РешениеОтговорът еE=302+2⋅152=6⋅152=1350.E=30^2+2\cdot15^2=6\cdot15^2=1350.Първо ще докажем горната граница. Твърдим, че графът не може да съдържа K5K_5. Действително, да разгледаме произволно двуцветно оцветяване на ребрата на K5K_5, в което няма едноцветен триъгълник. От всеки връх излизат четири ребра, затова по принципа на Дирихле има поне две ребра от един и същ цвят. Ако от някой връх излизаха три ребра от един цвят, то трите им други края не биха могли да са свързани с ребро от същия цвят, а тогава трите ребра между тях биха били в другия цвят и биха дали едноцветен триъгълник. Значи от всеки връх излизат точно две червени и две сини ребра. Следователно всеки от двата цветни подграфа е 22-регулярен граф върху 55 върха, тоест цикъл C5C_5. Така в K5K_5 непременно има едноцветен цикъл с дължина 55, противоречие. Значи целият граф е K5K_5-свободен. По теоремата на Туран броят на ребрата му е най-много броя на ребрата в пълния 44-делен граф с равни части по 1515 върха, тоестE≤(42)⋅152=1350.E\le \binom42\cdot15^2=1350.Остава да покажем, че тази граница се достига. Разделяме върховете на две групи от по 3030 върха и оцветяваме всички ребра между двете групи в червено; това е червен K30,30K_{30,30}. После във всяка от двете групи разделяме върховете на две подгрупи от по 1515 върха и оцветяваме всички ребра между тези две подгрупи в синьо; така получаваме два сини K15,15K_{15,15}. Полученият граф има30⋅30+2⋅15⋅15=135030\cdot30+2\cdot15\cdot15=1350ребра. И червеният, и синият подграф са двуделни, следователно нямат нечетни цикли изобщо. В частност няма едноцветни цикли с дължина 33 или 55. Това завършва доказателството.
Отвори задачатаEvan Chen VONVON TSTST 2014/5Условие — източник

Задача 6

Пълен запис
Условие
Нека a,b,c,da,b,c,d са различни положителни цели числа, а pp е нечетно просто число, което не дели никое от тях. Нека MM е цяло число. Разглеждаме безкрайната редицаca−db,ca2−db2,ca-db,\quad ca^2-db^2,ca3−db3,ca4−db4,….\quad ca^3-db^3,\quad ca^4-db^4,\quad\ldots.За всеки неин член гледаме показателя νp\nu_p на най-голямата степен на pp, която го дели. Да предположим, че тези показатели не са всички нула и че всички са най-много MM. Докажете, че съществува число TT, зависещо евентуално от a,b,c,d,p,Ma,b,c,d,p,M, такова че когато pp дели член на редицата, неговата pp-адична валуация е точно TT.
РешениеПърво описваме индексите на членовете, които се делят на pp. Условиетоp∣can−dbnp\mid ca^n-db^nе еквивалентно на(ab)n≡dc(modp),\left(\frac ab\right)^n\equiv\frac dc\pmod p,защото pp не дели a,b,c,da,b,c,d. Следователно, ако има поне едно решение n=κn=\kappa, всички решения са точноκ,κ+λ,κ+2λ,…,\kappa,\quad \kappa+\lambda,\quad \kappa+2\lambda,\quad\ldots,където λ\lambda е редът на a/ba/b по модул pp. За такива индекси имаме, понеже умножаваме само по числа с pp-адична валуация 00,νp(caκ+nλ−dbκ+nλ)=\nu_p\left(ca^{\kappa+n\lambda}-db^{\kappa+n\lambda}\right)=νp((aλbλ)n−dbκcaκ).\nu_p\left(\left(\frac{a^\lambda}{b^\lambda}\right)^n-\frac{db^\kappa}{ca^\kappa}\right).Така задачата се свежда до следното твърдение. Нека pp е нечетно просто число и нека x,y∈Q>0x,y\in\mathbb Q_{\gt{}0} са такива, че x≡y≡1(modp)x\equiv y\equiv1\pmod p. Ако редицатаνp(xn−y)\nu_p(x^n-y)от положителни цели числа не е константна, то тя е неограничена. Ще докажем по-силна стъпка за повишаване на валуацията. Нека m,nm,n са положителни цели числа иd=νp(xn−y)<νp(xm−y)=e.d=\nu_p(x^n-y)\lt{}\nu_p(x^m-y)=e.Тогаваνp(xm−xn)=νp((xm−y)−(xn−y))=d.\nu_p(x^m-x^n)=\nu_p\big((x^m-y)-(x^n-y)\big)=d.От лемата за повдигане на степента, приложена към x≡1(modp)x\equiv1\pmod p, следва, че можем да намерим kk сνp(xk−1)=e;\nu_p(x^k-1)=e;например можем да вземем k=pe−d∣m−n∣k=p^{e-d}|m-n|. Записвамеxk=1+peu,xm=y+pev,x^k=1+p^e u,\qquad x^m=y+p^e v,където u,v∈Qu,v\in\mathbb Q не се делят на pp в смисъл на pp-адична валуация. За всяко цяло rr с 1≤r≤p−11\le r\le p-1 разглеждамеxkr+m−y=(1+peu)r(y+pev)−y=pe(v+yur)+p2e(⋯ ).\begin{align*} x^{kr+m}-y&=(1+p^e u)^r(y+p^e v)-y\\ &=p^e(v+yur)+p^{2e}(\cdots). \end{align*}Понеже y≡1(modp)y\equiv1\pmod p, можем да изберем rr така, че v+yur≡0(modp)v+yur\equiv0\pmod p. Тогаваνp(xkr+m−y)≥e+1.\nu_p(x^{kr+m}-y)\ge e+1.Значи от две различни положителни стойности на редицата можем да произведем още по-голяма стойност. Повтаряйки това, получаваме, че ако редицата не е константна, тя е неограничена. В първоначалната задача обаче всички валуации са ограничени от MM. Следователно върху индексите, за които pp дели съответния член, валуацията е константна. Тази константа е търсеното TT.
Отвори задачатаEvan Chen VONVON TSTST 2014/6Условие — източник