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

Evan Chen / USA TSTST Solutions

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

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

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

2013

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

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

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

11-12

5 задачи

Задача 2

Пълен запис
Условие
Крайна редица от цели числа a1,a2,…,ana_1,a_2,\ldots,a_n се нарича регулярна, ако съществува реално число xx, такова че⌊kx⌋=akза 1≤k≤n.\lfloor kx\rfloor=a_k\qquad\text{за }1\le k\le n.За дадена регулярна редица a1,a2,…,ana_1,a_2,\ldots,a_n казваме, че членът aka_k е принуден, ако редицатаa1,a2,…,ak−1,ba_1,a_2,\ldots,a_{k-1},bе регулярна тогава и само тогава, когато b=akb=a_k. Намерете най-големия възможен брой принудени членове в регулярна редица с 10001000 члена.
РешениеОтговорът е 985985. Можем да изместим xx с цяло число и да приемем a1=0a_1=0, тоест 0≤x<10\le x\lt{}1. Самият първи член не е принуден. След като са избрани първите k−1k-1 члена, възможните стойности на xx образуват полуотворен интервалA≤x<B,A\le x\lt{}B,чиито краища са рационални числа. Членът aka_k не е принуден точно когато в този интервал има точка от вида m/km/k, защото тогава стойността на ⌊kx⌋\lfloor kx\rfloor може да се смени при преминаване през тази точка. Сега използваме стандартното свойство на редиците на Фарей. Ако в даден момент краищата са съседни дробиab≤x<cd,\frac ab\le x\lt{}\frac cd,то първата дроб с нов знаменател, която попада между тях, е медиантатаa+cb+d,\frac{a+c}{b+d},и тя се появява точно при момент k=b+dk=b+d. В този момент членът не е принуден; след като изберем от коя страна на медиантата да останем, единият край на интервала се заменя с медиантата. Така броят на непринудените членове е броят на знаменателите, които се появяват в процеса. Започваме със знаменателите 11 и 11. Ако текущите знаменатели са b≤db\le d, следващият непринуден момент е b+db+d. За да отложим максимално следващите непринудени моменти, трябва да заменим по-малкия знаменател с b+db+d, защото тогава следващата сума е b+2db+2d, а не 2b+d2b+d. Следователно оптималната стратегия дава последователни знаменатели1,2,3,5,8,13,…,1,2,3,5,8,13,\ldots,тоест числата на Фибоначи, започвайки от 1,21,2. Под 10001000 са точно1,2,3,5,8,13,21,34,55,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,89,144,233,377,610,987,общо 1515 числа. Значи във всяка редица има поне 1515 непринудени члена, а описаното избиране на страните постига точно толкова. Максималният брой принудени членове е1000−15=985.1000-15=985.
Отвори задачатаEvan Chen VONVON TSTST 2013/2Условие — източник

Задача 5

Пълен запис
Условие
Нека pp е просто число. Докажете, че във всеки пълен граф с 1000p1000p върха, чиито ребра са означени с цели числа, съществува цикъл, за който сумата от означенията на ребрата му се дели на pp.
РешениеРаботим по модул pp. Избираме произволно p−1p-1 несвързани триъгълника; това е възможно, понеже графът има много повече от 3(p−1)3(p-1) върха. Ако някой от тези триъгълници има сума на ребрата 0(modp)0\pmod p, сме готови. Иначе във всеки триъгълник можем да означим върховете с ui,xi,viu_i,x_i,v_i така, чеℓ(uixi)+ℓ(xivi)≢ℓ(uivi)(modp),\ell(u_ix_i)+\ell(x_iv_i)\not\equiv \ell(u_iv_i)\pmod p,където ℓ(ab)\ell(ab) е означението на реброто abab. Наистина, ако за всяко ребро означението му беше равно на сумата на другите две, сумата на трите ребра щеше да бъде 0(modp)0\pmod p, противно на избора ни. За всеки триъгълник поставямеAi=A_i={ℓ(uixi)+ℓ(xivi),ℓ(uivi)}⊆Z/pZ.\{\ell(u_ix_i)+\ell(x_iv_i),\ell(u_iv_i)\}\subseteq\mathbb Z/p\mathbb Z.Това е множество с два елемента. От Коши-Давенпорт и индукция получаваме∣A1+A2+⋯+At∣≥min⁡{p,t+1}|A_1+A_2+\cdots+A_t|\ge \min\{p,t+1\}за 1≤t≤p−11\le t\le p-1. СледователноA1+A2+⋯+Ap−1=Z/pZ.A_1+A_2+\cdots+A_{p-1}=\mathbb Z/p\mathbb Z.Остава само да свържем триъгълниците. Добавяме фиксираните ребраv1u2,v2u3,…,vp−2up−1,vp−1u1v_1u_2, v_2u_3, \ldots, v_{p-2}u_{p-1}, v_{p-1}u_1и нека сумата на техните означения е KK. Във всеки триъгълник избираме или пътя uixiviu_i x_i v_i, или директното ребро uiviu_iv_i. Понеже сумите от множествата AiA_i дават всички остатъци, можем да направим избора така, че вътрешната сума да бъде −K(modp)-K\pmod p. Тогава избраните вътрешни пътища заедно с фиксираните свързващи ребра образуват цикъл, чиято обща сума е 0(modp)0\pmod p. Това е търсеният цикъл.
Отвори задачатаEvan Chen VONVON TSTST 2013/5Условие — източник

Задача 6

Пълен запис
Условие
Нека N\mathbb N е множеството на положителните цели числа. Намерете всички функции f:N→Nf:\mathbb N\to\mathbb N, които удовлетворяват уравнениетоfabc−a(abc)+fabc−b(abc)+fabc−c(abc)=f^{abc-a}(abc)+f^{abc-b}(abc)+f^{abc-c}(abc)=a+b+ca+b+cза всички a,b,c≥2a,b,c\ge2. Тук fkf^k означава kk-кратно прилагане на функцията ff.
РешениеОтговорът еf(n)=n−1за всяко n≥3,f(n)=n-1\quad\text{за всяко } n\ge3,като f(1)f(1) и f(2)f(2) могат да бъдат произволни положителни цели числа. Наистина, при тази функция, докато започваме от abcabc и спираме в a,b,c≥2a,b,c\ge2, всяко прилагане просто намалява аргумента с 11, така че уравнението се проверява директно. Ще докажем, че други решения няма. Първо ни трябва лема. Твърдим, чеft2−t(t2)=tза всяко t≥2.f^{t^2-t}(t^2)=t\qquad\text{за всяко }t\ge2.Нека наречем число 1≤k≤81\le k\le8 добро, акоft9−tk(t9)=tkf^{t^9-t^k}(t^9)=t^kза всяко t≥2t\ge2. От уравнението при (a,b,c)=(t3,t3,t3)(a,b,c)=(t^3,t^3,t^3) получаваме, че k=3k=3 е добро, а от (a,b,c)=(t,t,t)(a,b,c)=(t,t,t) имаме ft3−t(t3)=tf^{t^3-t}(t^3)=t. Следователно, като композираме тези две равенства, получаваме, че k=1k=1 е добро. Сега при (a,b,c)=(t,t4,t4)(a,b,c)=(t,t^4,t^4) уравнението ставаft9−t(t9)+2ft9−t4(t9)=t+2t4.f^{t^9-t}(t^9)+2f^{t^9-t^4}(t^9)=t+2t^4.Понеже k=1k=1 е добро, следва, че k=4k=4 е добро. При (a,b,c)=(t2,t3,t4)(a,b,c)=(t^2,t^3,t^4) аналогично получаваме, че k=2k=2 е добро. Тогаваft9−t2(t9)=t2иft9−t(t9)=t,f^{t^9-t^2}(t^9)=t^2\quad\text{и}\quad f^{t^9-t}(t^9)=t,а разликата в броя на итерациите е t2−tt^2-t. Значи ft2−t(t2)=tf^{t^2-t}(t^2)=t, както твърдяхме. Фиксираме tt и за n<tn\lt{}t поставямеgt(n)=ft−n(t)−n.g_t(n)=f^{t-n}(t)-n.Ако a,b≥2a,b\ge2, ab∣tab\mid t и ab<tab\lt{}t, тогава ще покажем, чеgt(a)+gt(b)=gt(ab).g_t(a)+g_t(b)=g_t(ab).Нека t=abct=abc. Записваме даденото уравнение катоft−a(t)+ft−b(t)+ft−c(t)=a+b+c.f^{t-a}(t)+f^{t-b}(t)+f^{t-c}(t)=a+b+c.После го прилагаме към тройката (ab,t,c)(ab,t,c), чието произведение е t2t^2. Получавамеft2−ab(t2)+ft2−t(t2)+ft2−c(t2)=ab+t+c.f^{t^2-ab}(t^2)+f^{t^2-t}(t^2)+f^{t^2-c}(t^2)=ab+t+c.По лемата средният член е tt, а първият и третият член се свеждат съответно до ft−ab(t)f^{t-ab}(t) и ft−c(t)f^{t-c}(t). След изваждане на двете равенства остава точно тъждеството за gtg_t. Нека сега a,b≥2a,b\ge2 са произволни. Избираме прости числа p>q>max⁡{a,b}p\gt{}q\gt{}\max\{a,b\} и поставяме s=apbqs=a^p b^q, t=s2t=s^2. Повтаряйки току-що доказаната адитивност, получавамеpgt(a)+qgt(b)=gt(apbq)=p g_t(a)+q g_t(b)=g_t(a^p b^q)=gt(s)=fs2−s(s2)−s=0,g_t(s)=f^{s^2-s}(s^2)-s=0,където последното равенство е лемата. Оттук q∣gt(a)q\mid g_t(a) и p∣gt(b)p\mid g_t(b). Освен това gt(a)>−ag_t(a)\gt{}-a и gt(b)>−bg_t(b)\gt{}-b, защото стойностите на ff са положителни. Понеже p,qp,q са по-големи от a,ba,b, равенството pgt(a)+qgt(b)=0p g_t(a)+q g_t(b)=0 принуждава gt(a)=gt(b)=0g_t(a)=g_t(b)=0. В частност за произволно n≥2n\ge2 прилагаме това с a=na=n и b=n+1b=n+1. Получаваме едновременноft−n(t)=n,ft−(n+1)(t)=n+1f^{t-n}(t)=n,\qquad f^{t-(n+1)}(t)=n+1за подходящо tt. Следователно едно прилагане на ff изпраща n+1n+1 в nn, тоест f(n+1)=nf(n+1)=n за всяко n≥2n\ge2. Това е точно f(m)=m−1f(m)=m-1 за всяко m≥3m\ge3.
Отвори задачатаEvan Chen VONVON TSTST 2013/6Условие — източник

Задача 7

Пълен запис
Условие
В една държава има nn града, означени с 1,2,3,…,n1,2,3,\ldots,n. Тя иска да построи точно n−1n-1 пътища между някои двойки градове така, че от всеки град да може да се стигне до всеки друг. Не е позволено обаче да се строи път между два града, чиито означения се различават точно с 11, нито между градовете 11 и nn. Нека TnT_n е броят на възможните начини да се построят тези пътища. (a) Докажете, че за всяко нечетно nn числото TnT_n се дели на nn. (b) Докажете, че за всяко четно nn числото TnT_n се дели на n/2n/2.
РешениеРазполагаме градовете 1,2,…,n1,2,\ldots,n по окръжност. Забранените ребра са точно страните на този цикъл, следователно завъртането на означенията с една позиция запазва допустимия граф. Цикличната група Z/nZ\mathbb Z/n\mathbb Z действа върху множеството на всички допустими покриващи дървета. Ще разгледаме стабилизатора на едно такова дърво TT. Нека ротацията geg^e фиксира TT, и нека k=gcd⁡(e,n)k=\gcd(e,n). Тогава ротацията gkg^k също фиксира TT. Следователно редицата от степени на върховете в дървото е периодична с период kk, така чеnk∣∑vdeg⁡(v)=2n−2.\frac{n}{k}\mid \sum_v \deg(v)=2n-2.Ако nn е нечетно, то gcd⁡(n,2n−2)=1\gcd(n,2n-2)=1. Понеже n/kn/k дели и nn, и 2n−22n-2, получаваме n/k=1n/k=1, тоест k=nk=n. Значи никоя нетривиална ротация не фиксира дърво. Всички орбити имат размер nn, откъдето n∣Tnn\mid T_n. Ако nn е четно, то gcd⁡(n,2n−2)=2\gcd(n,2n-2)=2. Същият аргумент дава n/k≤2n/k\le2. Значи стабилизаторът на всяко дърво има размер най-много 22, а орбитата му има размер поне и всъщност кратен на n/2n/2. Следователно всички орбити имат размер, делящ се на n/2n/2, и n/2∣Tnn/2\mid T_n.
Отвори задачатаEvan Chen VONVON TSTST 2013/7Условие — източник

Задача 8

Пълен запис
Условие
Дефинираме функция f:N→Nf:\mathbb N\to\mathbb N чрез f(1)=1f(1)=1 иf(n+1)=f(n)+2f(n)f(n+1)=f(n)+2^{f(n)}за всяко положително цяло число nn. Докажете, че числатаf(1),f(2),…,f(32013)f(1),f(2),\ldots,f(3^{2013})дават различни остатъци при деление на 320133^{2013}.
РешениеЩе докажем по индукция по k≥1k\ge1 следното по-силно твърдение: всеки 3k3^k последователни члена на редицата ff дават различни остатъци по модул 3k3^k. За k=1k=1 твърдението се проверява веднага. Всички стойности на ff са нечетни, а по модул 33 имаме 2f(n)≡−12^{f(n)}\equiv -1, така че остатъците циклично се сменят като 1,0,2,1,0,2,…1,0,2,1,0,2,\ldots. Нека твърдението е вярно за kk. Понеже всички f(n)f(n) са нечетни, всяка група от 3k3^k последователни стойности, която е пълна по модул 3k3^k, е точно множеството на всички нечетни остатъци по модул 2⋅3k2\cdot3^k. А степените 2r2^r по модул 3k+13^{k+1} зависят от rr с период 2⋅3k2\cdot3^k. Следователно за всяко nn имамеf(n+3k)−f(n)=∑i=03k−12f(n+i)≡21+23+⋯+22⋅3k−1(mod3k+1)=2⋅43k−13.\begin{align*} f(n+3^k)-f(n) &=\sum_{i=0}^{3^k-1}2^{f(n+i)}\\ &\equiv 2^1+2^3+\cdots+2^{2\cdot3^k-1}\pmod{3^{k+1}}\\ &=2\cdot\frac{4^{3^k}-1}{3}. \end{align*}НекаC=2⋅43k−13.C=2\cdot\frac{4^{3^k}-1}{3}.По повдигане на показателя, или директно от стандартната формула за 33-адична валуация,ν3(C)=k.\nu_3(C)=k.Значи CC се дели на 3k3^k, но не се дели на 3k+13^{k+1}. Сега разглеждаме произволни 3k+13^{k+1} последователни члена и ги разделяме на три блока с дължина 3k3^k. По индукционното предположение във всеки блок остатъците по модул 3k3^k са различни. Преминаването от дадена позиция в един блок към същата позиция в следващия блок добавя CC по модул 3k+13^{k+1}, а трите стойности, различаващи се с 0,C,2C0,C,2C, лежат в три различни класа над един и същ остатък по модул 3k3^k. Следователно трите блока заедно дават различни остатъци по модул 3k+13^{k+1}. Индукцията е завършена, а при k=2013k=2013 получаваме точно исканото твърдение.
Отвори задачатаEvan Chen VONVON TSTST 2013/8Условие — източник