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

Evan Chen / USA TSTST Solutions

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

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

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

2019

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

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

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Намерете всички двуместни операции ♢ ⁣:R>0×R>0→R>0\diamondsuit\colon \mathbb R_{\gt{}0}\times \mathbb R_{\gt{}0}\to \mathbb R_{\gt{}0}, за коитоa♢(b♢c)=(a♢b)ca\diamondsuit (b\diamondsuit c)=(a\diamondsuit b)cза всички положителни реални числа a,b,ca,b,c, и освен това a♢a≥1a\diamondsuit a\ge 1 за всяко реално a≥1a\ge 1.
РешениеОтговорът еa♢b=abилиa♢b=ab.a\diamondsuit b=ab\qquad\text{или}\qquad a\diamondsuit b=\frac ab.Нека f(x)=1♢xf(x)=1\diamondsuit x. От даденото равенство следва, че за всяко фиксирано aa функцията x↦a♢xx\mapsto a\diamondsuit x е инективна: ако a♢u=a♢va\diamondsuit u=a\diamondsuit v, то от 1♢(a♢u)=(1♢a)u1\diamondsuit(a\diamondsuit u)=(1\diamondsuit a)u и 1♢(a♢v)=(1♢a)v1\diamondsuit(a\diamondsuit v)=(1\diamondsuit a)v получаваме u=vu=v. С подходящи замествания в основното тъждество получавамеa♢1=a,1♢(1♢x)=x,a♢b=a(1♢b).a\diamondsuit 1=a,\qquad 1\diamondsuit(1\diamondsuit x)=x,\qquad a\diamondsuit b=a(1\diamondsuit b).Следователно a♢b=af(b)a\diamondsuit b=af(b) и f(f(x))=xf(f(x))=x. Като заместим това обратно в условието, стигаме до f(bf(c))=f(b)cf(bf(c))=f(b)c, а понеже ff е инволюция, това е равносилно наf(xy)=f(x)f(y)f(xy)=f(x)f(y)за всички x,y>0x,y\gt{}0. Значи ff е мултипликативна и инволютивна. Второто условие ставаxf(x)≥1за всяко x≥1.x f(x)\ge 1\quad\text{за всяко }x\ge 1.Ще докажем, че за всяко x>0x\gt{}0 стойността f(x)f(x) е или xx, или 1/x1/x. Достатъчно е да разгледаме b>1b\gt{}1 и да положим f(b)=af(b)=a; тогава a≥1/ba\ge 1/b и f(a)=bf(a)=b. Ако ab=1ab=1, сме готови. Нека ab>1ab\gt{}1. За произволни цели m,nm,n с anbm≥1a^n b^m\ge 1 второто условие, приложено към anbma^n b^m, даваambn=f(anbm)≥1anbm.a^m b^n=f(a^n b^m)\ge \frac{1}{a^n b^m}.Следователно (ab)m+n≥1(ab)^{m+n}\ge 1, а понеже ab>1ab\gt{}1, получаваме m+n≥0m+n\ge 0. С други думи,m+n<0⟹nlog⁡ba+m<0m+n\lt{}0\quad\Longrightarrow\quad n\log_b a+m\lt{}0за всички цели m,nm,n. Плътността на рационалните числа принуждава log⁡ba=1\log_b a=1, тоест a=ba=b. Така f(b)f(b) е или bb, или 1/b1/b. Остава да видим, че изборът не може да се сменя от число на число. Поставяме g(t)=log⁡f(et)g(t)=\log f(e^t). От вече доказаното следва g(t)∈{t,−t}g(t)\in\{t,-t\}, а мултипликативността дава∣g(t)−g(s)∣=∣g(t−s)∣=∣t−s∣.|g(t)-g(s)|=|g(t-s)|=|t-s|.Значи gg е непрекъсната. Ако f(2)=2f(2)=2, то за всяко рационално qq имаме f(2q)=2qf(2^q)=2^q, а по непрекъснатост това важи за всяко положително число. Ако f(2)=1/2f(2)=1/2, аналогично f(x)=1/xf(x)=1/x за всяко x>0x\gt{}0. Получаваме точно двете операции от отговора, и директна проверка показва, че и двете удовлетворяват условията.
Отвори задачатаEvan Chen VONVON TSTST 2019/1Условие — източник

Задача 3

Пълен запис
Условие
В безкрайна квадратна мрежа са поставени краен брой коли, като всяка заема една клетка и е насочена в една от четирите основни посоки. Две коли никога не могат да заемат една и съща клетка. Дадено е, че клетката непосредствено пред всяка кола е празна, и освен това никои две коли не са насочени една към друга (например няма кола, насочена надясно, която да е вляво от кола, насочена наляво, в същия ред и т.н.). При един ход избираме кола и я преместваме една клетка напред в свободна клетка. Докажете, че съществува безкрайна последователност от допустими ходове, в която всяка кола се използва безкрайно много пъти.
РешениеНека SS е произволен правоъгълник, който съдържа всички коли. Разделяме SS на хоризонтални ивици с височина 11 и ги оцветяваме последователно в червено и зелено. Достатъчно е да докажем, че всички коли могат да напуснат SS: след като това е възможно за всеки достатъчно голям правоъгълник, можем последователно да избираме все по-големи правоъгълници и така да получим безкрайна допустима последователност от ходове, в която всяка конкретна кола се мести безкрайно много пъти.▶▽▶▽▽△▶▶△△◀◀▶◀▶▽▶▽▽△▶▶△△◀◀▶◀▶▽△▽▽▶▶△△◀▶▽▽▽▶▶△△◀Ще опишем пететапен план за колите. 1. Всички вертикални коли, които се намират в зелена клетка, се преместват с една клетка напред в червена клетка (или излизат от SS). Това е единственото място, където използваме условието, че непосредствено пред всяка кола има празна клетка. 2. Всички хоризонтални коли в зелени клетки могат да напуснат SS, защото в зелените клетки вече няма вертикални коли. Освен това две хоризонтални коли в един и същ ред не си пречат: условието, че няма две коли, насочени една към друга, означава, че колите, движещи се наляво и надясно, могат да се извеждат към съответните страни без да се сблъскат. 3. Всички вертикални коли, които се намират в червена клетка, се преместват с една клетка напред в зелена клетка (или излизат от SS), понеже всички зелени клетки вече са празни. 4. Всички хоризонтални коли в червени клетки могат да напуснат SS, защото в червените клетки вече няма вертикални коли, а хоризонталните коли отново не са насочени една към друга. 5. Останалите коли напускат SS, защото всички те са вертикални и вече няма хоризонтални коли, които да ги блокират. Това доказва, че всички коли могат да напуснат произволния правоъгълник SS, а оттук следва и исканата безкрайна последователност от ходове.
Отвори задачатаEvan Chen VONVON TSTST 2019/3Условие — източник

Задача 4

Пълен запис
Условие
Разглеждаме монети с положителни реални номинали, ненадминаващи 11. Намерете най-малката константа C>0C\gt{}0 със следното свойство: ако са дадени произволни 100100 такива монети с обща стойност 5050, винаги можем да ги разделим на две купчини по 5050 монети така, че абсолютната разлика между общите стойности на двете купчини да е най-много CC.
РешениеОтговорът е C=5051C=\frac{50}{51}. Първо ще покажем, че по-малка константа не стига. Вземаме 5151 монети с номинал 1/511/51 и 4949 монети с номинал 11. Ако в едната купчина попаднат xx от големите монети, то в другата попадат 49−x49-x от тях, а разликата между стойностите на двете купчини е∣x+50−x51−(49−x)−x+151∣=5051∣2x−49∣≥\left|x+\frac{50-x}{51}-(49-x)-\frac{x+1}{51}\right|=\frac{50}{51}|2x-49|\ge5051. \frac{50}{51}.Следователно C≥50/51C\ge 50/51. Сега доказваме, че C=50/51C=50/51 винаги е достатъчно. Нека стойностите на монетите са0<a1≤a2≤⋯≤a100≤1,∑i=1100ai=50.0\lt{}a_1\le a_2\le \cdots\le a_{100}\le 1,\qquad \sum_{i=1}^{100}a_i=50.Тогава a50≤50/51a_{50}\le 50/51, защото монетите a50,a51,…,a100a_{50},a_{51},\ldots,a_{100} са 5151 на брой и общата им стойност е най-много 5050. Също така a51≥1/51a_{51}\ge 1/51, защото ако a51<1/51a_{51}\lt{}1/51, първите 5151 монети биха имали обща стойност под 11, а останалите 4949 монети имат обща стойност най-много 4949. Поставяме в първата купчина монетитеa1,a3,…,a49,a52,a54,…,a100,a_1,a_3,\ldots,a_{49},\qquad a_{52},a_{54},\ldots,a_{100},а във втората - останалите 5050 монети. Нека DD е стойността на първата купчина минус стойността на втората. От една странаD=D=(a1−a2)+⋯+(a49−a50)−a51(a_1-a_2)+\cdots+(a_{49}-a_{50})-a_{51}+(a52−a53)+⋯+(a98−a99)+a100.+(a_{52}-a_{53})+\cdots+(a_{98}-a_{99})+a_{100}.Всички разлики в скобите са неположителни, затоваD≤−a51+a100≤−151+1=5051.D\le -a_{51}+a_{100}\le -\frac{1}{51}+1=\frac{50}{51}.От друга страна можем да запишем същия DD катоD=D=a1+(a3−a2)+⋯+(a49−a48)−a50a_1+(a_3-a_2)+\cdots+(a_{49}-a_{48})-a_{50}+(a52−a51)+⋯+(a100−a99).+(a_{52}-a_{51})+\cdots+(a_{100}-a_{99}).Всички разлики тук са неотрицателни, а a1>0a_1\gt{}0, следователноD≥−a50≥−5051.D\ge -a_{50}\ge -\frac{50}{51}.Получихме ∣D∣≤50/51|D|\le 50/51, така че тази константа винаги е достатъчна.
Отвори задачатаEvan Chen VONVON TSTST 2019/4Условие — източник

Задача 6

Пълен запис
Условие
Нека PP е полином с цели коефициенти, такъв че за всяко положително цяло число nn сумата на десетичните цифри на ∣P(n)∣|P(n)| не е число на Фибоначи. Вярно ли е, че PP трябва да е константен?
РешениеОтговорът е да: PP трябва да е константен. Нека S(n)S(n) означава сумата на десетичните цифри на ∣n∣|n|. Ще използваме две твърдения. Твърдение 1. Ако P(x)∈Z[x]P(x)\in\mathbb Z[x] е неконстантен полином с положителен старши коефициент, то съществува полином F(x)∈Z[x]F(x)\in\mathbb Z[x], такъв че всички коефициенти на P(F(x))P(F(x)) са положителни, с изключение на втория по степен, който е отрицателен. Доказателство. Всъщност ще построим кубичен FF. Наричаме полином с това свойство добър. Първо разглеждамеT0(x)=x3+x+1.T_0(x)=x^3+x+1.В T0(x)deg⁡PT_0(x)^{\deg P} всички коефициенти са строго положителни, освен втория по степен, който е нула. После разглеждамеT1(x)=x3−1Dx2+x+1.T_1(x)=x^3-\frac1D x^2+x+1.По непрекъснатост, ако DD е достатъчно голямо спрямо deg⁡P\deg P, то T1(x)deg⁡PT_1(x)^{\deg P} е добър; единственият отрицателен коефициент идва от члена −3Dx3deg⁡P−1-\frac3D x^{3\deg P-1}. Накрая вземамеF(x)=CT1(x),F(x)=C T_1(x),където CC е достатъчно голямо кратно на DD, така че FF да има цели коефициенти и водещият член на PP да доминира останалите членове при композицията. Това дава търсения полином. Твърдение 2. Във всеки остатъчен клас по модул 99 има безбройно много числа на Фибоначи. Доказателство. Редицата на Фибоначи е периодична по модул 99. Освен това, допускайки и отрицателни индекси, имаме представители на всички остатъци:F0=0≡0(mod9),F1=1≡1(mod9),F3=2≡2(mod9),F4=3≡3(mod9),F7=13≡4(mod9),F5=5≡5(mod9),F−4=−3≡6(mod9),F9=34≡7(mod9),F6=8≡8(mod9).\begin{align*} F_0&=0\equiv0\pmod9,\\ F_1&=1\equiv1\pmod9,\\ F_3&=2\equiv2\pmod9,\\ F_4&=3\equiv3\pmod9,\\ F_7&=13\equiv4\pmod9,\\ F_5&=5\equiv5\pmod9,\\ F_{-4}&=-3\equiv6\pmod9,\\ F_9&=34\equiv7\pmod9,\\ F_6&=8\equiv8\pmod9. \end{align*}Понеже периодът се повтаря, всеки остатък се среща безбройно много пъти. Да се върнем към задачата. Ако PP е неконстантен, заменяме при нужда PP с −P-P, което не променя ∣P(n)∣|P(n)|, и можем да приемем, че старшият коефициент е положителен. По Твърдение 1 избираме FF, така чеP(F(x))=cNxN−cN−1xN−1+cN−2xN−2+⋯+c0,P(F(x))=c_Nx^N-c_{N-1}x^{N-1}+c_{N-2}x^{N-2}+\cdots+c_0,където всички cic_i са положителни. Сега поставяме x=10ex=10^e, като ee е достатъчно голямо, например 10e>10max⁡ici10^e\gt{}10\max_i c_i. Тогава десетичният запис на P(F(10e))P(F(10^e)) се получава чрез заемане от водещия член и представлява конкатенация на записите наcN−1,10e−cN−1,cN−2,cN−3,…,c0,c_N-1,\quad 10^e-c_{N-1},\quad c_{N-2},\quad c_{N-3},\ldots,c_0,като между по-ниските блокове има нужните водещи нули. Например, акоP(F(x))=15x3−7x2+4x+19,P(F(x))=15x^3-7x^2+4x+19,тоP(F(1000))=14 993 004 019.P(F(1000))=14\,993\,004\,019.Следователно сумата на цифрите е от видаS(P(F(10e)))=9e+k,S(P(F(10^e)))=9e+k,където kk е константа, зависеща само от PP и FF, но не и от ee. По Твърдение 2 има произволно големи числа на Фибоначи, които са сравними с kk по модул 99. Някое от тях е равно на 9e+k9e+k за достатъчно голямо ee, което противоречи на условието. Значи PP не може да е неконстантен.
Отвори задачатаEvan Chen VONVON TSTST 2019/6Условие — източник

Задача 7

Пълен запис
Условие
Нека f ⁣:Z→{1,2,…,10100}f\colon\mathbb Z\to\{1,2,\ldots,10^{100}\} е функция, която удовлетворяваgcd⁡(f(x),f(y))=gcd⁡(f(x),x−y)\gcd(f(x),f(y))=\gcd(f(x),x-y)за всички цели числа xx и yy. Да се докаже, че съществуват положителни цели числа mm и nn, такива чеf(x)=gcd⁡(m+x,n)f(x)=\gcd(m+x,n)за всяко цяло число xx.
РешениеНека P\mathcal P е множеството от простите числа, ненадминаващи 1010010^{100}. За всяко p∈Pp\in\mathcal P поставямеep=max⁡xνp(f(x)),e_p=\max_x \nu_p(f(x)),и избираме cpc_p, за което максимумът се достига, т.е. νp(f(cp))=ep\nu_p(f(c_p))=e_p. Ще докажем, че това вече определя всички стойности на ff поотделно за всяко просто число. За всяко p∈Pp\in\mathcal P имамеνp(f(x))=min⁡(νp(x−cp),ep).\nu_p(f(x))=\min(\nu_p(x-c_p),e_p).Наистина, от условието при y=cpy=c_p получавамеgcd⁡(f(cp),f(x))=gcd⁡(f(cp),x−cp).\gcd(f(c_p),f(x))=\gcd(f(c_p),x-c_p).Вземаме νp\nu_p от двете страни. Понеже νp(f(x))≤νp(f(cp))=ep\nu_p(f(x))\le\nu_p(f(c_p))=e_p, получаваме точно желаната формула. Сега избираме nn и mm така:n=∏p∈Ppep,n=\prod_{p\in\mathcal P}p^{e_p},а mm удовлетворява системата сравненияm≡−cp(modpep)за всяко p∈P.m\equiv -c_p\pmod{p^{e_p}}\quad\text{за всяко }p\in\mathcal P.Такава стойност на mm съществува по Китайската теорема за остатъците, като простите степени в модулите са две по две взаимнопрости; модулите с ep=0e_p=0 просто се пропускат. Тогава за всяко x∈Zx\in\mathbb Z имамеf(x)=∏p∈Ppνp(f(x))=∏p∣npmin⁡(νp(x−cp),ep)=∏p∣npmin⁡(νp(x+m),νp(n))=gcd⁡(x+m,n).\begin{align*} f(x)&=\prod_{p\in\mathcal P}p^{\nu_p(f(x))} =\prod_{p\mid n}p^{\min(\nu_p(x-c_p),e_p)}\\ &=\prod_{p\mid n}p^{\min(\nu_p(x+m),\nu_p(n))} =\gcd\left(x+m,n\right). \end{align*}Това е точно исканото представяне.
Отвори задачатаEvan Chen VONVON TSTST 2019/7Условие — източник

Задача 8

Пълен запис
Условие
Дадени са 1616 точки в равнината, никои три от които не лежат на една права. От тях построяваме 88 отсечки, като всяка точка е край на точно една отсечка. Намерете най-малкия възможен брой начини това да се направи така, че никои две от отсечките да не се пресичат във вътрешни точки.
РешениеОтговорът е 14301430. Ще докажем по-общо твърдение: за всеки набор от 2n2n точки в общо положение броят на непересичащите се съвършени сдвоявания е понеCn=1n+1(2nn),C_n=\frac{1}{n+1}\binom{2n}{n},като равенство се достига, когато точките са върхове на изпъкъл 2n2n-ъгълник. За изпъкъл многоъгълник това е стандартното броене на Каталановите числа чрез избора на партньора на един фиксиран връх. Доказваме долната граница със силна индукция по nn. Избираме точка PP от изпъкналата обвивка и номерираме останалите точки A1,A2,…,A2n−1A_1,A_2,\ldots,A_{2n-1} по ъгъл около PP. За всяко k=0,1,…,n−1k=0,1,\ldots,n-1 разглеждаме сдвояванията, в които PP е свързана с A2k+1A_{2k+1}.PA₁A₂A₃A₄A₅A₆A₇A₈A₉A₁₀A₁₁Отсечката PA2k+1PA_{2k+1} разделя останалите точки на две групи с по 2k2k и 2(n−k−1)2(n-k-1) точки. Понеже PP е на изпъкналата обвивка, всяка отсечка, чиито краища са в едната група, не може да пресича отсечка, чиито краища са в другата група, ако и двете сдвоявания са непересичащи се. По индукционното предположение двете групи могат да се сдвоят поне по CkC_k и Cn−k−1C_{n-k-1} начина. Следователно сдвояванията, в които PP е свързана с A2k+1A_{2k+1}, са поне CkCn−k−1C_k C_{n-k-1}. Сумираме по всички възможни kk и получаваме∑k=0n−1CkCn−k−1=Cn,\sum_{k=0}^{n-1} C_k C_{n-k-1}=C_n,което е рекурентната формула за Каталановите числа. При n=8n=8 това дава C8=1430C_8=1430.
Отвори задачатаEvan Chen VONVON TSTST 2019/8Условие — източник