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

Evan Chen / USA TSTST Solutions

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

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

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

2022

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

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

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

11-12

6 задачи

Задача 1

Пълен запис
Условие
Нека nn е положително цяло число. Намерете най-малкото положително цяло число kk, такова че за всяко множество SS от nn точки във вътрешността на единичния квадрат съществува множество от kk правоъгълника със следните свойства: 1. страните на всеки правоъгълник са успоредни на страните на единичния квадрат; 2. никоя точка от SS не лежи във вътрешността на нито един от правоъгълниците; 3. всяка точка от вътрешността на единичния квадрат, която не е от SS, лежи във вътрешността на поне един от тези kk правоъгълника. Вътрешността на многоъгълник не съдържа границата му.
РешениеОтговорът е2n+2.\boxed{2n+2}.Ще мислим за задачата така: за всяко множество S⊂(0,1)2S\subset(0,1)^2 с nn точки трябва да покрием (0,1)2∖S(0,1)^2\setminus S с възможно най-малко отворени правоъгълници, успоредни на страните на квадрата. Първо доказваме долната граница. ИзбирамеS={(s1,s1),(s2,s2),…,(sn,sn)},S=\{(s_1,s_1),(s_2,s_2),\dots,(s_n,s_n)\},където0<s1<s2<⋯<sn<1,0\lt{}s_1\lt{}s_2\lt{}\dots\lt{}s_n\lt{}1,и вземаме достатъчно малко ε>0\varepsilon\gt{}0. Нека S′S' е множеството от 4n4n точки, получени от всяка точка на SS чрез преместване с ε\varepsilon наляво, надясно, нагоре или надолу:S′=S'=S+{(ε,0),(0,ε),(−ε,0),(0,−ε)}⊂(0,1)2.S+\{(\varepsilon,0),(0,\varepsilon),(-\varepsilon,0),(0,-\varepsilon)\}\subset(0,1)^2.Всички точки на S′S' трябва да бъдат покрити.Четирите правоъгълника, които покриват съответно точките(s1−ε,s1),(s1,s1−ε),(s_1-\varepsilon,s_1),\quad (s_1,s_1-\varepsilon),(sn+ε,sn),(sn,sn+ε),\quad (s_n+\varepsilon,s_n),\quad (s_n,s_n+\varepsilon),не могат да покрият други точки от S′S', без да съдържат точка от SS във вътрешността си. Всеки друг правоъгълник, който избягва точките на SS, може да покрие най-много две точки от S′S'. Следователно броят на правоъгълниците е поне4+∣S′∣−42=4+4n−42=2n+2.4+\frac{\lvert S'\rvert-4}{2}=4+\frac{4n-4}{2}=2n+2.Остава да построим покритие с 2n+22n+2 правоъгълника. По симетрия можем да предположим, че броят на различните yy-координати на точките от SS е поне броя на различните xx-координати. Нека тези различни xx-координати са0=x0<x1<⋯<xm<xm+1=1,0=x_0\lt{}x_1\lt{}\dots\lt{}x_m\lt{}x_{m+1}=1,а YiY_i да е множеството от yy-координатите на точките от SS, които имат xx-координата xix_i. За всяко 1≤i≤m1\le i\le m вземаме ∣Yi∣+1\lvert Y_i\rvert+1 правоъгълника, които заедно са(xi−1,xi+1)×((0,1)∖Yi).(x_{i-1},x_{i+1})\times((0,1)\setminus Y_i).Добавяме още двата странични правоъгълника(0,x1)×(0,1)и(xm,1)×(0,1).(0,x_1)\times(0,1)\qquad\text{и}\qquad (x_m,1)\times(0,1).Дотук използвахмеm+n+2m+n+2правоъгълника.Какво може да остане непокрито? Само точки, които лежат между две точки от SS с една и съща yy-координата и със съседни xx-координати. Ако хоризонтално ниво съдържа rr точки от SS, то дава r−1r-1 такива съседни двойки. Като сумираме по всички различни yy-координати, получаваме най-многоn−q≤n−mn-q\le n-mдвойки, където qq е броят на различните yy-координати, а по избора ни q≥mq\ge m. За всяка такава съседна двойка с координати (xi,y)(x_i,y) и (xi+1,y)(x_{i+1},y) добавяме много тънък правоъгълник(xi,xi+1)×(y−ε,y+ε),(x_i,x_{i+1})\times(y-\varepsilon,y+\varepsilon),като ε>0\varepsilon\gt{}0 се избира достатъчно малко, за да не се включват други точки от SS. Това покрива всички останали точки и използва най-много n−mn-m допълнителни правоъгълника. Общият брой е най-много(m+n+2)+(n−m)=2n+2.(m+n+2)+(n-m)=2n+2.Така долната граница се достига, следователно търсеното най-малко kk е 2n+22n+2.
Отвори задачатаEvan Chen VONVON TSTST 2022/1Условие — източник

Задача 3

Пълен запис
Условие
Да се определят всички положителни цели числа NN, за които съществува строго растяща редица от положителни цели числаs0<s1<s2<…s_0\lt{}s_1\lt{}s_2\lt{}\dotsсъс следните свойства: 1. редицата s1−s0,s2−s1,s3−s2,…s_1-s_0,s_2-s_1,s_3-s_2,\dots е периодична; 2. ssn−ssn−1≤N<s1+sn−ssn−1s_{s_n}-s_{s_{n-1}}\le N\lt{}s_{1+s_n}-s_{s_{n-1}} за всяко положително цяло число nn.
РешениеОтговорът е: всички NN, за които t2≤N<t2+tt^2\le N\lt{}t^2+t за някое положително цяло число tt. Първо, ако t2≤N<t2+tt^2\le N\lt{}t^2+t, редицата sn=tn+1s_n=tn+1 удовлетворява двете условия. Остава да докажем, че други стойности на NN не са възможни. Нека an=sn−sn−1a_n=s_n-s_{n-1} и нека pp е минималният период на редицата (an)(a_n). За всяко k≥0k\ge0 дефинираме f(k)f(k) като цялото число, за коетоsf(k)−sk≤N<sf(k)+1−sk.s_{f(k)}-s_k\le N\lt{}s_{f(k)+1}-s_k.От условието следва, че f(sn−1)=snf(s_{n-1})=s_n за всяко n≥1n\ge1. Ще докажем, че si≢sj(modp)s_i\not\equiv s_j\pmod p за всички i<j<i+pi\lt{}j\lt{}i+p. Да допуснем противното, т.е. si≡sj(modp)s_i\equiv s_j\pmod p за някои такива i,ji,j. Тогава, понеже (an)(a_n) е периодична с период pp, имамеasi+k=asj+kза всяко k≥0,a_{s_i+k}=a_{s_j+k}\quad\text{за всяко }k\ge0,и следователноssi+k−ssi=ssj+k−ssjза всяко k≥0.s_{s_i+k}-s_{s_i}=s_{s_j+k}-s_{s_j}\quad\text{за всяко }k\ge0.Оттук получавамеai+1=f(si)−si=f(sj)−sj=aj+1a_{i+1}=f(s_i)-s_i=f(s_j)-s_j=a_{j+1}и също si+1=f(si)≡f(sj)=sj+1(modp)s_{i+1}=f(s_i)\equiv f(s_j)=s_{j+1}\pmod p. Повтаряйки същия аргумент индуктивно, получаваме ai+k=aj+ka_{i+k}=a_{j+k} за всяко k≥0k\ge0, което дава период j−i<pj-i\lt{}p на (an)(a_n) - противоречие. Следователно за всяко ii числата si,si+1,…,si+p−1s_i,s_{i+1},\ldots,s_{i+p-1} образуват пълна система от остатъци по модул pp. В частност si+p≡si(modp)s_{i+p}\equiv s_i\pmod p за всяко ii. НекаT=sp−s0=a1+a2+⋯+ap.T=s_p-s_0=a_1+a_2+\cdots+a_p.Понеже (an)(a_n) е периодична с период pp, за всички i,ki,k имамеsi+kp−si=kT.s_{i+kp}-s_i=kT.От sp≡s0(modp)s_p\equiv s_0\pmod p следва p∣Tp\mid T. Тогава, прилагайки последната формула с i=s0i=s_0 и k=T/pk=T/p, получавамеssp−ss0=Tp⋅T=T2p.s_{s_p}-s_{s_0}=\frac Tp\cdot T=\frac{T^2}{p}.Сумираме неравенстватаssn−ssn−1≤N<s_{s_n}-s_{s_{n-1}}\le N\lt{}ssn+1−ssn−1=ssn−ssn−1+asn+1s_{s_n+1}-s_{s_{n-1}}=s_{s_n}-s_{s_{n-1}}+a_{s_n+1}за n=1,2,…,pn=1,2,\ldots,p. Лявата страна телескопира и даваT2p=ssp−ss0≤Np.\frac{T^2}{p}=s_{s_p}-s_{s_0}\le Np.От друга страна, понеже s1+1,s2+1,…,sp+1s_1+1,s_2+1,\ldots,s_p+1 също образуват пълна система от остатъци по модул pp, имамеas1+1+as2+1+⋯+asp+1=T.a_{s_1+1}+a_{s_2+1}+\cdots+a_{s_p+1}=T.ЗатоваNp<T2p+T.Np\lt{}\frac{T^2}{p}+T.Делим на pp и поставяме t=T/p∈Z+t=T/p\in\mathbb Z^+. Получаваме точноt2≤N<t2+t,t^2\le N\lt{}t^2+t,както трябваше.
Отвори задачатаEvan Chen VONVON TSTST 2022/3Условие — източник

Задача 4

Пълен запис
Условие
Функция f ⁣:N→Nf \colon \mathbb N \to \mathbb N има следното свойство: за всички положителни цели числа mm и nn точно едно от числатаf(m+1),f(m+2),…,f(m+f(n))f(m+1), f(m+2), \dots, f(m+f(n))се дели на nn. Докажете, че f(n)=nf(n)=n за безбройно много положителни цели числа nn.
РешениеЗапочваме със следното твърдение. Твърдение. Ако a∣ba\mid b, то f(a)∣f(b)f(a)\mid f(b). Доказателство. От условието, приложено за n=an=a, следва, че множествотоSa={t≥2:a∣f(t)}S_a=\{t\ge2: a\mid f(t)\}е аритметична прогресия с разлика f(a)f(a). По същия начинSb={t≥2:b∣f(t)}S_b=\{t\ge2: b\mid f(t)\}е аритметична прогресия с разлика f(b)f(b). От a∣ba\mid b следва Sb⊆SaS_b\subseteq S_a. Аритметична прогресия с разлика xx може да се съдържа в аритметична прогресия с разлика yy само ако y∣xy\mid x. Следователно f(a)∣f(b)f(a)\mid f(b). Нека сега a≥2a\ge2 е произволно положително цяло число. Понеже и f(a)f(a), и f(2a)f(2a) се делят на f(a)f(a), сред a+1a+1 последователни стойности на ff има поне две, делящи се на f(a)f(a). От условието за n=f(a)n=f(a) следва, че f(f(a))≤af(f(a))\le a. От друга страна, точно едно от числатаf(2),f(3),…,f(1+f(a))f(2), f(3), \dots, f(1+f(a))се дели на aa; нека това е f(t)f(t). ТогаваSa={t,t+f(a),t+2f(a),… }.S_a=\{t,t+f(a),t+2f(a),\dots\}.Понеже t∣2tt\mid2t, от доказаното твърдение получаваме f(t)∣f(2t)f(t)\mid f(2t). А тъй като a∣f(t)a\mid f(t), следва a∣f(2t)a\mid f(2t), така че 2t∈Sa2t\in S_a. Следователно tt е кратно на f(a)f(a). От 2≤t≤1+f(a)2\le t\le1+f(a) и f(a)≥2f(a)\ge2 получаваме t=f(a)t=f(a). Значи f(f(a))f(f(a)) се дели на aa. Заедно с f(f(a))≤af(f(a))\le a това даваf(f(a))=a.f(f(a))=a.За a=1a=1 също имаме f(f(1))=1f(f(1))=1, защото условието при n=1n=1 веднага дава f(1)=1f(1)=1. Следователно f(f(a))=af(f(a))=a за всяко aa, т.е. ff е биекция. Освен това вече знаем, че f(a)∣f(b)f(a)\mid f(b) влече f(f(a))∣f(f(b))f(f(a))\mid f(f(b)), тоест a∣ba\mid b. Значиa∣b⟺f(a)∣f(b).a\mid b \quad\Longleftrightarrow\quad f(a)\mid f(b).Заедно с биективността това показва, че f(n)f(n) има същия брой положителни делители като nn. Нека pp е просто число. Тогава f(p)=qf(p)=q също е просто число. Ако q≠pq\ne p, то от f(p)∣f(pq)f(p)\mid f(pq) и f(q)∣f(pq)f(q)\mid f(pq) следва pq∣f(pq)pq\mid f(pq). Понеже pqpq и f(pq)f(pq) имат еднакъв брой положителни делители, получаваме f(pq)=pqf(pq)=pq. Следователно за всяко просто число pp е вярно поне едно от двете: или f(p)=pf(p)=p, или f(pf(p))=pf(p)f(pf(p))=pf(p). Така за всяко просто число получаваме положително цяло число, което е неподвижна точка на ff. Тези числа са безбройно много: ако f(p)=pf(p)=p, получаваме самото просто число pp, а иначе получаваме произведението pf(p)pf(p), което има pp като делител и не може да съвпада за безбройно много различни прости числа. Значи f(n)=nf(n)=n за безбройно много nn.
Отвори задачатаEvan Chen VONVON TSTST 2022/4Условие — източник

Задача 5

Пълен запис
Условие
Нека A1,…,A2022A_1,\ldots,A_{2022} са върховете на правилен 20222022-ъгълник в равнината. Алис и Боб играят игра. Алис тайно избира права и оцветява всички точки от едната страна на правата в синьо, а всички точки от другата страна - в червено. Точките върху самата права се оцветяват в синьо, така че всяка точка от равнината е или червена, или синя. Боб не вижда цветовете на точките. На всеки ход Боб избира точка в равнината, не непременно измежду A1,…,A2022A_1,\ldots,A_{2022}, а Алис му казва вярно цвета на тази точка. Кое е най-малкото число QQ, за което Боб има стратегия винаги да определи цветовете на точките A1,…,A2022A_1,\ldots,A_{2022} за QQ хода?
РешениеОтговорът е 2222. За долната граница отбелязваме, че има 2022⋅2021+2>2212022\cdot2021+2\gt{}2^{21} възможни оцветявания на върховете. Ако Боб зададе по-малко от 2222 въпроса, той получава най-много 2212^{21} различни последователности от отговори, така че не може да различи всички възможни оцветявания. Следователно Q≥22Q\ge22. Ще покажем стратегия с 2222 въпроса. Основното наблюдение е, че множеството от червените точки е изпъкнало, както и множеството от сините точки. Затова, ако няколко точки са в един и същи цвят, цялата им изпъкнала обвивка е в този цвят. Лема 1. Нека B0,B1,…,Bk+1B_0,B_1,\ldots,B_{k+1} са равноотдалечени точки върху една окръжна дъга, като цветовете на B0B_0 и Bk+1B_{k+1} са известни и различни. Тогава цветовете на B1,…,BkB_1,\ldots,B_k могат да се определят с ⌈log⁡2k⌉\lceil\log_2 k\rceil въпроса. Доказателство. Съществува индекс 0≤i≤k0\le i\le k, такъв че B0,…,BiB_0,\ldots,B_i са в цвета на B0B_0, а Bi+1,…,Bk+1B_{i+1},\ldots,B_{k+1} са в цвета на Bk+1B_{k+1}. Иначе две едноцветни отсечки от различни цветове биха се пресекли, което е невъзможно по изпъкналост. Следователно можем да намерим мястото на прехода чрез двоично търсене. Лема 2. Нека B0,B1,…,Bk+1B_0,B_1,\ldots,B_{k+1} са равноотдалечени точки върху една окръжна дъга и нека цветовете на B0B_0, B⌈k/2⌉B_{\lceil k/2\rceil} и Bk+1B_{k+1} са известни и червени. Тогава е вярно поне едно от следните две твърдения: всички точки B1,…,B⌈k/2⌉B_1,\ldots,B_{\lceil k/2\rceil} са червени или всички точки B⌈k/2⌉,…,BkB_{\lceil k/2\rceil},\ldots,B_k са червени. Освен това с един въпрос можем да разберем кой от двата случая е изпълнен. Доказателство. Съществуването следва от същата изпъкналост като в първата лема. За да различим случаите, избираме точка PP, така че всички B0,…,Bk+1B_0,\ldots,B_{k+1} да лежат между лъчите PB0PB_0 и PB⌈k/2⌉PB_{\lceil k/2\rceil}, точките от първата половина да лежат вътре в триъгълника PB0B⌈k/2⌉PB_0B_{\lceil k/2\rceil}, а точките от втората половина - извън него. Такава точка се намира, като гледаме близо до пресечната точка на правите B0B1B_0B_1 и B⌈k/2⌉−1B⌈k/2⌉B_{\lceil k/2\rceil-1}B_{\lceil k/2\rceil}. Ако PP е червена, всички вътрешни точки са червени, защото лежат в изпъкналата обвивка на червените точки PP, B0B_0 и B⌈k/2⌉B_{\lceil k/2\rceil}. Ако PP е синя и някоя точка BiB_i с i>⌈k/2⌉i\gt{}\lceil k/2\rceil е синя, отсечката PBiPB_i е синя, а тя пресича червената отсечка B0B⌈k/2⌉B_0B_{\lceil k/2\rceil} - противоречие. Следователно във втория случай всички външни точки са червени. Сега стратегията е следната. Боб първо пита за цвета на A1A_1; без ограничение можем да го наречем червен. Ще докажем по индукция, че ако Боб не знае цветовете на най-много 2k−12^k-1 последователни върха Ai,…,AjA_i,\ldots,A_j, а всички останали върхове са известни като червени, тогава той може да довърши за 2k−12k-1 въпроса. При k=1k=1 има само една неизвестна точка и твърдението е ясно. Нека k>1k\gt{}1. Боб пита за средната точкаAi+⌈(j−i+1)/2⌉.A_{i+\lceil (j-i+1)/2\rceil}.Ако тя е синя, двете неизвестни части от дъгата вече имат известни краища с различни цветове, така че по Лема 1 Боб довършва с най-много2log⁡2⌈j−i+12⌉≤2(k−1)2\log_2\left\lceil\frac{j-i+1}{2}\right\rceil\le2(k-1)допълнителни въпроса, общо не повече от 2k−12k-1. Ако средната точка е червена, Боб задава още един въпрос от Лема 2 и научава, че поне едната половина от неизвестната дъга е изцяло червена. Остават най-много 2k−1−12^{k-1}-1 последователни неизвестни точки, а вече са използвани два въпроса; по индукционната хипотеза са достатъчни още 2(k−1)−12(k-1)-1 въпроса. Общо това са 2k−12k-1. След първия въпрос за A1A_1 остават 2021≤211−12021\le2^{11}-1 неизвестни върха. Прилагаме доказаното с k=11k=11 и получаваме още 2121 въпроса, т.е. общо 2222.
Отвори задачатаEvan Chen VONVON TSTST 2022/5Условие — източник

Задача 8

Пълен запис
Условие
Намерете всички функции f ⁣:N→Zf \colon \mathbb N \to \mathbb Z, такива че⌊f(mn)n⌋=f(m)\left\lfloor \frac{f(mn)}{n}\right\rfloor=f(m)за всички положителни цели числа mm и nn.
РешениеОтговорът е следният. Работят двете семействаf(n)=⌊αn⌋(α∈R)f(n)=\lfloor \alpha n\rfloor \quad (\alpha\in\mathbb R)иf(n)=⌈αn⌉−1(α∈R).f(n)=\lceil \alpha n\rceil-1 \quad (\alpha\in\mathbb R).При ирационално α\alpha двете формули съвпадат. Проверката е непосредствена и се свежда до тъждеството⌊⌊xn⌋n⌋=⌊x⌋,\left\lfloor \frac{\lfloor xn\rfloor}{n}\right\rfloor=\lfloor x\rfloor,валидно за всяко положително цяло число nn и всяко реално число xx; аналогичната проверка за горната цяла част е същата. Ще докажем, че други решения няма. Нека ff е решение и дефинираме редицатаan=f(n!)n!(n=1,2,… ).a_n=\frac{f(n!)}{n!} \qquad (n=1,2,\dots).Прилагайки даденото условие към двойката (n!,n+1)(n!,n+1), получавамеan+1∈[an,an+1n!).a_{n+1}\in\left[a_n,a_n+\frac1{n!}\right).Следователно редицата a1,a2,…a_1,a_2,\dots е не намаляваща и е ограничена отгоре, например от a1+ea_1+e. Значи тя има граница; да я означим с α\alpha. Ако съществува kk, за което ak=αa_k=\alpha, то aℓ=αa_\ell=\alpha за всяко ℓ>k\ell\gt{}k. За всяко положително цяло число mm избираме ℓ>k\ell\gt{}k, така че m∣ℓ!m\mid \ell!. Прилагаме условието с mn=ℓ!mn=\ell! и получавамеf(m)=⌊f(ℓ!)ℓ!/m⌋=⌊αm⌋.f(m)=\left\lfloor \frac{f(\ell!)}{\ell!/m}\right\rfloor=\lfloor \alpha m\rfloor.Това е първото семейство. Остава случаят, когато няма kk с ak=αa_k=\alpha. Тогава ak<αa_k\lt{}\alpha за всяко kk. Фиксираме положително цяло число mm и избираме ℓ\ell, за което m∣ℓ!m\mid\ell! иaℓ=α−xa_\ell=\alpha-xс произволно малко положително xx. Отново от условието при mn=ℓ!mn=\ell! имамеf(m)=⌊f(ℓ!)ℓ!/m⌋=⌊αm−mx⌋.f(m)=\left\lfloor \frac{f(\ell!)}{\ell!/m}\right\rfloor=\left\lfloor \alpha m-mx\right\rfloor.Ако αm\alpha m е цяло число, избираме ℓ\ell така, че mx<1mx\lt{}1, и получавамеf(m)=αm−1=⌈αm⌉−1.f(m)=\alpha m-1=\lceil \alpha m\rceil-1.Ако αm\alpha m не е цяло число, избираме ℓ\ell така, че mx<{αm}mx\lt{}\{\alpha m\}, и пак получавамеf(m)=⌊αm⌋=⌈αm⌉−1.f(m)=\lfloor \alpha m\rfloor=\lceil \alpha m\rceil-1.Следователно във втория случай ff е от второто семейство. Това завършва класификацията.
Отвори задачатаEvan Chen VONVON TSTST 2022/8Условие — източник

Задача 9

Пълен запис
Условие
Нека k>1k\gt{}1 е фиксирано положително цяло число. Докажете, че ако nn е достатъчно голямо положително цяло число, съществува редица от цели числа със следните свойства: 1. всеки член на редицата е между 11 и nn включително; 2. за всеки два различни последователни отрязъка от редицата с дължина между 22 и kk включително, мултимножествата от стойностите в тези два отрязъка са различни; 3. редицата има дължина поне 0.499n20.499n^2.
РешениеЩе наричаме една редица (n,k)(n,k)-добра, ако е крайна редица от цели числа между 11 и nn включително и удовлетворява второто условие от задачата. Трябва да докажем, че за всяко фиксирано kk и всяко достатъчно голямо nn има (n,k)(n,k)-добра редица с дължина поне 0.499n20.499n^2. Първо работим по модул nn, където n=pmn=p^m е степен на просто число и p>k+1p\gt{}k+1. Нека 0<g<nk−10\lt{}g\lt{}\frac nk-1, gcd⁡(g,n)=1\gcd(g,n)=1, и нека aa е най-малкото положително цяло число, за коетоga≡±1(modn).g^a\equiv\pm1\pmod n.Ще докажем, че при тези условия съществува (n,k)(n,k)-добра редица от остатъци по модул nn с дължина a(n+2)+2a(n+2)+2. Накрая остатъкът rr ще се замени с числото r+1r+1. Ще използваме следната лема. Нека SS е множеството от остатъците на аритметична прогресия с дължина i≤ki\le k и разлика, взаимнопроста с nn. Тогава съществуват единствени 0<d≤n20\lt{}d\le\frac n2 и 0≤b<n0\le b\lt{}n, за коитоS={b,b+d,…,b+(i−1)d}(modn).S=\{b,b+d,\ldots,b+(i-1)d\}\pmod n.Наистина, ако i=2j+1i=2j+1, средният член uu се намира като средно аритметично на остатъците в SS, защото ii е обратимо по модул nn. Ако XX е сумата от квадратите на остатъците, тоX≡(2j+1)u2+d2j(j+1)(2j+1)3(modn),X\equiv(2j+1)u^2+d^2\frac{j(j+1)(2j+1)}3\pmod n,откъдето се намира d2d^2. Ако i=2ji=2j, отново намираме средното uu и записваме прогресията около него катоu−(2j−1)h,u−(2j−3)h,…,u+(2j−1)h,u-(2j-1)h,u-(2j-3)h,\ldots,u+(2j-1)h,където действителната разлика е 2h2h. ТогаваX≡2ju2+h2(2j−1)2j(2j+1)3(modn),X\equiv2ju^2+h^2\frac{(2j-1)2j(2j+1)}3\pmod n,така че намираме h2h^2, а оттам и разликата 2h2h до знак. Понеже n=pmn=p^m с нечетно pp и разглежданата разлика е взаимнопроста с nn, от квадрат по модул nn тя се възстановява еднозначно до знак. Това доказва лемата. За 0≤ℓ<a0\le \ell\lt{}a дефинираме редицатаCℓ:0,gℓ,gℓ,2gℓ,3gℓ,C_\ell: 0,g^\ell,g^\ell,2g^\ell,3g^\ell,…,(n−1)gℓ,(n−1)gℓ(modn).\ldots,(n-1)g^\ell,(n-1)g^\ell\pmod n.Сега построяваме редицата SnS_n, като започваме с 00, след това поставяме последователно C0,C1,…,Ca−1C_0,C_1,\ldots,C_{a-1}, и накрая добавяме още един 00. Ясно е, че дължината е a(n+2)+2a(n+2)+2. Важното наблюдение е следното: ако последователен отрязък от SnS_n с дължина най-много kk съдържа два равни остатъка, тези два остатъка са съседни в отрязъка. Ако отрязъкът лежи изцяло в някое CℓC_\ell, това е очевидно от конструкцията. Иначе той пресича границата между Cℓ−1C_{\ell-1} и CℓC_\ell и има части от вида(n−r)gℓ−1,…,(n−1)gℓ−1,(n−1)gℓ−1(n-r)g^{\ell-1},\ldots,(n-1)g^{\ell-1},(n-1)g^{\ell-1}и0,gℓ,gℓ,2gℓ,…,sgℓ,0,g^\ell,g^\ell,2g^\ell,\ldots,sg^\ell,където r+s≤k−3r+s\le k-3. Ако има несъседно съвпадение между двете части, то за някои 0<u≤r0\lt{}u\le r и 0<v≤s0\lt{}v\le s ще имаме(n−u)gℓ−1≡vgℓ(modn),(n-u)g^{\ell-1}\equiv vg^\ell\pmod n,тоест u+gv≡0(modn)u+gv\equiv0\pmod n. Но 0<u+gv<k+kg<n0\lt{}u+gv\lt{}k+kg\lt{}n, невъзможно. Остава да покажем, че от мултимножеството на всеки отрязък с дължина 2≤i≤k2\le i\le k можем да възстановим самия отрязък. Нека MM е такова мултимножество от остатъци. Ако в MM има повторен остатък, предишното наблюдение оставя само няколко случая. Ако 00 се среща повече от веднъж, отрязъкът е началото на SnS_n. Ако има два различни повтарящи се остатъка, те трябва да са крайните повторения около граница между две съседни редици Cℓ−1C_{\ell-1} и CℓC_\ell, т.е. копия на −gℓ−1-g^{\ell-1} и на gℓg^\ell; индексът ℓ\ell се определя еднозначно. След деление на gℓ−1g^{\ell-1} остатъците се разделят като−r,−(r−1),…,−1,−1-r,-(r-1),\ldots,-1,-1и0,g,g,2g,…,sg,0,g,g,2g,\ldots,sg,а неравенствата sg≤kg<n−ksg\le kg\lt{}n-k и −r≡n−r≥n−k-r\equiv n-r\ge n-k определят еднозначно rr и ss. Ако има повторен само остатък gℓg^\ell, отрязъкът е в началото на CℓC_\ell, евентуално с последни членове от Cℓ−1C_{\ell-1}; след същото деление получаваме лесно различими възможности g,g,2g,…,tgg,g,2g,\ldots,tg, евентуално заедно с 00 или 0,−10,-1. Случаят с единствен повторен остатък −gℓ-g^\ell е аналогичен за края на CℓC_\ell, като използваме, че −t≡n−t≥n2-t\equiv n-t\ge\frac n2, докато g<n2g\lt{}\frac n2. Ако в MM няма повторен остатък, то отрязъкът не съдържа и двете копия на някое от специално повторените числа. Затова той или лежи изцяло в някое CℓC_\ell, където е част от аритметична прогресия и се възстановява от предишната лема, или пресича границата между CℓC_\ell и Cℓ+1C_{\ell+1} и тогава е отрязък от тричленната редица (−gℓ,0,gℓ+1)(-g^\ell,0,g^{\ell+1}), което също се разпознава еднозначно. Следователно SnS_n няма две различни отрязъка с еднакво мултимножество от стойности и е (n,k)(n,k)-добра. Сега фиксираме kk и вземаме просто число p>k+1p\gt{}k+1. При n=p2n=p^2 нека gg е най-малкият примитивен корен по модул p2p^2. Тогава a=p(p−1)2a=\frac{p(p-1)}2. Ще покажем, че g<pg\lt{}p, откъдето за достатъчно голямо pp имаме g<p2k−1g\lt{}\frac{p^2}{k}-1 и можем да приложим построението. Нека g0g_0 е примитивен корен по модул pp. Всеки от остатъците g0+tpg_0+tp, 0≤t<p0\le t\lt{}p, има ред, кратен на p−1p-1 по модул p2p^2, и е примитивен корен по модул p2p^2, освен ако(g0+tp)p−1≡1(modp2).(g_0+tp)^{p-1}\equiv1\pmod{p^2}.Но(g0+tp)p−1≡g0p−1+g0p−2tp(modp2),(g_0+tp)^{p-1}\equiv g_0^{p-1}+g_0^{p-2}tp\pmod{p^2},така че точно една стойност на tt дава ред p−1p-1, а останалите дават примитивни корени по модул p2p^2. Следователно или има примитивен корен между 00 и pp, или всички остатъци с ред p−1p-1 по модул p2p^2 лежат между 00 и pp. Второто е невъзможно: ако xx има ред p−1p-1, то и x−1x^{-1} има ред p−1p-1, но два остатъка между 00 и pp не могат да са взаимнообратни по модул p2p^2, освен тривиалния остатък 11, който няма ред p−1p-1. Значи g<pg\lt{}p. Получаваме (p2,k)(p^2,k)-добра редица с дължинаp(p−1)(p2+2)2.\frac{p(p-1)(p^2+2)}2.Накрая нека NN е достатъчно голямо. По теоремата за простите числа можем да изберем просто p<Np\lt{}\sqrt N с pN\frac p{\sqrt N} произволно близко до 11. Построената редица използва само остатъци по модул p2p^2, които заменяме с числата 1,2,…,p21,2,\ldots,p^2; понеже p2≤Np^2\le N, това е редица от числа между 11 и NN. Дължината й е асимптотично 12p4\frac12p^4, а понеже p2p^2 може да е произволно близко до NN, за всички достатъчно големи NN тя е поне 0.499N20.499N^2. Това доказва задачата.
Отвори задачатаEvan Chen VONVON TSTST 2022/9Условие — източник