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

Evan Chen / USA TSTST Solutions

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

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

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

2021

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

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

  • 2021 · 11-12: липсва задача 6, 7, 8

11-12

5 задачи

Задача 2

Пълен запис
Условие
Нека a1<a2<a3<a4<⋯a_1\lt{}a_2\lt{}a_3\lt{}a_4\lt{}\dotsb е безкрайна редица от реални числа в интервала (0,1)(0,1). Да се докаже, че съществува число, което се среща точно веднъж в редицатаa11,  a22,  a33,  a44,  … .\frac{a_1}{1},\;\frac{a_2}{2},\;\frac{a_3}{3},\;\frac{a_4}{4},\;\dots.
РешениеЩе докажем твърдението с противоречие. Да допуснем, че за всяко λ\lambda, за което множествотоSλ={k:ak/k=λ}S_\lambda=\{k: a_k/k=\lambda\}не е празно, то съдържа поне два елемента. Забелязваме, че всяко SλS_\lambda е крайно, защото от ak=kλ<1a_k=k\lambda\lt{}1 следва k<1/λk\lt{}1/\lambda. Нека mλm_\lambda и MλM_\lambda са съответно най-малкият и най-големият елемент на SλS_\lambda, и некаTλ={mλ,mλ+1,…,Mλ}.T_\lambda=\{m_\lambda,m_\lambda+1,\ldots,M_\lambda\}.Така всяко TλT_\lambda е интервал от поне две последователни положителни цели числа, а интервалите TλT_\lambda покриват N\mathbb N. Освен това всяко фиксирано положително цяло число е покрито краен брой пъти, защото има само краен брой възможни стойности на mλm_\lambda, които не надминават дадена граница. Ще използваме следното просто наблюдение: ако три интервала имат обща точка, то един от тях се съдържа в обединението на другите два. Следователно, ако някое положително цяло число е покрито повече от два пъти от интервалите TλT_\lambda, можем да премахнем един от тези интервали, без да развалим свойството, че останалите покриват N\mathbb N. Понеже всяка точка е покрита краен брой пъти, можем да повтаряме тази операция и да получим подсемейство, което още покрива N\mathbb N, но всяко положително цяло число се съдържа в най-много два от останалите интервали. Нека Λ\Lambda е множеството от стойностите на λ\lambda, чиито интервали са останали. Тогава⋃λ∈ΛTλ=N,\bigcup_{\lambda\in\Lambda}T_\lambda=\mathbb N,а всяко положително цяло число принадлежи на най-много два интервала TλT_\lambda. Затова∑λ∈Λ∑k∈Tλ(ak+1−ak)≤\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}(a_{k+1}-a_k)\le2∑k≥1(ak+1−ak)≤2, 2\sum_{k\ge1}(a_{k+1}-a_k)\le2,тъй като всички aka_k лежат между 00 и 11. От друга страна, за фиксирано λ∈Λ\lambda\in\Lambda имаме amλ=λmλa_{m_\lambda}=\lambda m_\lambda и aMλ=λMλa_{M_\lambda}=\lambda M_\lambda. Следователно2∑k∈Tλ(ak+1−ak)≥2∑mλ≤k<Mλ(ak+1−ak)=2(aMλ−amλ)=2(Mλ−mλ)λ=2(Mλ−mλ)amλmλ≥(Mλ−mλ+1)a1mλ≥a1∑k∈Tλ1k.\begin{align*} 2\sum_{k\in T_\lambda}(a_{k+1}-a_k)&\ge 2\sum_{m_\lambda\le k\lt{}M_\lambda}(a_{k+1}-a_k)\\ &=2(a_{M_\lambda}-a_{m_\lambda})=2(M_\lambda-m_\lambda)\lambda\\ &=2(M_\lambda-m_\lambda)\frac{a_{m_\lambda}}{m_\lambda}\\ &\ge (M_\lambda-m_\lambda+1)\frac{a_1}{m_\lambda}\\ &\ge a_1\sum_{k\in T_\lambda}\frac1k. \end{align*}Сумирайки по всички λ∈Λ\lambda\in\Lambda, получаваме4≥2∑λ∈Λ∑k∈Tλ(ak+1−ak)≥4\ge 2\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}(a_{k+1}-a_k)\gea1∑λ∈Λ∑k∈Tλ1k≥a1∑k≥11k. a_1\sum_{\lambda\in\Lambda}\sum_{k\in T_\lambda}\frac1k\ge a_1\sum_{k\ge1}\frac1k.Последното е невъзможно, понеже хармоничният ред е разходящ. Полученото противоречие доказва твърдението.
Отвори задачатаEvan Chen VONVON TSTST 2021/2Условие — източник

Задача 3

Пълен запис
Условие
Намерете всички положителни цели числа k>1k\gt{}1, за които съществува положително цяло число nn, такова че (nk)\binom nk се дели на nn, а (nm)\binom nm не се дели на nn за всяко 2≤m<k2\le m\lt{}k.
РешениеТакова число nn съществува за всяко k>1k\gt{}1. Първо нека kk е просто число. Избирамеn=(k−1)!.n=(k-1)!.За m<km\lt{}k от m!∣nm!\mid n следва(n−1)(n−2)⋯(n−m+1)≡(−1)(−2)⋯(−m+1)≡(−1)m−1(m−1)!≢0(modm!).\begin{align*} (n-1)(n-2)\cdots(n-m+1)&\equiv(-1)(-2)\cdots(-m+1)\\ &\equiv(-1)^{m-1}(m-1)!\not\equiv0\pmod{m!}. \end{align*}Затова m!m! не дели (n−1)(n−2)⋯(n−m+1)(n-1)(n-2)\cdots(n-m+1) и (nm)\binom nm не е кратно на nn. За m=km=k имаме(nk)=nk(n−1k−1).\binom nk=\frac nk\binom{n-1}{k-1}.Понеже k∤nk\nmid n, а kk е просто, от теоремата на Уилсън следва, че k∣(n−1k−1)k\mid\binom{n-1}{k-1}. Следователно n∣(nk)n\mid\binom nk. Сега нека kk е съставно. Ще изберем nn, удовлетворяващо няколко сравнения. За всяко просто p≤kp\le k полагамеtp=νp(lcm⁡(1,2,…,k−1))=t_p=\nu_p(\operatorname{lcm}(1,2,\dots,k-1))=max⁡(νp(1),νp(2),…,νp(k−1))\max(\nu_p(1),\nu_p(2),\dots,\nu_p(k-1))и избираме kp∈{1,2,…,k−1}k_p\in\{1,2,\dots,k-1\} възможно най-голямо, така че νp(kp)=tp\nu_p(k_p)=t_p. Искаме nn да удовлетворяваn≡0(modptp+1)ако p∤k,\labeleq:tstst2021−3−cong1νp(n−kp)=tp+νp(k)ако p∣k.\labeleq:tstst2021−3−cong2\begin{align} n&\equiv0\pmod{p^{t_p+1}} &&\text{ако } p\nmid k, \label{eq:tstst2021-3-cong1}\\ \nu_p(n-k_p)&=t_p+\nu_p(k) &&\text{ако } p\mid k. \label{eq:tstst2021-3-cong2} \end{align}за всички прости p≤kp\le k. По Китайската теорема за остатъците такова nn съществува. Например за \eqref{eq:tstst2021-3-cong2} е достатъчно да наложимn≡kp+ptp+νp(k)(modptp+νp(k)+1).n\equiv k_p+p^{t_p+\nu_p(k)}\pmod{p^{t_p+\nu_p(k)+1}}.Ще покажем, че това nn върши работа. Първо пресмятаме νp(n−i)\nu_p(n-i) за прости p<kp\lt{}k и 1≤i<k1\le i\lt{}k. Ако p∤kp\nmid k, то νp(i),νp(n−i)≤tp\nu_p(i),\nu_p(n-i)\le t_p и νp(n)>tp\nu_p(n)\gt{}t_p, откъдето νp(n−i)=νp(i)\nu_p(n-i)=\nu_p(i). Ако p∣kp\mid k и i≠kpi\ne k_p, отново имаме νp(i),νp(n−i)≤tp\nu_p(i),\nu_p(n-i)\le t_p и νp(n)≥tp\nu_p(n)\ge t_p, така че νp(n−i)=νp(i)\nu_p(n-i)=\nu_p(i). Ако p∣kp\mid k и i=kpi=k_p, тогава по конструкцияνp(n−i)=νp(i)+νp(k).\nu_p(n-i)=\nu_p(i)+\nu_p(k).Следователно винаги имаме νp(n−i)=νp(i)\nu_p(n-i)=\nu_p(i), освен при i=kpi=k_p, където се добавя νp(k)\nu_p(k); тази формула е безвредна и когато p∤kp\nmid k, понеже тогава νp(k)=0\nu_p(k)=0. Ще докажем, че (nk)\binom nk се дели на nn. Това е равносилно на това k!k! да дели(n−1)(n−2)⋯(n−k+1).(n-1)(n-2)\cdots(n-k+1).За всяко просто p≤kp\le k имамеνp((n−1)(n−2)⋯(n−k+1))=νp(n−kp)+∑i<ki≠kpνp(n−i)=νp(kp)+νp(k)+∑i<ki≠kpνp(i)=∑i=1kνp(i)=νp(k!).\begin{align*} \nu_p((n-1)(n-2)\cdots(n-k+1)) &=\nu_p(n-k_p)+\sum_{\substack{i\lt{}k\\ i\ne k_p}}\nu_p(n-i)\\ &=\nu_p(k_p)+\nu_p(k)+\sum_{\substack{i\lt{}k\\ i\ne k_p}}\nu_p(i)\\ &=\sum_{i=1}^k\nu_p(i)=\nu_p(k!). \end{align*}Значи k!k! дели произведението и n∣(nk)n\mid\binom nk. Накрая нека 1<m<k1\lt{}m\lt{}k. Ще покажем, че nn не дели (nm)\binom nm, т.е. че m!m! не дели (n−1)(n−2)⋯(n−m+1)(n-1)(n-2)\cdots(n-m+1). Ако mm има прост делител qq, който не дели kk, тогаваνq((n−1)(n−2)⋯(n−m+1))=∑i=1m−1νq(n−i)=∑i=1m−1νq(i)=νq((m−1)!)<νq(m!),\begin{align*} \nu_q((n-1)(n-2)\cdots(n-m+1)) &=\sum_{i=1}^{m-1}\nu_q(n-i)\\ &=\sum_{i=1}^{m-1}\nu_q(i)=\nu_q((m-1)!)\lt{}\nu_q(m!), \end{align*}което е достатъчно. Остава случаят, когато всички прости делители на mm делят kk. Ако има такъв прост делител pp, за който νp(m)>νp(k)\nu_p(m)\gt{}\nu_p(k), тогаваνp((n−1)(n−2)⋯(n−m+1))=νp(k)+∑i=1m−1νp(i)<νp(m)+∑i=1m−1νp(i)=νp(m!),\begin{align*} \nu_p((n-1)(n-2)\cdots(n-m+1)) &=\nu_p(k)+\sum_{i=1}^{m-1}\nu_p(i)\\ &\lt{}\nu_p(m)+\sum_{i=1}^{m-1}\nu_p(i)=\nu_p(m!), \end{align*}и пак сме готови. Ако пък νp(m)≤νp(k)\nu_p(m)\le\nu_p(k) за всяко p∣kp\mid k, то m∣km\mid k и понеже m<km\lt{}k, имаме m≤k/2m\le k/2. Нека pp е прост делител на mm. От избора на kpk_p следва kp≥k/2k_p\ge k/2: иначе вместо kpk_p бихме могли да използваме 2kp2k_p. Следователно m≤k/2≤kpm\le k/2\le k_p, иνp((n−1)(n−2)⋯(n−m+1))=∑i=1m−1νp(n−i)=∑i=1m−1νp(i)=νp((m−1)!)<νp(m!).\begin{align*} \nu_p((n-1)(n-2)\cdots(n-m+1)) &=\sum_{i=1}^{m-1}\nu_p(n-i)\\ &=\sum_{i=1}^{m-1}\nu_p(i)=\nu_p((m-1)!)\lt{}\nu_p(m!). \end{align*}Така и в последния случай m!m! не дели нужното произведение. Следователно (nm)\binom nm не се дели на nn за всяко m<km\lt{}k, а избраното nn има исканото свойство.
Отвори задачатаEvan Chen VONVON TSTST 2021/3Условие — източник

Задача 4

Пълен запис
Условие
Нека aa и bb са положителни цели числа. Да се предположи, че съществуват безбройно много двойки положителни цели числа (m,n)(m,n), за които и m2+an+bm^2+an+b, и n2+am+bn^2+am+b са точни квадрати. Докажете, че aa дели 2b2b.
РешениеРазглеждаме aa и bb като фиксирани. По условие има безбройно много четворки (m,n,r,s)(m,n,r,s) от положителни цели числа, удовлетворяващиm2+an+b=(m+r)2,n2+am+b=(n+s)2.\begin{gather*} m^2+an+b=(m+r)^2,\\ n^2+am+b=(n+s)^2. \end{gather*}Ще наричаме двойката (r,s)(r,s) изключителна, ако за нея съществуват безбройно много двойки (m,n)(m,n), удовлетворяващи тази система. Твърдение. Ако (r,s)(r,s) е изключителна двойка, то е изпълнено поне едно от следните:0<r<a2 и 0<s≤a24,0\lt{}r\lt{}\frac a2 \text{ и } 0\lt{}s\le\frac{a^2}{4},0<s<a2 и 0<r≤a24,0\lt{}s\lt{}\frac a2 \text{ и } 0\lt{}r\le\frac{a^2}{4},илиr2+s2≤2b.r^2+s^2\le2b.В частност има само краен брой изключителни двойки (r,s)(r,s). Доказателство на твърдението. Събираме двете уравнения и получавамеr2+s2−2b=(a−2r)m+(a−2s)n.(†)r^2+s^2-2b=(a-2r)m+(a-2s)n. \qquad(\dagger)Ако 0<r<a/20\lt{}r\lt{}a/2, използваме от първото уравнение оценката an+b≥2m+1an+b\ge2m+1, откъдетоm≤an+b−12.m\le\frac{an+b-1}{2}.Следователно(n+s)2=n2+am+b≤n2+a⋅an+b−12+b.(n+s)^2=n^2+am+b\le n^2+a\cdot\frac{an+b-1}{2}+b.За да е възможно това за безбройно много цели числа nn, при сравнение на коефициентите пред nn трябва да имаме 2s≤a2/22s\le a^2/2, т.е. s≤a2/4s\le a^2/4. Аналогично се разглежда случаят 0<s<a/20\lt{}s\lt{}a/2. Ако min⁡(r,s)>a/2\min(r,s)\gt{}a/2, тогава от (†)(\dagger) следва r2+s2≤2br^2+s^2\le2b. Това доказва твърдението. Понеже има краен брой възможни изключителни двойки, съществува конкретна двойка (r,s)(r,s), за която системата има безбройно много решения (m,n)(m,n). След опростяване системата ставаan=2rm+r2−b,2sn=am+b−s2.\begin{gather*} an=2rm+r^2-b,\\ 2sn=am+b-s^2. \end{gather*}Това е линейна система по m,nm,n. За да има безбройно много решения, двете уравнения трябва да са зависими. Следователноa2s=2ra=r2−bb−s2.\frac a{2s}=\frac{2r}{a}=\frac{r^2-b}{b-s^2}.Оттукa=2x2rsa=2\sqrt{\vphantom{x^2}rs}иb=s2r+r2sr+s.b=\frac{s^2\sqrt r+r^2\sqrt s}{\sqrt r+\sqrt s}.Понеже rsrs е точен квадрат, можем да запишемr=kx2,s=ky2,gcd⁡(x,y)=1.r=kx^2,\qquad s=ky^2,\qquad \gcd(x,y)=1.Тогава получавамеa=2kxya=2kxyиb=k2xy(x2−xy+y2).b=k^2xy(x^2-xy+y^2).Следователно2b=a⋅k(x2−xy+y2),2b=a\cdot k(x^2-xy+y^2),така че a∣2ba\mid2b, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2021/4Условие — източник

Задача 5

Пълен запис
Условие
Нека TT е дърво с nn върха и точно kk листа. Да се предположи, че съществува множество от поне n+k−12\frac{n+k-1}{2} върха на TT, никои два от които не са съседни. Докажете, че най-дългият път в TT съдържа четен брой ребра.
РешениеНай-дългият път в дърво винаги свързва две листа. Ще покажем, че при единственото правилно двуцветяване на TT всички листа са в един и същи цвят; тогава всеки път между две листа има четен брой ребра. Първо решение. Ще използваме следната лема. Лема. Ако SS е независимо множество от върхове в TT, то∑v∈Sdeg⁡(v)≤n−1.\sum_{v\in S}\deg(v)\le n-1.Равенство има тогава и само тогава, когато SS е един от двата цветови класа в единственото двуцветяване на дървото. Доказателство на лемата. Всяко ребро на TT е инцидентно с най-много един връх от SS, понеже SS е независимо. Това дава неравенството чрез броене на ребрата според върховете от SS, към които са инцидентни. За равенство всяко ребро трябва да е инцидентно с точно един връх от SS, което е точно условието SS да бъде един от двата цветови класа. По условие съществува независимо множество с поне n+k−12\frac{n+k-1}{2} върха. За да минимизираме сумата от степените на толкова върхове, първо бихме взели всички kk листа, които имат степен 11, а останалите избрани върхове имат степен поне 22. Следователно сумата от степените на избраните върхове е понеk+2⋅n−k−12=n−1.k+2\cdot\frac{n-k-1}{2}=n-1.От лемата тя е и най-много n−1n-1, така че навсякъде имаме равенство. Следователно независимото множество съдържа всички листа и е един от двата цветови класа. Значи всички листа са в един и същи цвят, както искахме. Второ решение. Ще използваме друга лема. Лема. Върховете на TT могат да се разбият на k−1k-1 пътя, така че ребрата на TT, които не са част от тези пътища, са инцидентни с краен връх на някой от пътищата. Доказателство. Повтаряме следната операция: вземаме листо и премахваме най-дългия път, който го съдържа и след чието премахване останалият граф все още е дърво. Така всеки път използва две листа от текущото дърво, с изключение на последната тривиална стъпка, и се получават k−1k-1 пътя с исканото свойство. Нека един от тези пътища има aa върха. В независимо множество могат да попаднат най-много a+12\frac{a+1}{2} от тях. Ако дължините на пътищата са a1,…,ak−1a_1,\dots,a_{k-1}, то максималният размер на независимо множество в TT е най-много∑iai+12=n+k−12.\sum_i\frac{a_i+1}{2}=\frac{n+k-1}{2}.Понеже по условие тази оценка се достига, всеки от пътищата трябва да има нечетен брой върхове. При двуцветяването на такъв път крайните му върхове са в един и същи цвят; да го наречем червен. Единственото независимо множество с размер n+k−12\frac{n+k-1}{2} е множеството от всички червени върхове по тези пътища. По лемата всяко ребро, което не е в някой от пътищата, свързва краен връх на път, т.е. червен връх, с друг връх. Този друг връх трябва да е син, защото червените върхове образуват независимо множество. Следователно двуцветяването на пътищата се продължава до единственото двуцветяване на цялото дърво. Всички листа на TT са крайни върхове на пътищата, значи всички са червени. Оттук най-дългият път, който свързва две листа, има четен брой ребра.
Отвори задачатаEvan Chen VONVON TSTST 2021/5Условие — източник

Задача 9

Пълен запис
Условие
Нека q=prq=p^r, където pp е просто число, а rr е положително цяло число. Нека ζ=e2πi/q\zeta=e^{2\pi i/q}. Намерете най-малкото положително цяло число nn, за което∑1≤k≤qgcd⁡(k,p)=11(1−ζk)n\begin{aligned}\sum_{\substack{1\le k\le q\\ \gcd(k,p)=1}}\frac{1}{(1-\zeta^k)^n}\end{aligned}не е цяло число. Сумата е по всички 1≤k≤q1\le k\le q, за които p∤kp\nmid k.
РешениеЩе докажем, че отговорът еn=((p−1)r−1)pr−1+1.n=((p-1)r-1)p^{r-1}+1.Нека SqS_q е множеството на примитивните qq-ти корени на единицата и некаd=ϕ(q)=(p−1)pr−1.d=\phi(q)=(p-1)p^{r-1}.Разглеждаме числата 11−ω\frac1{1-\omega} за ω∈Sq\omega\in S_q като корени на полиномаP(x)=xd−c1xd−1+c2xd−2−⋯±cd,P(x)=x^d-c_1x^{d-1}+c_2x^{d-2}-\dotsb\pm c_d,така че cjc_j е jj-ият елементарен симетричен полином на тези корени. ОзначавамеSn=∑ω∈Sq1(1−ω)n.S_n=\sum_{\omega\in S_q}\frac1{(1-\omega)^n}.По Нютоновите тъждества имаме напримерS1=c1,S2=c1S1−2c2,S_1=c_1,\qquad S_2=c_1S_1-2c_2,S3=c1S2−c2S1+3c3,\qquad S_3=c_1S_2-c_2S_1+3c_3,а общо за n≤dn\le dSn=S_n=[∑j=1n−1(−1)j+1cjSn−j]+(−1)n+1ncn.(1)\left[\sum_{j=1}^{n-1}(-1)^{j+1}c_jS_{n-j}\right]+(-1)^{n+1}nc_n.\tag{1}За n>dn\gt{}d съответната рекурсия еSn=∑j=1d(−1)j+1cjSn−j.(2)S_n=\sum_{j=1}^d(-1)^{j+1}c_jS_{n-j}.\tag{2}Първо ще опишем знаменателите на коефициентите cic_i. Лема 1. Всички cic_i са цели числа, освен cdc_d. Всъщност cd=1/pc_d=1/p. Доказателство. qq-тият циклотомен полином еΦq(x)=1+xpr−1+x2pr−1+⋯+x(p−1)pr−1.\Phi_q(x)=1+x^{p^{r-1}}+x^{2p^{r-1}}+\dotsb+x^{(p-1)p^{r-1}}.ПолиномътQ(x)=Q(x)=1+(1+x)pr−1+(1+x)2pr−11+(1+x)^{p^{r-1}}+(1+x)^{2p^{r-1}}+⋯+(1+x)(p−1)pr−1+\dotsb+(1+x)^{(p-1)p^{r-1}}има корени ω−1\omega-1 за ω∈Sq\omega\in S_q. Сравнявайки свободните членове, получавамеQ(x)=p(−x)dP(−1/x).Q(x)=p(-x)^dP(-1/x).Следователно cnc_n е 1/p1/p по коефициента пред xnx^n в Q(x)Q(x). В частност водещият коефициент на QQ е 11, така че cd=1/pc_d=1/p точно. Работим по модул pp. Понеже (x+y)p≡xp+yp(modp)(x+y)^p\equiv x^p+y^p\pmod p, имамеQ(x)≡1+(1+xpr−1)+(1+xpr−1)2+⋯+(1+xpr−1)p−1≡(1+xpr−1)p−1xpr−1(modp).\begin{align*} Q(x)&\equiv 1+(1+x^{p^{r-1}})+(1+x^{p^{r-1}})^2+\dotsb+(1+x^{p^{r-1}})^{p-1}\\ &\equiv \frac{(1+x^{p^{r-1}})^p-1}{x^{p^{r-1}}}\pmod p. \end{align*}Последният полином е сравним с xdx^d по модул pp. Значи всички коефициенти на Q(x)Q(x), освен водещия, се делят на pp. Оттук cnc_n е цяло число за n<dn\lt{}d, а cd=1/pc_d=1/p. Лемата е доказана. От (1) веднага следва, че SnS_n е цяло число за n<dn\lt{}d. Ако r=1r=1, тогава d=p−1d=p-1 и dcd=(p−1)/pdc_d=(p-1)/p не е цяло число; следователно от (1) получаваме, че SdS_d не е цяло число. В този случай отговорът е p−1p-1, което съвпада с формулата. По-нататък нека r≥2r\ge2. Тогава dcddc_d вече е цяло число, така че и SdS_d е цяло число. Трябва да проследим първия момент, в който рекурсиите внасят допълнителен фактор 1/p1/p. Ще използваме pp-адичната валуация νp\nu_p. Лема 2. За 1≤n≤d1\le n\le d е изпълнено νp(ncn)≥r−2\nu_p(nc_n)\ge r-2. Най-малкото nn, за което има равенство, еn=d−pr−1+1.n=d-p^{r-1}+1.Доказателство. Числото ncnnc_n е 1/p1/p по коефициента пред xn−1x^{n-1} в производната Q′(x)Q'(x). ИмамеQ′(x)=Q'(x)=pr−1(1+x)pr−1−1[∑k=1p−1k(1+x)(k−1)pr−1].p^{r-1}(1+x)^{p^{r-1}-1}\left[\sum_{k=1}^{p-1}k(1+x)^{(k-1)p^{r-1}}\right].Достатъчно е да видим, че всички коефициенти на полинома в квадратните скоби се делят на pp, освен водещия. Отново по модул pp, ако запишем w=xpr−1w=x^{p^{r-1}}, този полином става1+2(1+w)+3(1+w)2+⋯+(p−1)(1+w)p−2.1+2(1+w)+3(1+w)^2+\dotsb+(p-1)(1+w)^{p-2}.Това е производната по ww на1+(1+w)+(1+w)2+⋯+(1+w)p−1=(1+w)p−1w.1+(1+w)+(1+w)^2+\dotsb+(1+w)^{p-1}=\frac{(1+w)^p-1}{w}.Понеже междинните биномни коефициенти (pj)\binom pj се делят на pp, всички коефициенти на тази производна, освен водещия, са кратни на pp. Умножението с (1+x)pr−1−1(1+x)^{p^{r-1}-1} не може да създаде по-ранен некратен на pp коефициент: водещият член в скобите има степен (p−2)pr−1(p-2)p^{r-1} по xx, а най-ниската му поява в произведението е именно при степенd−pr−1=(p−2)pr−1.d-p^{r-1}=(p-2)p^{r-1}.Затова първото равенство νp(ncn)=r−2\nu_p(nc_n)=r-2 е при n=d−pr−1+1n=d-p^{r-1}+1. Лемата е доказана. Полагамеm=d−pr−1=(p−2)pr−1.m=d-p^{r-1}=(p-2)p^{r-1}.Ще докажем следното твърдение. Твърдение. За всички цели k≥0k\ge0 и 1≤j≤d1\le j\le d е вярноνp(Skd+m+1)=r−2−k,νp(Skd+m+j)≥r−2−k.\begin{align*} \nu_p(S_{kd+m+1})&=r-2-k,\\ \nu_p(S_{kd+m+j})&\ge r-2-k. \end{align*}Доказателство. Първо разглеждаме 1≤n≤d1\le n\le d. От Нютоновите тъждества и лема 2 следва, че S1,S2,…,SmS_1,S_2,\dots,S_m се делят на pr−1p^{r-1}. При n=m+1n=m+1 членът (m+1)cm+1(m+1)c_{m+1} има валуация точно r−2r-2, а всички предишни членове в (1) имат валуация поне r−1r-1, затоваνp(Sm+1)=r−2.\nu_p(S_{m+1})=r-2.По същия начин за m+1≤n≤dm+1\le n\le d получаваме νp(Sn)≥r−2\nu_p(S_n)\ge r-2. Сега използваме рекурсията (2). По лема 1 коефициентите c1,…,cd−1c_1,\dots,c_{d-1} са цели, а cd=1/pc_d=1/p. Затова единственият член, който може да намали pp-адичната валуация при преминаване от предишните dd стойности към SnS_n, е последният член с Sn−dS_{n-d}. Следователно за n>dn\gt{}d са валидни две прости последици: - ако νp(Sn−j)≥ℓ\nu_p(S_{n-j})\ge \ell за всички 1≤j≤d1\le j\le d и νp(Sn−d)≥ℓ+1\nu_p(S_{n-d})\ge \ell+1, то νp(Sn)≥ℓ\nu_p(S_n)\ge \ell; - ако νp(Sn−j)≥ℓ\nu_p(S_{n-j})\ge \ell за всички 1≤j≤d1\le j\le d и νp(Sn−d)=ℓ\nu_p(S_{n-d})=\ell, то νp(Sn)=ℓ−1\nu_p(S_n)=\ell-1. Във втория случай няма скрито съкращаване: членът cdSn−d=Sn−d/pc_dS_{n-d}=S_{n-d}/p има валуация ℓ−1\ell-1, а всички останали членове имат валуация поне ℓ\ell. Значи най-ниската валуация се появява само веднъж и остава видима в сумата. Двете твърдения се прилагат последователно и дават индукция по блокове с дължина dd. След първия блок имаме валуация точно r−2r-2 при индекса m+1m+1 и поне r−2r-2 до края на блока. Всеки следващ блок измества тази точна валуация с dd напред и я намалява с 11, докато останалите стойности в блока остават поне толкова големи. Това доказва твърдението. От твърдението най-малкото nn, за което νp(Sn)<0\nu_p(S_n)\lt{}0, еn=(r−1)d+m+1.n=(r-1)d+m+1.Тъй като всички SnS_n се получават от рекурсиите с рационални коефициенти с единствен възможен знаменател степен на pp, отрицателната pp-адична валуация е точно условието SnS_n да не бъде цяло число. Накрая(r−1)d+m+1=(r−1)(p−1)pr−1+(p−2)pr−1+1=((p−1)r−1)pr−1+1.\begin{align*} (r-1)d+m+1&=(r-1)(p-1)p^{r-1}+(p-2)p^{r-1}+1\\ &=((p-1)r-1)p^{r-1}+1. \end{align*}Това е търсеният най-малък положителен индекс.
Отвори задачатаEvan Chen VONVON TSTST 2021/9Условие — източник