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

Evan Chen / USA TSTST Solutions

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

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

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

2017

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

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

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

11-12

4 задачи

Задача 2

Пълен запис
Условие
Ана и Банана играят игра. Първо Ана избира дума, т.е. непразна редица от главни английски букви. После Банана избира неотрицателно цяло число kk и предизвиква Ана да даде дума, която има точно kk подниза, равни на думата на Ана. Тук подниз се получава чрез изтриване на някои букви, без да се променя редът на останалите. Ана печели, ако може да даде такава дума; иначе губи. Например, ако Ана избере думата TST\text{TST}, а Банана избере k=4k=4, Ана може да даде думата TSTST\text{TSTST}, която има 44 подниза, равни на TST\text{TST}. Кои думи може да избере Ана, така че да печели независимо от стойността на kk, избрана от Банана?
РешениеРазбиваме думата на Ана на блокове: блок е максимален непрекъснат участък от еднакви букви. Например думата AABBBCAAA\text{AABBBCAAA} има четири блока:AA,BBB,C,AAA.\text{AA},\quad \text{BBB},\quad \text{C},\quad \text{AAA}.Нека избраната от Ана дума еA=A1A2⋯Am=a1⋯a1⏟x1a2⋯a2⏟x2⋯am⋯am⏟xm,A=A_1A_2\cdots A_m=\underbrace{a_1\cdots a_1}_{x_1}\underbrace{a_2\cdots a_2}_{x_2}\cdots\underbrace{a_m\cdots a_m}_{x_m},където съседните букви aia_i са различни. Ще наричаме подниз, равен на AA, копие на AA. Задачата е да разберем кога Ана може да построи дума с точно kk такива копия за всяко k≥0k\ge0. Първо, ако някой блок има дължина 11, Ана винаги печели. Нека xi=1x_i=1. За дадено k≥1k\ge1 тя взема думата, получена от AA, като замени единичната буква aia_i с блок от kk копия на aia_i:W=A1⋯Ai−1ai⋯ai⏟kAi+1⋯Am.W=A_1\cdots A_{i-1}\underbrace{a_i\cdots a_i}_{k}A_{i+1}\cdots A_m.Има поне kk копия: избираме коя от kk-те букви в новия блок да бъде използвана за единичния блок AiA_i, а всички останали букви са принудени. Това са и всички копия. Наистина, в произволен подниз, равен на AA, буквата, която играе ролята на единичния блок AiA_i, не може да лежи преди края на A1⋯Ai−1A_1\cdots A_{i-1}, нито след началото на Ai+1⋯AmA_{i+1}\cdots A_m, защото тогава няма да остане място за предходните или следващите блокове в правилния ред. Следователно тя трябва да се избере от новия ii-ти блок, а всички останали копия на aia_i в този блок трябва да бъдат изтрити. Получаваме точно kk копия. За k=0k=0 Ана може да даде еднобуквена дума, различна от първата буква на AA, така че копия да няма. Остава да докажем, че ако всички блокове имат дължина поне 22, Банана може да избере k=2k=2 и Ана ще загуби. Ще покажем по-силно: ако някоя дума WW има две различни копия на AA, тогава има поне три копия. Нека W=w1w2⋯wnW=w_1w_2\cdots w_n и да разгледаме две различни копия в нея. Понеже те са различни, съществува блок ApA_p с дължина ℓ≥2\ell\ge2, чиито букви са избрани на различни позиции в двете копия. Нека първото копие използва позицииi1<i2<⋯<iℓi_1\lt{}i_2\lt{}\cdots\lt{}i_\ellза този блок, а второто използва позицииj1<j2<⋯<jℓ.j_1\lt{}j_2\lt{}\cdots\lt{}j_\ell.В интервала от min⁡(i1,j1)\min(i_1,j_1) до max⁡(iℓ,jℓ)\max(i_\ell,j_\ell) има поне ℓ+1\ell+1 срещания на буквата apa_p; иначе двете ℓ\ell-орки позиции биха съвпадали. Освен това всеки избор на ℓ\ell от тези срещания може да се допълни до копие на AA, като използваме същите избори за блоковете преди и след ApA_p от едно от двете вече дадени копия. Следователно броят на копията е поне(ℓ+1ℓ)=ℓ+1≥3.\binom{\ell+1}{\ell}=\ell+1\ge3.Значи дума с точно две копия не съществува, когато всички xi≥2x_i\ge2. Обобщаваме. Ана печели точно за думите, в които поне един блок има дължина 11: тогава тя повтаря тази изолирана буква kk пъти. Ако всички блокове имат дължина поне 22, Банана избира k=2k=2, а такава дума не може да бъде построена.
Отвори задачатаEvan Chen VONVON TSTST 2017/2Условие — източник

Задача 3

Пълен запис
Условие
Разглеждаме представянията наx2−cx+1=f(x)g(x),x^2-cx+1=\frac{f(x)}{g(x)},където ff и gg са ненулеви полиноми с неотрицателни реални коефициенти. За всяко c>0c\gt{}0 определете най-малката възможна степен на ff или докажете, че такива ff и gg не съществуват.
РешениеАко c≥2c\ge2, такива полиноми не съществуват: при x=1x=1 лявата страна е 2−c≤02-c\le0, а дясната страна е положителна, защото ff и gg са ненулеви полиноми с неотрицателни коефициенти. Нека занапред 0<c<20\lt{}c\lt{}2 и пишем c=2cos⁡θc=2\cos\theta, където 0<θ<π0\lt{}\theta\lt{}\pi. Отговорът еn=⌈πarccos⁡(c/2)⌉,n=\left\lceil\frac{\pi}{\arccos(c/2)}\right\rceil,тоест най-малкото цяло nn, за което sin⁡(nθ)≤0\sin(n\theta)\le0. Първо доказваме, че степента на ff не може да бъде по-малка. Нека f=(x2−2cos⁡θ x+1)gf=(x^2-2\cos\theta\,x+1)g и нека deg⁡f=n\deg f=n. Тогава deg⁡g=n−2\deg g=n-2, затова записвамеg(x)=a0+a1x+⋯+an−2xn−2,g(x)=a_0+a_1x+\cdots+a_{n-2}x^{n-2},ai≥0,an−2>0.\qquad a_i\ge0,\quad a_{n-2}\gt{}0.Неотрицателността на коефициентите на ff дава веригатаa1≥2cos⁡θ a0,a0+a2≥2cos⁡θ a1,a1+a3≥2cos⁡θ a2,⋮an−4+an−2≥2cos⁡θ an−3,an−3≥2cos⁡θ an−2.\begin{align*} a_1&\ge2\cos\theta\, a_0,\\ a_0+a_2&\ge2\cos\theta\, a_1,\\ a_1+a_3&\ge2\cos\theta\, a_2,\\ &\vdots\\ a_{n-4}+a_{n-2}&\ge2\cos\theta\, a_{n-3},\\ a_{n-3}&\ge2\cos\theta\, a_{n-2}. \end{align*}Ако sin⁡(kθ)>0\sin(k\theta)\gt{}0 за k=1,2,…,n−1k=1,2,\ldots,n-1, умножаваме тези неравенства съответно по sin⁡θ,sin⁡2θ,…,sin⁡((n−1)θ)\sin\theta,\sin2\theta,\ldots,\sin((n-1)\theta) и ги събираме. Тъждествотоsin⁡(kθ)+sin⁡((k+2)θ)=2sin⁡((k+1)θ)cos⁡θ\sin(k\theta)+\sin((k+2)\theta)=2\sin((k+1)\theta)\cos\thetaсъкращава всички вътрешни членове и оставаsin⁡((n−2)θ)an−2≥2cos⁡θsin⁡((n−1)θ)an−2.\sin((n-2)\theta)a_{n-2}\ge2\cos\theta\sin((n-1)\theta)a_{n-2}.След делене на an−2>0a_{n-2}\gt{}0 и още едно приложение на същото тъждество получаваме sin⁡(nθ)≤0\sin(n\theta)\le0. Значи за степен nn е необходимо sin⁡(nθ)≤0\sin(n\theta)\le0, което дава долната граница. Остава да построим пример, който я достига. Нека nn е най-малкото цяло число със sin⁡(nθ)≤0\sin(n\theta)\le0 и поставямеg(x)=∑k=0n−2sin⁡((k+1)θ)xk.g(x)=\sum_{k=0}^{n-2}\sin((k+1)\theta)x^k.По минималността на nn всички коефициенти на gg са неотрицателни, всъщност положителни. При умножаване с x2−2cos⁡θ x+1x^2-2\cos\theta\,x+1 всички вътрешни коефициенти се зануляват от същото тригонометрично тъждество, първият и последният са положителни, а коефициентът пред xn−1x^{n-1} е −sin⁡(nθ)≥0-\sin(n\theta)\ge0. Следователноf(x)=(x2−cx+1)g(x)f(x)=(x^2-cx+1)g(x)има неотрицателни коефициенти и степен точно nn. Това доказва и достижимостта, и минималността.
Отвори задачатаEvan Chen VONVON TSTST 2017/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички решения с неотрицателни цели числа a,b,c,na,b,c,n на уравнението2a+3b+5c=n!,2^a+3^b+5^c=n!,където n!n! означава факториела на nn.
РешениеЗа n≤4n\le4 проверката е кратка и дава точно следните решения:22+30+50=3!,2^2+3^0+5^0=3!,21+31+50=3!,2^1+3^1+5^0=3!,24+31+51=4!.2^4+3^1+5^1=4!.Тоест получаваме(a,b,c,n)=(2,0,0,3),(a,b,c,n)=(2,0,0,3),(1,1,0,3),(4,1,1,4).\quad(1,1,0,3),\quad(4,1,1,4).Ще докажем, че за n≥5n\ge5 няма решения. Тогава 120∣n!120\mid n!, така че лявата страна трябва да е 00 по модул 120120. Един бърз начин е да се отбележи, че2a(mod120)∈{1,2,4,8,16,32,64},2^a\pmod{120}\in\{1,2,4,8,16,32,64\},3b(mod120)∈{1,3,9,27,81},3^b\pmod{120}\in\{1,3,9,27,81\},5c(mod120)∈{1,5,25},5^c\pmod{120}\in\{1,5,25\},и никой избор на по един елемент от тези три множества не дава сума, деляща се на 120120. За пълнота даваме и стандартната проверка с по-малки модули. Първо нека a<3a\lt{}3. Ако a=0a=0, лявата страна е нечетна, което е невъзможно. Ако a=1a=1, то от уравнението по модул 88 следва3b+5c≡6(mod8),3^b+5^c\equiv6\pmod8,следователно bb е четно, а cc е нечетно. В частност c>0c\gt{}0, и по модул 55 получаваме 3b≡3(mod5)3^b\equiv3\pmod5, невъзможно за четно bb. Ако a=2a=2, от3b+5c≡4(mod8)3^b+5^c\equiv4\pmod8следва, че bb е нечетно, а cc е четно. По модул 55 имаме 3b+5c≡1(mod5)3^b+5^c\equiv1\pmod5, което е невъзможно както при c=0c=0, така и при c>0c\gt{}0. Остава a≥3a\ge3. По модул 88 получаваме 3b+5c≡0(mod8)3^b+5^c\equiv0\pmod8, което принуждава bb и cc да са нечетни, в частност положителни. Тогава по модул 33 равенството2a+5c≡0(mod3)2^a+5^c\equiv0\pmod3налага aa да е четно, защото cc е нечетно. От друга страна, по модул 55 равенството2a+3b≡0(mod5)2^a+3^b\equiv0\pmod5при нечетно bb налага aa да е нечетно. Получаваме противоречие. Следователно други решения няма.
Отвори задачатаEvan Chen VONVON TSTST 2017/4Условие — източник

Задача 6

Пълен запис
Условие
Наричаме редица от положителни цели числа (an)n≥1(a_n)_{n\ge1} от тип Фибоначи, ако тя удовлетворява рекурентната връзкаan+2=an+1+ana_{n+2}=a_{n+1}+a_nза всяко n≥1n\ge1. Възможно ли е множеството на положителните цели числа да се разбие на безкрайно много редици от тип Фибоначи?
РешениеДа, възможно е. Ще използваме числата на ФибоначиF1=F2=1,F3=2,F4=3,F5=5,….F_1=F_2=1,\qquad F_3=2,\qquad F_4=3,\qquad F_5=5,\ldots.Ще ни трябва теоремата на Цекендорф: всяко положително цяло число се представя единствено като сума от несъседни числа на Фибоначи, ако използваме числата F2,F3,F4,…F_2,F_3,F_4,\ldots. Нека припомним доказателството. Ако FkF_k е най-голямото число на Фибоначи, което не надминава nn, тогаваn−Fk<Fk+1−Fk=Fk−1.n-F_k\lt{}F_{k+1}-F_k=F_{k-1}.Затова алчният алгоритъм, който всеки път изважда най-голямото възможно число на Фибоначи, никога не избира две съседни числа на Фибоначи. От друга страна FkF_k е принудително да участва във всяко такова представяне, защотоFk>Fk−1+Fk−3+Fk−5+⋯ .F_k\gt{}F_{k-1}+F_{k-3}+F_{k-5}+\cdots.След това единствеността следва по индукция за остатъка n−Fkn-F_k. Записваме представянето на Цекендорф като двоичен низak⋯a2a1‾Fib,\overline{a_k\cdots a_2a_1}_{\mathrm{Fib}},където ai=1a_i=1 означава, че в сумата участва Fi+1F_{i+1}. Сега за всеки такъв низ, който завършва на a1=1a_1=1, разглеждаме редицатаak⋯a2a1‾Fib,ak⋯a2a10‾Fib,\overline{a_k\cdots a_2a_1}_{\mathrm{Fib}},\quad \overline{a_k\cdots a_2a_10}_{\mathrm{Fib}},ak⋯a2a100‾Fib,….\quad \overline{a_k\cdots a_2a_100}_{\mathrm{Fib}},\quad\ldots.Това е редица от тип Фибоначи: добавянето на една нула в края просто измества всички използвани числа на Фибоначи с един индекс нагоре, а самите числа на Фибоначи удовлетворяват същата рекурентна връзка. Остава да видим, че тези редици наистина дават разбиване. Всяко положително цяло число има единствено представяне на Цекендорф. Ако неговият низ завършва с няколко нули, премахваме точно тези крайни нули; получаваме единствен низ, който завършва на 11, и числото лежи в редицата, породена от него. Обратно, две различни начални представяния не могат да породят едно и също число, защото това би нарушило единствеността на представянето на Цекендорф. Има безкрайно много начални низове, завършващи на 11 и без съседни единици, например 11, 101101, 10011001, 1000110001, и така нататък. Следователно положителните цели числа се разбиват на безкрайно много редици от тип Фибоначи.
Отвори задачатаEvan Chen VONVON TSTST 2017/6Условие — източник