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

Evan Chen / USA TST Solutions

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

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

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

2023

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

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

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

11-12

3 задачи

Задача 3

Пълен запис
Условие
Разглеждаме двойки (f,g)(f,g) от функции от множеството на неотрицателните цели числа в себе си, за които са изпълнени: - f(0)≥f(1)≥f(2)≥⋯≥f(300)≥0f(0)\ge f(1)\ge f(2)\ge\dots\ge f(300)\ge0; - f(0)+f(1)+f(2)+⋯+f(300)≤300f(0)+f(1)+f(2)+\dots+f(300)\le300; - за произволни 2020 неотрицателни цели числа n1,n2,…,n20n_1,n_2,\ldots,n_{20}, не непременно различни, е вярноg(n1+n2+⋯+n20)≤g(n_1+n_2+\dots+n_{20})\lef(n1)+f(n2)+⋯+f(n20). f(n_1)+f(n_2)+\dots+f(n_{20}).Да се намери най-голямата възможна стойност на g(0)+g(1)+⋯+g(6000)g(0)+g(1)+\dots+g(6000).
РешениеЩе докажем малко по-общо твърдение. Нека 300300 се замени с s(s+1)2\frac{s(s+1)}2, където тук s=24s=24, а числото 2020 се замени с kk. Отговорът тогава еks(ks+1)2,\frac{ks(ks+1)}2,което за s=24s=24 и k=20k=20 дава 115440115440. Равенство се достига приf(n)=max⁡(s−n,0),g(n)=max⁡(ks−n,0).f(n)=\max(s-n,0),\qquad g(n)=\max(ks-n,0).Наистина, неравенството от условието ставаmax⁡(x1+⋯+xk,0)≤max⁡(x1,0)+⋯+max⁡(xk,0),\max(x_1+\dots+x_k,0)\le \max(x_1,0)+\dots+\max(x_k,0),където xi=s−nix_i=s-n_i. То следва от случая k=2k=2 и индукция. Остава горната граница. В това доказателство ще наричаме разбиение всяка ненарастваща функция p ⁣:Z≥0→Z≥0p\colon\mathbb Z_{\ge0}\to\mathbb Z_{\ge0}, която от някой момент нататък е нула. Нейният сбор е ∑n=0∞p(n)\sum_{n=0}^{\infty}p(n). Диаграмата на Юнг на pp е множествотоP={(x,y)∈Z≥02:y<p(x)}.\mathcal P=\{(x,y)\in\mathbb Z_{\ge0}^2:y\lt{}p(x)\}.Броят точки в P\mathcal P е точно сборът на pp. Спрегнатото разбиение еp∗(n)=#{i:p(i)>n},p_*(n)=\#\{i:p(i)\gt{}n\},и има същия сбор; геометрично неговата диаграма на Юнг е отражението на P\mathcal P спрямо правата x=yx=y. Понеже всяка стойност на g(n)g(n) може да се максимизира независимо, можем да приемемg(n)=min⁡n1+⋯+nk=n(f(n1)+⋯+f(nk)).(1)g(n)=\min_{n_1+\dots+n_k=n}\bigl(f(n_1)+\dots+f(n_k)\bigr).\tag{1}От условията следва f(s(s+1)2)=0f\bigl(\frac{s(s+1)}2\bigr)=0. За всички релевантни n≤ks(s+1)2n\le k\frac{s(s+1)}2 в минимума в (1) може да се избере оптимална kk-торка, в която всяко nin_i е най-много s(s+1)2\frac{s(s+1)}2: ако някой член е по-голям, заменяме го с s(s+1)2\frac{s(s+1)}2 и прехвърляме излишъка към по-малки членове, без да увеличим сумата, понеже ff е ненарастваща. Така можем да продължим ff с нули след s(s+1)2\frac{s(s+1)}2 и да разглеждаме ff като разбиение със сбор s(s+1)2\frac{s(s+1)}2. Тогава и gg е разбиение. Ключовото твърдение е, че задачата е инвариантна при спрегнато разбиение:g∗(n)=g_*(n)=min⁡n1+⋯+nk=n(f∗(n1)+⋯+f∗(nk)).(2)\min_{n_1+\dots+n_k=n}\bigl(f_*(n_1)+\dots+f_*(n_k)\bigr).\tag{2}Нека F\mathcal F и G\mathcal G са диаграмите на Юнг на ff и gg, а F‾\overline{\mathcal F} и G‾\overline{\mathcal G} са допълненията им в Z≥02\mathbb Z_{\ge0}^2. Долната граница на F‾\overline{\mathcal F} се състои от точките (n,f(n))(n,f(n)). По дефиницията на gg долната граница на G‾\overline{\mathcal G} се получава чрез събиране на kk точки от F‾\overline{\mathcal F}, тоестG‾=F‾+⋯+F‾⏟k пъти,\overline{\mathcal G}=\underbrace{\overline{\mathcal F}+\dots+\overline{\mathcal F}}_{k\text{ пъти}},където ++ е събиране на множества. Това описание не се променя при отражение спрямо x=yx=y, което разменя всяко разбиение със спрегнатото му. Следователно (2) е вярно. Нека AA е сборът на gg. Първо, от тъждеството на Ермитn=∑i=0k−1⌊n+ik⌋n=\sum_{i=0}^{k-1}\left\lfloor\frac{n+i}{k}\right\rfloorполучавамеA=∑n=0∞g(n)≤∑n=0∞∑i=0k−1f(⌊n+ik⌋)=k2∑n=0∞f(n)−k(k−1)2f(0)=k2s(s+1)2−k(k−1)2f(0).\begin{align*} A&=\sum_{n=0}^{\infty}g(n)\\ &\le \sum_{n=0}^{\infty}\sum_{i=0}^{k-1}f\left(\left\lfloor\frac{n+i}{k}\right\rfloor\right)\\ &=k^2\sum_{n=0}^{\infty}f(n)-\frac{k(k-1)}2f(0)\\ &=k^2\frac{s(s+1)}2-\frac{k(k-1)}2f(0).\tag{3} \end{align*}От инвариантността при спрегнато разбиение имаме иA≤k2s(s+1)2−k(k−1)2f∗(0).(4)A\le k^2\frac{s(s+1)}2-\frac{k(k-1)}2f_*(0).\tag{4}За трета оценка забелязваме, че f(f∗(0))=0f(f_*(0))=0, а значи g(kf∗(0))=0g(kf_*(0))=0. Освен това за 0≤q<k0\le q\lt{}k и 0≤r<f∗(0)0\le r\lt{}f_*(0) имамеg(qf∗(0)+r)≤g(qf_*(0)+r)\leqf(f∗(0))+(k−q−1)f(0)+f(r)= qf(f_*(0))+(k-q-1)f(0)+f(r)=(k−q−1)f(0)+f(r).(k-q-1)f(0)+f(r).СледователноA=∑0≤q<k0≤r<f∗(0)g(qf∗(0)+r)≤k(k−1)2f∗(0)f(0)+k∑0≤r<f∗(0)f(r)=k(k−1)2f∗(0)f(0)+ks(s+1)2.\begin{align*} A&=\sum_{\substack{0\le q\lt{}k\\0\le r\lt{}f_*(0)}}g(qf_*(0)+r)\\ &\le \frac{k(k-1)}2f_*(0)f(0)+k\sum_{0\le r\lt{}f_*(0)}f(r)\\ &=\frac{k(k-1)}2f_*(0)f(0)+k\frac{s(s+1)}2.\tag{5} \end{align*}Сега разглеждаме три случая. Ако f(0)≥sf(0)\ge s, то от (3)A≤k2s(s+1)2−k(k−1)2s=ks(ks+1)2.A\le k^2\frac{s(s+1)}2-\frac{k(k-1)}2s=\frac{ks(ks+1)}2.Ако f∗(0)≥sf_*(0)\ge s, аналогично от (4) получаваме същата оценка. В оставащия случай f(0)<sf(0)\lt{}s и f∗(0)<sf_*(0)\lt{}s, откъдето f(0)f∗(0)≤s2f(0)f_*(0)\le s^2; тогава (5) даваA≤k(k−1)2s2+ks(s+1)2=ks(ks+1)2.A\le \frac{k(k-1)}2s^2+k\frac{s(s+1)}2=\frac{ks(ks+1)}2.Във всички случаи A≤ks(ks+1)2A\le\frac{ks(ks+1)}2, а конструкцията по-горе показва, че тази граница е достижима.
Отвори задачатаEvan Chen VONVON TST 2023/3Условие — източник

Задача 4

Пълен запис
Условие
За неотрицателни цели числа aa и bb означаваме с a⊕ba\oplus b тяхното побитово xor. Например9⊕10=10012⊕10102=00112=3.9\oplus10=1001_2\oplus1010_2=0011_2=3.Да се намерят всички положителни цели числа aa, за които при произволни цели числа x>y≥0x\gt{}y\ge0 е изпълненоx⊕ax≠y⊕ay.x\oplus ax\ne y\oplus ay.
РешениеОтговорът е: точно четните положителни цели числа aa. Първо нека aa е четно и ν2(a)=k>0\nu_2(a)=k\gt{}0. Ще покажем, че числото xx може да се възстанови еднозначно отc=x⊕ax.c=x\oplus ax.Понеже aa е кратно на 2k2^k, последните kk бита на axax са нули, така че последните kk бита на cc съвпадат с последните kk бита на xx. След като ги знаем, знаем и последните 2k2k бита на axax, защото умножението по aa премества вече известните битове поне с kk позиции. Следователно можем да възстановим последните 2k2k бита на xx. Повтаряйки същия аргумент, възстановяваме последните 3k3k бита, после последните 4k4k бита и т.н. Така всички битове на xx са определени от cc, следователно функцията x↦x⊕axx\mapsto x\oplus ax е инжективна. Сега нека aa е нечетно. Избираме nn така, че 2n>a2^n\gt{}a, и поставямеx=11…1⏟n=2n−1,y=2n+1=100…0⏟n−11.x=\underbrace{11\dots1}_n=2^n-1,\qquad y=2^n+1=1\underbrace{00\dots0}_{n-1}1.Ще докажем, че x⊕ax=y⊕ayx\oplus ax=y\oplus ay. Нека PP е двоичният запис на aa, допълнен с водещи нули до дължина nn, а QQ е двоичният запис на a−1a-1, също допълнен до дължина nn. Нека RR е побитовото допълнение на QQ. Тогава P,Q,RP,Q,R са двоични низове с дължина nn. Понеже aa е нечетно, преминаването от PP към QQ само сменя последния бит от 11 на 00. Имамеax=a(2n−1)=a2n−a=(a−1)2n+(2n−a),ax=a(2^n-1)=a2^n-a=(a-1)2^n+(2^n-a),тоест двоичният запис на axax по блокове с дължина nn е QR‾\overline{QR}. Понеже xx има последен блок от nn единици, получавамеx⊕ax=QQ‾.x\oplus ax=\overline{QQ}.От друга страна,ay=a(2n+1)=a2n+a,ay=a(2^n+1)=a2^n+a,така че двоичният запис на ayay по същите блокове е PP‾\overline{PP}. Числото yy има по една единица в последния бит на всеки от двата блока, следователноy⊕ay=QQ‾.y\oplus ay=\overline{QQ}.Това дава сблъсък и показва, че нечетно aa не работи.
Отвори задачатаEvan Chen VONVON TST 2023/4Условие — източник

Задача 6

Пълен запис
Условие
Фиксирана е функция f ⁣:N→Nf\colon\mathbb N\to\mathbb N. За m,n∈Nm,n\in\mathbb N дефинирамеΔ(m,n)=ff(n)(m)−ff(m)(n),\Delta(m,n)=f^{f(n)}(m)-f^{f(m)}(n),където frf^r означава rr-кратно прилагане на ff. Ако Δ(m,n)≠0\Delta(m,n)\ne0 за всеки две различни числа m,n∈Nm,n\in\mathbb N, докажете, че Δ\Delta е неограничена: за всяка константа CC съществуват m,n∈Nm,n\in\mathbb N с ∣Δ(m,n)∣>C\left\lvert\Delta(m,n)\right\rvert\gt{}C.
РешениеДа допуснем противното: съществува NN, за което ∣Δ(m,n)∣≤N\left\lvert\Delta(m,n)\right\rvert\le N за всички m,nm,n. Първо, ff е инжективна, защотоf(m)=f(n)  ⟹  Δ(m,n)=0  ⟹  m=n.f(m)=f(n)\implies \Delta(m,n)=0\implies m=n.Нека GG е насоченият граф на стрелките на ff: върховете са положителните цели числа, а от nn излиза ребро към f(n)f(n). Инжективността означава, че всеки връх има най-много едно входящо ребро. Следователно GG е несвързано обединение на вериги и цикли. Ще уточним структурата му чрез няколко твърдения. Първо, GG няма цикли. Ако fk(n)=nf^k(n)=n за някои k≥2k\ge2 и nn, то при променливо mm числата Δ(m,n)\Delta(m,n) са ограничени, а ff(m)(n)f^{f(m)}(n) пробягва само крайно много стойности заради цикъла на nn. Следователно и ff(n)(m)f^{f(n)}(m) може да приема само крайно много стойности. Тогава за различни m1,m2m_1,m_2 бихме имали ff(n)(m1)=ff(n)(m2)f^{f(n)}(m_1)=f^{f(n)}(m_2), което противоречи на инжективността на ff. Второ, GG има най-много 2N+12N+1 вериги. Наистина, нека m1,…,mkm_1,\ldots,m_k лежат в различни вериги. Избираме положително цяло число B>max⁡{f(m1),…,f(mk)}B\gt{}\max\{f(m_1),\ldots,f(m_k)\}. От ограничеността следва∣Δ(mi,fB−f(mi)(1))∣≤N,\left\lvert\Delta\left(m_i,f^{B-f(m_i)}(1)\right)\right\rvert\le N,тоест∣fB(1)−ffB−f(mi)+1(1)(mi)∣≤N.\left\lvert f^B(1)-f^{f^{B-f(m_i)+1}(1)}(m_i)\right\rvert\le N.Понеже върховете mim_i са в различни вериги, числата ffB−f(mi)+1(1)(mi)f^{f^{B-f(m_i)+1}(1)}(m_i) са различни. Всички те лежат в интервала от 2N+12N+1 цели числа около fB(1)f^B(1), така че k≤2N+1k\le2N+1. Трето, GG всъщност се състои от една-единствена полу-безкрайна верига. Фиксираме връх cc. Наричаме число лошо, ако не е от вида fk(c)f^k(c) за никое k≥0k\ge0. Ще покажем, че лошите числа са крайно много. Тъй като веригите са краен брой, множеството от стойности на ff(c)(n)f^{f(c)}(n) съдържа всички достатъчно големи положителни цели числа; нека това са поне всички числа от някое MM нататък. Избираме B>A≥MB\gt{}A\ge M. Ако ff(c)(n)∈[A,B]f^{f(c)}(n)\in[A,B], тогава от ∣Δ(c,n)∣≤N\left\lvert\Delta(c,n)\right\rvert\le N имаме ff(n)(c)∈[A−N,B+N]f^{f(n)}(c)\in[A-N,B+N]. При различни nn тези стойности са различни, защото в графа няма цикли и има само вериги. Значи в интервала [A−N,B+N][A-N,B+N] има поне B−A+1B-A+1 добри числа и най-много 2N2N лоши числа. Като оставим BB да расте, виждаме, че над A−NA-N има най-много 2N2N лоши числа. Следователно извън веригата на cc има само крайно много върхове. Но друга компонента не може да има крайно много върхове, понеже всеки връх има изходящо ребро, а цикли няма. Значи има само една компонента. Освен това предшествениците на cc, ако има такива, са крайно много; преместваме cc в началото на тази верига. Така всяко положително цяло число е от вида fk(c)f^k(c) за единствено k≥0k\ge0. Дефинираме биекция g ⁣:Z≥0→Ng\colon\mathbb Z_{\ge0}\to\mathbb N чрезg(k)=fk(c).g(k)=f^k(c).Тогаваδ(a,b):=Δ(fa(c),fb(c))=\delta(a,b):=\Delta(f^a(c),f^b(c))=g(g(b+1)+a)−g(g(a+1)+b).g(g(b+1)+a)-g(g(a+1)+b).Условията стават ∣δ(a,b)∣≤N\left\lvert\delta(a,b)\right\rvert\le N за всички a,b≥0a,b\ge0 и δ(a,b)≠0\delta(a,b)\ne0 при a≠ba\ne b. Последното е еквивалентно наg(a+1)−a≠g(b+1)−b(a≠b),g(a+1)-a\ne g(b+1)-b\qquad(a\ne b),тоест функцията g(x)−xg(x)-x е инжективна за x≥1x\ge1. Нужна ни е една лема. За всяко MM съществува x≥0x\ge0, за което g(x)≤x−Mg(x)\le x-M. Ако това не е вярно, то g(x)−xg(x)-x е ограничена отдолу. Вземаме голямо положително KK. Понеже стойностите g(x)−xg(x)-x за x≥1x\ge1 са различни цели числа и са ограничени отдолу, съществува BB, такова че g(x)−x≥Kg(x)-x\ge K за всички x≥Bx\ge B. Тогава всички стойности g(B+1),g(B+2),…g(B+1),g(B+2),\ldots са поне B+KB+K, а първите B+1B+1 стойности g(0),…,g(B)g(0),\ldots,g(B) покриват само B+1B+1 числа. Остават поне K−1K-1 положителни цели числа, които не са стойности на gg, противоречие с биективността. Сега избираме безкрайно много BB, за коитоg(B)+N≤Bиg(B)>N.g(B)+N\le B\qquad\text{и}\qquad g(B)\gt{}N.Такива BB има, защото в лемата можем да вземаме MM произволно голямо, а крайно многото стойности с g(B)≤Ng(B)\le N не могат да осигуряват това за всички големи MM. Поставямеt=t=max⁡{g−1(g(B)−N),g−1(g(B)−N+1),…,g−1(g(B)+N)}.\max\{g^{-1}(g(B)-N),g^{-1}(g(B)-N+1),\ldots,g^{-1}(g(B)+N)\}.Понеже g(t)≤g(B)+N≤Bg(t)\le g(B)+N\le B, имаме∣δ(t−1,B−g(t))∣=\left\lvert\delta(t-1,B-g(t))\right\rvert=∣g(B)−g(t−1+g(B+1−g(t)))∣≤\left\lvert g(B)-g(t-1+g(B+1-g(t)))\right\rvert\leN. N.Следователноt−1+g(B+1−g(t))∈t-1+g(B+1-g(t))\in{g−1(g(B)−N),…,g−1(g(B)+N)}.\{g^{-1}(g(B)-N),\ldots,g^{-1}(g(B)+N)\}.По максималността на tt получаваме g(B+1−g(t))=1g(B+1-g(t))=1, тоестB+1−g(t)=g−1(1).B+1-g(t)=g^{-1}(1).А от ∣g(t)−g(B)∣≤N\left\lvert g(t)-g(B)\right\rvert\le N следва∣(B−g(B))+1−g−1(1)∣≤N.\left\lvert (B-g(B))+1-g^{-1}(1)\right\rvert\le N.Това е вярно за безкрайно много стойности на BB. Но за различни такива BB стойностите B−g(B)B-g(B) са различни, защото g(x)−xg(x)-x е инжективна. Получаваме безкрайно много цели числа в краен интервал - противоречие. Следователно първоначалното допускане за ограниченост на Δ\Delta е невъзможно.
Отвори задачатаEvan Chen VONVON TST 2023/6Условие — източник