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

Evan Chen / USA TSTST Solutions

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

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

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

2012

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

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

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

11-12

5 задачи

Задача 1

Пълен запис
Условие
Да се определят всички безкрайни низове от букви със следните свойства: (a) всяка буква е TT или SS; (b) ако на позиции ii и jj стои буквата TT, то на позиция i+ji+j стои буквата SS; (c) има безбройно много цели числа kk, за които на позиция 2k−12k-1 стои kk-тата буква TT.
РешениеЕдинственият възможен низ еT,S,T,S,T,S,…,T,S,T,S,T,S,\ldots,тоест буквата TT стои точно на нечетните позиции. Нека позициите, на които стои TT, саa1<a2<a3<⋯ .a_1\lt{}a_2\lt{}a_3\lt{}\dotsb.Тогава условието (b) казва, че не съществуват положителни цели числа i,j,ki,j,k, не непременно различни, за коитоai+aj=ak.a_i+a_j=a_k.А условието (c) казва, че за безбройно много kk имамеak=2k−1.a_k=2k-1.Фиксираме такова k>1k\gt{}1 и поставяме Ak={a1,a2,…,ak}A_k=\{a_1,a_2,\ldots,a_k\}. Всички елементи на AkA_k са между 11 и 2k−12k-1. Разглеждаме положителните разлики между два елемента на AkA_k. Никоя такава разлика не може да принадлежи на AkA_k: ако ai−aj=at>0a_i-a_j=a_t\gt{}0, то aj+at=aia_j+a_t=a_i, което противоречи на липсата на суми от вида ai+aj=aka_i+a_j=a_k. Следователно самите kk елемента на AkA_k и положителните разлики между тях са различни положителни числа, не по-големи от 2k−12k-1. Броят на положителните разлики е (∣Ak−Ak∣−1)/2(|A_k-A_k|-1)/2, затова2k−1≥∣Ak∣+∣Ak−Ak∣−12≥2k-1\ge |A_k|+\frac{|A_k-A_k|-1}{2}\gek+(2k−1)−12=2k−1, k+\frac{(2k-1)-1}{2}=2k-1,където използвахме стандартното неравенство ∣Ak−Ak∣≥2∣Ak∣−1|A_k-A_k|\ge2|A_k|-1. Следователно навсякъде има равенство. Равенството в ∣Ak−Ak∣≥2∣Ak∣−1|A_k-A_k|\ge2|A_k|-1 е възможно само когато AkA_k е аритметична прогресия. Понеже AkA_k съдържа kk положителни цели числа и най-големият му елемент е 2k−12k-1, тази прогресия трябва да бъде точноAk={1,3,5,…,2k−1}.A_k=\{1,3,5,\ldots,2k-1\}.Такива стойности на kk има безбройно много, следователно за всяко фиксирано mm можем да изберем k≥mk\ge m от тях и да получим am=2m−1a_m=2m-1. Значи всички позиции с буква TT са точно нечетните. Този низ очевидно удовлетворява условията: сборът на две нечетни позиции е четна позиция, а kk-тата буква TT е на позиция 2k−12k-1.
Отвори задачатаEvan Chen VONVON TSTST 2012/1Условие — източник

Задача 3

Пълен запис
Условие
Нека N\mathbb N е множеството на положителните цели числа. Нека f:N→Nf:\mathbb N\to\mathbb N е функция, която удовлетворява следните две условия: (a) f(m)f(m) и f(n)f(n) са взаимно прости, когато mm и nn са взаимно прости; (b) n≤f(n)≤n+2012n\le f(n)\le n+2012 за всяко nn. Докажете, че за всяко естествено число nn и всяко просто число pp, ако pp дели f(n)f(n), то pp дели nn.
РешениеНека p0,p1,p2,…p_0,p_1,p_2,\ldots е редицата на всички прости числа в произволен ред. За всяко ii избираме прост делител qiq_i на f(pi)f(p_i). Това е възможно, защото f(pi)≥pi>1f(p_i)\ge p_i\gt{}1. От условието следва, че числата f(pi)f(p_i) са взаимно прости две по две, следователно простите числа qiq_i също са различни две по две. Ще докажем, че задължително qi=piq_i=p_i за всяко ii. Да допуснем противното и след преномериране да имаме q0≠p0q_0\ne p_0, като изберем p1,p2,…,p2012p_1,p_2,\ldots,p_{2012} по-големи от 20122012. По китайската теорема за остатъците можем да намерим цяло число mm, такова че за 0≤i≤20120\le i\le2012m+i≡0(modqi),m≢0(modpi).m+i\equiv0\pmod{q_i},\qquad m\not\equiv0\pmod{p_i}.Втората система условия е съвместима с първата: ако за някое i>0i\gt{}0 се случи qi=piq_i=p_i, тогава първото условие дава m≡−i≢0(modpi)m\equiv-i\not\equiv0\pmod{p_i}, понеже pi>2012p_i\gt{}2012. Сега mm е взаимно просто с всяко от p0,p1,…,p2012p_0,p_1,\ldots,p_{2012}. Следователно f(m)f(m) е взаимно просто с всяко от числата f(pi)f(p_i), а значи не се дели на нито едно от q0,q1,…,q2012q_0,q_1,\ldots,q_{2012}. От друга страна m≤f(m)≤m+2012m\le f(m)\le m+2012, така че f(m)=m+if(m)=m+i за някое ii между 00 и 20122012. Но тогава qiq_i дели m+i=f(m)m+i=f(m), противоречие. Значи всяко избрано просто число qiq_i е равно на съответното pip_i. Тъй като изборът на прост делител на f(pi)f(p_i) беше произволен, всички прости делители на f(pi)f(p_i) са равни на pip_i, тоест f(pi)f(p_i) е степен на pip_i. Накрая нека pp е просто и p∤np\nmid n. Тогава pp и nn са взаимно прости, затова f(p)f(p) и f(n)f(n) са взаимно прости. Но pp дели f(p)f(p), понеже f(p)f(p) е положителна степен на pp. Следователно pp не дели f(n)f(n). Това е контрапозицията на исканото твърдение.
Отвори задачатаEvan Chen VONVON TSTST 2012/3Условие — източник

Задача 5

Пълен запис
Условие
Дадено е рационално число xx. Докажете, че съществува редица от рационални числаx0,x1,x2,…x_0,x_1,x_2,\ldotsсъс следните свойства: (a) x0=xx_0=x; (b) за всяко n≥1n\ge1 имаме или xn=2xn−1x_n=2x_{n-1}, или xn=2xn−1+1nx_n=2x_{n-1}+\frac1n; (c) някой член xnx_n е цяло число.
РешениеЩе записваме избора на всеки ход чрез число εn∈{0,1}\varepsilon_n\in\{0,1\}, така чеxn=2xn−1+εnn.x_n=2x_{n-1}+\frac{\varepsilon_n}{n}.Ако сме стигнали до момент tt и после фиксираме краен момент N>tN\gt{}t, тоxN=2N−txt+∑j=t+1Nεj2N−jj.x_N=2^{N-t}x_t+\sum_{j=t+1}^N \varepsilon_j\frac{2^{N-j}}{j}.Ще покажем как от знаменателя на текущата дроб се премахва един нечетен прост множител. След това повтаряме процедурата за всички нечетни прости множители, а когато останалият знаменател е степен на 22, вземаме само ходове от вида xn=2xn−1x_n=2x_{n-1}, докато получим цяло число. Нека при момент tt знаменателят на xtx_t в несъкратен вид има нечетна проста степен q=peq=p^e в своята pp-част. Избираме големи числа r,m,Nr,m,N така, чеt<2r+1q<2r+2q<⋯<2r+mq<N.t\lt{}2^{r+1}q\lt{}2^{r+2}q\lt{}\cdots\lt{}2^{r+m}q\lt{}N.Зануляваме всички нови εj\varepsilon_j освен евентуално тези при ji=2r+iqj_i=2^{r+i}q, 1≤i≤m1\le i\le m. Тогава приносът на такъв момент към xNx_N еεji2N−jiji=ciεjiq,\varepsilon_{j_i}\frac{2^{N-j_i}}{j_i}=\frac{c_i\varepsilon_{j_i}}{q},където cic_i е степен на 22. В частност ci≢0(modp)c_i\not\equiv0\pmod p. Привеждаме дробите към общ знаменател, чиято pp-част е qq. Умножението с частта на знаменателя, взаимнопроста с pp, само заменя всеки cic_i с ненулев остатък по модул pp. Следователно можем да избираме добавка от видаc1εj1+⋯+cmεjmq.\frac{c_1\varepsilon_{j_1}+\cdots+c_m\varepsilon_{j_m}}{q}.Когато mm е достатъчно голям, подмножествата от коефициентите cic_i дават всички остатъци по модул pp. Например това следва от Коши-Давенпорт: сумата на множествата {0,ci}\{0,c_i\} увеличава размера си с поне 11, докато не стане цялото поле Z/pZ\mathbb Z/p\mathbb Z. Затова можем да изберем εji\varepsilon_{j_i} така, че числителят на частта със знаменател qq да стане делим на pp. Така pp-степента в знаменателя намалява с 11. Възможно е междувременно да сме въвели само нови степени на 22 в знаменателя, но не и нови нечетни прости делители. Повтаряме крайно много пъти тази редукция за всяка нечетна проста степен в знаменателя. След това знаменателят е степен на 22, а достатъчно много последователни удвоявания превръщат числото в цяло. Това завършва конструкцията.
Отвори задачатаEvan Chen VONVON TSTST 2012/5Условие — източник

Задача 6

Пълен запис
Условие
Положителните реални числа x,y,zx,y,z удовлетворяватxyz+xy+yz+zx=x+y+z+1.xyz+xy+yz+zx=x+y+z+1.Докажете, че13(x21+x21+x+x21+y21+y+x21+z21+z)≤\frac13\left(\sqrt{\vphantom{x^2}\frac{1+x^2}{1+x}}+\sqrt{\vphantom{x^2}\frac{1+y^2}{1+y}}+\sqrt{\vphantom{x^2}\frac{1+z^2}{1+z}}\right)\le(x+y+z3)5/8. \left(\frac{x+y+z}{3}\right)^{5/8}.
РешениеНека s=x+y+zs=x+y+z. Ключовото тъждество еx2+1x+1=(x+y)(x+z)1+x+y+z,\frac{x^2+1}{x+1}=\frac{(x+y)(x+z)}{1+x+y+z},и аналогичните две тъждества. Наистина след умножаване по (x+1)(y+1)(z+1)(x+1)(y+1)(z+1) и използване наxyz+xy+yz+zx=x+y+z+1xyz+xy+yz+zx=x+y+z+1се получава(x2+1)(y+1)(z+1)=2(x+y)(x+z),(x^2+1)(y+1)(z+1)=2(x+y)(x+z),което е точно горната формула. Следователно∑cycx21+x21+x=\sum_{\mathrm{cyc}}\sqrt{\vphantom{x^2}\frac{1+x^2}{1+x}}=∑cycx2(x+y)(x+z)x21+s.\sum_{\mathrm{cyc}}\frac{\sqrt{\vphantom{x^2}(x+y)(x+z)}}{\sqrt{\vphantom{x^2}1+s}}.По неравенството на Коши-Шварц,(∑cycx2(x+y)(x+z)x21+s)2≤(∑cyc(x+y))(∑cyc(x+z))1+s=4s21+s.\begin{align*} \left(\sum_{\mathrm{cyc}}\frac{\sqrt{\vphantom{x^2}(x+y)(x+z)}}{\sqrt{\vphantom{x^2}1+s}}\right)^2 &\le \frac{\left(\sum_{\mathrm{cyc}}(x+y)\right)\left(\sum_{\mathrm{cyc}}(x+z)\right)}{1+s}\\ &=\frac{4s^2}{1+s}. \end{align*}Значи е достатъчно да докажем4s21+s≤9(s3)5/4.\frac{4s^2}{1+s}\le 9\left(\frac{s}{3}\right)^{5/4}.И двете страни са положителни, така че можем да повдигнем на четвърта степен след умножаване по 1+s1+s. Получаваме точно94(s3)5(1+s)4−(4s2)4=9^4\left(\frac{s}{3}\right)^5(1+s)^4-(4s^2)^4=s5(s−3)2(27s2+14s+3)≥s^5(s-3)^2(27s^2+14s+3)\ge0.0.Това доказва желаното неравенство.
Отвори задачатаEvan Chen VONVON TSTST 2012/6Условие — източник

Задача 9

Пълен запис
Условие
Дадено е множество SS от nn променливи. Двоична операция ×\times върху SS се нарича проста, ако удовлетворява(x×y)×z=x×(y×z)(x\times y)\times z=x\times(y\times z)за всички x,y,z∈Sx,y,z\in S и ако x×y∈{x,y}x\times y\in\{x,y\} за всички x,y∈Sx,y\in S. При дадена проста операция ×\times всеки низ от елементи на SS може да се редуцира до един елемент, например xyzxyz може да се пресметне като x×(y×z)x\times(y\times z). Низ от променливи от SS се нарича пълен, ако съдържа всяка променлива от SS поне веднъж. Два низа се наричат еквивалентни, ако дават една и съща променлива независимо от избраната проста операция ×\times. Например xxxxxx, xxxx и xx са еквивалентни, но са пълни само когато n=1n=1. Нека TT е множество от пълни низове, такова че всеки пълен низ е еквивалентен на точно един елемент на TT. Да се намери броят на елементите на TT.
РешениеОтговорът е(n!)2.(n!)^2.Първо отбелязваме, че простите операции всъщност имат следния вид. На всяка променлива се съпоставя реално число. Тогава x×yx\times y избира по-голямата от двете променливи, а при равенство се избира или лявата, или дясната променлива, като изборът на страна е фиксиран за всички променливи с една и съща стойност. Това описание ще бъде използвано по-долу за различаване на класовете. Ще са ни нужни две елементарни тъждества, валидни за всяка проста операция:xx=x,xyxzx=xyzx.xx=x,\qquad xyxzx=xyzx.Първото е непосредствено. Второто се проверява с асоциативността и условието, че всяко произведение избира един от двата си аргумента; еквивалентно, може да се провери по описаната по-горе класификация. Да наречем двоен разноцветен низ конкатенация на два пълни низа с дължина nn, т.е. конкатенация на две пермутации на елементите на SS. Такива низове има точно (n!)2(n!)^2. Ще докажем, че те са търсените представители. Първо, всеки пълен низ ss е еквивалентен на някакъв двоен разноцветен низ. Наистина, ss е еквивалентен на ssss, защото след пресмятане на ss получаваме някаква променлива uu, а uu=uuu=u. След това тъждеството xyxzx=xyzxxyxzx=xyzx позволява последователно да премахваме излишните повторения, докато във всяка от двете половини остане по едно срещане на всяка променлива. Така стигаме до конкатенация на две пермутации. Остава да видим, че два различни двойни разноцветни низа не са еквивалентни. Нека R1R_1 и R2R_2 са различни такива низове. Тогава съществуват две променливи aa и bb, които не се появяват в един и същ относителен ред в R1R_1 и R2R_2 при разглеждане на двете им срещания. След ограничаване само до буквите aa и bb се получава един от четирите низаabab,abba,baab,baba,abab,\qquad abba,\qquad baab,\qquad baba,и тези четири възможности са взаимно нееквивалентни. Действително, като избираме дали при равни най-големи елементи операцията взема левия или десния аргумент, тези четири низа дават различни резултати при подходящ избор. За да пренесем това към цялото множество SS, дефинираме проста операция, при която aa и bb са най-големите променливи, а всички останали са по-малки. Тогава останалите променливи не влияят на стойността на низа и различието между редовете на a,ba,b в R1R_1 и R2R_2 показва, че R1R_1 и R2R_2 не са еквивалентни. Следователно всеки клас на еквивалентност на пълни низове има точно един представител сред двойните разноцветни низове. Броят на тези представители е (n!)2(n!)^2, което е търсеният отговор.
Отвори задачатаEvan Chen VONVON TSTST 2012/9Условие — източник