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

IMO Shortlisted Problems

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

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

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

2022

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

11-12

25 задачи

Задача A1

Пълен запис
Условие
Нека a1,a2,…a_1,a_2,\ldots е редица от положителни реални числа, за коятоan+12+anan+2≤an+an+2a_{n+1}^2+a_na_{n+2}\le a_n+a_{n+2}за всяко положително цяло число nn. Докажете, че a2022≤1a_{2022}\le1.
РешениеОт даденото неравенство получавамеan+12−1≤a_{n+1}^2-1\lean+an+2−anan+2−1=(1−an)(an+2−1).(1) a_n+a_{n+2}-a_na_{n+2}-1=(1-a_n)(a_{n+2}-1).\tag{1}Да допуснем, че за някое nn са изпълнени an+1>1a_{n+1}\gt{}1 и an+2>1a_{n+2}\gt{}1. От (1) следва, че 1−an>01-a_n\gt{}0, а значиan+12−1≤(1−an)(an+2−1)<a_{n+1}^2-1\le(1-a_n)(a_{n+2}-1)\lt{}(1+an+2)(an+2−1)=an+22−1.(1+a_{n+2})(a_{n+2}-1)=a_{n+2}^2-1.От друга страна, прилагайки (1) с индекс n+1n+1, имамеan+22−1≤a_{n+2}^2-1\le(1−an+1)(an+3−1)=(an+1−1)(1−an+3)<(1-a_{n+1})(a_{n+3}-1)=(a_{n+1}-1)(1-a_{n+3})\lt{}(1+an+1)(an+1−1)=an+12−1,(1+a_{n+1})(a_{n+1}-1)=a_{n+1}^2-1,противоречие. Следователно не може да има два последователни члена, по-големи от 11, освен евентуално a1a_1 и a2a_2. Ако a2022>1a_{2022}\gt{}1, тогава a2021≤1a_{2021}\le1 и a2023≤1a_{2023}\le1. Но от (1) за n=2021n=2021 получаваме0<a20222−1≤(1−a2021)(a2023−1)≤0,0\lt{}a_{2022}^2-1\le(1-a_{2021})(a_{2023}-1)\le0,което е невъзможно. Значи a2022≤1a_{2022}\le1.
Отвори задачатаMathNetISL 2022 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека k≥2k\ge2 е цяло число. Да се намери най-малкото цяло число n≥k+1n\ge k+1 със следното свойство: съществува множество от nn различни реални числа, всеки елемент на което може да се представи като сума на kk други различни елемента на множеството.
РешениеОтговорът еn=k+4.n=k+4.Първо ще докажем, че n≥k+4n\ge k+4. Нека съществува такова множество и нека елементите му саa1<a2<⋯<an.a_1\lt{}a_2\lt{}\cdots\lt{}a_n.За да се представи a1a_1 като сума на kk различни други елемента, трябваa1≥a2+a3+⋯+ak+1.a_1\ge a_2+a_3+\cdots+a_{k+1}.Аналогично, за ana_n трябваan−k+an−k+1+⋯+an−1≥an.a_{n-k}+a_{n-k+1}+\cdots+a_{n-1}\ge a_n.Ако n=k+1n=k+1, първото неравенство даваa1≥a2+⋯+ak+1>a1+⋯+ak≥ak+1,a_1\ge a_2+\cdots+a_{k+1}\gt{}a_1+\cdots+a_k\ge a_{k+1},противоречие. Ако n=k+2n=k+2, то a1≥a2+⋯+ak+1≥ak+2a_1\ge a_2+\cdots+a_{k+1}\ge a_{k+2}, пак противоречие. Ако n=k+3n=k+3, събирамеa1≥a2+⋯+ak+1,a3+⋯+ak+2≥ak+3a_1\ge a_2+\cdots+a_{k+1},\qquad a_3+\cdots+a_{k+2}\ge a_{k+3}и получаваме a1+ak+2≥a2+ak+3a_1+a_{k+2}\ge a_2+a_{k+3}, което е невъзможно. Следователно n≥k+4n\ge k+4. Остава да построим пример с k+4k+4 елемента. Нека първо k=2ℓk=2\ell, където ℓ≥1\ell\ge1. За i=1,2,…,ℓ+2i=1,2,\ldots,\ell+2 положим Ai={−i,i}A_i=\{-i,i\} и разгледамеA1∪A2∪⋯∪Aℓ+2.A_1\cup A_2\cup\cdots\cup A_{\ell+2}.Това множество има 2ℓ+4=k+42\ell+4=k+4 елемента. Достатъчно е да представим положителните числа 1,2,…,ℓ+21,2,\ldots,\ell+2, защото представяне на ii веднага дава представяне на −i-i след смяна на знаците. Ако i<ℓ+2i\lt{}\ell+2, вземаме двата елемента от произволни ℓ−1\ell-1 множества AjA_j с j≠1,i+1j\ne1,i+1, както и числата i+1i+1 и −1-1. Сумата е ii, а броят на използваните числа е 2(ℓ−1)+2=2ℓ=k2(\ell-1)+2=2\ell=k. Ако i=ℓ+2i=\ell+2, вземаме двата елемента от произволни ℓ−1\ell-1 множества AjA_j с j≠1,ℓ+1j\ne1,\ell+1, както и числата ℓ+1\ell+1 и 11; сумата е ℓ+2\ell+2. За нечетно k=2ℓ+1k=2\ell+1 добавяме числото 00 към предишната конструкция за 2ℓ2\ell. Всяко вече построено представяне просто се допълва с 00. Самото 00 се представя като сума на 1,2,−31,2,-3 и на всички числа от останалите ℓ−1\ell-1 двойки A4,A5,…,Aℓ+2A_4,A_5,\ldots,A_{\ell+2}. Така и при нечетно kk получаваме множество с k+4k+4 елемента.
Отвори задачатаMathNetISL 2022 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека R>0\mathbb R_{\gt{}0} е множеството на положителните реални числа. Да се намерят всички функции f:R>0→R>0f:\mathbb R_{\gt{}0}\to\mathbb R_{\gt{}0}, за които за всяко x∈R>0x\in\mathbb R_{\gt{}0} съществува единствено y∈R>0y\in\mathbb R_{\gt{}0}, удовлетворяващоxf(y)+yf(x)≤2.xf(y)+yf(x)\le2.
РешениеОтговорът еf(x)=1x(x>0).f(x)=\frac1x\qquad(x\gt{}0).Първо проверяваме, че тази функция работи. По неравенството между средно аритметично и средно геометричноxy+yx≥2\frac xy+\frac yx\ge2за всички x,y>0x,y\gt{}0, като равенство има само при x=yx=y. Следователно за всяко фиксирано x>0x\gt{}0 единственото y>0y\gt{}0, за което x/y+y/x≤2x/y+y/x\le2, е y=xy=x. Нека сега ff е произволно решение. Ще наричаме двойка (x,y)(x,y) добра, ако xf(y)+yf(x)≤2xf(y)+yf(x)\le2. Ако (x,y)(x,y) е добра, то и (y,x)(y,x) е добра. Лема. Ако (x,y)(x,y) е добра, то x=yx=y. Да допуснем противното, x≠yx\ne y. Понеже за даденото xx доброто yy е единствено, двойката (x,x)(x,x) не е добра. Значи 2xf(x)>22xf(x)\gt{}2, тоест xf(x)>1xf(x)\gt{}1. По същия начин, понеже (y,x)(y,x) е добра, двойката (y,y)(y,y) не е добра и yf(y)>1yf(y)\gt{}1. Тогаваxf(y)+yf(x)≥xf(y)+yf(x)\ge2x2xf(y)⋅yf(x)=2x2xf(x)⋅yf(y)>2,2\sqrt{\vphantom{x^2}xf(y)\cdot yf(x)}=2\sqrt{\vphantom{x^2}xf(x)\cdot yf(y)}\gt{}2,противоречие с добротата на (x,y)(x,y). Лемата е доказана. От условието за всяко x>0x\gt{}0 съществува добра двойка, съдържаща xx. По лемата тя може да бъде само (x,x)(x,x), следователно2xf(x)≤2,2xf(x)\le2,илиf(x)≤1x(x>0).(1)f(x)\le\frac1x\qquad(x\gt{}0).\tag{1}Ако за някое xx има строго неравенство f(x)<1/xf(x)\lt{}1/x, избираме a>0a\gt{}0 така, чеf(x)<1a<1x.f(x)\lt{}\frac1a\lt{}\frac1x.Има поне две такива стойности на aa. От (1) получавамеaf(x)+xf(a)<1+xa<2,af(x)+xf(a)\lt{}1+\frac xa\lt{}2,тоест (x,a)(x,a) е добра двойка за поне две различни стойности на aa, противоречие с единствеността. Следователно навсякъде има равенство в (1), т.е. f(x)=1/xf(x)=1/x за всички x>0x\gt{}0.
Отвори задачатаMathNetISL 2022 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число и нека x1,x2,…,xnx_1,x_2,\ldots,x_n са реални числа от интервала [0,1][0,1]. Нека s=x1+x2+⋯+xns=x_1+x_2+\cdots+x_n и s≥3s\ge3. Докажете, че съществуват цели числа ii и jj с 1≤i<j≤n1\le i\lt{}j\le n, за които2j−ixixj>2s−3.2^{j-i}x_ix_j\gt{}2^{s-3}.
РешениеИзбираме 1≤a<b≤n1\le a\lt{}b\le n така, че 2b−axaxb2^{b-a}x_ax_b да е максимално. Понеже s≥3s\ge3, такъв максимум може да се вземе положителен. От максималността следваxa+t≤2txa(1−a≤t≤b−a−1)x_{a+t}\le2^t x_a\qquad(1-a\le t\le b-a-1)и аналогичноxb−t≤2txb(b−n≤t≤b−a+1).x_{b-t}\le2^t x_b\qquad(b-n\le t\le b-a+1).Нека u,vu,v са неотрицателни цели числа, за които2−u−1<xa≤2−u,2−v−1<xb≤2−v,2^{-u-1}\lt{}x_a\le2^{-u},\qquad 2^{-v-1}\lt{}x_b\le2^{-v},и запишем xa=2−αx_a=2^{-\alpha}, xb=2−βx_b=2^{-\beta}. Тогава u≤α<u+1u\le\alpha\lt{}u+1 и v≤β<v+1v\le\beta\lt{}v+1. От горните оценки получаваме∑i=1a+u−1xi<2uxa≤1,\sum_{i=1}^{a+u-1}x_i\lt{}2^u x_a\le1,и по същия начин∑i=b−v+1nxi<2vxb≤1.\sum_{i=b-v+1}^{n}x_i\lt{}2^v x_b\le1.Значи сумата на членовете извън интервала от индекси [a+u,b−v][a+u,b-v] е по-малка от 22. Тъй като общата сума е поне 33 и всеки член е най-много 11, в този интервал има поне два индекса, тоест a+u<b−va+u\lt{}b-v. Сега оценяваме двете крайни части по същия начин, а вътрешните членове тривиално с 11:s<2u+1xa+2v+1xb+(b−v−a−u−1).s\lt{}2^{u+1}x_a+2^{v+1}x_b+(b-v-a-u-1).След замяна на xax_a и xbx_b това ставаs<b−a+(2u+1−α+2v+1−β−u−v−1).s\lt{}b-a+\left(2^{u+1-\alpha}+2^{v+1-\beta}-u-v-1\right).За 0≤t≤10\le t\le1 имаме 2t≤1+t2^t\le1+t. Прилагайки това за t=u+1−αt=u+1-\alpha и t=v+1−βt=v+1-\beta, намираме2u+1−α+2v+1−β−u−v−1≤3−α−β.2^{u+1-\alpha}+2^{v+1-\beta}-u-v-1\le3-\alpha-\beta.Следователноs−3<b−a−α−β,s-3\lt{}b-a-\alpha-\beta,а оттук2s−3<2b−a−α−β=2b−axaxb.2^{s-3}\lt{}2^{b-a-\alpha-\beta}=2^{b-a}x_ax_b.Избраната двойка (a,b)(a,b) е търсената.
Отвори задачатаMathNetISL 2022 A4Условие — източник

Задача A5

Пълен запис
Условие
Да се намерят всички положителни цели числа n≥2n\ge2, за които съществуват реални числаa1<a2<⋯<ana_1\lt{}a_2\lt{}\cdots\lt{}a_nи реално число r>0r\gt{}0 такива, че всичките 12n(n−1)\frac12n(n-1) разлики aj−aia_j-a_i за 1≤i<j≤n1\le i\lt{}j\le n са равни, в някакъв ред, на числатаr1,r2,…,r12n(n−1).r^1,r^2,\ldots,r^{\frac12n(n-1)}.
РешениеОтговорът еn∈{2,3,4}.n\in\{2,3,4\}.Конструкциите за тези три стойности са следните. За n=2n=2 можем да вземем (a1,a2)=(1,3)(a_1,a_2)=(1,3) и r=2r=2. За n=3n=3 нека r>1r\gt{}1 е коренът на x2−x−1=0x^2-x-1=0 и нека(a1,a2,a3)=(0,r,r+r2).(a_1,a_2,a_3)=(0,r,r+r^2).Тогава разликите са r,r2,r+r2=r3r,r^2,r+r^2=r^3. За n=4n=4 нека r∈(1,2)r\in(1,2) е коренът на x3−x−1=0x^3-x-1=0 и нека(a1,a2,a3,a4)=(0,r,r+r2,r+r2+r3).(a_1,a_2,a_3,a_4)=(0,r,r+r^2,r+r^2+r^3).Тогава шестте разлики са r,r2,r3,r4,r5,r6r,r^2,r^3,r^4,r^5,r^6. Остава да докажем невъзможността за n≥5n\ge5. Ако е нужно, след умножаване на всички aia_i с една и съща положителна константа можем да заменим rr с 1/r1/r, така че ще считаме r>1r\gt{}1. Некаb=12n(n−1).b=\frac12n(n-1).Най-голямата разлика е an−a1=rba_n-a_1=r^b. Лема. Имаме rn−1>2r^{n-1}\gt{}2. Наистина, има само n−1n-1 съседни разлики ai+1−aia_{i+1}-a_i, затова някоя разлика aj−ai=rea_j-a_i=r^e с e≤ne\le n има j≥i+2j\ge i+2. Тогаваrn≥re=aj−ai=(aj−aj−1)+(aj−1−ai)>r^n\ge r^e=a_j-a_i=(a_j-a_{j-1})+(a_{j-1}-a_i)\gt{}r+r=2r,r+r=2r,откъдето rn−1>2r^{n-1}\gt{}2. За всяко i=2,3,…,n−1i=2,3,\ldots,n-1 разглеждамеan−a1=(an−ai)+(ai−a1).a_n-a_1=(a_n-a_i)+(a_i-a_1).Във всяко от тези n−2n-2 равенства поне един от двата члена вдясно е поне половината от an−a1a_n-a_1. От лематаrb−(n−1)=rbrn−1<12rb,r^{b-(n-1)}=\frac{r^b}{r^{n-1}}\lt{}\frac12r^b,така че достатъчно големите степени сред r1,…,rb−1r^1,\ldots,r^{b-1} са най-многоrb−1,rb−2,…,rb−(n−2).r^{b-1},r^{b-2},\ldots,r^{b-(n-2)}.Следователно големите членове в горните n−2n-2 равенства са точно тези степени, в някакъв ред. Записваме съответните малки степени така:rb=rb−i+rαi(i=1,2,…,n−2),r^b=r^{b-i}+r^{\alpha_i}\qquad(i=1,2,\ldots,n-2),където1≤α1<α2<⋯<αn−2≤b−(n−1).1\le\alpha_1\lt{}\alpha_2\lt{}\cdots\lt{}\alpha_{n-2}\le b-(n-1).Тъй като r>1r\gt{}1, от изпъкналостта на степенната функция следваα2−α1>α3−α2>⋯>αn−2−αn−3.\alpha_2-\alpha_1\gt{}\alpha_3-\alpha_2\gt{}\cdots\gt{}\alpha_{n-2}-\alpha_{n-3}.Освен това последната разлика е поне 22; ако беше 11, от равенството на съответните разлики на степени щеше да следва αn−3=b−(n−2)\alpha_{n-3}=b-(n-2), противоречие. Затоваαn−2−α1≥2+3+⋯+(n−2)=12n(n−3).\alpha_{n-2}-\alpha_1\ge2+3+\cdots+(n-2)=\frac12n(n-3).От друга страна,αn−2−α1≤b−n=12n(n−3).\alpha_{n-2}-\alpha_1\le b-n=\frac12n(n-3).Следователно навсякъде има равенство. В частност получаваме двете равенстваrb=rb−(n−2)+rb−(n−2)−1,r^b=r^{b-(n-2)}+r^{b-(n-2)-1},rb=rb−(n−3)+rb−(n−2)−3.\qquad r^b=r^{b-(n-3)}+r^{b-(n-2)-3}.Те са еквивалентни наrn−1=r+1,rn+1=r4+1.r^{n-1}=r+1,\qquad r^{n+1}=r^4+1.Но тогаваr4+1=rn+1=rn−1r2=(r+1)r2=r3+r2,r^4+1=r^{n+1}=r^{n-1}r^2=(r+1)r^2=r^3+r^2,тоест(r−1)(r3−r−1)=0.(r-1)(r^3-r-1)=0.Понеже r≠1r\ne1, имаме r3=r+1=rn−1r^3=r+1=r^{n-1}, откъдето n=4n=4, противоречие с n≥5n\ge5.
Отвори задачатаMathNetISL 2022 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека R\mathbb R е множеството на реалните числа. Нека F\mathcal F е множеството от всички функции f:R→Rf:\mathbb R\to\mathbb R, за коитоf(x+f(y))=f(x)+f(y)f(x+f(y))=f(x)+f(y)за всички x,y∈Rx,y\in\mathbb R. Да се намерят всички рационални числа qq, за които за всяка функция f∈Ff\in\mathcal F съществува z∈Rz\in\mathbb R със свойството f(z)=qzf(z)=qz.
РешениеОтговорът е{n+1n:n∈Z, n≠0}.\left\{\frac{n+1}{n}: n\in\mathbb Z,\ n\ne0\right\}.Нека Z\mathcal Z е множеството на всички рационални числа с търсеното свойство и некаS={n+1n:n∈Z, n≠0}.S=\left\{\frac{n+1}{n}: n\in\mathbb Z,\ n\ne0\right\}.Ще докажем Z=S\mathcal Z=S. Първо нека f∈Ff\in\mathcal F. От уравнението при (0,0)(0,0) следва f(f(0))=2f(0)f(f(0))=2f(0), а при (0,f(0))(0,f(0)) следва f(2f(0))=3f(0)f(2f(0))=3f(0). По индукция получавамеf(kf(0))=(k+1)f(0)(k≥1).f(kf(0))=(k+1)f(0)\qquad(k\ge1).Наистина, ако това е вярно за kk, то уравнението при (0,kf(0))(0,kf(0)) даваf((k+1)f(0))=f(0)+f(kf(0))=(k+2)f(0).f((k+1)f(0))=f(0)+f(kf(0))=(k+2)f(0).Следователно за всяко k≥1k\ge1 съществува z=kf(0)z=kf(0), за коетоf(z)=k+1kz.f(z)=\frac{k+1}{k}z.Аналогично, от уравнението при (−f(0),0)(-f(0),0) получаваме f(−f(0))=0f(-f(0))=0, а после по същата индукцияf(−kf(0))=(−k+1)f(0)(k≥1).f(-kf(0))=(-k+1)f(0)\qquad(k\ge1).Така всяко число от SS принадлежи на Z\mathcal Z. Остава да покажем, че друго рационално число не работи. Нека p∉Sp\notin S е рационално. Ще построим функция f∈Ff\in\mathcal F, за която f(z)≠pzf(z)\ne pz за всяко реално zz. За всяко α∈[0,1)\alpha\in[0,1) ще изберем цяло число mm така, чеm+n≠p(α+n)за всяко n∈Z.(1)m+n\ne p(\alpha+n)\qquad\text{за всяко }n\in\mathbb Z.\tag{1}Ако p=1p=1, това е очевидно. Ако p≠1p\ne1, равенството в (1) би било равносилно на това числотоm−pαp−1\frac{m-p\alpha}{p-1}да е цяло. Ако не можехме да изберем такова mm, тогава за две последователни цели числа mm и m+1m+1 горната дроб би била цяло число; разликата им е 1/(p−1)1/(p-1). Това би наложило 1/(p−1)∈Z1/(p-1)\in\mathbb Z, тоест p∈Sp\in S, противоречие. Дефинираме g:[0,1)→Zg:[0,1)\to\mathbb Z, като за всяко α\alpha избираме едно такова mm и слагаме g(α)=mg(\alpha)=m. Накрая полагамеf(x)=g({x})+⌊x⌋,f(x)=g(\{x\})+\lfloor x\rfloor,където {x}\{x\} е дробната част на xx. Тогава f(x)f(x) винаги е цяло число, затова{x+f(y)}={x},⌊x+f(y)⌋=⌊x⌋+f(y).\{x+f(y)\}=\{x\},\qquad \lfloor x+f(y)\rfloor=\lfloor x\rfloor+f(y).Следователноf(x+f(y))=g({x})+⌊x⌋+f(y)=f(x)+f(y),f(x+f(y))=g(\{x\})+\lfloor x\rfloor+f(y)=f(x)+f(y),тоест f∈Ff\in\mathcal F. Ако z={z}+⌊z⌋z=\{z\}+\lfloor z\rfloor, то по избора на g({z})g(\{z\}) имамеg({z})+⌊z⌋≠p({z}+⌊z⌋),g(\{z\})+\lfloor z\rfloor\ne p(\{z\}+\lfloor z\rfloor),тоест f(z)≠pzf(z)\ne pz. Значи p∉Zp\notin\mathcal Z, както трябваше.
Отвори задачатаMathNetISL 2022 A6Условие — източник

Задача A7

Пълен запис
Условие
За положително цяло число nn нека s(n)s(n) означава сумата от цифрите на nn. НекаP(x)=xn+an−1xn−1+⋯+a1x+a0P(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0е полином, където n≥2n\ge2 и aia_i е положително цяло число за всяко 0≤i≤n−10\le i\le n-1. Възможно ли е за всяко положително цяло число kk числата s(k)s(k) и s(P(k))s(P(k)) да имат една и съща четност?
РешениеОтговорът е не: за всеки такъв полином съществува положително цяло число kk, за което s(k)s(k) и s(P(k))s(P(k)) са с различна четност. Пишем an=1a_n=1. Избираме положително цяло число tt толкова голямо, че10t>10^t\gt{}max⁡{100n−1an−1(101/(n−1)−91/(n−1))n−1,an−19 10n−1,an−19(10an−1)n−1,…,an−19(10a0)n−1}.\max\left\{\frac{100^{n-1}a_{n-1}}{\left(10^{1/(n-1)}-9^{1/(n-1)}\right)^{n-1}},\frac{a_{n-1}}9\,10^{n-1},\frac{a_{n-1}}9(10a_{n-1})^{n-1},\ldots,\frac{a_{n-1}}9(10a_0)^{n-1}\right\}.Тогава интервалътI=I=[(9an−110t)1/(n−1),(1an−110t+1)1/(n−1))\left[\left(\frac9{a_{n-1}}10^t\right)^{1/(n-1)},\left(\frac1{a_{n-1}}10^{t+1}\right)^{1/(n-1)}\right)съдържа поне 100100 последователни положителни цели числа. Избираме X∈IX\in I с X≡1(mod100)X\equiv1\pmod{100}. От избора на II имаме9⋅10t≤an−1Xn−1<10t+1,9\cdot10^t\le a_{n-1}X^{n-1}\lt{}10^{t+1},така че първата цифра на an−1Xn−1a_{n-1}X^{n-1} е 99. От останалите условия за tt следва 10ai<X10a_i\lt{}X за всички i=0,1,…,n−1i=0,1,\ldots,n-1. Следователно числатаa0,a1X,…,anXna_0,a_1X,\ldots,a_nX^nса строго растящи и броят на цифрите им също строго расте. Нека α\alpha е броят на цифрите на an−1Xn−1a_{n-1}X^{n-1}, тоест10α−1≤an−1Xn−1<10α.10^{\alpha-1}\le a_{n-1}X^{n-1}\lt{}10^\alpha.Ще сравним P(10αX)P(10^\alpha X) и P(10α−1X)P(10^{\alpha-1}X). Забележете, чеs(10αX)=s(10α−1X)=s(X).s(10^\alpha X)=s(10^{\alpha-1}X)=s(X).При пресмятането наP(10αX)=P(10^\alpha X)=10αnXn+an−110α(n−1)Xn−1+⋯+a010^{\alpha n}X^n+a_{n-1}10^{\alpha(n-1)}X^{n-1}+\cdots+a_0отделните блокове от цифри не се застъпват и няма пренос, защото10α(i+1)>10αian−1Xn−1>10αiaiXi.10^{\alpha(i+1)}\gt{}10^{\alpha i}a_{n-1}X^{n-1}\gt{}10^{\alpha i}a_iX^i.Затоваs(P(10αX))=s(P(10^\alpha X))=s(Xn)+s(an−1Xn−1)+⋯+s(a0).(1)s(X^n)+s(a_{n-1}X^{n-1})+\cdots+s(a_0).\tag{1}Сега разглеждамеP(10α−1X)=P(10^{\alpha-1}X)=10(α−1)nXn10^{(\alpha-1)n}X^n+an−110(α−1)(n−1)Xn−1+⋯+a0.+a_{n-1}10^{(\alpha-1)(n-1)}X^{n-1}+\cdots+a_0.За i<n−1i\lt{}n-1 блоковете отново не се застъпват. Освен това числото10(α−1)(n−1)an−1Xn−110^{(\alpha-1)(n-1)}a_{n-1}X^{n-1}има точно (α−1)n+1(\alpha-1)n+1 цифри и първата му цифра е 99. От друга страна, понеже X≡1(mod100)X\equiv1\pmod{100}, числото 10(α−1)nXn10^{(\alpha-1)n}X^n има в края точно (α−1)n(\alpha-1)n нули, а непосредствено преди тях стоят цифрите 0101. При събирането съответните цифри 99 и 11 се превръщат в 00, създават един пренос към предишната нула, която става 11, и останалите цифри не се променят. Следователноs(P(10α−1X))=s(P(10^{\alpha-1}X))=s(Xn)+s(an−1Xn−1)+⋯+s(a0)−9=s(X^n)+s(a_{n-1}X^{n-1})+\cdots+s(a_0)-9=s(P(10αX))−9.s(P(10^\alpha X))-9.Двете суми на цифрите имат различна четност, докато входовете 10αX10^\alpha X и 10α−1X10^{\alpha-1}X имат една и съща сума на цифрите. Това доказва твърдението.
Отвори задачатаMathNetISL 2022 A7Условие — източник

Задача A8

Пълен запис
Условие
За положително цяло число nn наричаме nn-редица всяка редица (a0,…,an)(a_0,\ldots,a_n) от неотрицателни цели числа със следното свойство: ако ii и jj са неотрицателни цели числа с i+j≤ni+j\le n, то ai+aj≤na_i+a_j\le n иaai+aj=ai+j.a_{a_i+a_j}=a_{i+j}.Нека f(n)f(n) е броят на nn-редиците. Докажете, че съществуват положителни реални константи c1,c2c_1,c_2 и λ\lambda, за коитоc1λn<f(n)<c2λnc_1\lambda^n\lt{}f(n)\lt{}c_2\lambda^nза всички положителни цели числа nn.
РешениеЩе докажем твърдението сλ=31/6.\lambda=3^{1/6}.Идеята е да класифицираме всички nn-редици. Нека k=⌊n/2⌋k=\lfloor n/2\rfloor. Ще наричаме редицата голяма, ако някой неин член е по-голям от kk, и малка в противния случай. Тъждествената редица ai=ia_i=i се брои отделно; по-долу разглеждаме нетъждествена редица. Първо ни трябват няколко прости факта. Ако ar=asa_r=a_s и r,s<nr,s\lt{}n, тогаваar+1=aar+a1=aas+a1=as+1.(1)a_{r+1}=a_{a_r+a_1}=a_{a_s+a_1}=a_{s+1}.\tag{1}Ако i≤ki\le k, то i+i≤ni+i\le n, следователно 2ai≤n2a_i\le n и ai≤ka_i\le k. Освен това в нетъждествена редица има различни индекси r,sr,s с ar=asa_r=a_s: ако a0≠0a_0\ne0, тогава a2a0=a0a_{2a_0}=a_0, а ако a0=0a_0=0, то aai=aia_{a_i}=a_i за всяко ii и вземаме индекс с ai≠ia_i\ne i. Нека rr е най-малкият индекс, за който as=ara_s=a_r за някое s>rs\gt{}r, а dd е най-малкото положително число с ar+d=ara_{r+d}=a_r. От (1) следва, че опашката(ar,ar+1,…,an)(a_r,a_{r+1},\ldots,a_n)е периодична с минимален период dd: за u<vu\lt{}v имаме au=ava_u=a_v точно когато u,v≥ru,v\ge r и d∣v−ud\mid v-u. Освен това ai=ia_i=i за i<ri\lt{}r и ai≥ra_i\ge r за i≥ri\ge r. Ще казваме, че редицата има отместване rr и период dd. От равенството aai+a0=aia_{a_i+a_0}=a_i и минималността на периода следваd∣ai−i+a0за всички i.d\mid a_i-i+a_0\qquad\text{за всички }i.При i=0i=0 получаваме d∣2a0d\mid2a_0. Затова има две възможности:d∣ai−iза всички i,d\mid a_i-i\quad\text{за всички }i,или r=0r=0, dd е четно иd∣ai−i−d2за всички i.(2)d\mid a_i-i-\frac d2\quad\text{за всички }i.\tag{2}Във втория случай редицата е малка. Наистина, ако d≤k+1d\le k+1, периодът вече се състои от членове, не по-големи от kk. Ако d>k+1d\gt{}k+1, то от (2) имаме ad/2=0a_{d/2}=0, а след това индукция по ii дава ai≤ka_i\le k за всички ii. Ако редицата е малка, тогава r+d≤k+1r+d\le k+1: сред a0,a1,…,ak+1a_0,a_1,\ldots,a_{k+1} има повторение, а минималният период започва при rr. Ако редицата е голяма, тогава r+d>k+1r+d\gt{}k+1, и всъщностai=i(0≤i<r+d).a_i=i\qquad(0\le i\lt{}r+d).Наистина, периодът съдържа член, по-голям от kk, затова r+d−1>kr+d-1\gt{}k. В големия случай важи d∣ai−id\mid a_i-i; за r≤i≤kr\le i\le k това принуждава ai=ia_i=i, а за k<i<r+dk\lt{}i\lt{}r+d същото се довършва с индукция, понеже ai+(n−i)=ai+an−i≤na_i+(n-i)=a_i+a_{n-i}\le n. Така големите редици се определят само от двойката (r,d)(r,d) с0≤r<n,d≥1,k+1<r+d≤n,0\le r\lt{}n,\qquad d\ge1,\qquad k+1\lt{}r+d\le n,и броят им е(n−k−1)(n+k+2)2.\frac{(n-k-1)(n+k+2)}2.За малките редици при дадени r,dr,d трябва да изберем периода (ar,…,ar+d−1)(a_r,\ldots,a_{r+d-1}), катоr≤aj≤k,d∣aj−j.r\le a_j\le k,\qquad d\mid a_j-j.Ако дефинирамеg(x,d)=(p+1)qpd−q,p=⌊xd⌋,q=x−dp,g(x,d)=(p+1)^q p^{d-q},\qquad p=\left\lfloor\frac xd\right\rfloor,\quad q=x-dp,то броят на тези избори е g(k+1−r,d)g(k+1-r,d). Във втория случай от (2), когато dd е четно и r=0r=0, има още g(k+1,d)g(k+1,d) избора. Следователноf(n)=f(n)=1+(n−k−1)(n+k+2)21+\frac{(n-k-1)(n+k+2)}2+∑d′=1⌊(k+1)/2⌋g(k+1,2d′)+\sum_{d'=1}^{\lfloor(k+1)/2\rfloor}g(k+1,2d')+∑r=0k∑d=1k+1−rg(k+1−r,d).(3)+\sum_{r=0}^k\sum_{d=1}^{k+1-r}g(k+1-r,d).\tag{3}За достатъчно големи nn от (3) получаваме долна оценка:f(n)>g(k+1,⌊k+13⌋)≥3⌊(k+1)/3⌋.f(n)\gt{}g\left(k+1,\left\lfloor\frac{k+1}{3}\right\rfloor\right)\ge3^{\lfloor(k+1)/3\rfloor}.След евентуално намаляване на константата и покриване на крайно много малки стойности това дава f(n)>c1(31/6)nf(n)\gt{}c_1(3^{1/6})^n за всички nn. За горната оценка е достатъчно да използваме следната лема: съществува константа c3c_3, такава че за всяко положително цяло xx е изпълнено∑d=1xg(x,d)≤c33x/3.(4)\sum_{d=1}^x g(x,d)\le c_3 3^{x/3}.\tag{4}Лемата следва от оценкитеg(x,d)≤{3x/3(6481)x/3−d,d≤x/3,3x/3(89)d−x/3,d≥x/3.g(x,d)\le\begin{cases}3^{x/3}\left(\frac{64}{81}\right)^{x/3-d},&d\le x/3,\\[2mm]3^{x/3}\left(\frac89\right)^{d-x/3},&d\ge x/3. \end{cases}Те се доказват така. Функцията g(x,d)g(x,d) е максималното произведение на dd положителни цели числа със сума xx, а g(tx,td)=g(x,d)tg(tx,td)=g(x,d)^t. Ако 2d≤x≤3d2d\le x\le3d, тогава g(x,d)=23d−x3x−2dg(x,d)=2^{3d-x}3^{x-2d}; ако 3d≤x≤4d3d\le x\le4d, тогава g(x,d)=34d−x4x−3dg(x,d)=3^{4d-x}4^{x-3d}. От тези формули, приложени към подходящо разширени двойки, се получават двете показани геометрични оценки, а те сумират до (4). Сега (3) и (4) дават∑r=0k∑d=1k+1−rg(k+1−r,d)≤\sum_{r=0}^k\sum_{d=1}^{k+1-r}g(k+1-r,d)\lec3∑r=0k3(k+1−r)/3≤C43(k+1)/3, c_3\sum_{r=0}^k3^{(k+1-r)/3}\le C_4 3^{(k+1)/3},а допълнителната сума с четни периоди също е най-много c33(k+1)/3c_3 3^{(k+1)/3}. Броят на големите редици е само квадратичен по nn, следователно е ограничен от C53n/6C_5 3^{n/6} за подходяща абсолютна константа C5C_5. Понеже k≤n/2k\le n/2, оттук получавамеf(n)<c2(31/6)nf(n)\lt{}c_2(3^{1/6})^nза подходяща положителна константа c2c_2. Това завършва доказателството.
Отвори задачатаMathNetISL 2022 A8Условие — източник

Задача C1

Пълен запис
Условие
Една ±1\pm1-редица е редица от 20222022 числа a1,…,a2022a_1,\ldots,a_{2022}, всяко от които е равно на +1+1 или на −1-1. Да се намери най-голямото число CC със следното свойство: за всяка ±1\pm1-редица съществуват цяло число kk и индекси1≤t1<⋯<tk≤2022,1\le t_1\lt{}\cdots\lt{}t_k\le2022,такива че ti+1−ti≤2t_{i+1}-t_i\le2 за всички ii, и∣∑i=1kati∣≥C.\left|\sum_{i=1}^k a_{t_i}\right|\ge C.
РешениеОтговорът еC=506.C=506.Първо ще докажем, че такава стойност винаги може да се постигне. Без ограничение поне 10111011 от членовете са равни на +1+1; иначе умножаваме всички членове по −1-1 и накрая вземаме абсолютна стойност. Избираме подпоследователност отляво надясно по следното правило. Всеки член +1+1 включваме. Член −1-1 пропускаме, ако предишният член вече е включен; ако това не е възможно, включваме го. Така разликата между два съседни избрани индекса никога не надминава 22. Подпоследователността съдържа всички членове +1+1. Освен това на всеки включен член −1-1 съответства пропуснат член −1-1, затова включените отрицателни членове са най-много⌊10112⌋=505.\left\lfloor\frac{1011}{2}\right\rfloor=505.Следователно сумата на избраните членове е поне 1011−505=5061011-505=506. Остава да покажем, че по-голяма стойност не е възможна. Разглеждаме редицата, разделена на блокове{−1},{+1,+1},{−1,−1},{+1,+1},\{-1\},\{+1,+1\},\{-1,-1\},\{+1,+1\},…,{+1,+1},{−1,−1},{+1}.\ldots,\{+1,+1\},\{-1,-1\},\{+1\}.Има общо 10121012 блока: 506506 положителни и 506506 отрицателни. Двата крайни блока са едночленни, а всички останали са двучленни. Нека допустима подпоследователност среща kk положителни блока. Между всеки два срещнати положителни блока има отрицателен блок, от който трябва да бъде избран поне един член; иначе между два последователни избрани индекса би имало разлика по-голяма от 22. От всеки положителен блок могат да се вземат най-много два члена, следователно сумата е най-много2k−(k−1)=k+1.2k-(k-1)=k+1.Ако k<506k\lt{}506, това е най-много 506506. Ако k=506k=506, един от срещнатите положителни блокове е последният, който има само един член, и тогава горната граница е k=506k=506. Така за всяка допустима подпоследователност сумата е най-много 506506. Същият аргумент, приложен със сменени знаци, дава и долна граница −506-506. Следователно абсолютната стойност не може винаги да бъде по-голяма от 506506, което завършва доказателството.
Отвори задачатаMathNetISL 2022 C1Условие — източник

Задача C2

Пълен запис
Условие
Банката на Осло издава монети от два вида метал: алуминий, означен с AA, и мед, означена с CC. Морган има nn алуминиеви и nn медни монети и подрежда своите 2n2n монети в редица в произволен начален ред. За фиксирано положително цяло число k≤2nk\le2n тя повтаря следната операция: намира най-дългия блок от последователни монети от един и същ метал, който съдържа kk-тата монета отляво, и премества всички монети от този блок в левия край на редицата. Например при n=4n=4 и k=4k=4 процесът от конфигурацията AACCCACAAACCCACA еAACCCACA→CCCAAACA→AAACCCCA→CCCCAAAA→⋯ .AACCCACA\to CCCAAACA\to AAACCCCA\to CCCCAAAA\to\cdots.Да се намерят всички двойки (n,k)(n,k) с 1≤k≤2n1\le k\le2n, за които при всяка начална конфигурация в някакъв момент най-много една алуминиева монета ще бъде съседна на медна монета.
РешениеОтговорът е: всички двойки (n,k)(n,k), за коитоn≤k≤3n+12.n\le k\le\frac{3n+1}{2}.Ще наричаме блок максимална последователност от монети от един и същ метал. Нека MbM^b означава блок от bb монети от метал MM. Условието най-много една алуминиева монета да е съседна на медна е равносилно на това конфигурацията да има точно два блока: всички AA-монети и всички CC-монети. Първо доказваме необходимост. Ако k<nk\lt{}n, конфигурациятаAn−1Cn−1ACA^{n-1}C^{n-1}ACостава непроменена при операцията и винаги има четири блока. Акоk>3n+12,k\gt{}\frac{3n+1}{2},полагаме a=k−n−1a=k-n-1 и b=2n−k+1b=2n-k+1. Тогава k>2a+bk\gt{}2a+b и k>2b+ak\gt{}2b+a, затова конфигурацията AaCbAbCaA^aC^bA^bC^a се движи циклично:AaCbAbCa→CaAaCbAb→AbCaAaCb→CbAbCaAa→AaCbAbCa→⋯ .A^aC^bA^bC^a\to C^aA^aC^bA^b\to A^bC^aA^aC^b\to C^bA^bC^aA^a\to A^aC^bA^bC^a\to\cdots.Тя също винаги има четири блока. Следователно трябва n≤k≤(3n+1)/2n\le k\le(3n+1)/2. Сега доказваме достатъчност. Броят на блоковете не може да се увеличава. Ще покажем, че ако блоковете са повече от два, след краен брой операции броят им намалява. Нека текущата конфигурация има c≥3c\ge3 блока. Понеже k≥nk\ge n, левият блок не може да бъде преместен, освен ако вече всички монети от единия метал са в него; тогава блоковете са само два. Ако бъде преместен блок, който не е нито ляв, нито десен, двата му съседни блока се сливат и броят на блоковете намалява. Значи единственият начин броят на блоковете да не намалее на следващата стъпка е да бъде преместен десният блок. Ако cc е нечетно, левият и десният блок са от един и същ метал, така че и тогава след преместването има сливане. Остава случаят, в който c≥4c\ge4 е четно. Да допуснем, че от някакъв момент нататък винаги се мести десният блок. Нека размерите на блоковете в една такава конфигурация са a1,a2,…,aca_1,a_2,\ldots,a_c. За да бъде местен десният блок при всяка от циклично получаваните конфигурации, трябваk≥2n+1−ai(i=1,2,…,c).k\ge2n+1-a_i\qquad(i=1,2,\ldots,c).Сумирайки, получавамеck≥2cn+c−∑i=1cai=2cn+c−2n,ck\ge 2cn+c-\sum_{i=1}^c a_i=2cn+c-2n,т.е.k≥2n+1−2nc≥3n2+1,k\ge2n+1-\frac{2n}{c}\ge \frac{3n}{2}+1,понеже c≥4c\ge4. Това противоречи на k≤(3n+1)/2k\le(3n+1)/2. Следователно рано или късно десният блок няма да бъде преместен и броят на блоковете ще намалее. Повтаряйки аргумента, стигаме до два блока, както трябва.
Отвори задачатаMathNetISL 2022 C2Условие — източник

Задача C3

Пълен запис
Условие
Във всяка клетка на градина с форма на дъска 2022×20222022\times2022 първоначално има дърво с височина 00. Градинар и дървар играят следната игра, като градинарят е пръв: - Градинарят избира клетка от градината. Дървото в тази клетка и всички дървета в съседните околни клетки, най-много осем, порастват с една единица. - След това дърварят избира четири различни клетки на дъската. Всяко дърво с положителна височина в тези клетки се смалява с една единица. Дърво ще наричаме величествено, ако височината му е поне 10610^6. Да се намери най-голямото число KK, за което градинарят може да гарантира, че някога ще има KK величествени дървета, независимо как играе дърварят.
РешениеОтговорът еK=5⋅202229=2271380.K=\frac{5\cdot2022^2}{9}=2271380.По-общо ще докажем, че за дъска 3N×3N3N\times3N отговорът е 5N25N^2. Първо даваме стратегия за дърваря, която не допуска повече от 5N25N^2 величествени дървета. Номерираме редовете и стълбовете с 1,2,…,3N1,2,\ldots,3N и оцветяваме клетките, за които поне една от двете координати се дели на 33. Във всеки квадрат 3×33\times3 има точно 55 оцветени и 44 неоцветени клетки; на края на дъската неоцветените в околността са още по-малко. След всеки ход на градинаря дърварят избира всички неоцветени клетки, в които току-що е имало растеж, и намалява тези дървета. Така след всеки негов ход никое неоцветено дърво няма положителна височина. Следователно величествени могат да бъдат само оцветените дървета, а те са 5N25N^2. Остава да покажем, че градинарят може да постигне 5N25N^2 величествени дървета. Ще докажем това дори в по-трудна за него игра. В нея след хода на градинаря дърварят може да намали с 11 всички дървета извън току-що порасналата околност, както и произволни четири от дърветата в тази околност. Ако градинарят успее в тази по-силна игра, успява и в първоначалната. НекаM=(95).M=\binom95.В по-силната игра, когато градинарят избере квадрат 3×33\times3, дърварят фактически избира една от MM възможни петорки клетки в него: дърветата в тази петорка нарастват с 11, останалите дървета в квадрата остават без промяна, а всички дървета извън квадрата намаляват с 11. Ако градинарят избере един и същ квадрат MlMl пъти, по принципа на Дирихле някоя петорка ще бъде избрана от дърваря най-малко ll пъти, така че пет дървета в този квадрат ще са получили поне ll нараствания от тези ходове. Градинарят разделя дъската на N2N^2 непресичащи се квадрата 3×33\times3 и ги номерира с 0,1,…,N2−10,1,\ldots,N^2-1. После, заb=N2−1,N2−2,…,0,b=N^2-1,N^2-2,\ldots,0,той играе върху квадрат номер bb точно106M(M+1)b10^6M(M+1)^bпъти. Докато играе върху този квадрат, някоя петорка дървета в него нараства поне 106(M+1)b10^6(M+1)^b пъти. След това всички по-късни ходове са върху квадрати с по-малки номера, а броят им е106M((M+1)b−1+(M+1)b−2+⋯+1)=10^6M\left((M+1)^{b-1}+(M+1)^{b-2}+\cdots+1\right)=106((M+1)b−1).10^6\left((M+1)^b-1\right).Следователно всяко от тези пет дървета в квадрат номер bb завършва с височина поне106(M+1)b−106((M+1)b−1)=106.10^6(M+1)^b-10^6\left((M+1)^b-1\right)=10^6.Така във всеки от N2N^2-те квадрата има поне пет величествени дървета, общо 5N25N^2. За 2022=3⋅6742022=3\cdot674 това дава 5⋅6742=22713805\cdot674^2=2271380.
Отвори задачатаMathNetISL 2022 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека n>3n\gt{}3 е положително цяло число. Да предположим, че nn деца са подредени в кръг и между тях са разпределени nn монети, като някои деца може да нямат монети. На всяка стъпка дете с поне 22 монети може да даде по 11 монета на двамата си непосредствени съседи. Да се определят всички начални разпределения на монетите, от които е възможно след краен брой стъпки всяко дете да има точно една монета.
РешениеНомерираме децата с 1,2,…,n1,2,\ldots,n по кръга и нека cic_i е началният брой монети на ii-тото дете. Отговорът е: точно онези разпределения, за които∑i=1nici≡n(n+1)2(modn).\sum_{i=1}^n i c_i\equiv \frac{n(n+1)}2\pmod n.Една стъпка намалява някое cic_i с 22 и увеличава ci−1c_{i-1} и ci+1c_{i+1} с 11, като индексите се разглеждат по модул nn. Понеже(i−1)−2i+(i+1)=0,(i-1)-2i+(i+1)=0,величината ∑ici\sum i c_i по модул nn е инвариант. В крайната равномерна конфигурация тя е 1+2+⋯+n=n(n+1)/21+2+\cdots+n=n(n+1)/2, така че условието е необходимо. Ще докажем, че е и достатъчно. Първо, без да караме дете nn да прави ход, извършваме ход от всяко друго дете, което има повече от една монета, докато това е възможно. Този процес спира: например сумата ∑i=1ni2ci\sum_{i=1}^n i^2c_i се увеличава с положително цяло число при всеки такъв ход и е ограничена отгоре, защото общият брой монети е nn. Получаваме състояние(z1,z2,…,zn−1,M),(z_1,z_2,\ldots,z_{n-1},M),където всяко ziz_i е 00 или 11. Ще наричаме такова състояние полуравномерно, а MM - негова неправилност. Ще използваме следната лема за пренасяне през поредица от единици. Ако по някоя дъга на кръга монетите саa,1,…,1⏟k,b,1,…,1⏟k,ca,\underbrace{1,\ldots,1}_{k},b,\underbrace{1,\ldots,1}_{k},cи b≥2b\ge2, то с краен брой разрешени ходове можем да стигнем доa+1,1,…,1⏟k,b−2,1,…,1⏟k,c+1.a+1,\underbrace{1,\ldots,1}_{k},b-2,\underbrace{1,\ldots,1}_{k},c+1.За k=0k=0 това е точно един ход. За k=1k=1 първо ходи средното дете с bb монети, после двамата му съседи, после отново средното дете. За k≥2k\ge2 ходи детето с bb монети, после двамата му съседи; получава сеa,1,…,1⏟k−2,2,0,b,0,2,1,…,1⏟k−2,c.a,\underbrace{1,\ldots,1}_{k-2},2,0,b,0,2,\underbrace{1,\ldots,1}_{k-2},c.След това двете двойки монети се придвижват навън през единиците, докато се получиa+1,0,1,…,1⏟k−2,b,1,…,1⏟k−2,0,c+1,a+1,0,\underbrace{1,\ldots,1}_{k-2},b,\underbrace{1,\ldots,1}_{k-2},0,c+1,и прилагаме индукционното предположение към централната част. Това доказва лемата. Сега ще покажем, че от всяко полуравномерно състояние можем да стигнем до полуравномерно състояние с неправилност най-много 22. Ако M>3M\gt{}3, сред останалите n−1n-1 деца има поне две деца без монети. Избираме двете нули, най-близки до детето с MM монети от двете страни. Между тях дъгата има вид0,1,…,1⏟a,M,1,…,1⏟b,0.0,\underbrace{1,\ldots,1}_{a},M,\underbrace{1,\ldots,1}_{b},0.Ако a=ba=b, лемата веднага пренася по една монета от MM към двете нули и намалява MM. Ако, да речем, a>ba\gt{}b, прилагаме лемата симетрично на разстояние b+1b+1 от MM и получаваме част от вида0,1,…,1⏟a−b−1,2,1,…,1⏟b,M−2.0,\underbrace{1,\ldots,1}_{a-b-1},2,\underbrace{1,\ldots,1}_{b},M-2.Детето с 22 монети вече се използва по същата лема: то или запълва лявата нула, или прехвърля една монета към детето с M−2M-2 монети и създава по-къса дъга със същия вид. Дължината на разглежданата дъга строго намалява, така че след краен брой повторения неправилността намалява с 11 или с 22. Повтаряйки, стигаме до полуравномерно състояние с M≤2M\le2. Ако M=1M=1, всички деца имат по една монета и сме готови. Случаят M=0M=0 е невъзможен, защото общият брой монети е nn. Остава M=2M=2. Тогава точно едно от първите n−1n-1 деца, да го означим с kk, няма монета, всички останали имат по една, а детето nn има две. За това състояние∑i=1nici=n(n+1)2−k(modn).\sum_{i=1}^n i c_i=\frac{n(n+1)}2-k\pmod n.Но инвариантът трябва да е равен на n(n+1)/2n(n+1)/2 по модул nn, следователно k≡0(modn)k\equiv0\pmod n, което е невъзможно за 1≤k≤n−11\le k\le n-1. Значи случаят M=2M=2 не може да възникне при начално разпределение, удовлетворяващо условието. Следователно всяко такова разпределение може да бъде доведено до равномерното.
Отвори задачатаMathNetISL 2022 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека m,n≥2m,n\ge2 са цели числа, нека XX е множество с nn елемента и нека X1,X2,…,XmX_1,X_2,\ldots,X_m са по двойки различни непразни, не непременно непресичащи се, подмножества на XX. Функцияf:X→{1,2,…,n+1}f:X\to\{1,2,\ldots,n+1\}се нарича хубава, ако съществува индекс kk, такъв че∑x∈Xkf(x)>∑x∈Xif(x)за всички i≠k.\sum_{x\in X_k} f(x)\gt{}\sum_{x\in X_i} f(x)\qquad\text{за всички }i\ne k.Да се докаже, че броят на хубавите функции е поне nnn^n.
РешениеЗа подмножество Y⊆XY\subseteq X ще пишемf(Y)=∑y∈Yf(y).f(Y)=\sum_{y\in Y}f(y).Една функция f:X→{1,2,…,n+1}f:X\to\{1,2,\ldots,n+1\} е хубава точно когато максимумът сред числата f(Xi)f(X_i) се достига за единствен индекс. Разглеждаме множеството F\mathcal F от всички функцииf:X→{1,2,…,n}.f:X\to\{1,2,\ldots,n\}.То има nnn^n елемента. За всяка такава функция избираме индекс ll, за който f(Xl)f(X_l) е максимално, и построяваме функция f+:X→{1,2,…,n+1}f^+:X\to\{1,2,\ldots,n+1\} чрезf+(x)={f(x)+1,x∈Xl,f(x),x∉Xl.f^+(x)=\begin{cases}f(x)+1,&x\in X_l,\\ f(x),&x\notin X_l.\end{cases}Твърдим, че f+f^+ е хубава и че единственият максимизиращ индекс е ll. Нека j≠lj\ne l. Включването Xl⊆XjX_l\subseteq X_j е невъзможно, защото множествата са различни и тогава f(Xj)>f(Xl)f(X_j)\gt{}f(X_l), против избора на XlX_l. Следователно∣Xl∣>∣Xj∩Xl∣.|X_l|\gt{}|X_j\cap X_l|.Сегаf+(Xl)=f(Xl)+∣Xl∣≥f(Xj)+∣Xl∣>f^+(X_l)=f(X_l)+|X_l|\ge f(X_j)+|X_l|\gt{}f(Xj)+∣Xj∩Xl∣=f+(Xj).f(X_j)+|X_j\cap X_l|=f^+(X_j).Това доказва твърдението. Накрая виждаме, че от f+f^+ можем еднозначно да възстановим ff: първо намираме единствения индекс ll, за който f+(Xl)f^+(X_l) е максимално, а после намаляваме с 11 стойностите на f+f^+ върху XlX_l. Значи различните функции от F\mathcal F дават различни хубави функции. Следователно хубавите функции са поне ∣F∣=nn|\mathcal F|=n^n.
Отвори задачатаMathNetISL 2022 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека nn е положително цяло число. Започваме с nn купчинки камъчета, всяка от които първоначално съдържа по едно камъче. Разрешен е следният ход: избират се две купчинки, взема се равен брой камъчета от всяка от тях и от взетите камъчета се образува нова купчинка. За всяко положително цяло число nn да се намери най-малкият възможен брой непразни купчинки, който може да се получи след краен брой такива ходове.
РешениеОтговорът е 11, ако nn е степен на 22, и 22 във всички останали случаи. Ако n=2kn=2^k, можем последователно да обединяваме равни купчинки:2k купчинки по 1→2k−1 купчинки по 2→⋯→1 купчинка от 2k.2^k\text{ купчинки по }1\to 2^{k-1}\text{ купчинки по }2\to\cdots\to 1\text{ купчинка от }2^k.Нека сега nn не е степен на 22. Избираме NN така, че2N<n<2N+1,2^N\lt{}n\lt{}2^{N+1},и полагаме m=n−2Nm=n-2^N. Първо от 2N2^N единични купчинки правим една голяма купчинка от 2N2^N камъчета. Остават mm единични купчинки. Избираме една от тях и заедно с едно камъче от голямата купчинка образуваме купчинка от 22 камъчета. После, докато голямата купчинка стане с размер mm, вземаме по едно камъче от нея и по едно от текущата купчинка с 22 камъчета, образувайки нова купчинка с 22 камъчета. В края имаме една купчинка от mm камъчета, една купчинка от 22 камъчета и 2N−22^N-2 единични купчинки. Сдвояваме единичните купчинки в купчинки от 22 камъчета; така получаваме 2N−12^{N-1} купчинки от 22 камъчета, които могат да се обединят в една купчинка от 2N2^N камъчета. Остават точно две непразни купчинки. Остава да докажем, че една купчинка е невъзможна, когато nn не е степен на 22. Нека d>1d\gt{}1 е нечетен делител на nn. Разглеждаме един ход, при който от купчинки с размери aa и bb се вземат по cc камъчета и се образува нова купчинка с 2c2c камъчета. Ако след хода всички размери на купчинки се делят на dd, то d∣2cd\mid 2c, d∣a−cd\mid a-c и d∣b−cd\mid b-c. Понеже dd е нечетно, следва d∣cd\mid c, а оттук d∣ad\mid a и d∣bd\mid b. Значи ако след ход всички купчинки се делят на dd, то същото е било вярно и преди хода. Ако можехме да стигнем до една купчинка от nn камъчета, в крайното състояние всички купчинки биха имали размер, делящ се на dd. Връщайки ходовете назад с горното наблюдение, началните единични купчинки също трябваше да се делят на dd, невъзможно. Следователно минимумът е 22.
Отвори задачатаMathNetISL 2022 C6Условие — източник

Задача C7

Пълен запис
Условие
Люси започва, като записва ss целочислени 20222022-торки на дъската. След това тя може да вземе произволни две, не непременно различни, вече записани 20222022-торкиv=(v1,…,v2022)иw=(w1,…,w2022)v=(v_1,\ldots,v_{2022})\quad\text{и}\quad w=(w_1,\ldots,w_{2022})и да приложи една от операциитеv+w=(v1+w1,…,v2022+w2022),v+w=(v_1+w_1,\ldots,v_{2022}+w_{2022}),v∨w=(max⁡(v1,w1),…,max⁡(v2022,w2022)),v\vee w=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022})),след което записва получената 20222022-торка на дъската. Оказва се, че по този начин Люси може след краен брой стъпки да запише всяка целочислена 20222022-торка. Кое е най-малкото възможно число ss на първоначално записаните 20222022-торки?
РешениеОтговорът еs=3.s=3.Ще докажем по-общо, че за nn-торки при всяко n≥3n\ge3 отговорът е 33. Първо показваме, че три начални nn-торки стигат. Нека eje_j е nn-торката с 11 на jj-тата координата и 00 навсякъде другаде, а нека cc е константната nn-торкаc=(−1,−1,…,−1).c=(-1,-1,\ldots,-1).Ако Люси може да получи e1,…,ene_1,\ldots,e_n и cc, то може да получи всяка целочислена nn-торка vv: избира kk така, че k+vi>0k+v_i\gt{}0 за всички ii, и записваkc+(k+v1)e1+⋯+(k+vn)en=v.kc+(k+v_1)e_1+\cdots+(k+v_n)e_n=v.Нека началните три nn-торки са a,b,ca,b,c, къдетоai=−i2,bi=i,ci=−1(1≤i≤n).a_i=-i^2,\qquad b_i=i,\qquad c_i=-1\quad(1\le i\le n).За всяко jj Люси може чрез събиране да получиdj=2a+4jb+(2j2−1)c.d_j=2a+4jb+(2j^2-1)c.Неговата ii-та координата е(dj)i=−2i2+4ij−(2j2−1)=1−2(i−j)2.(d_j)_i=-2i^2+4ij-(2j^2-1)=1-2(i-j)^2.Тя е 11 при i=ji=j и е най-много −1-1 иначе. Следователноd1∨d2∨⋯∨dn=(1,1,…,1).d_1\vee d_2\vee\cdots\vee d_n=(1,1,\ldots,1).Оттук Люси получава нулевата nn-торка като (1,…,1)+c(1,\ldots,1)+c, а послеej=dj∨(0,…,0).e_j=d_j\vee(0,\ldots,0).Както видяхме, това е достатъчно за всички целочислени nn-торки. Остава да докажем, че две начални nn-торки не стигат. Ще използваме наблюдение. Нека λ≥0\lambda\ge0 и две nn-торки v,wv,w удовлетворяватvj≥λvk,wj≥λwkv_j\ge \lambda v_k,\qquad w_j\ge \lambda w_kза някои координати j,kj,k. Тогава същите неравенства се запазват и за v+wv+w, и за v∨wv\vee w. За сумата това е непосредствено. За максимума m=v∨wm=v\vee w имаме mj≥vj≥λvkm_j\ge v_j\ge\lambda v_k и mj≥wj≥λwkm_j\ge w_j\ge\lambda w_k, а mkm_k е едно от числата vk,wkv_k,w_k. Следователно ако двете начални nn-торки удовлетворяват едно такова неравенство, всички получени nn-торки също го удовлетворяват и не могат да бъдат всички целочислени nn-торки. Да допуснем, че началните са само vv и ww. Ако за някоя координата ii числата viv_i и wiw_i са едновременно неотрицателни, или едновременно неположителни, то знакът на тази координата никога не може да се промени в другата посока; пак не могат да се получат всички nn-торки. Значи за всяко ii числата viv_i и wiw_i имат противоположни знаци. Понеже n≥3n\ge3, има две координати j≠kj\ne k, за които vjv_j и vkv_k имат един и същ знак, а също wjw_j и wkw_k имат един и същ знак. Без ограничение нека vj,vk>0v_j,v_k\gt{}0 и wj,wk<0w_j,w_k\lt{}0. Полагаме λ=vj/vk>0\lambda=v_j/v_k\gt{}0. Ако wj/wk≤λw_j/w_k\le\lambda, понеже wk<0w_k\lt{}0, получаваме wj≥λwkw_j\ge\lambda w_k, и заедно с vj=λvkv_j=\lambda v_k имаме забраняващо неравенство. Ако wj/wk>λw_j/w_k\gt{}\lambda, тогава с μ=1/λ\mu=1/\lambda получавамеvk=μvj,wk≥μwj,v_k=\mu v_j,\qquad w_k\ge \mu w_j,и отново имаме забраняващо неравенство. Противоречие. Следователно са нужни поне три начални nn-торки, а доказателството е завършено.
Отвори задачатаMathNetISL 2022 C7Условие — източник

Задача C8

Пълен запис
Условие
Алиса запълва клетките на дъска n×nn\times n с числата от 11 до n2n^2, като всяко число се използва точно веднъж. След това тя преброява общия брой добри пътища на дъската. Добър път е последователност от клетки с произволна дължина, включително 11, такава че: (i) първата клетка е съседна само на клетки с по-големи числа; (ii) всяка следваща клетка е съседна на предишната; (iii) числата, записани в клетките на последователността, са в нарастващ ред. Две клетки се наричат съседни, ако имат обща страна. Да се намери най-малкият възможен брой добри пътища като функция на nn.
РешениеОтговорът е2n2−2n+1.2n^2-2n+1.Ще наричаме кладенец клетка, която е съседна само на клетки с по-големи числа. На втора дъска BB записваме във всяка клетка броя на добрите пътища, които завършват в съответната клетка на първата дъска AA. Ако клетката е кладенец, в нея завършва точно един добър път - пътят от една клетка. Ако клетката не е кладенец, броят на добрите пътища, завършващи в нея, е сумата от стойностите в BB на съседните клетки с по-малки числа. Следователно, когато запълваме BB по реда на числата в AA, всяка клетка без вече запълнен съсед получава стойност 11, а всяка друга получава сумата от стойностите на вече запълнените си съседи. Има поне един кладенец, именно клетката с числото 11, така че сумата на стойностите в кладенците е поне 11. Сумата на стойностите в некладенците може да се преброи по съседни двойки клетки: на всяка съседна двойка приписваме стойността в BB на клетката с по-малко число. Тогава сборът на приписаните стойности е точно сумата на стойностите в некладенците. Всяка приписана стойност е поне 11, а броят на съседните двойки в дъска n×nn\times n е2n(n−1).2n(n-1).Затова общият брой добри пътища е поне2n(n−1)+1=2n2−2n+1.2n(n-1)+1=2n^2-2n+1.Остава да построим запълване, при което се достига равенство. Достатъчно е да маркираме множество клетки със следните две свойства: немаркираните клетки не са съседни две по две, а графът на маркираните клетки по съседство е дърво. Тогава поставяме най-малките числа в маркираните клетки в ред, който обхожда дървото от корен към листа; всяка маркирана клетка ще има стойност 11 на дъската BB. После поставяме всички останали числа в немаркираните клетки. Понеже няма две съседни немаркирани клетки, при всяка съседна двойка по-малката стойност в BB е 11; понеже маркираните клетки образуват дърво, има точно един кладенец. Така долната граница се достига. Ще дадем текстово построение на такова маркиране. За n=1n=1 маркираме единствената клетка, а за n=2n=2 маркираме три клетки, образуващи L-тромино. Нека n>2n\gt{}2. Пишем координатите като (x,y)(x,y), където 1≤x,y≤n1\le x,y\le n. Ако n≡0,2(mod3)n\equiv0,2\pmod3, полагаме s=2s=2, а ако n≡1(mod3)n\equiv1\pmod3, полагаме s=1s=1. Първо маркираме в първите две колони клетките (1,y)(1,y), за които yy не е от вида 6r+s6r+s, и клетките (2,y)(2,y), за които yy е от вида 6r+s−16r+s-1, 6r+s6r+s или 6r+s+16r+s+1. Това образува свързан път. След това разглеждаме всички клетки от вида (2,6r+s)(2,6r+s) и (1,6r+s+3)(1,6r+s+3), които лежат в дъската. За всяка такава клетка (x,y)(x,y) маркираме всички клетки (u,y)(u,y) с u>xu\gt{}x, както и всички клетки (x+2r,y−1)(x+2r,y-1) и (x+2r,y+1)(x+2r,y+1), когато координатите са в дъската. Проверката е пряка по остатъците на редовете. Всяка добавена част се прикрепя към вече построения път в точно една клетка, така че цикъл не се създава и маркираните клетки остават дърво. Немаркираните клетки са точно от редуващите се форми, оставени между тези хоризонтални и вертикални разклонения; две такива клетки никога не споделят страна. Следователно съществува нужното маркиране за всяко nn, а минималният брой добри пътища е 2n2−2n+12n^2-2n+1.
Отвори задачатаMathNetISL 2022 C8Условие — източник

Задача C9

Пълен запис
Условие
Нека Z≥0\mathbb Z_{\ge0} е множеството на неотрицателните цели числа и некаf:Z≥0×Z≥0→Z≥0f:\mathbb Z_{\ge0}\times\mathbb Z_{\ge0}\to\mathbb Z_{\ge0}е биекция със следното свойство: акоf(x1,y1)>f(x2,y2),f(x_1,y_1)\gt{}f(x_2,y_2),тоf(x1+1,y1)>f(x2+1,y2)f(x_1+1,y_1)\gt{}f(x_2+1,y_2)\quadиf(x1,y1+1)>f(x2,y2+1).\text{и}\quad f(x_1,y_1+1)\gt{}f(x_2,y_2+1).Нека NN е броят на двойките цели числа (x,y)(x,y) с 0≤x,y<1000\le x,y\lt{}100, за които f(x,y)f(x,y) е нечетно. Да се намерят най-малката и най-голямата възможна стойност на NN.
РешениеОтговорът е2500≤N≤7500,2500\le N\le7500,като и двете граници се достигат. Първо описваме функциите ff. Даденото условие всъщност запазва реда при едновременно преместване с (1,0)(1,0) или с (0,1)(0,1) в двете сравнявани точки. За ненулев вектор (k,l)(k,l) с неотрицателни цели координати знакът наf(x+k,y)−f(x,y+l)f(x+k,y)-f(x,y+l)не зависи от (x,y)(x,y). Наричаме (k,l)(k,l) игла, ако този знак е положителен. Иглите и неиглите са затворени относно събиране, а оттук и относно съкращаване на общ множител. Затова за положителни рационални числа има праг α\alpha: числото k/lk/l е над прага точно когато (k,l)(k,l) е игла. От това следва ключовото свойство: акоx1+y1α>x2+y2α,x_1+y_1\alpha\gt{}x_2+y_2\alpha,тоf(x1,y1)>f(x2,y2).f(x_1,y_1)\gt{}f(x_2,y_2).Наистина, ако и двете координати на първата точка са не по-малки, твърдението е ясно; в останалите случаи то е точно определението на прага чрез подходящата разлика на координатите. Ако α\alpha е рационално, равенствата се разрешават с фиксирано правило по една от координатите. За нашия краен квадрат можем леко да преместим α\alpha и да приемем, че α\alpha е ирационално. При ирационално α\alpha имаме явната формулаf(a,b)=#{(x,y)∈Z≥02:x+yα<a+bα}.f(a,b)=\#\{(x,y)\in\mathbb Z_{\ge0}^2:x+y\alpha\lt{}a+b\alpha\}.От нея следва, че за всички x,y≥0x,y\ge0f(x,y)+f(x+1,y+1)=f(x,y)+f(x+1,y+1)=f(x+1,y)+f(x,y+1)+1.(1)f(x+1,y)+f(x,y+1)+1.\tag{1}Действително, двете разлики f(x+1,y+1)−f(x,y+1)f(x+1,y+1)-f(x,y+1) и f(x+1,y)−f(x,y)f(x+1,y)-f(x,y) броят точки в две успоредни ивици с ширина 11, като в първата има точно с една точка повече. Вземаме (1) по модул 22. Във всеки квадрат 2×22\times2 от стойности на ff броят на нечетните стойности е нечетен, тоест е 11 или 33. Разделяме квадрата 0≤x,y<1000\le x,y\lt{}100 на 50⋅5050\cdot50 такива квадрата 2×22\times2. Получаваме2500≤N≤7500.2500\le N\le7500.Остава да построим функции, които достигат границите. За ирационално α\alpha близко до 200200 отдолу, например α=200−ε\alpha=200-\varepsilon с достатъчно малко положително ирационално ε\varepsilon, формулата даваf(t,0)=t(0≤t≤100)f(t,0)=t\qquad(0\le t\le100)иf(0,k)≡k(mod2)(0≤k≤100).f(0,k)\equiv k\pmod2\qquad(0\le k\le100).Тогава от (1) по индукция по редовете следва следната паритетна картина в квадрата 100×100100\times100: във всеки ред с четно yy паритетите се редуват, а във всеки ред с нечетно yy всички стойности са нечетни. Следователно броят на нечетните стойности е50⋅50+50⋅100=7500.50\cdot50+50\cdot100=7500.За ирационално α\alpha близко до 200200 отгоре, например α=200+ε\alpha=200+\varepsilon, отново имаме f(t,0)=tf(t,0)=t, но вечеf(0,k)≡0(mod2)(0≤k≤100).f(0,k)\equiv0\pmod2\qquad(0\le k\le100).Пак чрез (1) получаваме, че редовете с четно yy имат редуващи се паритети, а редовете с нечетно yy са изцяло четни. ТогаваN=50⋅50=2500.N=50\cdot50=2500.Двете крайни стойности са постижими, което завършва решението.
Отвори задачатаMathNetISL 2022 C9Условие — източник

Задача N1

Пълен запис
Условие
Едно число ще наричаме норвежко, ако има три различни положителни делителя, чиято сума е равна на 20222022. Да се намери най-малкото норвежко число. Бележка. Общият брой положителни делители на едно норвежко число може да е по-голям от 33.
РешениеОтговорът е1344.1344.Числото 13441344 е норвежко, защото 66, 672672 и 13441344 са три различни негови делителя и6+672+1344=2022.6+672+1344=2022.Остава да докажем, че няма по-малко такова число. Да допуснем противното и нека N<1344N\lt{}1344 е норвежко. Нека трите избрани делителя саNa,Nb,Nc,\frac Na,\quad \frac Nb,\quad \frac Nc,където a<b<ca\lt{}b\lt{}c. Тогава2022=N(1a+1b+1c)<2022=N\left(\frac1a+\frac1b+\frac1c\right)\lt{}1344(1a+1b+1c),1344\left(\frac1a+\frac1b+\frac1c\right),следователно1a+1b+1c>\frac1a+\frac1b+\frac1c\gt{}20221344=337224=32+1224.\frac{2022}{1344}=\frac{337}{224}=\frac32+\frac1{224}.Ако a>1a\gt{}1, то1a+1b+1c≤\frac1a+\frac1b+\frac1c\le12+13+14=1312<32, \frac12+\frac13+\frac14=\frac{13}{12}\lt{}\frac32,противоречие. Значи a=1a=1. По същия начин трябва b<4b\lt{}4, защото при b≥4b\ge4 имаме1+1b+1c≤1+14+15<32.1+\frac1b+\frac1c\le 1+\frac14+\frac15\lt{}\frac32.Остават случаите b=2b=2 и b=3b=3. Нека първо b=3b=3. Тогава1c>32+1224−1−13>16,\frac1c\gt{}\frac32+\frac1{224}-1-\frac13\gt{}\frac16,така че c=4c=4 или c=5c=5. При c=4c=4 получаваме2022=N(1+13+14)=1912N,2022=N\left(1+\frac13+\frac14\right)=\frac{19}{12}N,което е невъзможно, понеже 19∤202219\nmid 2022. При c=5c=5 получаваме2022=N(1+13+15)=2315N,2022=N\left(1+\frac13+\frac15\right)=\frac{23}{15}N,което също е невъзможно, понеже 23∤202223\nmid 2022. Остава b=2b=2. От неравенството следва1c>32+1224−1−12=1224,\frac1c\gt{}\frac32+\frac1{224}-1-\frac12=\frac1{224},т.е. c<224c\lt{}224. Освен това2022=N(1+12+1c)=3c+22cN,2022=N\left(1+\frac12+\frac1c\right)=\frac{3c+2}{2c}N,следователно(3c+2)N=4044c.(3c+2)N=4044c.Понеже gcd⁡(c,3c+2)=gcd⁡(c,2)\gcd(c,3c+2)=\gcd(c,2), получаваме 3c+2∣8088=23⋅3⋅3373c+2\mid 8088=2^3\cdot3\cdot337. Но 3c+23c+2 не се дели на 33, а още 3c+2>83c+2\gt{}8 и 3c+2≠3373c+2\ne337. Следователно 3c+2≥2⋅3373c+2\ge2\cdot337, което противоречи на c<224c\lt{}224. Значи най-малкото норвежко число е 13441344.
Отвори задачатаMathNetISL 2022 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се намерят всички положителни цели числа n>2n\gt{}2, за коитоn!∣∏p<q≤np,q прости(p+q).\begin{aligned}n!\mid \prod_{\substack{p\lt{}q\le n\\ p,q\text{ прости}}}(p+q).\end{aligned}
РешениеОтговорът е единственоn=7.n=7.Нека nn удовлетворява условието и нека2=p1<p2<⋯<pm≤n2=p_1\lt{}p_2\lt{}\cdots\lt{}p_m\le nса простите числа, ненадминаващи nn. Понеже простото число pmp_m дели n!n!, то трябва да дели някой множител pi+pjp_i+p_j от произведението. Но0<pi+pjpm<pm+pmpm=2,0\lt{}\frac{p_i+p_j}{p_m}\lt{}\frac{p_m+p_m}{p_m}=2,така че непременноpm=pi+pj.p_m=p_i+p_j.Сумата на две нечетни прости числа е четна и по-голяма от 22, затова единият събираем е 22, а другият е най-голямото предходно просто число. Следователноpm=2+pm−1.p_m=2+p_{m-1}.Сега разглеждаме pm−1p_{m-1}. То също дели n!n!, следователно дели някоя сума pk+plp_k+p_l. Имаме0<pk+plpm−1≤0\lt{}\frac{p_k+p_l}{p_{m-1}}\lepm+pm−1pm−1=2pm−1+2pm−1<3. \frac{p_m+p_{m-1}}{p_{m-1}}=\frac{2p_{m-1}+2}{p_{m-1}}\lt{}3.Значи или pm−1=pk+plp_{m-1}=p_k+p_l, или 2pm−1=pk+pl2p_{m-1}=p_k+p_l. В първия случай, както по-горе, получаваме pm−1=2+pm−2p_{m-1}=2+p_{m-2}. Във втория случай трябва pk>pm−1p_k\gt{}p_{m-1}, следователно pk=pm=pm−1+2p_k=p_m=p_{m-1}+2, и тогава2pm−1=pl+pm=pl+pm−1+2,2p_{m-1}=p_l+p_m=p_l+p_{m-1}+2,т.е. пак pm−1=pl+2=pm−2+2p_{m-1}=p_l+2=p_{m-2}+2. Така трите числаpm−2,pm−1=pm−2+2,pm=pm−2+4p_{m-2},\quad p_{m-1}=p_{m-2}+2,\quad p_m=p_{m-2}+4са прости, а pm−2>2p_{m-2}\gt{}2. Сред три последователни нечетни числа, през 22, едно се дели на 33, затова pm−2=3p_{m-2}=3 и pm=7p_m=7. Следователно 7≤n<117\le n\lt{}11. Остава проверката за n=7,8,9,10n=7,8,9,10. За n=7n=7 простите са 2,3,5,72,3,5,7 и∏p<q≤7p,q прости(p+q)=\begin{aligned}\prod_{\substack{p\lt{}q\le7\\p,q\text{ прости}}}(p+q)=\end{aligned}5⋅7⋅9⋅8⋅10⋅12,5\cdot7\cdot9\cdot8\cdot10\cdot12,което се дели на 7!7!. Същото произведение не се дели на 8!8!, а значи не се дели и на 9!9! или 10!10!. Следователно единственото решение е n=7n=7.
Отвори задачатаMathNetISL 2022 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека a>1a\gt{}1 е положително цяло число и нека d>1d\gt{}1 е положително цяло число, взаимнопросто с aa. Нека x1=1x_1=1 и за k≥1k\ge1 да е дефинираноxk+1={xk+d,ако a∤xk,xk/a,ако a∣xk.x_{k+1}=\begin{cases}x_k+d,&\text{ако }a\nmid x_k,\\x_k/a,&\text{ако }a\mid x_k.\end{cases}Да се намери най-голямото положително цяло число nn, за което съществува индекс kk такъв, че xkx_k се дели на ana^n.
РешениеОтговорът е: единственото положително цяло число nn, за коетоd<an<ad.d\lt{}a^n\lt{}ad.Такова nn съществува и е единствено, понеже dd и aa са взаимнопрости и dd не е степен на aa. Първо ще докажем горна граница. По индукция всеки член xkx_k е взаимнопрост с dd. Освен това в редицата не може да има aa последователни увеличения с dd, защото сред числатаx,x+d,x+2d,…,x+(a−1)dx,x+d,x+2d,\ldots,x+(a-1)dточно едно се дели на aa. Оттук следва, че всеки член на редицата е по-малък от adad: веднага след деление на aa членът е по-малък от dd, а после могат да последват най-много a−1a-1 увеличения с dd. Ако някой член се дели на ara^r и r≥n+1r\ge n+1, то този член е поне an+1>ada^{n+1}\gt{}ad, противоречие. Следователно най-големият възможен показател е най-много nn. Остава да докажем, че ana^n наистина дели някой член. Разглеждаме множествотоS={x∈Z>0:0<x<ad, gcd⁡(x,d)=1}S=\{x\in\mathbb Z_{\gt{}0}:0\lt{}x\lt{}ad,\ \gcd(x,d)=1\}и функциятаf(x)={x+d,ако a∤x,x/a,ако a∣x.f(x)=\begin{cases}x+d,&\text{ако }a\nmid x,\\x/a,&\text{ако }a\mid x. \end{cases}Тя изпраща SS в себе си, а редицата е xk+1=f(xk)x_{k+1}=f(x_k). Функцията ff е обратима върху SS. Ако f(x)=yf(x)=y, тогаваf−1(y)={y−d,ако y>d,ay,ако y<d.f^{-1}(y)=\begin{cases}y-d,&\text{ако }y\gt{}d,\\ay,&\text{ако }y\lt{}d. \end{cases}Наистина, при y>dy\gt{}d числото y−dy-d е в SS, а ayay не е в SS; при y<dy\lt{}d е обратното. Значи ff е пермутация на крайното множество SS, следователно редицата е периодична и приема стойността 11 безкрайно много пъти. Нека xk1=1x_{k_1}=1 за някое k1>1k_1\gt{}1. Тъй като1<a<a2<⋯<an−1<d<an<ad,1\lt{}a\lt{}a^2\lt{}\cdots\lt{}a^{n-1}\lt{}d\lt{}a^n\lt{}ad,последователното прилагане на обратната функция даваxk1=1,xk1−1=a,x_{k_1}=1,\quad x_{k_1-1}=a,xk1−2=a2,…,xk1−n=an.\quad x_{k_1-2}=a^2,\quad\ldots,\quad x_{k_1-n}=a^n.Следователно някой член на редицата се дели на ana^n, както трябваше да докажем.
Отвори задачатаMathNetISL 2022 N3Условие — източник

Задача N4

Пълен запис
Условие
Да се намерят всички тройки положителни цели числа (a,b,p)(a,b,p), където pp е просто число иap=b!+p.a^p=b!+p.
РешениеОтговорът е(a,b,p)=(2,2,2)и(a,b,p)=(3,4,3).(a,b,p)=(2,2,2)\quad\text{и}\quad(a,b,p)=(3,4,3).Проверяват се непосредствено. Ще докажем, че други няма. Ясно е, че a>1a\gt{}1. Разглеждаме три случая. Първи случай: a<pa\lt{}p. Ако a≤ba\le b, то aa дели и apa^p, и b!b!, следователно a∣pa\mid p, невъзможно при 1<a<p1\lt{}a\lt{}p. Ако a>ba\gt{}b, тогава b!≤a!<ap−pb!\le a!\lt{}a^p-p, откъдето b!+p<apb!+p\lt{}a^p, пак противоречие. Втори случай: a>pa\gt{}p. Тогаваb≠ap−p>pp−p≥p!,b\neq{}a^p-p\gt{}p^p-p\ge p!,така че b>pb\gt{}p. Значи p∣b!p\mid b!, а от ap=b!+pa^p=b!+p следва p∣ap\mid a. Но тогава b≠ap−pb\neq{}a^p-p се дели на pp, но не и на p2p^2, следователно b<2pb\lt{}2p. Ако a<p2a\lt{}p^2, то цялото число a/pa/p е по-малко от pp и дели както apa^p, така и b!b!; тогава то дели и p=ap−b!p=a^p-b!, противоречие. Ако пък a≥p2a\ge p^2, тоap≥(p2)p=p2p>(2p−1)!+p≥b!+p,a^p\ge (p^2)^p=p^{2p}\gt{}(2p-1)!+p\ge b!+p,където неравенството p2p>(2p−1)!+pp^{2p}\gt{}(2p-1)!+p следва например от(2p−1)≠(2p-1)\neq{}[1⋅(2p−1)][2⋅(2p−2)]⋯[(p−1)(p+1)]⋅p<[1\cdot(2p-1)][2\cdot(2p-2)]\cdots[(p-1)(p+1)]\cdot p\lt{}p2p−1.p^{2p-1}.Получаваме противоречие. Трети случай: a=pa=p. Тогава b≠pp−pb\neq{}p^p-p. При p=2p=2 и p=3p=3 получаваме двете посочени решения, а при p=5p=5 решение няма. Нека p≥5p\ge5. Тогава pp>p!+pp^p\gt{}p!+p, следователно b>pb\gt{}p. Ще работим по модул (p+1)2(p+1)^2. Имамеpp−p=(p+1−1)p−p≡p^p-p=(p+1-1)^p-p\equiv(p1)(p+1)(−1)p−1+(−1)p−p=p2−1(mod(p+1)2), \binom p1(p+1)(-1)^{p-1}+(-1)^p-p=p^2-1\pmod{(p+1)^2},което не е 00 по модул (p+1)2(p+1)^2. От друга страна, при p≥5p\ge5 числата 22 и (p+1)/2(p+1)/2 са различни и не надминават pp, затова p+1∣p!p+1\mid p! и следователно (p+1)2∣(p+1)!(p+1)^2\mid (p+1)!. Понеже b≥p+1b\ge p+1, получаваме (p+1)2∣b!(p+1)^2\mid b!, противоречие. Следователно единствените решения са (2,2,2)(2,2,2) и (3,4,3)(3,4,3).
Отвори задачатаMathNetISL 2022 N4Условие — източник

Задача N5

Пълен запис
Условие
За всяко 1≤i≤91\le i\le9 и T∈NT\in\mathbb N нека di(T)d_i(T) е общият брой появявания на цифрата ii, когато всички кратни на 18291829 между 11 и TT включително се запишат в десетична бройна система. Докажете, че съществуват безкрайно много T∈NT\in\mathbb N, за които сред числатаd1(T),d2(T),…,d9(T)d_1(T),d_2(T),\ldots,d_9(T)има точно две различни стойности.
РешениеНека n=1829n=1829. Избираме kk така, чеn∣10k−1.n\mid10^k-1.Например всяко кратно на φ(n)\varphi(n) върши работа, понеже gcd⁡(n,10)=1\gcd(n,10)=1. Ще докажем, че за всяко такова kk поне едно от числата T=10k−1T=10^k-1 и T=10k−2T=10^k-2 има исканото свойство. Тъй като kk може да се избира произволно голямо, това ще даде безкрайно много стойности на TT. Достатъчно е да покажем, че множеството{di(10k−1):1≤i≤9}\{d_i(10^k-1):1\le i\le9\}има най-много две стойности. Ако то има точно две стойности, сме готови. Ако има една стойност, тогава 10k−110^k-1 е кратно на nn и се състои само от деветки, така че при преминаване от T=10k−1T=10^k-1 към T=10k−2T=10^k-2 броевете за цифрите 1,2,…,81,2,\ldots,8 не се променят, а броят за цифрата 99 намалява. Следователно при T=10k−2T=10^k-2 ще има точно две различни стойности. Остава да докажем твърдението за 10k−110^k-1. Записваме всяко число между 11 и 10k−110^k-1 с точно kk цифри, като допускаме водещи нули. Акоak−1ak−2…a0a_{k-1}a_{k-2}\ldots a_0е такъв запис, то той е кратен на nn тогава и само тогава, когато циклично преместеният записak−2…a0ak−1a_{k-2}\ldots a_0a_{k-1}е кратен на nn. Наистина,10⋅ak−1ak−2…a0−ak−2…a0ak−1=10\cdot a_{k-1}a_{k-2}\ldots a_0-a_{k-2}\ldots a_0a_{k-1}=(10k−1)ak−1,(10^k-1)a_{k-1},което се дели на nn. Значи множеството от кратните на nn между 11 и 10k−110^k-1 е инвариантно при едновременно циклично преместване на цифрите. Затова за всяко i∈{1,2,…,9}i\in\{1,2,\ldots,9\} числото di(10k−1)d_i(10^k-1) е kk пъти броя на kk-цифрените записи, които започват с цифрата ii и са кратни на nn. А тези записи са точно кратните на nn в интервал от дължина 10k−110^{k-1}, следователно броят им е или⌊10k−1n⌋,\left\lfloor\frac{10^{k-1}}n\right\rfloor,или с 11 по-голям. Така числата di(10k−1)d_i(10^k-1) приемат най-много две различни стойности. Доказателството е завършено.
Отвори задачатаMathNetISL 2022 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека QQ е множество от прости числа, не непременно крайно. За положително цяло число nn разглеждаме разлагането му на прости множители; нека p(n)p(n) е сумата на всички показатели, а q(n)q(n) - сумата на показателите само при простите числа от QQ. Положително цяло число nn се нарича специално, ако p(n)+p(n+1)p(n)+p(n+1) и q(n)+q(n+1)q(n)+q(n+1) са четни. Докажете, че съществува константа c>0c\gt{}0, независеща от множеството QQ, такава че за всяко положително цяло число N>100N\gt{}100 броят на специалните числа в [1,N][1,N] е поне cNcN. Например, ако Q={3,7}Q=\{3,7\}, то p(42)=3p(42)=3, q(42)=2q(42)=2, p(63)=3p(63)=3, q(63)=3q(63)=3, p(2022)=3p(2022)=3, q(2022)=1q(2022)=1.
РешениеЩе докажем твърдението с c=1/2000c=1/2000. Да наречем две положителни цели числа m,nm,n приятели, ако p(m)+p(n)p(m)+p(n) и q(m)+q(n)q(m)+q(n) са четни. Двойката(p(t),q(t))(mod2)(p(t),q(t))\pmod2може да приема най-много 44 стойности, затова сред всеки пет различни положителни цели числа има две, които са приятели. Освен това функциите pp и qq са адитивни при умножение:f(ab)=f(a)+f(b).f(ab)=f(a)+f(b).Следователно, ако dd дели и mm, и nn, тоf(m)+f(n)=f(m/d)+f(n/d)+2f(d).f(m)+f(n)=f(m/d)+f(n/d)+2f(d).Значи m,nm,n са приятели тогава и само тогава, когато m/d,n/dm/d,n/d са приятели. Да наречем множество {n1,n2,…,n5}\{n_1,n_2,\ldots,n_5\} интересно, ако за всеки два индекса i,ji,j разликатаdij=∣ni−nj∣d_{ij}=|n_i-n_j|дели и nin_i, и njn_j. Ако всички елементи на интересно множество са положителни, то от него получаваме специално число. Наистина, сред петте елемента има приятелска двойка ni,njn_i,n_j. Тогава иnidij,njdij\frac{n_i}{d_{ij}},\quad \frac{n_j}{d_{ij}}са приятели, а тези две числа са последователни. Следователно по-малкото от тях е специално. Сега построяваме много интересни множества. Множеството{0,6,8,9,12}\{0,6,8,9,12\}е интересно, а най-малкото общо кратно на всички негови положителни двойки разлики е72=23⋅32.72=2^3\cdot3^2.Затова за всяко k≥1k\ge1 множеството{72k,72k+6,72k+8,72k+9,72k+12}\{72k,72k+6,72k+8,72k+9,72k+12\}също е интересно. Като разгледаме частните на двойките елементи с подходящите им разлики, получаваме, че множествотоSk=S_k={6k,8k,9k,12k,12k+1,18k+2,24k+2,24k+3,36k+3,72k+8}\{6k,8k,9k,12k,12k+1,18k+2,24k+2,24k+3,36k+3,72k+8\}съдържа поне едно специално число. За всяко j≤kj\le k всички елементи на SjS_j лежат в интервала [1,100k][1,100k]. Следователно множествата S1,S2,…,SkS_1,S_2,\ldots,S_k дават поне по едно специално число в този интервал. Едно и също число може да принадлежи на най-много десет от множествата SjS_j, понеже във всяка от десетте линейни форми стойността определя jj еднозначно. Значи в [1,100k][1,100k] има поне k/10k/10 специални числа. Накрая нека N=100k+rN=100k+r, където k≥1k\ge1 и 0≤r<1000\le r\lt{}100. Тогава N<100(k+1)≤200kN\lt{}100(k+1)\le200k, а интервалът [1,100k][1,100k] се съдържа в [1,N][1,N]. Броят на специалните числа в [1,N][1,N] е понеk10>N2000.\frac{k}{10}\gt{}\frac{N}{2000}.Това доказва твърдението.
Отвори задачатаMathNetISL 2022 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека kk е положително цяло число и нека SS е крайно множество от нечетни прости числа. Докажете, че има най-много един начин, с точност до ротация и отражение, да се разположат елементите на SS по окръжност така, че произведението на всеки два съседни елемента да е от видаx2+x+kx^2+x+kза някое положително цяло число xx.
РешениеЩе докажем малко по-силно твърдение, като позволим и x=0x=0. Да наречем двойка различни прости числа {p,q}\{p,q\} специална, акоpq=x2+x+kpq=x^2+x+kза някое неотрицателно цяло число xx. Ключово е следното твърдение. 1. За всяко просто число rr има най-много две прости числа, по-малки от rr, които образуват специална двойка с rr. 2. Ако такива две числа pp и qq съществуват, то двойката {p,q}\{p,q\} също е специална. За първата част разглеждаме решенията xx наx2+x+k≡0(modr).x^2+x+k\equiv0\pmod r.Когато pr=x2+x+kpr=x^2+x+k и p<rp\lt{}r, имаме 0≤x<r0\le x\lt{}r, а квадратно сравнение по модул rr има най-много две решения. Това доказва първата част. За втората част нека p<q<rp\lt{}q\lt{}r иx2+x+k=pr,y2+y+k=qr.x^2+x+k=pr,\qquad y^2+y+k=qr.Тогава 0≤x<y≤r−10\le x\lt{}y\le r-1, а xx и yy са двете решения на горното квадратно сравнение. По формулите на Виетx+y≡−1(modr),x+y\equiv -1\pmod r,следователно x+y=r−1x+y=r-1. ПолагамеK=4k−1,X=2x+1,Y=2y+1.K=4k-1,\qquad X=2x+1,\qquad Y=2y+1.Тогава4pr=X2+K,4qr=Y2+K,X+Y=2r.4pr=X^2+K,\qquad 4qr=Y^2+K,\qquad X+Y=2r.Умножаваме първите две равенства:16pqr2=(X2+K)(Y2+K)=16pqr^2=(X^2+K)(Y^2+K)=(XY−K)2+K(X+Y)2=(XY−K)2+4Kr2.(XY-K)^2+K(X+Y)^2=(XY-K)^2+4Kr^2.Затова4pq=Z2+K4pq=Z^2+Kза цялото число Z=(XY−K)/(2r)Z=(XY-K)/(2r). Числото ZZ е нечетно, така че за z=(∣Z∣−1)/2z=(|Z|-1)/2 получавамеpq=z2+z+k.pq=z^2+z+k.Следователно {p,q}\{p,q\} е специална двойка. Сега завършваме с индукция по ∣S∣|S|. При ∣S∣≤3|S|\le3 твърдението е ясно. Нека ∣S∣=n+1|S|=n+1 и приемем, че твърдението е доказано за всички множества с nn елемента. Нека rr е най-голямото просто число в SS. Във всяко допустимо разполагане двата съседа на rr трябва да са точно двете прости числа, по-малки от rr, които образуват специална двойка с него; ако няма такива две числа, допустимо разполагане изобщо няма. Ако премахнем rr от окръжността, двата му бивши съседа стават съседни, а по доказаното твърдение тяхната двойка е специална. Получаваме допустимо разполагане на S∖{r}S\setminus\{r\}. По индукционното предположение то е единствено с точност до ротация и отражение, а мястото на rr между неговите два вече определени съседа също е принудено. Значи допустимото разполагане на SS е най-много едно.
Отвори задачатаMathNetISL 2022 N7Условие — източник

Задача N8

Пълен запис
Условие
Докажете, че 5n−3n5^n-3^n не се дели на 2n+652^n+65 за никое положително цяло число nn.
РешениеДа допуснем противното. Некаm=2n+65m=2^n+65и нека5n≡3n(modm).5^n\equiv3^n\pmod m.Ако nn е четно, то 3∣m3\mid m, защото 2n≡1(mod3)2^n\equiv1\pmod3 и 65≡2(mod3)65\equiv2\pmod3. Но тогава5n−3n≡(−1)n−0≡1(mod3),5^n-3^n\equiv (-1)^n-0\equiv1\pmod3,противоречие. Следователно nn е нечетно. Случаят n=1n=1 е непосредствено невъзможен, така че n≥3n\ge3. Тогава mm е нечетно и m≡1(mod8)m\equiv1\pmod8. Ще използваме символа на Якоби. Понеже nn е нечетно, 2n2^n е сравнимо с 22 или 33 по модул 55, така че(m5)=−1.\left(\frac{m}{5}\right)=-1.От квадратичната реципрочност и 5≡1(mod4)5\equiv1\pmod4 следва(5m)=(m5)=−1.\left(\frac{5}{m}\right)=\left(\frac{m}{5}\right)=-1.От сравнението 5n≡3n(modm)5^n\equiv3^n\pmod m получаваме(5nm)=(3nm).\left(\frac{5^n}{m}\right)=\left(\frac{3^n}{m}\right).Тъй като nn е нечетно, това дава(5m)=(3m).\left(\frac5m\right)=\left(\frac3m\right).Следователно−1=(5m)=(3m).-1=\left(\frac5m\right)=\left(\frac3m\right).Но m≡1(mod8)m\equiv1\pmod8, затова при реципрочност между 33 и mm няма смяна на знака, и(3m)=(m3).\left(\frac3m\right)=\left(\frac m3\right).Понеже nn е нечетно,m=2n+65≡−1+2≡1(mod3),m=2^n+65\equiv -1+2\equiv1\pmod3,така че(m3)=1.\left(\frac m3\right)=1.Получаваме едновременно (3m)=−1\left(\frac3m\right)=-1 и (3m)=1\left(\frac3m\right)=1, противоречие. Следователно 2n+652^n+65 не дели 5n−3n5^n-3^n за никое положително цяло число nn.
Отвори задачатаMathNetISL 2022 N8Условие — източник