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

Evan Chen / USA TSTST Solutions

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

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

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

2015

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Нека a1,a2,…,ana_1,a_2,\ldots,a_n е редица от реални числа и нека m<nm\lt{}n е фиксирано положително цяло число. Ще наричаме индекс kk с 1≤k≤n1\le k\le n добър, ако съществува ℓ\ell с 1≤ℓ≤m1\le\ell\le m, такова чеak+ak+1+⋯+ak+ℓ−1≥0,a_k+a_{k+1}+\dotsb+a_{k+\ell-1}\ge0,където индексите се вземат по модул nn. Нека TT е множеството на всички добри индекси. Докажете, че∑k∈Tak≥0.\sum_{k\in T}a_k\ge0.
РешениеПърво доказваме твърдението в нецикличен вариант, т.е. когато индексите не се вземат по модул nn. Ще казваме, че индексът kk е ℓ\ell-добър, ако ℓ\ell е най-малкото число, за коетоak+ak+1+⋯+ak+ℓ−1≥0,a_k+a_{k+1}+\cdots+a_{k+\ell-1}\ge0,и освен това ℓ≤m\ell\le m. Ако kk е ℓ\ell-добър, тогава индексите k+1,k+2,…,k+ℓ−1k+1,k+2,\ldots,k+\ell-1 също са добри: за всеки от тях можем да вземем съответната опашка на същия блок, а минималността на ℓ\ell показва, че предходните частични суми са отрицателни. Сега минаваме отляво надясно с алчен алгоритъм. Вземаме първия добър индекс, да кажем че е ℓ\ell-добър, и групираме блокаak,ak+1,…,ak+ℓ−1.a_k,a_{k+1},\ldots,a_{k+\ell-1}.Сумата на този блок е неотрицателна, а всички негови индекси са добри. После продължаваме след края на блока и повтаряме. Така всички добри индекси в нецикличната редица се разбиват на неприпокриващи се блокове с неотрицателни суми. Следователно сумата на членовете с добри индекси е неотрицателна. Връщаме се към цикличната задача. Нека NN е голямо положително цяло число и запишем една след друга NN копия на дадената циклична редица. Прилагаме току-що доказания нецикличен резултат към тази дълга редица. Всички вътрешни копия дават точно същите добри индекси като в цикличната задача; разлика може да се появи само в краищата, където блоковете могат да бъдат отрязани. Затова получаваме неравенство от видаN∑k∈Tak+cN≥0,N\sum_{k\in T}a_k+c_N\ge0,където грешката cNc_N идва само от краищата. Тя е ограничена независимо от NN; например може да се оцени чрез константа, зависеща само от a1,…,ana_1,\ldots,a_n и mm. Делим на NN и пускаме NN да расте. Получаваме∑k∈Tak≥0,\sum_{k\in T}a_k\ge0,както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2015/1Условие — източник

Задача 3

Пълен запис
Условие
Нека PP е множеството на всички прости числа, а MM е непразно подмножество на PP. Да се предположи, че за всяко непразно подмножество {p1,p2,…,pk}\{p_1,p_2,\ldots,p_k\} на MM всички прости делители наp1p2⋯pk+1p_1p_2\cdots p_k+1също принадлежат на MM. Докажете, че M=PM=P.
РешениеПърво MM е безкрайно: ако умножим всички известни елементи на MM и прибавим 11, получаваме нов прост делител от MM. Да допуснем за противоречие, че съществува просто число p∉Mp\notin M. Ще наричаме простото число q∈Mq\in M рядко, ако има само краен брой елементи на MM, които са сравними с qq по модул pp. Има само краен брой редки прости числа, защото има само краен брой класове по модул pp. Нека CC е произведението на всички редки прости числа; ако такива няма, вземаме C=1C=1. Понеже p∉Mp\notin M, имаме p∤Cp\nmid C. Започваме с a0=1a_0=1. За k≥0k\ge0 разглеждаме простото разлагане наCak+1.Ca_k+1.Всеки негов прост делител принадлежи на MM по условието, приложено към простите множители на aka_k заедно с редките множители в CC. Освен това никой от тези прости делители не е рядък, защото редките прости вече делят CC, а следователно не делят Cak+1Ca_k+1. За всеки прост делител на Cak+1Ca_k+1 избираме произволен елемент на MM в същия остатъчен клас по модул pp, различен от всички вече избрани; това е възможно, понеже класът не е рядък. Нека ak+1a_{k+1} е произведението на избраните представители, всеки по веднъж. Тогава ak+1a_{k+1} е произведение на различни прости числа от MM иak+1≡Cak+1(modp).a_{k+1}\equiv Ca_k+1\pmod p.Следователно по индукцияak≡Ck+Ck−1+⋯+1(modp).a_k\equiv C^k+C^{k-1}+\cdots+1\pmod p.Понеже C≢0(modp)C\not\equiv0\pmod p, можем да изберем kk, за което дясната страна е 00 по модул pp: ако C≡1(modp)C\equiv1\pmod p, вземаме k=p−1k=p-1, а иначе вземаме k=p−2k=p-2, тъй като тогава1+C+⋯+Cp−2=Cp−1−1C−1≡0(modp).1+C+\cdots+C^{p-2}=\frac{C^{p-1}-1}{C-1}\equiv0\pmod p.Получаваме p∣akp\mid a_k. Това е невъзможно, защото aka_k е произведение на прости числа от MM, а p∉Mp\notin M. Противоречието доказва, че M=PM=P.
Отвори задачатаEvan Chen VONVON TSTST 2015/3Условие — източник

Задача 4

Пълен запис
Условие
Нека x,y,zx,y,z са реални числа, не непременно положителни, такива чеx4+y4+z4+xyz=4.x^4+y^4+z^4+xyz=4.Докажете, че x≤2x\le2 иx22−x≥y+z2.\sqrt{\vphantom{x^2}2-x}\ge\frac{y+z}{2}.
РешениеПърво доказваме по-лесното твърдение x≤2x\le2. Имаме5=x4+y4+(z4+1)+xyz=3x44+(x44+y4)+(z4+1)+xyz≥3x44+x2y2+2z2+xyz.\begin{align*} 5&=x^4+y^4+(z^4+1)+xyz\\ &=\frac{3x^4}{4}+\left(\frac{x^4}{4}+y^4\right)+(z^4+1)+xyz\\ &\ge \frac{3x^4}{4}+x^2y^2+2z^2+xyz. \end{align*}Последните три члена са неотрицателни, защото x2y2+xyz+2z2x^2y^2+xyz+2z^2 е положително определена квадратна форма в xyxy и zz. Следователно x4≤20/3<16x^4\le20/3\lt{}16, откъдето x<2x\lt{}2, и в частност x≤2x\le2. Остава да докажем второто неравенство. Ако (y+z)/2≤0(y+z)/2\le0, то е очевидно. В противен случай е достатъчно да докажем квадрата му, тоест2−x≥(y+z2)2.2-x\ge\left(\frac{y+z}{2}\right)^2.Да допуснем противното:2−x<(y+z2)2,2-x\lt{}\left(\frac{y+z}{2}\right)^2,или еквивалентно4x+y2+2yz+z2>8.4x+y^2+2yz+z^2\gt{}8.От неравенстватаx4+3≥4x,y4+12≥y2,z4+12≥z2x^4+3\ge4x,\qquad \frac{y^4+1}{2}\ge y^2,\qquad \frac{z^4+1}{2}\ge z^2получавамеx4+y4+z42+2yz+4>8.x^4+\frac{y^4+z^4}{2}+2yz+4\gt{}8.Заместваме x4=4−y4−z4−xyzx^4=4-y^4-z^4-xyz и намираме−y4+z42+(2−x)yz>0.-\frac{y^4+z^4}{2}+(2-x)yz\gt{}0.Следователно yz>0yz\gt{}0 иy4+z42yz<2−x<(y+z2)2.\frac{y^4+z^4}{2yz}\lt{}2-x\lt{}\left(\frac{y+z}{2}\right)^2.Умножавайки по 4yz>04yz\gt{}0, получаваме2y4+2z4<yz(y+z)2=y3z+2y2z2+yz3.2y^4+2z^4\lt{}yz(y+z)^2=y^3z+2y^2z^2+yz^3.Това е невъзможно, защото при yz>0yz\gt{}0 разликата на лявата и дясната страна е2y4−y3z−2y2z2−yz3+2z4=2y^4-y^3z-2y^2z^2-yz^3+2z^4=(y−z)2(2y2+3yz+2z2)≥(y-z)^2(2y^2+3yz+2z^2)\ge0.0.Противоречието доказва желаното неравенство.
Отвори задачатаEvan Chen VONVON TSTST 2015/4Условие — източник

Задача 5

Пълен запис
Условие
Нека φ(n)\varphi(n) означава броя на положителните цели числа, по-малки от nn, които са взаимно прости с nn. Докажете, че съществува положително цяло число mm, за което уравнениетоφ(n)=m\varphi(n)=mима поне 20152015 решения за nn.
РешениеЩе дадем конструкция с най-малките прости числа. Нека2=p1<p2<⋯<p20152=p_1\lt{}p_2\lt{}\cdots\lt{}p_{2015}са най-малките 20152015 прости числа. Разглеждаме следните 20152015 числа:n1=(p1−1)p2p3⋯p2015,n2=p1(p2−1)p3⋯p2015,⋮n2015=p1p2⋯p2014(p2015−1).\begin{align*} n_1&=(p_1-1)p_2p_3\cdots p_{2015},\\ n_2&=p_1(p_2-1)p_3\cdots p_{2015},\\ &\vdots\\ n_{2015}&=p_1p_2\cdots p_{2014}(p_{2015}-1). \end{align*}Ще покажем, че всички те имат една и съща стойност на функцията на Ойлер. Фиксираме ii. Числото pi−1p_i-1 има само прости делители, по-малки от pip_i, защото е по-малко от pip_i. Тези прости делители са сред p1,p2,…,pi−1p_1,p_2,\ldots,p_{i-1}. Следователно простите делители на nin_i са точно сред p1,p2,…,p2015p_1,p_2,\ldots,p_{2015}, като pip_i не се появява. Използваме мултипликативната формулаφ(N)=N∏q∣N(1−1q).\varphi(N)=N\prod_{q\mid N}\left(1-\frac1q\right).Тъй като новите прости множители от pi−1p_i-1 вече са сред по-малките pjp_j, директно получавамеφ(ni)=(pi−1)∏j≠i(pj−1)=\varphi(n_i)=(p_i-1)\prod_{j\ne i}(p_j-1)=∏j=12015(pj−1).\prod_{j=1}^{2015}(p_j-1).Така всички числа n1,n2,…,n2015n_1,n_2,\ldots,n_{2015} са решения на едно и също уравнение φ(n)=m\varphi(n)=m, къдетоm=∏j=12015(pj−1).m=\prod_{j=1}^{2015}(p_j-1).Остава само да отбележим, че числата nin_i са различни. Ако i<ji\lt{}j, то pjp_j дели nin_i, но не дели njn_j: наистина pjp_j не дели pj−1p_j-1, а всички останали фактори в njn_j са по-малки от pjp_j или са различни прости числа. Следователно имаме поне 20152015 различни решения, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2015/5Условие — източник

Задача 6

Пълен запис
Условие
Ним-подобна игра се задава по следния начин. Избират се две положителни цели числа kk и nn, както и крайно множество SS от kk-орки цели числа (не непременно положителни). В началото на играта на дъската е записана kk-орката (n,0,0,…,0)(n,0,0,\ldots,0). Разрешен ход се състои в това да се изтрие записаната kk-орка (a1,a2,…,ak)(a_1,a_2,\ldots,a_k) и да се замени с (a1+b1,a2+b2,…,ak+bk)(a_1+b_1,a_2+b_2,\ldots,a_k+b_k), където (b1,b2,…,bk)∈S(b_1,b_2,\ldots,b_k)\in S. Двама играчи се редуват да правят разрешени ходове, а първият, който запише отрицателно цяло число, губи. Ако никой от играчите никога не бъде принуден да запише отрицателно цяло число, играта е реми. Докажете, че съществува избор на kk и SS със следното свойство: първият играч има печеливша стратегия, ако nn е степен на 22, а иначе вторият играч има печеливша стратегия.
РешениеЩе дадем конструкция с 1414 регистъра и 2222 хода. Регистрите саX,Y,Go⁡,SX0,SX,SX′,SY0,X,Y,\operatorname{Go},S_X^0,S_X,S_X',S_Y^0,SY,SY′,Cl⁡,A,B,Die⁡,Die⁡′.S_Y,S_Y',\operatorname{Cl},A,B,\operatorname{Die},\operatorname{Die}'.В началото X=nX=n, а всички останали регистри са нули. За компактност в таблицата пишем G=Go⁡G=\operatorname{Go}, X0=SX0X_0=S_X^0, X1=SXX_1=S_X, X2=SX′X_2=S_X', Y0=SY0Y_0=S_Y^0, Y1=SYY_1=S_Y, Y2=SY′Y_2=S_Y', C=Cl⁡C=\operatorname{Cl}, D=Die⁡D=\operatorname{Die} и D′=Die⁡′D'=\operatorname{Die}'. Нека k=14k=14, а SS е множеството от следните 2222 хода, записани като 14-орки в реда X,Y,G,X0,X1,X2,Y0,Y1,Y2,C,A,B,D,D′X,Y,G,X_0,X_1,X_2,Y_0,Y_1,Y_2,C,A,B,D,D': Init = (-1,0,1,0,0,0,0,0,0,0,0,1,1,1) Begin = (1,0,-1,1,0,0,0,0,0,0,-1,1,0,0) Sleep = (0,0,0,0,0,0,0,0,0,0,1,-1,0,0) StartX = (0,0,0,-1,1,0,0,0,0,0,-1,1,0,0) WorkX = (-1,0,0,0,-1,1,0,0,0,0,-1,1,0,0) WorkX' = (-1,1,0,0,1,-1,0,0,0,0,-1,1,0,0) DoneX = (0,0,0,0,-1,0,1,0,0,0,-1,1,0,0) WrongX = (-1,0,0,0,0,0,-1,0,0,0,0,-1,0,0) StartY = (0,0,0,0,0,0,-1,1,0,0,-1,1,0,0) WorkY = (0,-1,0,0,0,0,0,-1,1,0,-1,1,0,0) WorkY' = (1,-1,0,0,0,0,0,1,-1,0,-1,1,0,0) DoneY = (0,0,0,1,0,0,0,-1,0,0,-1,1,0,0) WrongY = (0,-1,0,-1,0,0,0,0,0,0,0,-1,0,0) ClaimX = (-1,0,0,-1,0,0,0,0,0,1,-1,1,0,0) ClaimY = (0,-1,0,0,0,0,-1,0,0,1,-1,1,0,0) FakeX = (-1,0,0,0,0,0,0,0,0,-1,0,-1,0,0) FakeY = (0,-1,0,0,0,0,0,0,0,-1,0,-1,0,0) Win = (0,0,0,0,0,0,0,0,0,-1,-1,0,0,0) PunA = (0,0,0,0,0,0,0,0,0,0,0,-2,0,0) PunB = (0,0,0,0,0,0,0,0,0,0,-1,-1,0,0) Kill = (0,0,0,0,0,0,0,0,0,0,0,-1,-2,1) Kill' = (0,0,0,0,0,0,0,0,0,0,0,-1,1,-2) Първият играч ще наричаме Алиса, а втория - Боб. Механиката се управлява от броячите AA и BB. След първия ход Алиса играе Init. По-нататък казваме, че играта е в главната част, ако A+B=1A+B=1 и никой не е играл Init втори път; във всички други случаи тя е в смъртната част. В главната част на ход на Алиса винаги е (A,B)=(1,0)(A,B)=(1,0), а на ход на Боб е (A,B)=(0,1)(A,B)=(0,1). Първо, играч, който играе Init за втори път, губи. В частност губи и играч, който трябва да мести при A=B=0A=B=0. Ако нарушителят е при A=B=0A=B=0, той е принуден да играе Init; другият играч отговаря с Kill, после нарушителят пак е принуден към Init, а другият отговаря с Kill'. Това се повтаря, докато XX стане отрицателно. Ако Алиса играе Init при (A,B)=(1,0)(A,B)=(1,0), Боб я наказва с PunB и стига до същия сценарий; ако Боб играе Init при (A,B)=(0,1)(A,B)=(0,1), Алиса го наказва с PunA. Следователно рационалната игра избягва смъртната част. Вторият ход е Sleep на Боб, после Алиса играе Begin (което възстановява стойността nn в XX), а Боб пак играе Sleep. В главната част състоянието е един от регистрите SX0,SX,SX′,SY0,SY,SY′S_X^0,S_X,S_X',S_Y^0,S_Y,S_Y' или Cl⁡\operatorname{Cl} да е равен на 11, а всички останали такива регистри да са нули. Това разделя играта на XX-фази и YY-фази. Да разгледаме XX-фаза, започваща при (X,Y)=(x,0)(X,Y)=(x,0) с x>1x\gt{}1. Алиса може да я завърши без загуба тогава и само тогава, когато xx е четно; в този случай започва YY-фаза с (X,Y)=(0,x/2)(X,Y)=(0,x/2). Наистина, при x>1x\gt{}1 ходът ClaimX е лош, защото Боб отговаря с FakeX и печели. Чрез редуване на WorkX и WorkX' Алиса намалява XX с 22 и увеличава YY с 11; Боб през това време има само Sleep. Накрая тя трябва да спре с DoneX. Ако тогава X≠0X\ne0, Боб печели с WrongX; ако X=0X=0, той може само да играе Sleep. Аналогично твърдение важи за YY-фазите. Така всеки успешен цикъл дели текущото положително число на 22 и го прехвърля между XX и YY. Ако nn не е степен на 22, в някоя фаза се появява нечетно число по-голямо от 11 и Алиса губи. Ако n=2mn=2^m, Алиса последователно стига до(X,Y)=(0,2m−1),(2m−2,0),…(X,Y)=(0,2^{m-1}),(2^{m-2},0),\ldotsи накрая до (1,0)(1,0) или (0,1)(0,1). Тогава тя играе съответно ClaimX или ClaimY и влиза в състояние Cl⁡\operatorname{Cl}. Боб вече не може да играе FakeX или FakeY, затова играе Sleep, а Алиса печели с Win. Това доказва, че първият играч печели точно когато nn е степен на 22.
Отвори задачатаEvan Chen VONVON TSTST 2015/6Условие — източник