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

Evan Chen / USA TST Solutions

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

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

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

2020

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

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

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

11-12

4 задачи

Задача 1

Пълен запис
Условие
Избират се положителни цели числа b1,b2,…b_1,b_2,\ldots, така че1=b112>b222>b332>b442>⋯ .1=\frac{b_1}{1^2}\gt{}\frac{b_2}{2^2}\gt{}\frac{b_3}{3^2}\gt{}\frac{b_4}{4^2}\gt{}\cdots.Нека rr е най-голямото реално число, за което bnn2≥r\frac{b_n}{n^2}\ge r за всяко положително цяло число nn. Намерете всички възможни стойности на rr при всички допустими избори на редицата (bn)(b_n).
РешениеОтговорът е всички реални числа rr с 0≤r≤120\le r\le\frac12. Първо, очевидно r≥0r\ge0. Ще докажем горната граница. Твърдим, че за всяко n≥1n\ge1 е изпълненоbnn2≤12+12n.\frac{b_n}{n^2}\le \frac12+\frac1{2n}.Доказателството е по индукция. При n=1n=1 това следва от b1=1b_1=1. За индукционната стъпка имамеbn<n2bn−1(n−1)2≤n2(12+12(n−1))=n32(n−1)=12(n2+n+1+1n−1)=n(n+1)2+12(1+1n−1)≤n(n+1)2+1.\begin{align*} b_n&\lt{}n^2\frac{b_{n-1}}{(n-1)^2}\le n^2\left(\frac12+\frac1{2(n-1)}\right)\\ &=\frac{n^3}{2(n-1)}=\frac12\left(n^2+n+1+\frac1{n-1}\right)\\ &=\frac{n(n+1)}2+\frac12\left(1+\frac1{n-1}\right)\le \frac{n(n+1)}2+1. \end{align*}Понеже bnb_n е цяло число, оттук следва bn≤n(n+1)2b_n\le\frac{n(n+1)}2, което е точно желаното неравенство. При n→∞n\to\infty получаваме r≤12r\le\frac12. Остава да построим редици за всички стойности в този интервал. За r=12r=\frac12 вземамеbn=n(n+1)2,b_n=\frac{n(n+1)}2,а за r=0r=0 вземаме bn=1b_n=1 за всяко nn. Нека сега 0<r<120\lt{}r\lt{}\frac12. Избираме NN достатъчно голямо, така че⌈rn2+n⌉<n(n+1)2\left\lceil rn^2+n\right\rceil\lt{}\frac{n(n+1)}2за всяко n≥Nn\ge N, и дефинирамеbn={⌈rn2+n⌉,n≥N,n2+n2,n<N.b_n=\begin{cases}\left\lceil rn^2+n\right\rceil,& n\ge N,\\ \frac{n^2+n}2,& n\lt{}N.\end{cases}Тогаваbnn2=rn2+n+O(1)n2→r,\frac{b_n}{n^2}=\frac{rn^2+n+O(1)}{n^2}\to r,така че най-голямата долна граница е rr. Остава само да проверим, че дробите са строго намаляващи. Това е ясно за n<Nn\lt{}N от формулата n+12n\frac{n+1}{2n}, а преходът през NN е осигурен от избора на NN. За n≥Nn\ge N имамеbnn2≥rn2+nn2>\frac{b_n}{n^2}\ge\frac{rn^2+n}{n^2}\gt{}r(n+1)2+(n+1)+1(n+1)2≥bn+1(n+1)2,\frac{r(n+1)^2+(n+1)+1}{(n+1)^2}\ge\frac{b_{n+1}}{(n+1)^2},където средното неравенство е еквивалентно на 1n>n+2(n+1)2\frac1n\gt{}\frac{n+2}{(n+1)^2}. Следователно конструкцията работи.
Отвори задачатаEvan Chen VONVON TST 2020/1Условие — източник

Задача 3

Пълен запис
Условие
Нека α≥1\alpha\ge1 е реално число. Хефест и Посейдон играят походова игра върху безкрайна квадратна мрежа от единични клетки. Преди началото на играта Посейдон избира краен брой клетки, които са наводнени. Хефест строи дига: множество от единични ребра на мрежата, наричани стени, които образуват свързан несамопресичащ се път или контур. Играта започва с ход на Хефест. На своя nn-ти ход той добавя една или повече стени към дигата, стига след този ход общата дължина на дигата да е най-много αn\alpha n. На всеки ход на Посейдон всяка клетка, която е съседна по страна на вече наводнена клетка и между тях няма стена, също се наводнява. Хефест печели, ако дигата образува затворен контур, в чиято вътрешност се намират всички наводнени клетки, и така спре потопа. За кои стойности на α\alpha Хефест може да си гарантира победа за краен брой ходове, независимо кои клетки е наводнил Посейдон в началото?
РешениеОтговорът еα>2.\alpha\gt{}2.Ще докажем, че при α>2\alpha\gt{}2 Хефест има печеливша стратегия, а при α=2\alpha=2 (следователно и при α≤2\alpha\le2) той не може да овладее дори потоп, започнал от една клетка. Първо нека α>2\alpha\gt{}2. Въвеждаме координати от Z2\mathbb Z^2 върху клетките. Ако вместо първоначалното множество наводним повече клетки, задачата за Хефест само става по-трудна, затова можем да предположим, че в началото са наводнени всички клетки (x,y)(x,y) с∣x∣+∣y∣≤d|x|+|y|\le dза някое d≥2d\ge2. Тогава на kk-тия ход на Хефест водата се съдържа в областта ∣x∣+∣y∣≤d+k−1|x|+|y|\le d+k-1. Целта е да я затворим в голям правоъгълник. Избираме големи цели числа N1N_1 и N2N_2, за коитоαN1>2N1+(2d+3),α(N1+N2)>2N2+(6N1+8d+4).\begin{align*} \alpha N_1&\gt{}2N_1+(2d+3),\\ \alpha(N_1+N_2)&\gt{}2N_2+(6N_1+8d+4). \end{align*}Маркираме точките Xi,YiX_i,Y_i за 1≤i≤61\le i\le6, както е показано на схемата; червените означения показват съответните разстояния по страните на правоъгълника.X1Y1X2Y2X3Y3X4Y4X5Y5X6Y61N1N1ddd+1d+1N2N2N1+dN1+dСтратегията е следната. 1. На ход 11 Хефест поставя стената X1Y1X_1Y_1. Така спира разпространението на север. 2. От ход 22 до ход N1+1N_1+1 той удължава дигата до отсечката X2Y2X_2Y_2, като продължава да не допуска вода на север. 3. На ход N1+2N_1+2 добавя наведнъж начупените линии X4X3X2X_4X_3X_2 и Y4Y3Y2Y_4Y_3Y_2. Така спира потопа от запад и от изток. 4. От ход N1+2N_1+2 до ход N1+N2+1N_1+N_2+1 удължава дигата по отсечките X4X5X_4X_5 и Y4Y5Y_4Y_5, като държи водата между тях. 5. На ход N1+N2+2N_1+N_2+2 добавя наведнъж начупената линия X5X6Y6Y5X_5X_6Y_6Y_5 и затваря контура. Изборът на N1N_1 и N2N_2 гарантира две неща едновременно: всяка нова част от дигата се поставя преди водата да я достигне, и общата дължина след съответния ход остава под разрешената граница αn\alpha n. Следователно при всяко α>2\alpha\gt{}2 Хефест може да спре потопа за краен брой ходове. Остава да докажем, че α=2\alpha=2 не стига. Нека първоначално е наводнена само една клетка и да допуснем, че Хефест затваря потопа на своя (n+1)(n+1)-ви ход. Ще покажем, че тогава вече са построени поне 2n+42n+4 стени. Нека c0,c1,…,cnc_0,c_1,\ldots,c_n са клетки, такива че c0c_0 е първоначално наводнената клетка, а за i≥1i\ge1 клетката cic_i се наводнява на ii-тия ход на Посейдон от клетката ci−1c_{i-1}. В края дигата е затворен контур, който съдържа всички тези клетки. Твърдим, че ако cic_i и cjc_j са съседни клетки, то ∣i−j∣=1|i-j|=1. Наистина, ако са съседни и ∣i−j∣>1|i-j|\gt{}1, между тях трябва да има стена; но тогава затворената дига поставя двете клетки от различни страни на контура, противоречие. Значи клетките cic_i образуват път от клетки. Оцветяваме в зелено всяко ребро на единичната мрежа, което е ребро на точно една от клетките cic_i; това са ребрата от границата на полученото полимино. Понеже полиминото има n+1n+1 клетки и точно nn вътрешни общи ребра, зелените ребра са точно4(n+1)−2n=2n+4.4(n+1)-2n=2n+4.От центъра на всяка клетка cic_i изпращаме по един лазер към всяко зелено ребро на тази клетка. Така имаме общо 2n+42n+4 лазера. На схемата е показан пример за n=6n=6, като дигата е отбелязана в кафяво.c0c1c2c3c4c5c6Ще докажем, че никоя стена не може да бъде улучена от повече от един лазер. Да допуснем противното и нека стената ww е улучена от лазери, излизащи от cic_i и cjc_j. Без загуба на общност тези два лазера са вертикални, така че cic_i и cjc_j са в една и съща колона. Ако ww лежи между cic_i и cjc_j, то отсечката между центровете им пресича дигата точно веднъж, а двата му края са вътре в затворения контур. Това е невъзможно. Остава случаят, когато ww лежи от една и съща страна на двете клетки; например над тях, като i<ji\lt{}j. Тогава между cic_i и cjc_j няма стена. Нека ρ≥1\rho\ge1 е разстоянието между центровете на cic_i и cjc_j. Клетката cjc_j се наводнява от cic_i по права линия за най-много ρ\rho хода, а това е единственият най-кратък път. Следователно такава ситуация е възможна само ако j=i+ρj=i+\rho и клетките ci,ci+1,…,cjc_i,c_{i+1},\ldots,c_j образуват една колона. Но тогава вертикалните лазери от cic_i и cjc_j не могат да сочат в една и съща посока, противоречие. Следователно всяка от 2n+42n+4-те лазерни отсечки удря различна стена. Значи на (n+1)(n+1)-вия ход дължината на дигата е поне 2n+42n+4, откъдетоα≥2n+4n+1>2.\alpha\ge\frac{2n+4}{n+1}\gt{}2.Това доказва, че при α=2\alpha=2 Хефест няма гарантирана победа, и завършва решението.
Отвори задачатаEvan Chen VONVON TST 2020/3Условие — източник

Задача 4

Пълен запис
Условие
За краен прост граф GG дефинираме G′G' като граф върху същото множество от върхове, в който за два различни върха uu и vv двойката {u,v}\{u,v\} е ребро в G′G' точно когато uu и vv имат общ съсед в GG. Докажете, че ако крайният прост граф GG е изоморфен на (G′)′(G')', то GG е изоморфен и на G′G'.
РешениеЩе наречем връх на графа опасен, ако има степен поне 33 и някои два от съседите му не са съседни помежду си. Първо твърдим, че G′G' има поне толкова триъгълници, колкото GG, а има строго повече, ако GG има опасен връх. Наистина, всеки триъгълник в GG остава триъгълник в G′G', защото всяка двойка негови върхове има третия за общ съсед. Ако vv е опасен връх, съседите на vv образуват клика в G′G', която не е била клика в GG; следователно се появява поне един нов триъгълник. Ако G≅(G′)′G\cong(G')', броят на триъгълниците в GG и в (G′)′(G')' е един и същ. От току-що доказаното следва, че нито GG, нито G′G' може да има опасен връх. Значи е достатъчно да разгледаме графи без опасни върхове. В такъв граф всяка свързана компонента е един от следните видове: клика, включително единичен връх; цикъл; или път. Наистина, ако някой връх има степен поне 33, всички негови съседи трябва да са съседни помежду си, и същото условие се разпространява в компонентата, която става клика. Ако максималната степен е най-много 22, компонентата е път или цикъл. Сега наблюдаваме кои от тези компоненти са устойчиви при операцията. Изолиран връх, цикъл с нечетна дължина и клика с поне три върха се преобразуват в изоморфни компоненти. От друга страна, цикъл с четна дължина и път с ненулева дължина се разпадат на повече свързани компоненти при преминаване към G′G'. Следователно, ако GG има такава компонента, тогава G′G' има строго повече свързани компоненти от GG, а (G′)′(G')' има поне толкова, колкото G′G'. Това е несъвместимо с G≅(G′)′G\cong(G')'. Затова графите, които могат да удовлетворят G≅(G′)′G\cong(G')', са точно несвързани обединения на изолирани върхове, нечетни цикли и клики с поне три върха. За всяка от тези компоненти вече видяхме, че G′≅GG'\cong G върху компонентата, следователно и за целия граф имаме G≅G′G\cong G'. Това доказва твърдението.
Отвори задачатаEvan Chen VONVON TST 2020/4Условие — източник

Задача 5

Пълен запис
Условие
Намерете всички цели числа n≥2n\ge2, за които съществуват цяло число mm и полином P(x)P(x) с цели коефициенти, удовлетворяващи следните три условия: - m>1m\gt{}1 и gcd⁡(m,n)=1\gcd(m,n)=1; - числата P(0),P2(0),…,Pm−1(0)P(0),P^2(0),\ldots,P^{m-1}(0) не се делят на nn; - числото Pm(0)P^m(0) се дели на nn. Тук PkP^k означава kk-кратно прилагане на PP, така че P1(0)=P(0)P^1(0)=P(0), P2(0)=P(P(0))P^2(0)=P(P(0)) и т.н.
РешениеОтговорът е: това е възможно точно когато съществуват прости числа p′<pp'\lt{}p, такива че p∣np\mid n, но p′∤np'\nmid n. Еквивалентно, радикалът на nn не е произведение на първите няколко прости числа. За полином PP и цяло число NN въвеждаме означениетоzord(P mod N)=min⁡{e>0∣Pe(0)≡0(modN)},\mathbf{zord}(P\bmod N)=\min\{e\gt{}0\mid P^e(0)\equiv0\pmod N\},като по условие минимумът на празното множество е 00. По китайската теорема за остатъците имамеzord(P mod N)=lcm⁡q∣Nzord(P mod q),(1)\mathbf{zord}(P\bmod N)=\operatorname*{lcm}_{q\mid N}\mathbf{zord}(P\bmod q),\tag{1}където qq пробягва простите степени, делящи NN. Първо ще направим конструкцията. Нужен ни е следният случай на проста степен. Нека pep^e е проста степен и 1≤k<p1\le k\lt{}p. Тогава полиномътf(X)=f(X)=X+1−k⋅X(X−1)(X−2)⋯(X−(k−2))(k−1)!,X+1-k\cdot\frac{X(X-1)(X-2)\cdots(X-(k-2))}{(k-1)!},разглеждан в (Z/peZ)[X](\mathbb Z/p^e\mathbb Z)[X], удовлетворяваzord(f mod pe)=k.\mathbf{zord}(f\bmod p^e)=k.При k=1k=1 произведението е празно и се приема за 11. Наистина, понеже (k−1)!(k-1)! е обратимо по модул pep^e, формулата е смислена, а директно получавамеf(0)=1,f(1)=2,…,f(0)=1,\quad f(1)=2,\quad\ldots,f(k−2)=k−1,f(k−1)=0.\quad f(k-2)=k-1,\quad f(k-1)=0.Сега нека p′<pp'\lt{}p са прости числа, p∣np\mid n и p′∤np'\nmid n. За простата степен pe∣np^e\mid n с основа pp избираме полином по горната лема с zord=p′\mathbf{zord}=p'. За всяка друга проста степен qq, деляща nn, изискваме P(0)≡0(modq)P(0)\equiv0\pmod q, тоест zord(P mod q)=1\mathbf{zord}(P\bmod q)=1. Китайската теорема за остатъците позволява да изберем един полином P∈Z[x]P\in\mathbb Z[x], който удовлетворява всички тези условия едновременно. От (1) следваzord(P mod n)=p′.\mathbf{zord}(P\bmod n)=p'.Поставяме m=p′m=p'. Тогава m>1m\gt{}1, gcd⁡(m,n)=1\gcd(m,n)=1, защото p′∤np'\nmid n, и условията на задачата са изпълнени. Остава необходимостта. По (1) е достатъчно да докажем следното твърдение: ако q=peq=p^e е проста степен и f(x)∈Z[x]f(x)\in\mathbb Z[x], а zord(f mod q)\mathbf{zord}(f\bmod q) е ненулево число, то всички негови прости делители са най-много pp. Доказваме това по индукция по ee. При e=1e=1 принципът на Дирихле дава веднага zord(f mod p)≤p\mathbf{zord}(f\bmod p)\le p, защото преди първото попадане в 00 остатъците 0,f(0),f2(0),…0,f(0),f^2(0),\ldots не могат да съдържат повторение извън 00. Нека e≥2e\ge2 и поставимk=zord(f mod pe−1),Q=fk.k=\mathbf{zord}(f\bmod p^{e-1}),\qquad Q=f^k.За да се стигне до 00 по модул pep^e, първо трябва да се стигне до 00 по модул pe−1p^{e-1}, затоваzord(f mod pe)=k⋅zord(Q mod pe).\mathbf{zord}(f\bmod p^e)=k\cdot\mathbf{zord}(Q\bmod p^e).По индукционната хипотеза всички прости делители на kk са най-много pp. Освен това Q(0)≡0(modpe−1)Q(0)\equiv0\pmod{p^{e-1}}, а оттук и всички числа Q(0),Q2(0),…Q(0),Q^2(0),\ldots са кратни на pe−1p^{e-1}. По модул pep^e има само pp такива остатъка, следователноzord(Q mod pe)≤p.\mathbf{zord}(Q\bmod p^e)\le p.Така и zord(f mod pe)\mathbf{zord}(f\bmod p^e) има само прости делители, които са най-много pp. Сега нека за дадено nn съществуват mm и PP от условието. Тогава m=zord(P mod n)m=\mathbf{zord}(P\bmod n) и gcd⁡(m,n)=1\gcd(m,n)=1. От (1) някоя проста степен pe∣np^e\mid n има ред, делящ се на някой прост делител p′p' на mm. По току-що доказаното p′≤pp'\le p, а от gcd⁡(m,n)=1\gcd(m,n)=1 следва p′∤np'\nmid n. Ако беше p′=pp'=p, това би противоречало на p∣np\mid n, значи p′<pp'\lt{}p. Получаваме точно необходимото условие.
Отвори задачатаEvan Chen VONVON TST 2020/5Условие — източник