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

Evan Chen / USA TST Solutions

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

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

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

2024

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Да се намери най-малката константа C>1C\gt{}1, за която е вярно следното твърдение: за всяко цяло число n≥2n\ge2 и всяка редица от положителни реални числа a1,a2,…,ana_1,a_2,\ldots,a_n, които не са цели и удовлетворяват1a1+1a2+⋯+1an=1,\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=1,могат да се изберат положителни цели числа bib_i, такива че: (i) за всяко i=1,2,…,ni=1,2,\ldots,n имаме или bi=⌊ai⌋b_i=\lfloor a_i\rfloor, или bi=⌊ai⌋+1b_i=\lfloor a_i\rfloor+1; (ii) изпълнено е1<1b1+1b2+⋯+1bn≤C.1\lt{}\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\le C.
РешениеОтговорът еC=32.C=\frac32.Първо доказваме, че по-малка константа не е възможна. Некаa1=4n−32n−1,ai=4n−32(i>1).a_1=\frac{4n-3}{2n-1},\qquad a_i=\frac{4n-3}{2}\quad(i\gt{}1).Тогава b1∈{1,2}b_1\in\{1,2\}, а за i>1i\gt{}1 имаме bi∈{2n−2,2n−1}b_i\in\{2n-2,2n-1\}. Ако изберем b1=2b_1=2, получаваме1b1+1b2+⋯+1bn≤\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\le12+(n−1)⋅12n−2=1,\frac12+(n-1)\cdot\frac1{2n-2}=1,което не е позволено. Значи трябва да изберем b1=1b_1=1, а тогава1b1+1b2+⋯+1bn≥\frac1{b_1}+\frac1{b_2}+\cdots+\frac1{b_n}\ge1+(n−1)⋅12n−1=3n−22n−1.1+(n-1)\cdot\frac1{2n-1}=\frac{3n-2}{2n-1}.При n→∞n\to\infty това показва C≥32C\ge\frac32. Остава да докажем, че C=32C=\frac32 винаги стига. За 0≤k≤n0\le k\le n положетеck=c_k=∑i=1k1⌊ai⌋+∑i=k+1n1⌊ai⌋+1.\sum_{i=1}^{k}\frac1{\lfloor a_i\rfloor}+\sum_{i=k+1}^{n}\frac1{\lfloor a_i\rfloor+1}.Понеже всяко aia_i не е цяло число, при смяната на ⌊ai⌋+1\lfloor a_i\rfloor+1 с ⌊ai⌋\lfloor a_i\rfloor сумата строго нараства. Следователноc0<c1<⋯<cn.c_0\lt{}c_1\lt{}\cdots\lt{}c_n.Освен товаc0<1a1+1a2+⋯+1an=1<cn.c_0\lt{}\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=1\lt{}c_n.Значи съществува единствено kk, за коетоck−1<1<ck.c_{k-1}\lt{}1\lt{}c_k.За това kk имаме1<ck=ck−1+1⌊ak⌋(⌊ak⌋+1)<1\lt{}c_k=c_{k-1}+\frac1{\lfloor a_k\rfloor(\lfloor a_k\rfloor+1)}\lt{}1+11⋅2=32.1+\frac1{1\cdot2}=\frac32.Избираме bi=⌊ai⌋b_i=\lfloor a_i\rfloor за i≤ki\le k и bi=⌊ai⌋+1b_i=\lfloor a_i\rfloor+1 за i>ki\gt{}k. Тогава сумата на реципрочните стойности е точно ckc_k, така че тя лежи в искания интервал. Следователно най-малката възможна константа е 32\frac32.
Отвори задачатаEvan Chen VONVON TST 2024/1Условие — източник

Задача 3

Пълен запис
Условие
Нека n>k≥1n\gt{}k\ge1 са цели числа и нека простото число pp дели (nk)\binom nk. Докажете, че kk-елементните подмножества на {1,2,…,n}\{1,2,\ldots,n\} могат да се разделят на pp класа с равен брой елементи така, че всеки две подмножества с една и съща сума на елементите си да принадлежат на един и същ клас.
РешениеЗа подмножество SS означаваме с σ(S)\sigma(S) сумата на неговите елементи и разглеждаме генериращата функцияP(x):=∑S⊆{1,2,…,n}∣S∣=kxσ(S).\begin{aligned}P(x):=\sum_{\substack{S\subseteq\{1,2,\ldots,n\}\\ |S|=k}}x^{\sigma(S)}.\end{aligned}Нека cjc_j е коефициентът пред xjx^j в P(x)P(x), тоест броят на kk-елементните подмножества със сума jj. По формулата на Льожандр имамеνp(nk)=\nu_p\binom nk=∑r=1∞(⌊npr⌋−⌊kpr⌋−⌊n−kpr⌋).\sum_{r=1}^{\infty}\left(\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor\right).Тъй като p∣(nk)p\mid\binom nk, съществува положително цяло число rr, за което⌊npr⌋−⌊kpr⌋−⌊n−kpr⌋>0.\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor\gt{}0.Ключовото твърдение е, че P(x)P(x) се дели на циклотомния полиномΦpr(x)=\Phi_{p^r}(x)=x(p−1)pr−1+x(p−2)pr−1+⋯+xpr−1+1.x^{(p-1)p^{r-1}}+x^{(p-2)p^{r-1}}+\cdots+x^{p^{r-1}}+1.Първо ще видим защо това решава задачата. Пишем P(x)=Φpr(x)Q(x)P(x)=\Phi_{p^r}(x)Q(x), където QQ е полином с цели коефициенти. За 0≤i<pr0\le i\lt{}p^r положетеsi=∑j≡i(modpr)cj.s_i=\sum_{j\equiv i\pmod{p^r}}c_j.От множителя Φpr\Phi_{p^r} следва, че за всяко 0≤t<pr−10\le t\lt{}p^{r-1} са равни числатаst=st+pr−1=st+2pr−1=⋯=st+(p−1)pr−1.s_t=s_{t+p^{r-1}}=s_{t+2p^{r-1}}=\cdots=s_{t+(p-1)p^{r-1}}.Сега поставяме подмножество със сума zz в класа⌊z mod prpr−1⌋∈{0,1,…,p−1}.\left\lfloor\frac{z\bmod p^r}{p^{r-1}}\right\rfloor\in\{0,1,\ldots,p-1\}.Две подмножества с една и съща сума очевидно попадат в един и същ клас, а горните равенства за sis_i показват, че pp-те класа имат равни размери. Остава да докажем делимостта. Нека ℓ=n−k\ell=n-k. Между kk-елементните подмножества на {1,2,…,n}\{1,2,\ldots,n\} и двоичните низове с kk нули и ℓ\ell единици има естествена биекция: подмножеството {a1<a2<⋯<ak}\{a_1\lt{}a_2\lt{}\cdots\lt{}a_k\} отговаря на низа, чиито нули са на позиции a1,a2,…,aka_1,a_2,\ldots,a_k. Броят на инверсиите в този низ е(a1+a2+⋯+ak)−k(k+1)2.(a_1+a_2+\cdots+a_k)-\frac{k(k+1)}2.Следователно, с точност до умножение по степен на xx, нашият полином P(x)P(x) е qq-биномният коефициент(x−1)(x2−1)⋯(xn−1)((x−1)(x2−1)⋯(xk−1))((x−1)(x2−1)⋯(xℓ−1)).\frac{(x-1)(x^2-1)\cdots(x^n-1)}{\big((x-1)(x^2-1)\cdots(x^k-1)\big)\big((x-1)(x^2-1)\cdots(x^{\ell}-1)\big)}.Множителят Φpr(x)\Phi_{p^r}(x) участва в xm−1x^m-1 точно когато pr∣mp^r\mid m. Затова кратността му в горния израз е⌊npr⌋−⌊kpr⌋−⌊n−kpr⌋,\left\lfloor\frac n{p^r}\right\rfloor-\left\lfloor\frac k{p^r}\right\rfloor-\left\lfloor\frac{n-k}{p^r}\right\rfloor,която е положителна по избора на rr. Следователно Φpr(x)\Phi_{p^r}(x) дели P(x)P(x) и доказателството е завършено.
Отвори задачатаEvan Chen VONVON TST 2024/3Условие — източник

Задача 5

Пълен запис
Условие
Нека a1<a2<⋯<a2024a_1\lt{}a_2\lt{}\cdots\lt{}a_{2024} е аритметична прогресия от положителни цели числа, а b1<b2<⋯<b2024b_1\lt{}b_2\lt{}\cdots\lt{}b_{2024} е геометрична прогресия от положителни цели числа. Да се намери най-големият възможен брой цели числа, които могат да се срещат и в двете редици.
РешениеОтговорът е 1111. Първо този брой се достига: вземамеai=i,bi=2i−1.a_i=i,\qquad b_i=2^{i-1}.Общите членове са 1,2,4,…,10241,2,4,\ldots,1024, общо 1111 числа. Остава да докажем, че повече не може. Ще използваме следното твърдение. Нека pp е просто число и разгледаме редицатаνp(a1),νp(a2),…,νp(a2024).\nu_p(a_1),\nu_p(a_2),\ldots,\nu_p(a_{2024}).АкоC=⌊log⁡p2023⌋,C=\left\lfloor\log_p 2023\right\rfloor,то в тази редица има най-много C+2C+2 различни стойности. Доказателство на твърдението. След деление на всички членове на аритметичната прогресия на общия им делител можем да приемем, че ai=a+dia_i=a+di и gcd⁡(a,d)=1\gcd(a,d)=1. Ако p∣dp\mid d, тогава p∤ap\nmid a, така че всички νp(ai)\nu_p(a_i) са равни на 00. Нека сега p∤dp\nmid d. Всъщност ще докажем, че всички стойности лежат в {0,1,…,C}\{0,1,\ldots,C\}, с най-много едно изключение. Нека M=max⁡iνp(ai)M=\max_i\nu_p(a_i). Ако M≤CM\le C, няма какво да доказваме. Иначе избираме индекс mm, за който νp(am)=M\nu_p(a_m)=M. За всеки i≠mi\ne m имаме ∣i−m∣≤2023|i-m|\le2023, следователноνp(d(i−m))=νp(i−m)≤C<M=νp(am).\nu_p(d(i-m))=\nu_p(i-m)\le C\lt{}M=\nu_p(a_m).Понеже ai=am+d(i−m)a_i=a_m+d(i-m), получавамеνp(ai)=νp(d(i−m))≤C.\nu_p(a_i)=\nu_p(d(i-m))\le C.Така ama_m е единственото възможно изключение и твърдението е доказано. Връщаме се към геометричната прогресия. Нека r∈Qr\in\mathbb Q е нейното частно. Ако съществува просто число p≥3p\ge3 с νp(r)≠0\nu_p(r)\ne0, то всички членове на геометричната прогресия имат различни pp-адични валуации. Следователно общите членове са най-много броя на различните стойности в редицата νp(ai)\nu_p(a_i), което е не повече от2+log⁡32023<11.2+\log_3 2023\lt{}11.Остава случаят, когато частното rr е степен на 22. Понеже геометричната прогресия е растяща и от цели числа, можем да пишем r=2tr=2^t за някое положително цяло число tt. От вече доказаното за p=2p=2 имаме груба горна граница 1212, защото ⌊log⁡22023⌋=10\lfloor\log_2 2023\rfloor=10. Ако t≥2t\ge2, сред валуациите на членовете на геометричната прогресия се пропускат стойности, така че общите членове са още по-малко от 1212. Значи единственият начин да се надяваме на 1212 общи члена е r=2r=2. Да допуснем, че при r=2r=2 има 1212 общи члена. Тогава стойностите на ν2(ai)\nu_2(a_i) сред тях трябва да са 0,1,…,10,M0,1,\ldots,10,M за някое M≥11M\ge11. Нека bb е единственият нечетен член на геометричната прогресия, който се среща и в аритметичната прогресия. Тогава и 2b2b се среща в аритметичната прогресия, затова общата разлика на аритметичната прогресия е най-много bb. Но прогресия от 20242024 члена, която съдържа bb и има разлика най-много bb, не може да има член по-голям отb+2023b=2024b.b+2023b=2024b.От друга страна, общият член с валуация M≥11M\ge11 е 2Mb>2024b2^M b\gt{}2024b, противоречие. Следователно 1212 общи члена са невъзможни, а максималният брой е 1111.
Отвори задачатаEvan Chen VONVON TST 2024/5Условие — източник

Задача 6

Пълен запис
Условие
Намерете всички функции f:R→Rf:\mathbb R\to\mathbb R, за които за всички реални числа xx и yy е изпълнено функционалното уравнениеf(xf(y))+f(y)=f(x+y)+f(xy).f(xf(y))+f(y)=f(x+y)+f(xy).
РешениеВсички константни функции са решения, а също така работи и f(x)≡x+1f(x)\equiv x+1. Ще докажем, че други решения няма. Нека P(x,y)P(x,y) означава даденото равенство. Твърдение 1. Ако ff е периодична, то ff е константна. Нека d≠0d\ne0 е период на ff. От P(x,y+d)P(x,y+d) получавамеf(x(y+d))=f(x+y+d)−f(y+d)−f(xf(y+d))=f(x(y+d))=f(x+y+d)-f(y+d)-f(xf(y+d))=f(x+y)−f(y)−f(xf(y)).f(x+y)-f(y)-f(xf(y)).Сравнено с P(x,y)P(x,y), това дава f(x(y+d))=f(xy)f(x(y+d))=f(xy). При y=0y=0 следва f(dx)=f(0)f(dx)=f(0) за всяко реално xx, а понеже d≠0d\ne0, функцията е константна. Твърдение 2. За всички реални x,yx,y е изпълненоf(f(x)+y)=f(f(y)+x).f(f(x)+y)=f(f(y)+x).Наистина, от P(f(x),y)P(f(x),y) и после от P(y,x)P(y,x) имамеf(f(x)f(y))=f(f(x)+y)+f(f(x)y)−f(y)=f(f(x)+y)+f(x+y)+f(xy)−f(x)−f(y).\begin{align*} f(f(x)f(y))&=f(f(x)+y)+f(f(x)y)-f(y)\\ &=f(f(x)+y)+f(x+y)+f(xy)-f(x)-f(y). \end{align*}Като разменим xx и yy, получаваме желаната симетрия. Твърдение 3. Ако ff не е константна, тоf(f(x)+y)=f(x)+f(y)f(f(x)+y)=f(x)+f(y)за всички реални x,yx,y. Некаd=f(f(x)+y)−f(x)−f(y).d=f(f(x)+y)-f(x)-f(y).За произволно реално zz, чрез многократно използване на Твърдение 2, получавамеf(z+f(f(x)+y))=f(f(z)+f(x)+y)=f(f(x)+f(z)+y)=f(x+f(f(z)+y))=f(x+f(f(y)+z))=f(f(x)+f(y)+z)=f(z+f(x)+f(y)).\begin{align*} f(z+f(f(x)+y))&=f(f(z)+f(x)+y)\\ &=f(f(x)+f(z)+y)\\ &=f(x+f(f(z)+y))\\ &=f(x+f(f(y)+z))\\ &=f(f(x)+f(y)+z)\\ &=f(z+f(x)+f(y)). \end{align*}Ако d≠0d\ne0, това прави ff периодична с период dd, противоречие с Твърдение 1. Значи d=0d=0. Твърдение 4. Ако ff не е константна, то f(0)=1f(0)=1 иf(x+1)=f(x)+1.f(x+1)=f(x)+1.От P(z,0)P(z,0) имаме f(zf(0))=f(z)f(zf(0))=f(z) за всяко реално zz. От друга страна, сравнявайки P(xf(0),y)P(xf(0),y) и P(x,y)P(x,y), получавамеf(xf(0)+y)=f(y)+f(xf(0)f(y))−f(xf(0)y)=f(y)+f(xf(y))−f(xy)=f(x+y).\begin{align*} f(xf(0)+y)&=f(y)+f(xf(0)f(y))-f(xf(0)y)\\ &=f(y)+f(xf(y))-f(xy)=f(x+y). \end{align*}Ако f(0)≠1f(0)\ne1, тогава xf(0)−xxf(0)-x би бил период на ff за всеки xx, което противоречи на Твърдение 1. Следователно f(0)=1f(0)=1. После, при x=0x=0 в Твърдение 3, получаваме f(y+1)=f(y)+1f(y+1)=f(y)+1. Твърдение 5. Ако ff не е константна, тоf(x)+f(y)=f(x+y)+1.f(x)+f(y)=f(x+y)+1.От P(x+1,y)P(x+1,y) и Твърдение 4 имамеf((x+1)f(y))=f(x+y+1)+f(xy+y)−f(y)=f((x+1)f(y))=f(x+y+1)+f(xy+y)-f(y)=f(x+y)+f(xy+y)−f(y)+1.f(x+y)+f(xy+y)-f(y)+1.От Твърдение 3 и P(x,y)P(x,y) пък следваf((x+1)f(y))=f((x+1)f(y))=f(xf(y))+f(y)=f(x+y)+f(xy).f(xf(y))+f(y)=f(x+y)+f(xy).Следователноf(xy)=f(xy+y)−f(y)+1.f(xy)=f(xy+y)-f(y)+1.Като заменим xx с x/yx/y при y≠0y\ne0, получаваме твърдението; случаят y=0y=0 следва от f(0)=1f(0)=1. Накрая, ако ff не е константна, от Твърдения 3, 5 и 4 имамеf(f(x)+y)=f(x)+f(y)=f(x+y)+1=f(x+y+1).f(f(x)+y)=f(x)+f(y)=f(x+y)+1=f(x+y+1).Ако за някое xx имаме f(x)≠x+1f(x)\ne x+1, Твърдение 1 отново дава противоречие, защото f(x)−x−1f(x)-x-1 е ненулев период. Следователно f(x)=x+1f(x)=x+1 за всяко реално xx. Така всички решения са всички константни функции и функцията f(x)=x+1f(x)=x+1.
Отвори задачатаEvan Chen VONVON TST 2024/6Условие — източник