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

Evan Chen / USA TSTST Solutions

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

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

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

2020

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

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

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

11-12

5 задачи

Задача 3

Пълен запис
Условие
Ще наричаме неизроден триъгълник с ъгли с мерки θ1\theta_1, θ2\theta_2, θ3\theta_3 особен, ако съществуват цели числа r1r_1, r2r_2, r3r_3, не всички нули, такива чеr1θ1+r2θ2+r3θ3=0.r_1\theta_1+r_2\theta_2+r_3\theta_3=0.Да се намерят всички цели числа n≥3n\ge3, за които триъгълник със страни n−1n-1, nn, n+1n+1 е особен.
РешениеОтговорът е n=3,4,5,7n=3,4,5,7. Ще използваме следната стандартна разновидност на полиномите на Чебишов. За всяко k≥0k\ge0 съществува полином Pk(X)∈Z[X]P_k(X)\in\mathbb Z[X], който за k≥1k\ge1 е моничен от степен kk, и за койтоPk(X+X−1)=Xk+X−k.P_k(X+X^{-1})=X^k+X^{-k}.Първите няколко са P0(X)=2P_0(X)=2, P1(X)=XP_1(X)=X, P2(X)=X2−2P_2(X)=X^2-2, P3(X)=X3−3XP_3(X)=X^3-3X. Това следва веднага по индукция от рекурсиятаPk+1(T)=TPk(T)−Pk−1(T).P_{k+1}(T)=T P_k(T)-P_{k-1}(T).Нека ъглите на триъгълника са α<β<γ\alpha\lt{}\beta\lt{}\gamma, съответно срещу страните n−1,n,n+1n-1,n,n+1. От косинусовата теорема получаваме2cos⁡α=n+4n+1,2cos⁡γ=n−4n−1.2\cos\alpha=\frac{n+4}{n+1},\qquad 2\cos\gamma=\frac{n-4}{n-1}.Триъгълникът е особен тогава и само тогава, когато съществуват цели неотрицателни r,sr,s, не и двете нули, такива чеcos⁡(rα)=±cos⁡(sγ),\cos(r\alpha)=\pm\cos(s\gamma),или еквивалентноPr(n+4n+1)=±Ps(n−4n−1).P_r\left(\frac{n+4}{n+1}\right)=\pm P_s\left(\frac{n-4}{n-1}\right).Наистина, ако xα+yβ+zγ=0x\alpha+y\beta+z\gamma=0, то от α+β+γ=π\alpha+\beta+\gamma=\pi следва(x−y)α=(y−z)γ−yπ.(x-y)\alpha=(y-z)\gamma-y\pi.Затова можем да вземем r=∣x−y∣r=|x-y| и s=∣y−z∣s=|y-z|; случаят r=s=0r=s=0 би дал x=y=zx=y=z, а тогава xπ=0x\pi=0, тоест трите коефициента са нули. Обратно, ако cos⁡(rα)=±cos⁡(sγ)\cos(r\alpha)=\pm\cos(s\gamma), то rα±sγ=kπ=k(α+β+γ)r\alpha\pm s\gamma=k\pi=k(\alpha+\beta+\gamma) за някое цяло kk, което дава нетривиална целочислена линейна зависимост между ъглите. Ако r=0r=0, то от теоремата за рационалните корени, приложена към Ps(X)±2P_s(X)\pm2, следва, че n−4n−1\frac{n-4}{n-1} трябва да е цяло число. При n≥3n\ge3 това става само за n=4n=4. По същия начин се обработва случаят s=0s=0. По-нататък приемаме n≠4n\ne4 и r,s>0r,s\gt{}0. Нужен ни е следният прост извод. Ако A/BA/B е несъкратима дроб и P(X)∈Z[X]P(X)\in\mathbb Z[X] е моничен от положителна степен, тогава знаменателят на P(A/B)P(A/B) в несъкратим вид има същите прости делители като BB. Действително, след умножаване по подходяща степен на BB, водещият член дава числител, сравним с AdA^d по всеки прост делител на BB, и затова никой такъв прост делител не се съкращава напълно. Следователно, ако n≠4n\ne4 работи, то знаменателите на дробите n+4n+1\frac{n+4}{n+1} и n−4n−1\frac{n-4}{n-1} след съкращаване имат едно и също множество от прости делители. Ноgcd⁡(n+1,n−1)∣2,\gcd(n+1,n-1)\mid2,а числата gcd⁡(n+4,n+1)\gcd(n+4,n+1) и gcd⁡(n−4,n−1)\gcd(n-4,n-1) делят 33. Значи след съкращаване всички нечетни прости делители, освен евентуално 33, са невъзможни. Получават се само следните три случая: 1. n+1=2un+1=2^u и n−1=2vn-1=2^v. Това дава само n=3n=3. Тогава 2cos⁡α=742\cos\alpha=\frac74 и 2cos⁡γ=−122\cos\gamma=-\frac12, а P2(−1/2)=−74P_2(-1/2)=-\frac74. 2. n+1=3⋅2un+1=3\cdot2^u и n−1=2vn-1=2^v. Това дава само n=5n=5. Тогава 2cos⁡α=322\cos\alpha=\frac32 и 2cos⁡γ=142\cos\gamma=\frac14, а P2(3/2)=14P_2(3/2)=\frac14. 3. n+1=2un+1=2^u и n−1=3⋅2vn-1=3\cdot2^v. Това дава само n=7n=7. Тогава 2cos⁡α=1182\cos\alpha=\frac{11}{8} и 2cos⁡γ=122\cos\gamma=\frac12, а P3(1/2)=−118P_3(1/2)=-\frac{11}{8}. Накрая n=4n=4 също работи, защото триъгълникът със страни 3,4,53,4,5 е правоъгълен и за ъглите му е изпълнено α+β−γ=0\alpha+\beta-\gamma=0. Така точно n=3,4,5,7n=3,4,5,7 са решения.
Отвори задачатаEvan Chen VONVON TSTST 2020/3Условие — източник

Задача 4

Пълен запис
Условие
Да се намерят всички двойки положителни цели числа (a,b)(a,b), които удовлетворяват следните условия: 1. aa дели b4+1b^4+1; 2. bb дели a4+1a^4+1; 3. ⌊a⌋=⌊b⌋\lfloor\sqrt a\rfloor=\lfloor\sqrt b\rfloor.
РешениеЕдинствените решения са (1,1)(1,1), (1,2)(1,2) и (2,1)(2,1); те очевидно работят. Ще докажем, че други няма. Първо, ясно е, че gcd⁡(a,b)=1\gcd(a,b)=1. От условията следва, че и aa, и bb делят (a−b)4+1(a-b)^4+1, следователноab∣(a−b)4+1.ab\mid(a-b)^4+1.Поставямеk=(b−a)4+1ab.k=\frac{(b-a)^4+1}{ab}.Оценка. Имаме k≤16k\le16. Наистина, некаn=⌊a⌋=⌊b⌋.n=\lfloor\sqrt a\rfloor=\lfloor\sqrt b\rfloor.Тогава a,b∈[n2,n2+2n]a,b\in[n^2,n^2+2n]. Следователноab≥n2(n2+1)≥n4+1ab\ge n^2(n^2+1)\ge n^4+1и(b−a)4+1≤(2n)4+1=16n4+1,(b-a)^4+1\le(2n)^4+1=16n^4+1,откъдето k≤16k\le16. Ще докажем, че всъщност k=1k=1. Първо, kk не може да е четно. Ако беше четно, тогава aa и bb щяха да са с различна четност, но тогава (b−a)4+1≡2(mod4)(b-a)^4+1\equiv2\pmod4, докато kabkab се дели на 44 - противоречие. Значи kk е нечетно. Всеки нечетен прост делител на число от вида x4+1x^4+1 е сравним с 11 по модул 88: ако q∣x4+1q\mid x^4+1, то x8≡1(modq)x^8\equiv1\pmod q, но x4≢1(modq)x^4\not\equiv1\pmod q, така че редът на xx по модул qq е 88. Следователно 8∣q−18\mid q-1. Така всеки нечетен прост делител е поне 1717. Понеже k≤16k\le16, получаваме k=1k=1. Остава да решимab=(b−a)4+1.ab=(b-a)^4+1.Пишем b=a+db=a+d и без ограничение приемаме d≥0d\ge0. Тогаваa(a+d)=d4+1,a(a+d)=d^4+1,илиa2+ad−(d4+1)=0.a^2+ad-(d^4+1)=0.Дискриминантатаd2+4(d4+1)=4d4+d2+4d^2+4(d^4+1)=4d^4+d^2+4трябва да е точен квадрат. При d=0d=0 получаваме (1,1)(1,1), а при d=1d=1 получаваме (1,2)(1,2). Ако d≥2d\ge2, то(2d2)2<4d4+d2+4<4d4+4d2+1=(2d2+1)2,(2d^2)^2\lt{}4d^4+d^2+4\lt{}4d^4+4d^2+1=(2d^2+1)^2,така че дискриминантата не може да е точен квадрат. Това дава само (1,1)(1,1) и (1,2)(1,2) при b≥ab\ge a; по симетрия получаваме и (2,1)(2,1).
Отвори задачатаEvan Chen VONVON TSTST 2020/4Условие — източник

Задача 7

Пълен запис
Условие
Да се намерят всички неконстантни полиноми P(z)P(z) с комплексни коефициенти, за които всички комплексни корени на полиномите P(z)P(z) и P(z)−1P(z)-1 имат модул 11.
РешениеОтговорът е: полиномитеP(z)=λzn−μ,P(z)=\lambda z^n-\mu,където n≥1n\ge1, ∣λ∣=∣μ∣|\lambda|=|\mu| и Re⁡μ=−12\operatorname{Re}\mu=-\frac12. Лесно се проверява, че всички такива полиноми работят: корените на PP имат модул 11, когато ∣μ∣=∣λ∣|\mu|=|\lambda|, а корените на P−1P-1 имат модул 11, когато ∣μ+1∣=∣λ∣|\mu+1|=|\lambda|; двете условия са еквивалентни на написаното. Остава да докажем, че други решения няма. НекаP(z)=cnzn+cn−1zn−1+⋯+c1z+c0=cn(z+α1)(z+α2)⋯(z+αn),P(z)−1=cn(z+β1)(z+β2)⋯(z+βn).\begin{align*} P(z)&=c_nz^n+c_{n-1}z^{n-1}+\cdots+c_1z+c_0\\ &=c_n(z+\alpha_1)(z+\alpha_2)\cdots(z+\alpha_n),\\ P(z)-1&=c_n(z+\beta_1)(z+\beta_2)\cdots(z+\beta_n). \end{align*}По условие ∣αi∣=∣βi∣=1|\alpha_i|=|\beta_i|=1 за всички ii. Понеже при комплексно спрегнатите числа имаме αi‾=1/αi\overline{\alpha_i}=1/\alpha_i и βi‾=1/βi\overline{\beta_i}=1/\beta_i, от равенството(z+α1)⋯(z+αn)=(z+β1)⋯(z+βn)+cn−1(z+\alpha_1)\cdots(z+\alpha_n)=(z+\beta_1)\cdots(z+\beta_n)+c_n^{-1}след спрягане на коефициентите получаваме(z+1α1)⋯(z+1αn)=\left(z+\frac1{\alpha_1}\right)\cdots\left(z+\frac1{\alpha_n}\right)=(z+1β1)⋯(z+1βn)+cn‾ −1.\left(z+\frac1{\beta_1}\right)\cdots\left(z+\frac1{\beta_n}\right)+\overline{c_n}^{\,-1}.Сравняваме коефициентите пред zkz^k в последното равенство. За k=1,2,…,n−1k=1,2,\ldots,n-1 това даваcn−kα1α2⋯αn=cn−kβ1β2⋯βn.\frac{c_{n-k}}{\alpha_1\alpha_2\cdots\alpha_n}=\frac{c_{n-k}}{\beta_1\beta_2\cdots\beta_n}.Но от свободните членове в равенството за PP и P−1P-1 имамеα1α2⋯αn−β1β2⋯βn=1cn≠0.\alpha_1\alpha_2\cdots\alpha_n-\beta_1\beta_2\cdots\beta_n=\frac1{c_n}\ne0.Следователно cn−k=0c_{n-k}=0 за всяко k=1,2,…,n−1k=1,2,\ldots,n-1. Значи всички междинни коефициенти на PP са нули иP(z)=λzn−μ.P(z)=\lambda z^n-\mu.Както вече отбелязахме, условията за корените са точно ∣λ∣=∣μ∣=∣μ+1∣|\lambda|=|\mu|=|\mu+1|, което е еквивалентно на ∣λ∣=∣μ∣|\lambda|=|\mu| и Re⁡μ=−12\operatorname{Re}\mu=-\frac12.
Отвори задачатаEvan Chen VONVON TSTST 2020/7Условие — източник

Задача 8

Пълен запис
Условие
За всяко положително цяло число NN нека σ(N)\sigma(N) означава сумата на положителните делители на NN. Да се намерят всички цели числа m≥n≥2m\ge n\ge2, за коитоσ(m)−1m−1=σ(n)−1n−1=σ(mn)−1mn−1.\frac{\sigma(m)-1}{m-1}=\frac{\sigma(n)-1}{n-1}=\frac{\sigma(mn)-1}{mn-1}.
РешениеОтговорът е: mm и nn трябва да са степени на едно и също просто число. Първо проверяваме, че всички такива двойки работят. Ако m=pam=p^a и n=pbn=p^b, то за всяко e≥1e\ge1 имамеσ(pe)−1pe−1=(1+p+⋯+pe)−1pe−1=\frac{\sigma(p^e)-1}{p^e-1}=\frac{(1+p+\cdots+p^e)-1}{p^e-1}=p(1+p+⋯+pe−1)pe−1=pp−1.\frac{p(1+p+\cdots+p^{e-1})}{p^e-1}=\frac{p}{p-1}.Същото важи и за mn=pa+bmn=p^{a+b}, така че условията са изпълнени. Сега доказваме обратното. Нека λ\lambda е общата стойност на трите дроби. Делителите на mnmn включват всички делители на mm, както и числата mdm d, където dd пробягва делителите на nn; числото mm е преброено два пъти, затова го изваждаме веднъж. Следователноσ(mn)≥σ(m)+mσ(n)−m=(λm−λ+1)+m(λn−λ+1)−m=λmn−λ+1.\begin{align*} \sigma(mn)&\ge\sigma(m)+m\sigma(n)-m\\ &=(\lambda m-\lambda+1)+m(\lambda n-\lambda+1)-m\\ &=\lambda mn-\lambda+1. \end{align*}Но от дефиницията на λ\lambda имаме точно σ(mn)=λmn−λ+1\sigma(mn)=\lambda mn-\lambda+1. Значи равенството в горната оценка е равенство и всеки делител на mnmn е или делител на mm, или е от вида mdm d за някой делител dd на nn. Прилагайки същия аргумент със сменени роли на mm и nn, получаваме също, че всеки делител на mnmn е или делител на nn, или е от вида ndn d за някой делител dd на mm. Ще покажем, че mm и nn имат само един и същ прост делител. Ако съществува просто число p∣np\mid n, но p∤mp\nmid m, тогава pp е делител на mnmn, но не е делител на mm и не може да е от вида mdmd понеже m≥2m\ge2. Противоречие. По симетрия всеки прост делител на mm дели nn, така че mm и nn имат едни и същи прости делители. Да допуснем, че има поне две различни такива прости числа, pp и qq. Некаνp(m)=α,νp(n)=β.\nu_p(m)=\alpha,\qquad \nu_p(n)=\beta.Тогава p^{\alpha+eta} е делител на mnmn. Той не е делител на mm, защото степента на pp е твърде голяма. Не може да е и от вида mdm d с d∣nd\mid n, защото qq дели mm, а числото p^{\alpha+eta} няма делител qq. Това е противоречие. Следователно има само едно просто число в разлаганията на mm и nn, т.е. mm и nn са степени на едно и също просто число.
Отвори задачатаEvan Chen VONVON TSTST 2020/8Условие — източник

Задача 9

Пълен запис
Условие
Десет милиона светулки светят в R3\mathbb R^3 в полунощ. Някои от светулките са приятелки, като приятелството винаги е взаимно. Всяка секунда една светулка се премества на ново място така, че разстоянието й до всяка от приятелките й е същото, каквото е било преди преместването. Това е единственият начин, по който светулките някога променят положенията си. Никои две светулки никога не могат да заемат една и съща точка. Първоначално никои две светулки, независимо дали са приятелки, или не, не са на разстояние повече от един метър. След краен брой секунди всички светулки се оказват на разстояние поне десет милиона метра от първоначалните си положения. При тези условия намерете най-големия възможен брой приятелства между светулките.
РешениеОтговорът е⌊10143⌋=33333333333333.\left\lfloor\frac{10^{14}}3\right\rfloor=33333333333333.По-общо ще докажем, че за n≥70n\ge70 най-големият възможен брой приятелства еf(n)=⌊n23⌋.f(n)=\left\lfloor\frac{n^2}3\right\rfloor.Първо описваме конструкция. Избираме три успоредни прави ℓA,ℓB,ℓC\ell_A,\ell_B,\ell_C, чието перпендикулярно сечение е равностранен триъгълник с много малка положителна страна. Поставяме светулките възможно най-равно върху трите прави, в достатъчно къси отрязъци, така че първоначално всички разстояния да са най-много 11 и никои две светулки да не съвпадат. Обявяваме две светулки за приятелки точно когато лежат върху различни от трите прави. Така получаваме пълен триделен граф с възможно най-равни дялове, следователно броят на приятелствата е f(n)f(n). Да видим, че тази конфигурация е допустима. Отразяваме последователно всички светулки върху ℓA\ell_A спрямо равнината през ℓB\ell_B и ℓC\ell_C, после всички светулки върху ℓB\ell_B спрямо равнината през текущите ℓC\ell_C и ℓA\ell_A, после всички светулки върху ℓC\ell_C спрямо равнината през текущите ℓA\ell_A и ℓB\ell_B, и повтаряме. Всяко такова отражение може да се извърши светулка по светулка, защото приятелките на движещата се светулка лежат в равнината на отражение, а отражението запазва разстоянията до всички точки от тази равнина. В перпендикулярно сечение това е разгъване по триъгълната решетка, затова след достатъчно много повторения трите прави, а значи и всички светулки, са на произволно голямо разстояние от началните си положения. Това дава долната граница. Сега доказваме горната граница. Разглеждаме произволна допустима конфигурация с nn светулки. Ако графът на приятелствата няма 44-клика, то по теоремата на Туран броят на ребрата е най-много f(n)f(n). Остава случаят, когато има четири взаимно приятелски светулки, да ги означим с a,b,c,da,b,c,d. Нека g(n)g(n) е най-големият възможен брой приятелства при наличие на такава 44-клика. Ще използваме прост факт: за да може една светулка да се премести на друго място, всичките й приятелки в този момент трябва да са в една равнина, понеже те лежат в срединната равнина на отсечката между старото и новото й положение. Първо не може четири копланарни светулки да са две по две приятелки. Ако това се случи, никоя от тях не може да се премести нетривиално, запазвайки разстоянията до другите три; в изродения случай с три колинеарни точки ограничението е още по-силно. Това противоречи на факта, че накрая всяка светулка се е отдалечила много от началното си положение. Ключово твърдение. Има най-много 1212 светулки ee, които са приятелки с поне три от a,b,c,da,b,c,d. Нека A,B,C,DA,B,C,D са текущите положения на a,b,c,da,b,c,d. Тези точки се менят с времето, но тетраедърът ABCDABCD винаги има една и съща форма, защото шестте му ръба са разстояния между приятелки. Ще използваме този тетраедър като подвижна отправна система. Без ограничение нека ee е приятелка с a,b,ca,b,c. Тогава спрямо триъгълника ABCABC светулката ee винаги се намира в една от две възможни точки E1E_1 и E2E_2, симетрични спрямо равнината ABCABC, така че E1ABCE_1ABC и E2ABCE_2ABC са тетраедри с фиксирана форма. Точките D,E1,E2D,E_1,E_2 са различни; ако например DD съвпадне с една от тези две възможности, някоя от светулките от 44-кликата няма да може да се движи нетривиално. Поглеждаме момента, в който се движи светулката aa. Тогава приятелките й b,c,d,eb,c,d,e трябва да са копланарни, следователно една от точките E1,E2E_1,E_2 лежи в равнината BCDBCD. По същия начин, когато се движат bb и cc, една от точките E1,E2E_1,E_2 лежи съответно в равнините ACDACD и ABDABD. От три равнини и две възможни точки следва, че след преименуване можем да считаме, че E1E_1 лежи едновременно в равнините BCDBCD и ACDACD. Значи E1E_1 лежи на правата CDCD, а E2E_2 лежи в равнината ABDABD. Това определя еднозначно двойката {E1,E2}\{E_1,E_2\} спрямо тетраедъра ABCDABCD: точката E1E_1 е пресечната точка на правата CDCD с отражението на равнината ABDABD спрямо равнината ABCABC, а E2E_2 е пресечната точка на равнината ABDABD с отражението на правата CDCD спрямо равнината ABCABC. Като отчетем избора на трите приятелки измежду a,b,c,da,b,c,d и избора кои две равнини се падат на една и съща от двете възможни точки, получаваме най-много 1212 възможности за положението на ee. Освен това една светулка не може да е приятелка и с четирите от a,b,c,da,b,c,d, защото приятелките й не биха били копланарни. Следователно всяка от тези най-много 1212 светулки дава най-много 33 ребра към четворката. Затова ребрата, които имат точно един край измежду a,b,c,da,b,c,d, са най-много(n−16)⋅2+12⋅3=2n+4.(n-16)\cdot2+12\cdot3=2n+4.След премахване на четирите светулки a,b,c,da,b,c,d получавамеg(n)≤6+(2n+4)+max⁡{f(n−4),g(n−4)}.g(n)\le6+(2n+4)+\max\{f(n-4),g(n-4)\}.За n≥24n\ge24 имаме(2n+10)+f(n−4)≤f(n),(2n+10)+f(n-4)\le f(n),следователноg(n)≤max⁡{f(n),(2n+10)+g(n−4)}.g(n)\le\max\{f(n),(2n+10)+g(n-4)\}.Итерираме това неравенство. Нека rr е такова, чеn−4r−4<24≤n−4r.n-4r-4\lt{}24\le n-4r.Тогаваg(n)≤max⁡{f(n), (2n+10)+(2(n−4)+10)+⋯+(2(n−4r)+10)+g(n−4r−4)}.\begin{align*} g(n)\le\max\Big\{f(n),\ &(2n+10)+(2(n-4)+10)+\cdots\\ &+(2(n-4r)+10)+g(n-4r-4)\Big\}. \end{align*}Последният сбор е най-много(r+1)(2n−4r+10)+(242)≤(n4−5)(n+37)+(242),\begin{align*} &(r+1)(2n-4r+10)+\binom{24}{2}\\ &\le\left(\frac n4-5\right)(n+37)+\binom{24}{2}, \end{align*}а за n≥70n\ge70 това е по-малко от f(n)f(n). Следователно и при наличие на 44-клика имаме най-много f(n)f(n) приятелства. За n=107n=10^7 получаваме търсения отговор ⌊1014/3⌋=33333333333333\left\lfloor10^{14}/3\right\rfloor=33333333333333.
Отвори задачатаEvan Chen VONVON TSTST 2020/9Условие — източник