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

Evan Chen / USA TSTST Solutions

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

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

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

2023

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

11-12

9 задачи

Задача 1

Пълен запис
Условие
Нека ABCABC е триъгълник с медицентър GG. Точките RR и SS са избрани съответно върху лъчите GBGB и GCGC така, че ∠ABS=∠ACR=180∘−∠BGC\angle ABS=\angle ACR=180^\circ-\angle BGC. Да се докаже, че ∠RAS+∠BAC=∠BGC\angle RAS+\angle BAC=\angle BGC.
РешениеНека MM и NN са средите съответно на ACAC и ABAB. Понеже GG е медицентър, точките B,G,MB,G,M са колинеарни, както и точките C,G,NC,G,N. От условието получаваме ∠ACR=180∘−∠BGC=∠CGM\angle ACR=180^\circ-\angle BGC=\angle CGM. Тъй като A,M,CA,M,C са колинеарни и R,G,MR,G,M са колинеарни, триъгълниците MCRMCR и MGCMGC са подобни. Следователно MC2=MG⋅MRMC^2=MG\cdot MR. Но MM е среда на ACAC, така че MA=MCMA=MC и получаваме MA2=MG⋅MRMA^2=MG\cdot MR. По теоремата за допирателната и хордата това дава ∠RAC=∠MGA\angle RAC=\angle MGA. Напълно аналогично, като използваме средата NN и условието ∠ABS=180∘−∠BGC=∠BGN\angle ABS=180^\circ-\angle BGC=\angle BGN, получаваме NA2=NG⋅NSNA^2=NG\cdot NS и оттук ∠BAS=∠AGN\angle BAS=\angle AGN. Сега събираме двете равенства: ∠RAS+∠BAC=∠RAC+∠BAS=∠MGA+∠AGN=∠MGN\angle RAS+\angle BAC=\angle RAC+\angle BAS=\angle MGA+\angle AGN=\angle MGN. А понеже M,G,BM,G,B и N,G,CN,G,C лежат на едни и същи прави, ъгълът ∠MGN\angle MGN е равен на ∠BGC\angle BGC. Следователно ∠RAS+∠BAC=∠BGC\angle RAS+\angle BAC=\angle BGC, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2023/1Условие — източник

Задача 2

Пълен запис
Условие
Нека n≥m≥1n\ge m\ge1 са цели числа. Да се докаже, че∑k=mn(1k2+1k3)≥m(∑k=mn1k2)2.\sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right)\ge m\left(\sum_{k=m}^n\frac1{k^2}\right)^2.
РешениеЩе използваме неравенството на Коши-Шварц в дробна форма. Понеже1k2+1k3=k+1k3,\frac1{k^2}+\frac1{k^3}=\frac{k+1}{k^3},имаме∑k=mn(1k2+1k3)=∑k=mn(1/k2)21/(k(k+1))≥(∑k=mn1k2)2∑k=mn1k(k+1).\begin{align*} \sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right) &=\sum_{k=m}^n\frac{(1/k^2)^2}{1/(k(k+1))}\\ &\ge\frac{\left(\sum_{k=m}^n\frac1{k^2}\right)^2}{\sum_{k=m}^n\frac1{k(k+1)}}. \end{align*}А знаменателят се телескопира:∑k=mn1k(k+1)=\sum_{k=m}^n\frac1{k(k+1)}=∑k=mn(1k−1k+1)=1m−1n+1<\sum_{k=m}^n\left(\frac1k-\frac1{k+1}\right)=\frac1m-\frac1{n+1}\lt{}1m.\frac1m.Следователно∑k=mn(1k2+1k3)>\sum_{k=m}^n\left(\frac1{k^2}+\frac1{k^3}\right)\gt{}(∑k=mn1k2)21/m=m(∑k=mn1k2)2, \frac{\left(\sum_{k=m}^n\frac1{k^2}\right)^2}{1/m} =m\left(\sum_{k=m}^n\frac1{k^2}\right)^2,което е дори малко по-силно от исканото.
Отвори задачатаEvan Chen VONVON TSTST 2023/2Условие — източник

Задача 3

Пълен запис
Условие
Да се намерят всички положителни цели числа nn, за които е възможно някои клетки на безкрайна решетка от единични квадрати да се оцветят в червено така, че всеки правоъгълник, съставен от точно nn клетки и със страни по линиите на решетката, да съдържа нечетен брой червени клетки.
РешениеЩе докажем, че това е възможно за всяко положително цяло число nn. Да наречем едно положително цяло число добро, ако за него съществува такова оцветяване. Ще използваме две твърдения: (1) ако nn е добро и pp е нечетно просто число, то pnpn е добро; (2) за всяко k≥0k\ge0 числото 2k2^k е добро. Те дават резултата, защото всяко положително цяло число е произведение на степен на 22 и нечетни прости множители. Да докажем (1). Ако всеки правоъгълник от nn клетки съдържа нечетен брой червени клетки, то всеки правоъгълник от pnpn клетки също съдържа нечетен брой червени клетки. Наистина, ако размерите му са a×ba\times b и ab=pnab=pn, то поне една от страните се дели на pp, така че правоъгълникът се разбива на pp правоъгълника от по nn клетки. Всеки от тях има нечетен брой червени клетки, а сумата на нечетен брой нечетни числа е нечетна. Остава да докажем (2). Нека n=2kn=2^k. Правоъгълниците от nn клетки имат точно k+1k+1 възможни форми: 2m×2k−m2^m\times2^{k-m} за 0≤m≤k0\le m\le k. За всяка такава форма ще построим помощно оцветяване. Номерираме клетките с двойки (x,y)∈Z2(x,y)\in\mathbb Z^2 според координатите на долния им ляв ъгъл и оцветяваме клетката (x,y)(x,y) в червено точно когато xx има остатък 00 по модул 2m2^m и yy има остатък 00 по модул 2k−m2^{k-m}. Всеки правоъгълник с форма 2m×2k−m2^m\times2^{k-m} съдържа точно по един представител на всеки остатък за xx по модул 2m2^m и на всеки остатък за yy по модул 2k−m2^{k-m}, следователно съдържа точно една червена клетка. Сега да разгледаме правоъгълник с друга форма 2ℓ×2k−ℓ2^\ell\times2^{k-\ell}. Ако ℓ>m\ell\gt{}m, броят на допустимите координати xx е 2ℓ−m2^{\ell-m}, което е четно, а броят на допустимите координати yy е 00 или 11. Значи общият брой червени клетки е четен. Случаят ℓ<m\ell\lt{}m е аналогичен, като ролите на xx и yy се разменят. Накрая вземаме сумата по модул 22 на тези k+1k+1 помощни оцветявания: една клетка е червена в окончателното оцветяване точно когато е червена в нечетен брой от помощните оцветявания. За правоъгълник с форма 2m×2k−m2^m\times2^{k-m} съответното помощно оцветяване дава нечетен брой червени клетки, а всички останали помощни оцветявания дават четен брой. Следователно окончателното оцветяване дава нечетен брой червени клетки за всяка възможна форма. Така 2k2^k е добро за всяко k≥0k\ge0, а заедно с (1) това доказва, че всички положителни цели числа nn работят.
Отвори задачатаEvan Chen VONVON TSTST 2023/3Условие — източник

Задача 4

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число и нека KnK_n е пълният граф с nn върха. Всяко ребро на KnK_n е оцветено в червено, зелено или синьо. Нека AA е броят на триъгълниците, чиито три ребра са в един и същ цвят, а BB е броят на триъгълниците, чиито три ребра са в три различни цвята. Да се докаже, чеB≤2A+n(n−1)3.B\le2A+\frac{n(n-1)}3.
РешениеРазглеждаме всички ненаредени двойки различни ребра, които имат общ връх. Ще ги наричаме ъгли. Даваме на всеки такъв ъгъл заряд +2+2, ако двете му ребра са с един и същ цвят, и заряд −1-1 иначе. Ще пресметнем общия заряд по два начина. Първо сумираме по триъгълници. Всеки ъгъл принадлежи на точно един триъгълник. Ако триъгълникът е едноцветен, трите му ъгъла дават заряд 3⋅2=63\cdot2=6. Ако използва точно два цвята, зарядът е 2−1−1=02-1-1=0. Ако трите му ребра са в различни цветове, зарядът е −3-3. Следователно общият заряд е6A−3B.6A-3B.Сега сумираме по върхове. Нека от даден връх излизат aa червени, bb зелени и cc сини ребра. Зарядът на ъглите с център този връх е2((a2)+(b2)+(c2))−(ab+ac+bc)=a2+b2+c2−ab−ac−bc−(a+b+c)=a2+b2+c2−ab−ac−bc−(n−1)≥−(n−1),\begin{align*} 2\left(\binom a2+\binom b2+\binom c2\right)-(ab+ac+bc) &=a^2+b^2+c^2-ab-ac-bc-(a+b+c)\\ &=a^2+b^2+c^2-ab-ac-bc-(n-1)\\ &\ge -(n-1), \end{align*}защото a2+b2+c2−ab−ac−bc≥0a^2+b^2+c^2-ab-ac-bc\ge0. Сумирайки по всички nn върха, получаваме, че общият заряд е поне −n(n−1)-n(n-1). Затова6A−3B≥−n(n−1),6A-3B\ge -n(n-1),което е еквивалентно наB≤2A+n(n−1)3.B\le2A+\frac{n(n-1)}3.Това доказва твърдението.
Отвори задачатаEvan Chen VONVON TSTST 2023/4Условие — източник

Задача 5

Пълен запис
Условие
Нека aa, bb и cc са комплексни числа с произведение 11. Да се предположи, че никое от тях не е реално и никое няма модул 11. Дефинираме p=(a+b+c)+(1a+1b+1c),p=(a+b+c)+\left(\frac1a+\frac1b+\frac1c\right),q=ab+bc+ca.\qquad q=\frac{a}{b}+\frac{b}{c}+\frac{c}{a}. Ако pp и qq са реални числа, да се намерят всички възможни стойности на наредената двойка (p,q)(p,q).
РешениеЩе докажем, че единствената възможност е (p,q)=(−3,3)(p,q)=(-3,3). Записваме a=yx,b=zy,c=xza=\frac yx,\qquad b=\frac zy,\qquad c=\frac xz за ненулеви комплексни числа x,y,zx,y,z. Тогава abc=1abc=1 автоматично. Пряко пресмятане дава p+3=3+∑cyc(xy+yx)=p+3=3+\sum_{\mathrm{cyc}}\left(\frac xy+\frac yx\right)=(x+y+z)(xy+yz+zx)xyz\frac{(x+y+z)(xy+yz+zx)}{xyz} и q−3=−3+∑cycy2zx=x3+y3+z3−3xyzxyz=q-3=-3+\sum_{\mathrm{cyc}}\frac{y^2}{zx}=\frac{x^3+y^3+z^3-3xyz}{xyz}=(x+y+z)(x2+y2+z2−xy−yz−zx)xyz.\frac{(x+y+z)(x^2+y^2+z^2-xy-yz-zx)}{xyz}. Ако x+y+z=0x+y+z=0, веднага получаваме p=−3p=-3 и q=3q=3. Остава да покажем, че друг случай е невъзможен. Да допуснем, че x+y+z≠0x+y+z\ne0. Умножаваме едновременно x,y,zx,y,z по подходящо ненулево комплексно число, така че x+y+zx+y+z да стане реално. Тъй като 3(p+3)+(q−3)=(x+y+z)3xyz3(p+3)+(q-3)=\frac{(x+y+z)^3}{xyz} е реално, следва, че xyzxyz е реално. Понеже и p+3p+3 е реално, от първата формула получаваме, че xy+yz+zxxy+yz+zx също е реално. Следователно x,y,zx,y,z са корени на кубичен полином с реални коефициенти. Значи или трите числа са реални, или две от тях са комплексно спрегнати. В първия случай a,b,ca,b,c са реални, което е забранено. Във втория случай отношението на спрегнатата двойка има модул 11, така че едно от a,b,ca,b,c има модул 11, което също е забранено. Следователно непременно x+y+z=0x+y+z=0, а тогава (p,q)=(−3,3)(p,q)=(-3,3). Остава да видим, че тази двойка се постига. Например вземаме x=3x=3, y=4iy=4i, z=−(3+4i)z=-(3+4i) и дефинираме a=y/xa=y/x, b=z/yb=z/y, c=x/zc=x/z. Тогава abc=1abc=1, никое от a,b,ca,b,c не е реално или с модул 11, а понеже x+y+z=0x+y+z=0, получаваме точно (p,q)=(−3,3)(p,q)=(-3,3).
Отвори задачатаEvan Chen VONVON TSTST 2023/5Условие — източник

Задача 6

Пълен запис
Условие
Нека ABCABC е разностранен триъгълник и нека PP и QQ са две различни точки във вътрешността му. Да се предположи, че ъглополовящите на ∠PAQ\angle PAQ, ∠PBQ\angle PBQ и ∠PCQ\angle PCQ са съответно височините на триъгълника ABCABC. Да се докаже, че средата на PQPQ лежи на правата на Ойлер на ABCABC.
РешениеНека HH е ортоцентърът на ABCABC. Първо ще използваме следния стандартен факт: съществува точка P′P' такава, че∠APH+∠AP′H=∠BPH+∠BP′H=\angle APH+\angle AP'H=\angle BPH+\angle BP'H=∠CPH+∠CP′H=0\angle CPH+\angle CP'H=0като насочени ъгли. След инверсия с център HH това е точно твърдението, че образът на PP има изогонално спрегната точка спрямо образа на триъгълника ABCABC. Нека XX, YY и ZZ са отраженията на PP съответно спрямо правите AHAH, BHBH и CHCH. Нека Q′Q' е образът на QQ при инверсията спрямо окръжността (PXYZ)(PXYZ). Ще покажем, че четириъгълниците ABCP′ABCP' и XYZQ′XYZQ' са подобни в противоположна ориентация. Наистина,∠YXZ=∠YPZ=∠(BH,CH)=−∠BAC,\angle YXZ=\angle YPZ=\angle(BH,CH)=-\angle BAC,и аналогичните равенства важат циклично. Освен това∠HQ′X=−∠HXQ=−∠HXA=∠HPA=−∠HP′A,\angle HQ'X=-\angle HXQ=-\angle HXA=\angle HPA=-\angle HP'A,и отново циклично; събирането по двойки дава ∠YQ′Z=−∠BP′C\angle YQ'Z=-\angle BP'C и аналогичните две равенства. Следователно ABCP′ABCP' и XYZQ′XYZQ' са подобни. Нека OO е центърът на описаната окръжност на ABCABC. От полученото подобие следва ABCOP′∼XYZHQ′ABCOP'\sim XYZHQ'. Понеже ∠HP′A=∠OP′A\angle HP'A=\angle OP'A, точката P′P' лежи на OHOH. Подобно пренасяне показва, че Q′Q' лежи на правата на Ойлер на триъгълника XYZXYZ. Остава да преведем това обратно към средата на PQPQ. Нека G1G_1 и G2G_2 са медицентровете съответно на ABCABC и XYZXYZ. Работим със знакови лица. Понеже Q′Q', G2G_2 и HH са колинеарни, имаме[G1HP]+[G1HQ][G_1HP]+[G_1HQ]=[AHP]+[BHP]+[CHP]3+[AHQ]+[BHQ]+[CHQ]3=\frac{[AHP]+[BHP]+[CHP]}3+\frac{[AHQ]+[BHQ]+[CHQ]}3=[AHQ]−[AHX]+[BHQ]−[BHY]+[CHQ]−[CHZ]3=\frac{[AHQ]-[AHX]+[BHQ]-[BHY]+[CHQ]-[CHZ]}3=[HQX]+[HQY]+[HQZ]3=[QG2H]=0.=\frac{[HQX]+[HQY]+[HQZ]}3=[QG_2H]=0.Следователно точките PP и QQ имат противоположни знакови отстояния спрямо правата G1HG_1H. Значи G1HG_1H минава през средата на PQPQ. Но G1HG_1H е правата на Ойлер на ABCABC, което доказва твърдението.
Отвори задачатаEvan Chen VONVON TSTST 2023/6Условие — източник

Задача 7

Пълен запис
Условие
В редица от 20232023 монети най-лявата монета е тура, а след това монетите се редуват тура, ези, тура, ези и така нататък. С всяка операция избираме една монета и я обръщаме, но след първата операция всяка следваща избрана монета трябва да е съседна на монетата, избрана в предишната операция. Да се намери най-малкият възможен брой операции, след който всички монети могат да бъдат ези.
РешениеЩе докажем по-общо твърдение за 4n+34n+3 монети. Отговорът тогава е 8n+48n+4, а при 4n+3=20234n+3=2023 имаме n=505n=505, така че търсеният брой е 40444044. За долната оценка номерираме монетите отляво надясно. Монетите на нечетни позиции започват тура и трябва да бъдат обърнати нечетен брой пъти; монетите на четни позиции започват ези и трябва да бъдат обърнати четен брой пъти. Първата и последната монета са на нечетни позиции и трябва да се обърнат поне веднъж. Понеже последователните операции са върху съседни монети, за да се стигне от единия край до другия, трябва да се посетят всички позиции. Значи всяка четна позиция се обръща поне два пъти, общо поне 4n+24n+2 обръщания върху четни позиции. Броят обръщания върху нечетни позиции се различава от него с най-много 11, а освен това е четен, защото има 2n+22n+2 нечетни позиции и всяка от тях се обръща нечетен брой пъти. Следователно и върху нечетни позиции има поне 4n+24n+2 обръщания. Общо са нужни поне 8n+48n+4 операции. Конструкцията постига тази граница: за всяко k=0,1,…,n−1k=0,1,\ldots,n-1 извършваме последователно операциите върху позициите 4k+1,4k+2,4k+3,4k+2,4k+1,4k+2,4k+3,4k+2,4k+3,4k+4,4k+3,4k+4,4k+3,4k+4,4k+3,4k+4, а накрая върху 4n+1,4n+2,4n+3,4n+2.4n+1,4n+2,4n+3,4n+2. Лесна проверка по четност показва, че всяка нечетна позиция е обърната нечетен брой пъти, всяка четна позиция - четен брой пъти, и всички избрани позиции са съседни на предишната. Затова 8n+48n+4 операции са достатъчни и необходими.
Отвори задачатаEvan Chen VONVON TSTST 2023/7Условие — източник

Задача 8

Пълен запис
Условие
Нека ABCABC е равностранен триъгълник със страна 11. Точките A1A_1 и A2A_2 са избрани върху страната BCBC, точките B1B_1 и B2B_2 са избрани върху страната CACA, а точките C1C_1 и C2C_2 са избрани върху страната ABAB така, че BA1<BA2BA_1\lt{}BA_2, CB1<CB2CB_1\lt{}CB_2 и AC1<AC2AC_1\lt{}AC_2. Да се предположи, че отсечките B1C2B_1C_2, C1A2C_1A_2 и A1B2A_1B_2 се пресичат в една точка, а периметрите на триъгълниците AB2C1AB_2C_1, BC2A1BC_2A_1 и CA2B1CA_2B_1 са равни. Да се намерят всички възможни стойности на този общ периметър.
РешениеЩе докажем, че единствената възможна стойност на общия периметър е 11. Първо записваме една стандартна лема. Ако шестте точки са избрани така, че триъгълниците AB2C1AB_2C_1, BC2A1BC_2A_1 и CA2B1CA_2B_1 имат периметър 11, тогава правите B1C2B_1C_2, C1A2C_1A_2 и A1B2A_1B_2 се пресичат в една точка. Наистина, в равностранен триъгълник със страна 11 условието AB2+B2C1+C1A=1AB_2+B_2C_1+C_1A=1 е точно условието правата B2C1B_2C_1 да е допирателна към вписаната окръжност на ABCABC. Аналогично C2A1C_2A_1 и A2B1A_2B_1 също са допирателни към същата окръжност. Следователно шестоъгълникът с върхове A1,A2,B1,B2,C1,C2A_1,A_2,B_1,B_2,C_1,C_2 е описан около тази окръжност, а по теоремата на Брианшон неговите главни диагонали A1B2A_1B_2, A2C1A_2C_1 и B1C2B_1C_2 се пресичат в една точка. Това доказва лемата. Нека сега общият периметър е pp. Ясно е, че p>0p\gt{}0. Ако p=1p=1, лемата показва, че такава конфигурация наистина съществува; например може да се вземат трите малки триъгълника равностранни със страна 1/31/3. Остава да покажем, че p≠1p\ne1 е невъзможно. Прилагаме хомотетия към отсечката B2C1B_2C_1 с център AA и коефициент 1/p1/p и получаваме отсечката B2′C1′B_2'C_1'. По същия начин, циклично, получаваме C2′A1′C_2'A_1' и A2′B1′A_2'B_1'. Новите три малки триъгълника имат периметър 11, затова по лемата правите B1′C2′B_1'C_2', C1′A2′C_1'A_2' и A1′B2′A_1'B_2' се пресичат в една точка. Ако p<1p\lt{}1, тогава новите точки са по-далече от съответните върхове от първоначалните точки. Правите B1C2B_1C_2, C1A2C_1A_2 и A1B2A_1B_2 трябва да лежат съответно във вътрешностите на трите четириъгълника BCB1′C2′BCB_1'C_2', CAC1′A2′CAC_1'A_2' и ABA1′B2′ABA_1'B_2'. Тези три четириъгълника нямат обща вътрешна точка, което противоречи на това, че дадените три прави се пресичат в една точка. Следователно p≥1p\ge1. Същият аргумент, приложен с разменени роли на първоначалната и новата конфигурация, дава p≤1p\le1. Значи непременно p=1p=1, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2023/8Условие — източник

Задача 9

Пълен запис
Условие
Нека pp е фиксирано просто число, а a≥2a\ge2 и e≥1e\ge1 са фиксирани цели числа. За функция f:Z/aZ→Z/peZf:\mathbb Z/a\mathbb Z\to\mathbb Z/p^e\mathbb Z и цяло число k≥0k\ge0 дефинираме kk-тата крайна разлика Δkf:Z/aZ→Z/peZ\Delta^k f:\mathbb Z/a\mathbb Z\to\mathbb Z/p^e\mathbb Z рекурсивно чрез Δ0f(n)=f(n),\Delta^0f(n)=f(n),Δkf(n)=Δk−1f(n+1)−Δk−1f(n)\qquad \Delta^k f(n)=\Delta^{k-1}f(n+1)-\Delta^{k-1}f(n) за k=1,2,…k=1,2,\ldots. Да се определи броят на функциите ff, за които съществува k≥1k\ge1 с Δkf=f\Delta^k f=f.
РешениеОтговорът е pe(a−pνp(a)).p^{e(a-p^{\nu_p(a)})}. Поставяме d=νp(a)d=\nu_p(a) и a=pdba=p^d b, така че p∤bp\nmid b. Ще наричаме функцията ff съществена, ако f=Δkff=\Delta^k f за някое k≥1k\ge1. Основното твърдение е следното: ff е съществена тогава и само тогава, когато за всяко x∈Z/aZx\in\mathbb Z/a\mathbb Z f(x)+f(x+pd)+⋯+f(x+(b−1)pd)=0.f(x)+f(x+p^d)+\cdots+f(x+(b-1)p^d)=0. Първо доказваме необходимостта. Нека h=Δpdgh=\Delta^{p^d}g. От биномната формула за крайни разлики h(x)=∑j=0pd(−1)j(pdj)g(x+pd−j).h(x)=\sum_{j=0}^{p^d}(-1)^j\binom{p^d}{j}g(x+p^d-j). Всички вътрешни биномни коефициенти (pdj)\binom{p^d}{j}, 1≤j≤pd−11\le j\le p^d-1, се делят на pp, следователно h(x)≡g(x+pd)+(−1)pdg(x)(modp).h(x)\equiv g(x+p^d)+(-1)^{p^d}g(x)\pmod p. Сумирайки това по x,x+pd,…,x+(b−1)pdx,x+p^d,\ldots,x+(b-1)p^d, получаваме сума, която е 00 по модул pp: за pp нечетно членовете се телескопират, а за p=2p=2 множителят 22 също я занулява по модул 22. Повтаряйки същия аргумент ee пъти, следва, че ако h=Δepdgh=\Delta^{e p^d}g, то h(x)+h(x+pd)+⋯+h(x+(b−1)pd)=0h(x)+h(x+p^d)+\cdots+h(x+(b-1)p^d)=0 в Z/peZ\mathbb Z/p^e\mathbb Z. Ако ff е съществена, тогава ff лежи в образа на всяка достатъчно голяма степен на Δ\Delta, понеже от f=Δkff=\Delta^k f следва f=Δmkff=\Delta^{mk}f за всички mm. В частност ff лежи в образа на Δepd\Delta^{e p^d}, и необходимото равенство е доказано. Обратно, нека SS е множеството от всички функции, които удовлетворяват това равенство. Ясно е, че Δ\Delta изпраща SS в себе си. Достатъчно е да покажем, че Δ\Delta е инективно върху SS; понеже SS е крайно, тогава Δ\Delta е пермутация на SS, а всяка функция в SS е периодична под итерациите на Δ\Delta, тоест съществена. Ако f,g∈Sf,g\in S и Δf=Δg\Delta f=\Delta g, тогава g−fg-f е константа; да пишем g=f+λg=f+\lambda. Прилагайки равенството за ff и за gg в един и същ клас x,x+pd,…,x+(b−1)pdx,x+p^d,\ldots,x+(b-1)p^d, получаваме bλ=0b\lambda=0 в Z/peZ\mathbb Z/p^e\mathbb Z. Понеже p∤bp\nmid b, числото bb е обратимо по модул pep^e, следователно λ=0\lambda=0 и f=gf=g. Значи Δ\Delta е инективно върху SS. Остава броенето. Условието казва, че във всеки от pdp^d-те класа x, x+pd, …, x+(b−1)pdx,\ x+p^d,\ \ldots,\ x+(b-1)p^d последната стойност се определя еднозначно от предишните b−1b-1 стойности. Затова произволно можем да изберем точно a−pda-p^d стойности на функцията, всяка по pep^e начина, а останалите pdp^d стойности са принудени. Следователно броят на функциите е (pe)a−pd=pe(a−pνp(a)),(p^e)^{a-p^d}=p^{e(a-p^{\nu_p(a)})}, както се искаше.
Отвори задачатаEvan Chen VONVON TSTST 2023/9Условие — източник