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

Evan Chen / USA TST Solutions

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

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

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

2018

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Нека n≥2n\ge2 е положително цяло число и нека σ(n)\sigma(n) означава сумата на положителните делители на nn. Докажете, че nn-тото най-малко положително цяло число, взаимно просто с nn, е поне σ(n)\sigma(n), и определете за кои nn се достига равенство.
РешениеРавенство се достига точно когато n=pen=p^e, където pp е просто число и ee е положително цяло число. Първо да проверим този случай. Ако n=pen=p^e, тогаваσ(n)=1+p+p2+⋯+pe.\sigma(n)=1+p+p^2+\cdots+p^e.Броят на положителните цели числа, не по-големи от σ(n)\sigma(n) и взаимно прости с nn, е броят на числата в този интервал, които не се делят на pp:σ(n)−⌊σ(n)p⌋=\sigma(n)-\left\lfloor\frac{\sigma(n)}p\right\rfloor=(1+p+⋯+pe)−(1+p+⋯+pe−1)=pe=n.(1+p+\cdots+p^e)-(1+p+\cdots+p^{e-1})=p^e=n.Освен това σ(n)\sigma(n) не се дели на pp, така че именно σ(n)\sigma(n) е nn-тото такова число. Остава да докажем, че в останалите случаи не може да има равенство. Нека d1,d2,…,dkd_1,d_2,\ldots,d_k са всички положителни делители на nn в някакъв ред и разгледаме последователните интервалиI1=[1,d1],I2=[d1+1,d1+d2],…,I_1=[1,d_1],\quad I_2=[d_1+1,d_1+d_2],\quad \ldots,Ik=[d1+⋯+dk−1+1,d1+⋯+dk].\quad I_k=[d_1+\cdots+d_{k-1}+1,d_1+\cdots+d_k].Интервалът IjI_j има дължина djd_j. Във всеки интервал от djd_j последователни цели числа има точно φ(dj)\varphi(d_j) числа, взаимно прости с djd_j. Понеже dj∣nd_j\mid n, всяко число, взаимно просто с nn, е взаимно просто и с djd_j; следователно в IjI_j има най-много φ(dj)\varphi(d_j) числа, взаимно прости с nn. Сумирайки по всички делители, получаваме, че в интервала [1,σ(n)][1,\sigma(n)] има най-много∑d∣nφ(d)=n\sum_{d\mid n}\varphi(d)=nчисла, взаимно прости с nn. Ако nn има поне два различни прости делителя, нека p<qp\lt{}q са два от тях. Подреждаме делителите така, че първият интервал да има дължина qq, тоест d1=qd_1=q. Тогава и pp, и qq лежат в I1=[1,q]I_1=[1,q], но нито едно от тях не е взаимно просто с nn. Значи в I1I_1 има строго по-малко от φ(q)=q−1\varphi(q)=q-1 числа, взаимно прости с nn. Така в целия интервал [1,σ(n)][1,\sigma(n)] има строго по-малко от nn такива числа. Следователно nn-тото положително цяло число, взаимно просто с nn, е строго по-голямо от σ(n)\sigma(n). Значи равенство е възможно само за простите степени, а те вече бяха проверени.
Отвори задачатаEvan Chen VONVON TST 2018/1Условие — източник

Задача 2

Пълен запис
Условие
Намерете всички функции f ⁣:Z2→[0,1]f\colon\mathbb Z^2\to[0,1], такива че за всички цели числа xx и yy е изпълненоf(x,y)=f(x−1,y)+f(x,y−1)2.f(x,y)=\frac{f(x-1,y)+f(x,y-1)}2.
РешениеЩе докажем, че единствените решения са константните функции. Ясно е, че всяка константна функция работи. Итерираме даденото равенство nn пъти. Получавамеf(x,y)=12n∑i=0n(ni)f(x−i,y−(n−i)).f(x,y)=\frac1{2^n}\sum_{i=0}^n\binom ni f(x-i,y-(n-i)).Сравняваме тази формула за точките (x,y)(x,y) и (x−1,y+1)(x-1,y+1). След преномериране на членовете получаваме∣f(x,y)−f(x−1,y+1)∣≤12n∑i=0n+1∣(ni)−(ni−1)∣,\begin{align*} |f(x,y)-f(x-1,y+1)| &\le \frac1{2^n}\sum_{i=0}^{n+1}\left|\binom ni-\binom n{i-1}\right|, \end{align*}където приемаме (n−1)=(nn+1)=0\binom n{-1}=\binom n{n+1}=0. Разликите на последователните биномиални коефициенти първо са неотрицателни, а после неположителни, затова сумата от абсолютните стойности е два пъти най-големият биномен коефициент. Следователно∣f(x,y)−f(x−1,y+1)∣≤2(n⌊n/2⌋)2n.|f(x,y)-f(x-1,y+1)|\le \frac{2\binom n{\lfloor n/2\rfloor}}{2^n}.Но (n⌊n/2⌋)=o(2n)\binom n{\lfloor n/2\rfloor}=o(2^n), така че при n→∞n\to\infty дясната страна клони към 00. Значиf(x,y)=f(x−1,y+1)f(x,y)=f(x-1,y+1)за всички цели x,yx,y. Следователно ff е константна върху всяка права x+y=constx+y=\text{const}. Нека стойността върху правата x+y=sx+y=s е g(s)g(s). Даденото уравнение даваg(s)=g(s−1)+g(s−1)2=g(s−1).g(s)=\frac{g(s-1)+g(s-1)}2=g(s-1).Значи всички стойности g(s)g(s) са равни, а оттук ff е константна върху цялото Z2\mathbb Z^2.
Отвори задачатаEvan Chen VONVON TST 2018/2Условие — източник

Задача 4

Пълен запис
Условие
Нека nn е положително цяло число и нека S⊆{0,1}nS\subseteq\{0,1\}^n е множество от двоични низове с дължина nn. За нечетен брой низове x1,…,x2k+1∈Sx_1,\ldots,x_{2k+1}\in S, не непременно различни, тяхното мнозинство е низът y∈{0,1}ny\in\{0,1\}^n, чийто ii-ти бит е най-често срещаният бит измежду ii-тите битове на x1,…,x2k+1x_1,\ldots,x_{2k+1}. Например при n=4n=4 мнозинството на 0000,0000,1101,1100,01010000,0000,1101,1100,0101 е 01000100. Да кажем, че SS има свойството PkP_k, ако мнозинството на всеки 2k+12k+1 низа от SS, с възможни повторения, също принадлежи на SS. Докажете, че ако SS има свойството PkP_k за някое положително цяло число kk, то SS има свойството PrP_r за всяко положително цяло число rr.
РешениеЩе докажем по-силно, че за фиксирано nn всички свойства PkP_k са еквивалентни. Индукцията е по nn. При n=1n=1 твърдението е очевидно, а при n=2n=2 се проверява директно: всяко множество от двумерни двоични низове, затворено относно някакво нечетно мнозинство, е затворено и относно мнозинство на три низа. Нека n≥3n\ge3 и да приемем, че твърдението е доказано за дължина n−1n-1. Да допуснем, че S⊆{0,1}nS\subseteq\{0,1\}^n има свойството PℓP_\ell, но няма свойството PkP_k. Тогава съществуват низове x1,…,x2k+1∈Sx_1,\ldots,x_{2k+1}\in S, чието мнозинствоy=M(x1,…,x2k+1)y=M(x_1,\ldots,x_{2k+1})не принадлежи на SS. Ще докажем следното твърдение. Нека yiy_i е низът, който се различава от yy само в ii-тия бит. Тогава yi∈Sy_i\in S. Наистина, за низ ss нека s^\widehat s е низът, получен от ss чрез изтриване на ii-тия бит. РазглеждамеT={s^∣s∈S}⊆{0,1}n−1.T=\{\widehat s\mid s\in S\}\subseteq\{0,1\}^{n-1}.Понеже изтриването на един бит комутира с вземането на мнозинство, от свойството PℓP_\ell за SS следва свойството PℓP_\ell за TT. По индукционната хипотеза TT има и свойството PkP_k. СледователноM(x^1,…,x^2k+1)=y^M(\widehat{x}_1,\ldots,\widehat{x}_{2k+1})=\widehat yпринадлежи на TT. Значи има s∈Ss\in S с s^=y^\widehat s=\widehat y. Такъв низ ss може да бъде само yy или yiy_i. Но y∉Sy\notin S, затова s=yis=y_i, както искахме. Сега вземаме общо 2ℓ+12\ell+1 низа измежду y1,…,yny_1,\ldots,y_n, като броят на копията на кои да е два от тях се различава с най-много 11. Понеже n≥3n\ge3, нито един от низовете yiy_i не е взет повече от ℓ\ell пъти. При фиксирана координата ii само низът yiy_i има бит, различен от съответния бит на yy; всички останали избрани низове имат бита на yy. Затова мнозинството на избраните 2ℓ+12\ell+1 низа е точно yy. Но всички избрани низове лежат в SS, а SS има свойството PℓP_\ell. Следователно и тяхното мнозинство yy трябва да лежи в SS, противоречие. Това завършва индукцията и доказва задачата.
Отвори задачатаEvan Chen VONVON TST 2018/4Условие — източник

Задача 6

Пълен запис
Условие
Алиса и Боб играят игра. Първо Алиса тайно избира крайно множество SS от решетъчни точки в декартовата равнина. После за всяка права ℓ\ell в равнината, която е хоризонтална, вертикална или има наклон +1+1 или −1-1, тя казва на Боб броя на точките от SS, лежащи на ℓ\ell. Боб печели, ако след това може да определи множеството SS. Докажете, че ако Алиса избере SS във видаS={(x,y)∈Z2∣m≤x2+y2≤n}S=\{(x,y)\in\mathbb Z^2\mid m\le x^2+y^2\le n\}за някои положителни цели числа mm и nn, то Боб може да спечели. Боб не знае предварително, че SS е от този вид.
РешениеБоб веднага знае броя N=∣S∣N=|S|, като събере точките по вертикалните прави. Ще използваме следното твърдение. За фиксирани mm и nn от условието, измежду всички множества T⊆Z2T\subseteq\mathbb Z^2 с NN точки множеството SS е единственото, което максимизираF(T)=∑(x,y)∈T(x2+y2)(m+n−(x2+y2)).F(T)=\sum_{(x,y)\in T}(x^2+y^2)(m+n-(x^2+y^2)).Действително, отделните точки не си взаимодействат в тази сума. Стойността за точка зависи само от r=x2+y2r=x^2+y^2 и еr(m+n−r)=(m+n2)2−(r−m+n2)2.r(m+n-r)=\left(\frac{m+n}2\right)^2-\left(r-\frac{m+n}2\right)^2.Тя е най-голяма точно за стойности на rr, най-близки до (m+n)/2(m+n)/2. Понеже SS съдържа точно всички решетъчни точки с m≤r≤nm\le r\le n, това са точно най-големите NN възможни приноса, и максимизаторът е единствен. Значи е достатъчно да покажем, че от данните Боб може да изчисли F(S)F(S). Нека (X,Y)(X,Y) е равномерно избрана случайна точка от SS. Данните по вертикалните прави дават разпределението на XX, данните по хоризонталните прави дават разпределението на YY, а данните по правите с наклон −1-1 и +1+1 дават съответно разпределенията на X+YX+Y и X−YX-Y. Следователно Боб може да изчисли моментите на всяка от четирите величини XX, YY, X+YX+Y, X−YX-Y. СегаF(S)N=E[(m+n)(X2+Y2)−(X2+Y2)2]=(m+n)(E[X2]+E[Y2])−E[X4]−E[Y4]−2E[X2Y2].\begin{align*} \frac{F(S)}N &=\mathbb E\left[(m+n)(X^2+Y^2)-(X^2+Y^2)^2\right]\\ &=(m+n)(\mathbb E[X^2]+\mathbb E[Y^2])-\mathbb E[X^4]-\mathbb E[Y^4]-2\mathbb E[X^2Y^2]. \end{align*}Остава смесеният момент. Той също се изразява чрез известните разпределения, защотоE[X2Y2]=\mathbb E[X^2Y^2]=E[(X+Y)4]+E[(X−Y)4]−2E[X4]−2E[Y4]12.\frac{\mathbb E[(X+Y)^4]+\mathbb E[(X-Y)^4]-2\mathbb E[X^4]-2\mathbb E[Y^4]}{12}.Така F(S)F(S) се изчислява от информацията, която Алиса е дала. Накрая, ако някое друго крайно множество TT дава същите отговори на всички въпроси на Боб, то има същия брой точки и същите разпределения на XX, YY, X+YX+Y и X−YX-Y, следователно същата стойност на FF. По твърдението за единственост на максимизатора получаваме T=ST=S. Значи данните определят SS еднозначно и Боб може да спечели.
Отвори задачатаEvan Chen VONVON TST 2018/6Условие — източник