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

IMO Shortlisted Problems

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

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

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

2023

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

11-12

22 задачи

Задача A1

Пълен запис
Условие
Професор Оук храни своите 100100 покемона. Всеки покемон има купичка, чиято вместимост е положително реално число килограми. Тези вместимости са известни на професор Оук, а общата вместимост на всички купички е 100100 килограма. Професор Оук разпределя 100100 килограма храна така, че всеки покемон получава неотрицателен цял брой килограми храна (който може да е по-голям от вместимостта на купичката му). Нивото на неудовлетвореност на покемон, който е получил NN килограма храна и чиято купичка има вместимост CC килограма, е равно на ∣N−C∣|N-C|. Да се намери най-малкото реално число DD, такова че независимо от вместимостите на купичките професор Оук винаги може да разпредели храната така, че сумата от нивата на неудовлетвореност на всички 100100 покемона да е най-много DD.
РешениеОтговорът е D=50D=50. Първо ще покажем, че по-малко число не е възможно. Нека 9999 от купичките имат вместимост 0.50.5 килограма, а последната - 50.550.5 килограма. При всяко разпределение всеки покемон има неудовлетвореност поне 0.50.5, понеже получава цял брой килограми. Следователно общата неудовлетвореност е поне 5050, така че D≥50D\ge50. Остава да докажем, че 5050 винаги стига. Номерираме покемоните от 11 до 100100 и нека Ci>0C_i\gt{}0 е вместимостта на купичката на ii-тия покемон. ИмамеC1+C2+⋯+C100=100.C_1+C_2+\cdots+C_{100}=100.ПишемFi=Ci−⌊Ci⌋F_i=C_i-\lfloor C_i\rfloorза дробната част на CiC_i и без ограничение на общността подреждаме така, чеF1≤F2≤⋯≤F100.F_1\le F_2\le\cdots\le F_{100}.НекаR=100−⌊C1⌋−⋯−⌊C100⌋=F1+⋯+F100.R=100-\lfloor C_1\rfloor-\cdots-\lfloor C_{100}\rfloor=F_1+\cdots+F_{100}.Числото RR е цяло. Професор Оук първо дава на ii-тия покемон ⌊Ci⌋\lfloor C_i\rfloor килограма храна, а после дава по още 11 килограм на RR-те покемона с най-големи стойности на FiF_i. Тогава общата неудовлетвореност еd=d=F1+⋯+F100−R+(1−F100−R+1)+⋯+(1−F100).F_1+\cdots+F_{100-R}+(1-F_{100-R+1})+\cdots+(1-F_{100}).Понеже F1+⋯+F100=RF_1+\cdots+F_{100}=R, получавамеd=2(F1+⋯+F100−R).d=2(F_1+\cdots+F_{100-R}).Средното аритметично на F1,…,F100−RF_1,\ldots,F_{100-R} не надминава средното аритметично на всички F1,…,F100F_1,\ldots,F_{100}, затоваd≤2(100−R)⋅R100=2R(100−R)100≤50,d\le 2(100-R)\cdot\frac{R}{100}=\frac{2R(100-R)}{100}\le50,където последното неравенство следва от (R−50)2≥0(R-50)^2\ge0. Следователно винаги има разпределение с обща неудовлетвореност най-много 5050.
Отвори задачатаMathNetISL 2023 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека R\mathbb R е множеството на реалните числа. Нека f:R→Rf:\mathbb R\to\mathbb R е функция, такава чеf(x+y)f(x−y)≥f(x)2−f(y)2f(x+y)f(x-y)\ge f(x)^2-f(y)^2за всички x,y∈Rx,y\in\mathbb R. Да предположим, че неравенството е строго за някои x0,y0∈Rx_0,y_0\in\mathbb R. Докажете, че f(x)≥0f(x)\ge0 за всяко x∈Rx\in\mathbb R или f(x)≤0f(x)\le0 за всяко x∈Rx\in\mathbb R.
РешениеПоставямеs=x+y,t=x−y.s=x+y,\qquad t=x-y.Тогава x=(s+t)/2x=(s+t)/2 и y=(s−t)/2y=(s-t)/2, а даденото неравенство ставаf(s)f(t)≥f(s+t2)2−f(s−t2)2(1)f(s)f(t)\ge f\left(\frac{s+t}{2}\right)^2-f\left(\frac{s-t}{2}\right)^2\tag{1}за всички реални s,ts,t. Заменяме tt с −t-t в (1). Получавамеf(s)f(−t)≥f(s−t2)2−f(s+t2)2.(2)f(s)f(-t)\ge f\left(\frac{s-t}{2}\right)^2-f\left(\frac{s+t}{2}\right)^2.\tag{2}Събирайки (1) и (2), намирамеf(s)(f(t)+f(−t))≥0(3)f(s)\bigl(f(t)+f(-t)\bigr)\ge0\tag{3}за всички реални s,ts,t. За s0=x0+y0s_0=x_0+y_0 и t0=x0−y0t_0=x_0-y_0 първото от двете събирани неравенства е строго, а второто е вярно. Следователно в (3) при s=s0,t=t0s=s_0,t=t_0 имаме строго неравенство. В частностf(t0)+f(−t0)≠0.f(t_0)+f(-t_0)\ne0.Сега от (3) с фиксирано t=t0t=t_0 следва, че всички стойности f(s)f(s) имат един и същ знак: ако f(t0)+f(−t0)>0f(t_0)+f(-t_0)\gt{}0, то f(s)≥0f(s)\ge0 за всяко ss, а ако f(t0)+f(−t0)<0f(t_0)+f(-t_0)\lt{}0, то f(s)≤0f(s)\le0 за всяко ss. Това доказва твърдението.
Отвори задачатаMathNetISL 2023 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека x1,x2,…,x2023x_1,x_2,\ldots,x_{2023} са различни положителни реални числа, такива чеan=a_n=x2(x1+x2+⋯+xn)(1x1+1x2+⋯+1xn)\sqrt{\vphantom{x^2}(x_1+x_2+\cdots+x_n)\left(\frac1{x_1}+\frac1{x_2}+\cdots+\frac1{x_n}\right)}е цяло число за всяко n=1,2,…,2023n=1,2,\ldots,2023. Докажете, че a2023≥3034a_{2023}\ge3034.
РешениеПърво отбелязваме, че a1=1a_1=1. Ще докажем, че за всяко nn е изпълненоan+2≥an+3.(1)a_{n+2}\ge a_n+3.\tag{1}НекаX=x1+⋯+xn,Y=1x1+⋯+1xn,X=x_1+\cdots+x_n,\qquad Y=\frac1{x_1}+\cdots+\frac1{x_n},U=xn+1+xn+2,V=1xn+1+1xn+2.U=x_{n+1}+x_{n+2},\qquad V=\frac1{x_{n+1}}+\frac1{x_{n+2}}.Тогава an2=XYa_n^2=XY иan+22=(X+U)(Y+V)=XY+UV+XV+UY.a_{n+2}^2=(X+U)(Y+V)=XY+UV+XV+UY.От неравенството между средно аритметично и средно геометрично получавамеXV+UY≥2x2XYUV=2anx2UV.XV+UY\ge2\sqrt{\vphantom{x^2}XYUV}=2a_n\sqrt{\vphantom{x^2}UV}.Освен това, понеже xn+1≠xn+2x_{n+1}\ne x_{n+2},UV=(xn+1+xn+2)(1xn+1+1xn+2)>4.UV=(x_{n+1}+x_{n+2})\left(\frac1{x_{n+1}}+\frac1{x_{n+2}}\right)\gt{}4.Следователноan+22>an2+4+4an=(an+2)2.a_{n+2}^2\gt{}a_n^2+4+4a_n=(a_n+2)^2.Двете числа an+2a_{n+2} и ana_n са положителни цели числа, затова от последното строго неравенство следва (1). Прилагайки (1) последователно, получавамеa2k+1≥3k+1a_{2k+1}\ge 3k+1за всяко k≥0k\ge0. При k=1011k=1011 това даваa2023≥3⋅1011+1=3034,a_{2023}\ge3\cdot1011+1=3034,както трябваше да се докаже.
Отвори задачатаMathNetISL 2023 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека R>0\mathbb R_{\gt{}0} е множеството на положителните реални числа. Да се намерят всички функции f:R>0→R>0f:\mathbb R_{\gt{}0}\to\mathbb R_{\gt{}0}, за коитоx(f(x)+f(y))≥(f(f(x))+y)f(y)x\bigl(f(x)+f(y)\bigr)\ge\bigl(f(f(x))+y\bigr)f(y)за всички x,y∈R>0x,y\in\mathbb R_{\gt{}0}.
РешениеОтговорът еf(x)=cx(c>0).f(x)=\frac{c}{x}\qquad(c\gt{}0).Нека ff е решение. Ще пишем fn(x)f^n(x) за nn-тата итерация на ff, като f0(x)=xf^0(x)=x. Замествайки y=xy=x в условието, получаваме2xf(x)≥(f2(x)+x)f(x).2xf(x)\ge (f^2(x)+x)f(x).Понеже f(x)>0f(x)\gt{}0, следваx≥f2(x).(1)x\ge f^2(x).\tag{1}Сега заместваме x=f(y)x=f(y) в условието и делим на положителното число f(y)f(y). Получавамеf(y)+f2(y)≥y+f3(y),f(y)+f^2(y)\ge y+f^3(y),тоестf(y)−f3(y)≥y−f2(y).(2)f(y)-f^3(y)\ge y-f^2(y).\tag{2}Заменяйки yy с fn−1(y)f^{n-1}(y) в (2), намирамеfn(y)−fn+2(y)≥fn−1(y)−fn+1(y)f^n(y)-f^{n+2}(y)\ge f^{n-1}(y)-f^{n+1}(y)за всяко n≥1n\ge1. От (1) и индукция следваfn(y)−fn+2(y)≥y−f2(y)≥0(3)f^n(y)-f^{n+2}(y)\ge y-f^2(y)\ge0\tag{3}за всяко n≥1n\ge1. За четни индекси получавамеy−f2m(y)=∑i=0m−1(f2i(y)−f2i+2(y))≥y-f^{2m}(y)=\sum_{i=0}^{m-1}\bigl(f^{2i}(y)-f^{2i+2}(y)\bigr)\gem(y−f2(y)). m\bigl(y-f^2(y)\bigr).Но f2m(y)>0f^{2m}(y)\gt{}0, така че лявата страна е по-малка от yy. Това е вярно за всяко m≥1m\ge1, а числото y−f2(y)y-f^2(y) е неотрицателно; следователноf2(y)=yf^2(y)=yза всяко y>0y\gt{}0. Тогава първоначалното неравенство се свежда доxf(x)≥yf(y)xf(x)\ge yf(y)за всички положителни x,yx,y. Разменяйки xx и yy, получаваме и обратното неравенство, следователно xf(x)xf(x) е константа. Значи xf(x)=cxf(x)=c за някое c>0c\gt{}0, илиf(x)=cx.f(x)=\frac{c}{x}.Накрая, всяка функция от този вид наистина е решение: за нея f(f(x))=xf(f(x))=x и двете страни на исканото неравенство се различават само с тъждеството xf(x)=yf(y)=cxf(x)=yf(y)=c.
Отвори задачатаMathNetISL 2023 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека a1,a2,…,a2023a_1,a_2,\ldots,a_{2023} са положителни цели числа, такива че - a1,a2,…,a2023a_1,a_2,\ldots,a_{2023} е пермутация на 1,2,…,20231,2,\ldots,2023; - ∣a1−a2∣,∣a2−a3∣,…,∣a2022−a2023∣|a_1-a_2|,|a_2-a_3|,\ldots,|a_{2022}-a_{2023}| е пермутация на 1,2,…,20221,2,\ldots,2022. Докажете, чеmax⁡(a1,a2023)≥507.\max(a_1,a_{2023})\ge507.
РешениеЩе докажем малко по-общо твърдение. Нека NN е положително цяло число и a1,a2,…,a2N−1a_1,a_2,\ldots,a_{2N-1} е пермутация на 1,2,…,2N−11,2,\ldots,2N-1, а∣a1−a2∣,∣a2−a3∣,…,∣a2N−2−a2N−1∣|a_1-a_2|,|a_2-a_3|,\ldots,|a_{2N-2}-a_{2N-1}|е пермутация на 1,2,…,2N−21,2,\ldots,2N-2. Тогаваa1+a2N−1≥N+1,a_1+a_{2N-1}\ge N+1,откъдетоmax⁡(a1,a2N−1)≥⌈N+12⌉.\max(a_1,a_{2N-1})\ge\left\lceil\frac{N+1}{2}\right\rceil.Оригиналната задача е случаят N=1012N=1012, което дава 507507. За a∈{1,2,…,2N−1}a\in\{1,2,\ldots,2N-1\} дефинираме неговата оценкаs(a)=∣a−N∣.s(a)=|a-N|.От неравенството на триъгълника имаме∣a−b∣≤∣a−N∣+∣b−N∣=s(a)+s(b).|a-b|\le |a-N|+|b-N|=s(a)+s(b).Следователно(N−1)(2N−1)=1+2+⋯+(2N−2)=∣a1−a2∣+∣a2−a3∣+⋯+∣a2N−2−a2N−1∣≤2(s(a1)+s(a2)+⋯+s(a2N−1))−s(a1)−s(a2N−1).\begin{aligned} (N-1)(2N-1)&=1+2+\cdots+(2N-2)\\ &=|a_1-a_2|+|a_2-a_3|+\cdots+|a_{2N-2}-a_{2N-1}|\\ &\le 2\bigl(s(a_1)+s(a_2)+\cdots+s(a_{2N-1})\bigr)-s(a_1)-s(a_{2N-1}). \end{aligned}Понеже a1,a2,…,a2N−1a_1,a_2,\ldots,a_{2N-1} е пермутация на 1,2,…,2N−11,2,\ldots,2N-1, числата s(ai)s(a_i) са точно0,1,1,2,2,…,N−1,N−1.0,1,1,2,2,\ldots,N-1,N-1.Тяхната сума е N(N−1)N(N-1). Затова от предходното неравенство получавамеs(a1)+s(a2N−1)≤s(a_1)+s(a_{2N-1})\le2N(N−1)−(N−1)(2N−1)=N−1. 2N(N-1)-(N-1)(2N-1)=N-1.НакраяN−a1+N−a2N−1≤N-a_1+N-a_{2N-1}\le∣N−a1∣+∣N−a2N−1∣=s(a1)+s(a2N−1)≤N−1, |N-a_1|+|N-a_{2N-1}|=s(a_1)+s(a_{2N-1})\le N-1,което е еквивалентно на a1+a2N−1≥N+1a_1+a_{2N-1}\ge N+1. Това доказва общото твърдение, а с него и задачата.
Отвори задачатаMathNetISL 2023 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека k≥2k\ge2 е цяло число. Да се определят всички редици от положителни цели числа a1,a2,…a_1,a_2,\ldots, за които съществува моничен полином PP от степен kk с неотрицателни цели коефициенти, такъв чеP(an)=an+1an+2⋯an+kP(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}за всяко цяло n≥1n\ge1.
РешениеОтговорът е: всички аритметични прогресии от положителни цели числа с обща разлика d≥0d\ge0. За такава редица подходящият полином еP(x)=(x+d)(x+2d)⋯(x+kd).P(x)=(x+d)(x+2d)\cdots(x+kd).Проверката е непосредствена. Нека сега редицата и полиномът удовлетворяват условието. Тъй като PP е моничен и има неотрицателни коефициенти, той е строго растящ върху положителните реални числа. Ако редицата е константна от някое място нататък, то от равенството P(a)=akP(a)=a^k за положително цяло aa следва, че всички по-ниски коефициенти на PP са нули, тоест P(x)=xkP(x)=x^k. Тогава по обратна индукция всички членове на редицата са равни. Така получаваме константните решения, които съответстват на d=0d=0. Занапред предполагаме, че редицата не е константна от някое място нататък. Сравнявайки равенстватаP(an)=an+1an+2⋯an+k,P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k},P(an+1)=an+2an+3⋯an+k+1,P(a_{n+1})=a_{n+2}a_{n+3}\cdots a_{n+k+1},и използвайки строгата монотонност на PP, получавамеan<an+1⟺an+1<an+k+1,(1)a_n\lt{}a_{n+1}\Longleftrightarrow a_{n+1}\lt{}a_{n+k+1},\tag{1}и аналогично за знаците >\gt{} и ==. Ще покажем, че редицата е ненамаляваща. Ако има спад am>am+1a_m\gt{}a_{m+1}, то от (1) за знака >\gt{} следва am+1>am+k+1a_{m+1}\gt{}a_{m+k+1}. Избираме най-малкия индекс j>m+1j\gt{}m+1, за който aj<am+1a_j\lt{}a_{m+1}. Тогава j≤m+k+1j\le m+k+1 и по минималност aj−1>aja_{j-1}\gt{}a_j. Така от един спад получаваме по-късен спад с по-малък десен член. Повтаряйки, бихме получили безкрайна строго намаляваща редица от положителни цели числа, което е невъзможно. Следователно an≤an+1a_n\le a_{n+1} за всяко nn. Ако за някое nn имаме an=an+1a_n=a_{n+1}, то от (1) за равенство следва an+1=an+k+1a_{n+1}=a_{n+k+1}. Понеже редицата е ненамаляваща, получавамеan=an+1=⋯=an+k+1.a_n=a_{n+1}=\cdots=a_{n+k+1}.Повтаряйки същия аргумент, редицата би била константна от някое място нататък, противно на предположението. Значиan<an+1(n≥1).(2)a_n\lt{}a_{n+1}\qquad(n\ge1).\tag{2}Нека bb е коефициентът пред xk−1x^{k-1} в P(x)P(x). За положителни цели числа c1,…,ckc_1,\ldots,c_k сравнението на коефициентите пред xk−1x^{k-1} показва следното: съществува граница AA, така че за всяко x≥Ax\ge A имамеP(x)<(x+c1)(x+c2)⋯(x+ck)P(x)\lt{}(x+c_1)(x+c_2)\cdots(x+c_k)ако c1+⋯+ck>bc_1+\cdots+c_k\gt{}b, аP(x)>(x+c1)(x+c2)⋯(x+ck)P(x)\gt{}(x+c_1)(x+c_2)\cdots(x+c_k)ако c1+⋯+ck<bc_1+\cdots+c_k\lt{}b. Достатъчно е да се вземе обща граница за крайните на брой гранични случаи; останалите следват от монотонност на произведението по всяко cic_i. Понеже редицата е строго растяща, an→∞a_n\to\infty. Избираме NN, такова че an≥Aa_n\ge A за n≥Nn\ge N. За такива nn поставямеci=an+i−an(1≤i≤k).c_i=a_{n+i}-a_n\qquad(1\le i\le k).От равенствотоP(an)=(an+c1)(an+c2)⋯(an+ck)P(a_n)=(a_n+c_1)(a_n+c_2)\cdots(a_n+c_k)и от сравнението по-горе следва∑i=1k(an+i−an)=b(n≥N).(3)\sum_{i=1}^k(a_{n+i}-a_n)=b\qquad(n\ge N).\tag{3}Изваждайки равенството (3) за nn от равенството (3) за n+1n+1, получавамеan+k+1−an+1=k(an+1−an).(4)a_{n+k+1}-a_{n+1}=k(a_{n+1}-a_n).\tag{4}Некаd=min⁡{an+1−an∣n≥N},d=\min\{a_{n+1}-a_n\mid n\ge N\},и нека минимумът се достига при някой индекс n≥Nn\ge N. От (4) следва∑i=1k(an+i+1−an+i)=k(an+1−an)=kd.\sum_{i=1}^k(a_{n+i+1}-a_{n+i})=k(a_{n+1}-a_n)=kd.Всеки събираем вляво е поне dd, затова всички те са равни на dd. По индукция получавамеam+1−am=da_{m+1}-a_m=dза всяко достатъчно голямо mm. Тогава за безкрайно много стойности x=amx=a_m е вярноP(x)=(x+d)(x+2d)⋯(x+kd),P(x)=(x+d)(x+2d)\cdots(x+kd),следователно това е тъждество на полиноми. Остава да върнем аритметичността назад. Ако вече знаем, че am,am+1,…a_m,a_{m+1},\ldots образуват аритметична прогресия с разлика dd, пишем e=am−am−1>0e=a_m-a_{m-1}\gt{}0. От тъждеството за PP и от условието за n=m−1n=m-1 получаваме∏i=1k(am−1+id)=∏i=0k−1(am−1+e+id).\prod_{i=1}^k(a_{m-1}+id)=\prod_{i=0}^{k-1}(a_{m-1}+e+id).Дясната страна като функция на ee е строго растяща за e>0e\gt{}0, а при e=de=d съвпада с лявата. Значи e=de=d. Обратната индукция доказва, че цялата редица е аритметична прогресия с обща разлика dd.
Отвори задачатаMathNetISL 2023 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека NN е положително цяло число. Докажете, че съществуват три пермутации a1,a2,…,aNa_1,a_2,\ldots,a_N; b1,b2,…,bNb_1,b_2,\ldots,b_N; и c1,c2,…,cNc_1,c_2,\ldots,c_N на 1,2,…,N1,2,\ldots,N, такива че∣x2ak+x2bk+x2ck−2N∣<2023\left|\sqrt{\vphantom{x^2}a_k}+\sqrt{\vphantom{x^2}b_k}+\sqrt{\vphantom{x^2}c_k}-2\sqrt N\right|\lt{}2023за всяко k=1,2,…,Nk=1,2,\ldots,N.
РешениеЗа N=1N=1 твърдението е очевидно, затова нека N≥2N\ge2. Ще използваме следното просто закръгляне: числатаr2−r+1,r2−r+2,…,r2+rr^2-r+1,r^2-r+2,\ldots,r^2+rимат квадратни корени на разстояние по-малко от 0.50.5 от rr. Така квадратните корени на числата 1,2,…,N1,2,\ldots,N могат да се заменят с най-близките цели числа, като грешката във всеки член е по-малка от 0.50.5. За мултимножество ще пишем rsr^s за ss копия на rr. ДефинирамеTm,n={11,22,…,mm,(m+1)n}T_{m,n}=\{1^1,2^2,\ldots,m^m,(m+1)^n\}\qquad(0≤n≤m+1).(0\le n\le m+1).Ще докажем следното твърдение. За всяко m≥1m\ge1 и 0≤n≤m+10\le n\le m+1 съществуват три пермутации (uk),(vk),(wk)(u_k),(v_k),(w_k) на елементите на Tm,nT_{m,n}, такива че сумите uk+vk+wku_k+v_k+w_k са:2m+1ако n=0,2m+1\quad\text{ако }n=0,принадлежат на множеството {2m+1,2m+2,2m+3}\{2m+1,2m+2,2m+3\}, ако 1≤n≤m1\le n\le m, и са2m+3ако n=m+1.2m+3\quad\text{ако }n=m+1.Доказателството е по индукция по mm. Случаите n=0n=0 и n=m+1n=m+1 се получават от една и съща конструкция: за Tm,0={11,22,…,mm}T_{m,0}=\{1^1,2^2,\ldots,m^m\} има три пермутации с константна сума 2m+12m+1. При m=1m=1 това е 1+1+1=31+1+1=3, а преходът се прави така. Ако имаме конструкция за Tm−1,0T_{m-1,0} със сума 2m−12m-1, тоTm,0=Tm−1,0∪{mm}=T_{m,0}=T_{m-1,0}\cup\{m^m\}=(Tm−1,0+1)∪{1,2,…,m}.(T_{m-1,0}+1)\cup\{1,2,\ldots,m\}.Към старите колони прибавяме 11 във втория и третия ред, а новите mm колони избираме катоm+r+(m+1−r)=2m+1(1≤r≤m).m+r+(m+1-r)=2m+1\qquad(1\le r\le m).Това дава трите нужни пермутации. Случаят n=m+1n=m+1 е същият, приложен към Tm+1,0T_{m+1,0}. Остава случаят 1≤n≤m1\le n\le m. Използваме разлаганетоTm,n=Tm−1,n∪{mm−n,(m+1)n}=T_{m,n}=T_{m-1,n}\cup\{m^{m-n},(m+1)^n\}=(Tm−1,n+1)∪{1,2,…,m}.(T_{m-1,n}+1)\cup\{1,2,\ldots,m\}.По индукционното предположение има три пермутации на Tm−1,nT_{m-1,n} със суми в {2m−1,2m,2m+1}\{2m-1,2m,2m+1\}. За старите колони оставяме първия ред същия, а към втория и третия добавяме 11; сумите стават в {2m+1,2m+2,2m+3}\{2m+1,2m+2,2m+3\}. За новите mm колони, при r=1,2,…,mr=1,2,\ldots,m, вземаме втори и трети елемент rr и m+1−rm+1-r, а първия елемент вземаме mm за първите m−nm-n стойности на rr и m+1m+1 за последните nn стойности. Получените суми отново са в {2m+1,2m+2}\{2m+1,2m+2\}. Така индукцията е завършена. Сега избираме mm, така чеm(m+1)≤N<(m+1)(m+2),m(m+1)\le N\lt{}(m+1)(m+2),и пишем N=m(m+1)+tN=m(m+1)+t, където 0≤t≤2m+10\le t\le2m+1. Мултимножеството от най-близките цели числа до 1,2,…,N\sqrt1,\sqrt2,\ldots,\sqrt N е{12,24,…,m2m,(m+1)t}.\{1^2,2^4,\ldots,m^{2m},(m+1)^t\}.Некаn1=⌊t2⌋,n2=⌈t2⌉.n_1=\left\lfloor\frac{t}{2}\right\rfloor,\qquad n_2=\left\lceil\frac{t}{2}\right\rceil.Тогава това мултимножество е обединение на Tm,n1T_{m,n_1} и Tm,n2T_{m,n_2}. Прилагаме доказаното твърдение към двете части и съединяваме получените колони. Така получаваме три пермутации на закръглените стойности, за които всяка сума е между 2m+12m+1 и 2m+32m+3. Заменяме всяко закръглено число с различно число от 1,2,…,N1,2,\ldots,N, което се закръгля до него. Това дава три пермутации ak,bk,cka_k,b_k,c_k на 1,2,…,N1,2,\ldots,N. Понеже всяка от трите квадратнокоренни стойности се различава от закръглената си стойност с по-малко от 0.50.5, получаваме2m+1−1.5<2m+1-1.5\lt{}x2ak+x2bk+x2ck<2m+3+1.5.\sqrt{\vphantom{x^2}a_k}+\sqrt{\vphantom{x^2}b_k}+\sqrt{\vphantom{x^2}c_k}\lt{}2m+3+1.5.От m<N<m+2m\lt{}\sqrt N\lt{}m+2 следва2N−4.5<x2ak+x2bk+x2ck<2N+4.5.2\sqrt N-4.5\lt{}\sqrt{\vphantom{x^2}a_k}+\sqrt{\vphantom{x^2}b_k}+\sqrt{\vphantom{x^2}c_k}\lt{}2\sqrt N+4.5.Следователно∣x2ak+x2bk+x2ck−2N∣<4.5<2023\left|\sqrt{\vphantom{x^2}a_k}+\sqrt{\vphantom{x^2}b_k}+\sqrt{\vphantom{x^2}c_k}-2\sqrt N\right|\lt{}4.5\lt{}2023за всяко kk, както се искаше.
Отвори задачатаMathNetISL 2023 A7Условие — източник

Задача C1

Пълен запис
Условие
Нека mm и nn са положителни цели числа, по-големи от 11. Във всяка клетка на дъска m×nm\times n лежи монета с ези нагоре. Един ход се състои от следното: избираме квадрат 2×22\times2, обръщаме монетите в горната лява и долната дясна клетка и обръщаме още една от монетите в горната дясна или долната лява клетка. Да се намерят всички двойки (m,n)(m,n), за които е възможно след краен брой ходове всички монети да са с тура нагоре.
РешениеОтговорът е: точно двойките (m,n)(m,n), за които 3∣mn3\mid mn. Първо нека 3∣m3\mid m; случаят 3∣n3\mid n е симетричен. Номерираме редовете и стълбовете от 11. Ако nn е четно, за всяко 1≤k≤m/31\le k\le m/3 и 1≤l≤n/21\le l\le n/2 правим два хода върху блоковете с горен ляв ъгъл (3k−2,2l−1)(3k-2,2l-1) и (3k−1,2l−1)(3k-1,2l-1): в първия обръщаме горна лява, долна дясна и горна дясна клетка, а във втория - горна лява, долна дясна и долна лява клетка. Така всяка монета се обръща точно веднъж. Ако nn е нечетно, правим същото за първите n−1n-1 стълба; остава последният стълб. За всяко kk три подходящи хода в последните два стълба обръщат точно клетките (3k−2,n),(3k−1,n),(3k,n)(3k-2,n),(3k-1,n),(3k,n), така че отново всички монети се обръщат веднъж. За необходимостта оцветяваме клетката (i,j)(i,j) с остатъка на i+j−2i+j-2 по модул 33. Всеки ход обръща по една клетка от всеки от трите цвята. Следователно паритетите на броевете обърнати монети във всеки цвят винаги остават еднакви. В началото тези три паритета са равни на 00, а в крайната конфигурация са равни на броевете клетки от трите цвята. Лесна проверка по остатъците на mm и nn по модул 33 показва, че тези три броя имат един и същи паритет точно когато 3∣mn3\mid mn. Следователно условието е необходимо и достатъчно.
Отвори задачатаMathNetISL 2023 C1Условие — източник

Задача C2

Пълен запис
Условие
Да се определи най-голямата дължина LL на редица a1,…,aLa_1,\ldots,a_L от положителни цели числа със следните две свойства: всеки член е най-много 220232^{2023} и не съществува блок от последователни членове ai,ai+1,…,aja_i,a_{i+1},\ldots,a_j, за който могат да се изберат знаци si,si+1,…,sj∈{1,−1}s_i,s_{i+1},\ldots,s_j\in\{1,-1\} така, че siai+si+1ai+1+⋯+sjaj=0.s_i a_i+s_{i+1}a_{i+1}+\cdots+s_j a_j=0.
РешениеОтговорът е L=22024−1L=2^{2024}-1. Ще докажем по-общо, че при горна граница 2k2^k максимумът е 2k+1−12^{k+1}-1. Нека n=2kn=2^k. За построение вземаме редицата с дължина 2n−12n-1, зададена чрезai=2k−v2(i)(1≤i≤2n−1),a_i=2^{k-v_2(i)}\qquad(1\le i\le2n-1),където v2(i)v_2(i) е показателят на най-високата степен на 22, деляща ii. Във всеки интервал от последователни индекси има единствен индекс xx, за който v2(x)v_2(x) е максимален; следователно axa_x не се дели на два пъти по-голямата степен на 22, докато всички останали членове в интервала се делят на нея. Затова никаква подписана сума върху този интервал не може да е 00. Остава горната граница. Нека a1,…,aLa_1,\ldots,a_L е произволна редица с ai≤na_i\le n. Избираме знаци рекурсивно: ако текущата частична сума е най-много 00, вземаме следващия знак +1+1, а ако е поне 11, вземаме −1-1. Получените частични суми b0=0,b1,…,bLb_0=0,b_1,\ldots,b_L винаги лежат в интервала [−n+1,n][-n+1,n], който съдържа точно 2n2n цели числа. Ако L≥2nL\ge2n, две от тези L+1L+1 частични суми съвпадат; разликата им дава забранен блок с подписана сума 00. Следователно L≤2n−1L\le2n-1, което за n=22023n=2^{2023} дава 22024−12^{2024}-1.
Отвори задачатаMathNetISL 2023 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека nn е положително цяло число. Подреждаме 1+2+⋯+n1+2+\cdots+n кръгчета в триъгълник с nn реда, като ii-тият ред съдържа точно ii кръгчета. Нинджа-път е редица от кръгчета, получена чрез многократно слизане от дадено кръгче към едно от двете кръгчета непосредствено под него. В зависимост от nn да се намери най-голямото kk, за което при всяко оцветяване на по едно кръгче от всеки ред в червено съществува нинджа-път, съдържащ поне kk червени кръгчета.
РешениеОтговорът еk=1+⌊log⁡2n⌋.k=1+\lfloor\log_2 n\rfloor.Нека N=⌊log⁡2n⌋N=\lfloor\log_2 n\rfloor, така че 2N≤n<2N+12^N\le n\lt{}2^{N+1}. Първо ще покажем, че не може да се гарантира повече от N+1N+1. За всеки ред i=2a+bi=2^a+b, където 0≤a≤N0\le a\le N и 0≤b<2a0\le b\lt{}2^a, оцветяваме в червено кръгчето с номер 2b+12b+1 в този ред. Един нинджа-път може да попадне в най-много едно червено кръгче сред редовете 2a,2a+1,…,2a+1−12^a,2^a+1,\ldots,2^{a+1}-1 за всяко фиксирано aa, така че съдържа най-много N+1N+1 червени кръгчета. За обратната посока на всяко кръгче CC приписваме максималния брой червени кръгчета по нинджа-път от върха до CC. Ако ред rr има приписани числа със сума σr\sigma_r, ще докажем по индукция, чеσ2j≥j2j+1(0≤j≤N).\sigma_{2^j}\ge j2^j+1\qquad(0\le j\le N).За j=0j=0 това е вярно. Ако е вярно за 2j2^j, то в този ред има кръгче с приписано число поне j+1j+1. При преминаване към следващ ред сумата на приписаните числа нараства поне с този максимум и още с 11, защото в новия ред има едно червено кръгче. Следователно за всеки от следващите 2j2^j прехода сумата нараства поне с j+2j+2, откъдетоσ2j+1≥j2j+1+2j(j+2)=(j+1)2j+1+1.\sigma_{2^{j+1}}\ge j2^j+1+2^j(j+2)=(j+1)2^{j+1}+1.При j=Nj=N някое кръгче в ред 2N2^N има стойност поне N+1N+1, т.е. има нинджа-път с поне N+1N+1 червени кръгчета.
Отвори задачатаMathNetISL 2023 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека n≥2n\ge2 е положително цяло число. Павел има правоъгълна лента 1×n21\times n^2 от n2n^2 единични квадратчета, като ii-тото квадратче е означено с ii за всяко 1≤i≤n21\le i\le n^2. Той иска да нареже лентата на няколко части, всяка от които се състои от последователни квадратчета, и след това чрез преместване без завъртане и обръщане да получи квадрат n×nn\times n със следното свойство: ако квадратчето в ii-тия ред и jj-тия стълб е означено с aija_{ij}, то aij−(i+j−1)a_{ij}-(i+j-1) се дели на nn. Да се намери най-малкият възможен брой части.
РешениеОтговорът е 2n−12n-1. Конструкция с 2n−12n-1 части се получава например чрез разрязване на лентата на части с дължиниn,1,n,1,…,n,1,1,n,1,n,1,\ldots,n,1,1,като частите с дължина 11 се поставят в последния ред; директно се проверява, че остатъците по модул nn са правилни. За оптималността ще разгледаме обратния процес. Имаме nn хоризонтални ленти с дължина nn, като kk-тата съдържа остатъците k,k+1,…,k+n−1k,k+1,\ldots,k+n-1 по модул nn, и искаме да ги разрежем и подредим в една лента. Всяко получено парче от вида a,a+1,…,b−1a,a+1,\ldots,b-1 представяме като ребро от aa към bb в мултиграф с върхове 1,…,n1,\ldots,n по модул nn. Парчетата от първоначалната kk-та лента образуват цикъл γk\gamma_k, минаващ през върха kk. Понеже всички парчета могат да се подредят в една дълга лента, графът има ейлеров цикъл и е свързан. Избираме по едно ребро от всеки цикъл γk\gamma_k и го изтриваме. Тези цикли нямат общи ребра и свързаността не се нарушава. Останалият граф е свързан, следователно има поне n−1n-1 ребра. Преди изтриването е имало още nn ребра, т.е. общо поне 2n−12n-1 парчета.
Отвори задачатаMathNetISL 2023 C4Условие — източник

Задача C5

Пълен запис
Условие
Елиза има 20232023 сандъка със съкровища, като в началото всички са отключени и празни. Всеки ден Елиза добавя един нов скъпоценен камък в един отключен сандък по свой избор; след това фея действа по следните правила: ако има повече от един отключен сандък, тя заключва един от тях, а ако има само един отключен сандък, отключва всички сандъци. Да се докаже, че съществува константа CC със следното свойство: Елиза може да гарантира, че разликата между броя камъни във всеки два сандъка никога не надхвърля CC, независимо как феята избира кои сандъци да заключва.
РешениеЩе докажем по-общо твърдение за nn сандъка. Достатъчна е константа C=3n(n−1)+nC=3n(n-1)+n; за задачата вземаме n=2023n=2023. Елиза играе на блокове от по nn дни. В началото на всеки блок тя номерира сандъците C1,…,CnC_1,\ldots,C_n така, че броят камъни в тях е ненамаляващ, и през следващите nn дни винаги поставя камъка в отключения сандък с най-малък номер. Нека c1t≤⋯≤cntc_1^t\le\cdots\le c_n^t са броевете камъни в началото на tt-тия блок, а δit\delta_i^t - броят камъни, добавени в CiC_i през блока. Тогаваδ1t+⋯+δkt≥k(1≤k≤n),\delta_1^t+\cdots+\delta_k^t\ge k\qquad(1\le k\le n),защото преди да може да се пренебрегне някой от първите kk сандъка, всички те трябва да са заключени. Сравняваме (cit)(c_i^t) с редицатаdit=3n(i−n+12)+t.d_i^t=3n\left(i-\frac{n+1}{2}\right)+t.Двете редици имат една и съща сума ntnt. По индукция по tt се проверява, че (dit)(d_i^t) мажорира (cit)(c_i^t): ако след добавянията първите kk най-малки елемента идват от първите kk стари сандъка, неравенството следва веднага от δ1t+⋯+δkt≥k\delta_1^t+\cdots+\delta_k^t\ge k; иначе някой от първите kk е изпреварил някой следващ, а празнината di+1t−dit=3nd_{i+1}^t-d_i^t=3n дава нужния резерв. Следователноcnt−c1t≤dnt−d1t=3n(n−1)c_n^t-c_1^t\le d_n^t-d_1^t=3n(n-1)в началото на всеки блок. В рамките на един блок се добавят само nn камъка, така че разликата никога не надхвърля 3n(n−1)+n3n(n-1)+n.
Отвори задачатаMathNetISL 2023 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека NN е положително цяло число и да разгледаме дъска N×NN\times N. Десно-надолу път е редица от клетки, при която всяка следваща клетка е или една клетка надясно, или една клетка надолу от предишната. Десно-нагоре път е редица от клетки, при която всяка следваща клетка е или една клетка надясно, или една клетка нагоре от предишната. Докажете, че клетките на дъската N×NN\times N не могат да се разбият на по-малко от NN десно-надолу или десно-нагоре пътища.
РешениеЩе докажем твърдението с индукция по NN. За N=1N=1 е очевидно. Нека N≥2N\ge2 и да имаме разбиване на дъската N×NN\times N. Нека PP е пътят, който съдържа горния ляв ъгъл. Ако PP е десно-нагоре път, той лежи само в най-горния ред и най-левия стълб. Останалата долна дясна поддъска (N−1)×(N−1)(N-1)\times(N-1) по индукционното предположение изисква поне N−1N-1 пътища, различни от PP, така че общо имаме поне NN. Остава случаят, когато PP е десно-надолу път. Ще го разширим до десно-надолу път QQ, стигащ до долния десен ъгъл, като при всяко разширение добавяме крайна част от друг път или две съседни клетки от десно-нагоре път. Нека AA е последната клетка на текущия QQ, а BB и CC са клетките под и вдясно от AA, когато съществуват. Ако AA не е долният десен ъгъл, поне една от допустимите операции позволява да добавим клетки след AA така, че QQ да остане десно-надолу път и отново да няма непосредствено продължение в същия стар път. Процесът завършва в долния десен ъгъл. Премахваме QQ и слепваме двете останали части на дъската по естествения диагонален разрез; получаваме дъска (N−1)×(N−1)(N-1)\times(N-1). Всеки стар път, който среща QQ, след премахването му остава десно-надолу или десно-нагоре път, защото добавянето на QQ е било направено само чрез крайни части или чрез две съседни клетки, които след слепването се свързват коректно. Следователно получаваме разбиване на дъска (N−1)×(N−1)(N-1)\times(N-1), което по индукция използва поне N−1N-1 пътища. Заедно с първоначалния път, съдържащ се в QQ, това дава поне NN пътища.
Отвори задачатаMathNetISL 2023 C6Условие — източник

Задача C7

Пълен запис
Условие
Архипелагът Имомия се състои от n≥2n\ge2 острова. Между всеки два различни острова има единствена фериботна линия в двете посоки, а всяка линия се обслужва от една от kk компании. Известно е, че ако която и да е от kk-те компании спре всичките си линии, става невъзможно пътешественик, независимо от началния остров, да посети всички острови точно по веднъж. Да се определи най-голямата възможна стойност на kk в зависимост от nn.
РешениеОтговорът е k=⌊log⁡2n⌋k=\lfloor\log_2 n\rfloor. Превеждаме задачата на езика на пълния граф KnK_n: ребрата са оцветени с kk цвята и всеки хамилтонов път трябва да съдържа ребро от всеки цвят. Конструкция. Нека k=⌊log⁡2n⌋k=\lfloor\log_2 n\rfloor и върховете са 1,2,…,n1,2,\ldots,n. Оцветяваме върха ii с цвят min⁡(⌊log⁡2i⌋+1,k)\min(\lfloor\log_2 i\rfloor+1,k), а реброто ijij при i<ji\lt{}j - с цвета на по-малкия връх ii. Върховете с цвят kk са поне n/2+1n/2+1, затова всеки хамилтонов път има ребро между два такива върха и то е с цвят kk. Ако липсва цвят r<kr\lt{}k в някой хамилтонов път, тогава върховете с цвят rr могат да са съседни само на върхове с по-малък цвят. Но върховете с цвят rr са 2r−12^{r-1}, а върховете с по-малък цвят са 2r−1−12^{r-1}-1, което не стига да ги раздели в път. Противоречие. За горната граница започваме от произволно добро оцветяване. Чрез следната операция можем да опростим оцветяването, без да го развалим: ако реброто ABAB е с цвят jj, а при AA най-често срещаният цвят е i≠ji\ne j и не по-рядък от най-честия цвят при BB, пребоядисваме ABAB в цвят ii. Ако това унищожава добротата, съществува хамилтонов път, в който ABAB е единственото ребро с цвят jj; пренареждането на пътя показва, че броят на ребрата с цвят jj около AA и BB е поне nn, противоречие с избора. Повтаряйки операцията, стигаме до подредба A1,…,AnA_1,\ldots,A_n и цветове c1,…,cnc_1,\ldots,c_n, така че всяко ребро AuAvA_uA_v при u<vu\lt{}v има цвят cuc_u, а оцветяването пак е добро. За всеки цвят rr трябва да има индекс pp такъв, че сред A1,…,ApA_1,\ldots,A_p върховете с цвят rr са повече от p/2p/2; иначе можем да редуваме върховете с цвят rr с всички останали и да получим хамилтонов път без ребро от този цвят. Нека prp_r е най-малкият такъв индекс и ги подредим p1<⋯<pkp_1\lt{}\cdots\lt{}p_k. Тогава индуктивноpi≥2i−1.p_i\ge2^i-1.Ако n=2k−1n=2^k-1, всички неравенства са равенства и цветовите блокове имат размери 1,2,4,…,2k−11,2,4,\ldots,2^{k-1}; тогава може да се построи хамилтонов път без последния цвят, противоречие. Значи n≥2kn\ge2^k, т.е. k≤⌊log⁡2n⌋k\le\lfloor\log_2 n\rfloor.
Отвори задачатаMathNetISL 2023 C7Условие — източник

Задача N1

Пълен запис
Условие
Да се намерят всички положителни съставни числа nn със следното свойство: ако положителните делители на nn са1=d1<d2<⋯<dk=n,1=d_1\lt{}d_2\lt{}\cdots\lt{}d_k=n,то did_i дели di+1+di+2d_{i+1}+d_{i+2} за всяко 1≤i≤k−21\le i\le k-2.
РешениеОтговорът е: всички числа от вида prp^r, където pp е просто число и r≥2r\ge2. Най-напред, ако n=prn=p^r с r≥2r\ge2, тогава делителите са 1,p,p2,…,pr1,p,p^2,\ldots,p^r и за всяко допустимо ii имамеpi−1∣pi+pi+1,p^{i-1}\mid p^i+p^{i+1},така че тези числа наистина удовлетворяват условието. Нека сега nn удовлетворява условието. Понеже didk+1−i=nd_i d_{k+1-i}=n, за всяко 1≤i≤k−21\le i\le k-2 условието, приложено към делителите от края на списъка, даваndi+2∣ndi+1+ndi.\frac{n}{d_{i+2}}\mid \frac{n}{d_{i+1}}+\frac{n}{d_i}.След умножаване по didi+1di+2d_i d_{i+1}d_{i+2} и съкращаване на nn получавамеdidi+1∣didi+2+di+1di+2,d_i d_{i+1}\mid d_i d_{i+2}+d_{i+1}d_{i+2},откъдето в частностdi∣di+1di+2.(1)d_i\mid d_{i+1}d_{i+2}.\tag{1}От първоначалното условие също имамеdi∣di+1(di+1+di+2)=di+12+di+1di+2.d_i\mid d_{i+1}(d_{i+1}+d_{i+2})=d_{i+1}^2+d_{i+1}d_{i+2}.Заедно с (1) това даваdi∣di+12(2)d_i\mid d_{i+1}^2\tag{2}за всички 1≤i≤k−21\le i\le k-2. Нека d2=pd_2=p е най-малкият прост делител на nn. Ще докажем по индукция, че p∣dip\mid d_i за всяко 2≤i≤k−12\le i\le k-1. Базата i=2i=2 е ясна. Ако p∣djp\mid d_j за някое 2≤j≤k−22\le j\le k-2, то от (2) следваp∣dj∣dj+12,p\mid d_j\mid d_{j+1}^2,а понеже pp е просто, получаваме p∣dj+1p\mid d_{j+1}. Индукцията е завършена. Ако nn имаше друг прост делител q≠pq\ne p, то qq щеше да е един от делителите d2,d3,…,dk−1d_2,d_3,\ldots,d_{k-1}, следователно p∣qp\mid q, невъзможно. Значи nn има само един прост делител, тоест n=prn=p^r. Понеже nn е съставно, r≥2r\ge2.
Отвори задачатаMathNetISL 2023 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се намерят всички двойки (a,p)(a,p) от положителни цели числа, където pp е просто число, такива чеpa+a4p^a+a^4е точен квадрат.
РешениеОтговорът е(a,p)=(1,3),(2,3),(6,3),(9,3).(a,p)=(1,3),(2,3),(6,3),(9,3).Некаpa+a4=b2p^a+a^4=b^2за някое положително цяло число bb. Тогаваpa=b2−a4=(b+a2)(b−a2).p^a=b^2-a^4=(b+a^2)(b-a^2).Следователно двата множителя са степени на pp. Пишемb−a2=px,b+a2=pa−x,b-a^2=p^x,\qquad b+a^2=p^{a-x},където a−x>xa-x\gt{}x. Изваждането дава2a2=px(pa−2x−1).(1)2a^2=p^x\bigl(p^{a-2x}-1\bigr).\tag{1}Първо нека p=2p=2. Тогава от (1) получавамеa2=2x−1(2a−2x−1).a^2=2^{x-1}\bigl(2^{a-2x}-1\bigr).Вторият множител е нечетен, следователноx−1=2v2(a)x-1=2v_2(a)и 2a−2x−12^{a-2x}-1 е квадрат. Ако v2(a)>0v_2(a)\gt{}0, то aa е четно и 2a−2x2^{a-2x} също е квадрат; тогава два квадрата се различават с 11, което принуждава 2a−2x=12^{a-2x}=1 и после a=0a=0, невъзможно. Ако v2(a)=0v_2(a)=0, то x=1x=1 иa2=2a−2−1.a^2=2^{a-2}-1.За a≥4a\ge4 дясната страна е 33 по модул 44, а малките стойности a=1,2,3a=1,2,3 не дават решение. Значи при p=2p=2 решения няма. Остава pp да е нечетно. В (1) вторият множител не се дели на pp, затова x=2vp(a)x=2v_p(a). Нека m=vp(a)m=v_p(a) и a=pmna=p^m n, където p∤np\nmid n. След деление на p2mp^{2m} получаваме2n2+1=ppmn−4m.(2)2n^2+1=p^{p^m n-4m}.\tag{2}Ако p≥5p\ge5, то pm>4mp^m\gt{}4m. При n≥3n\ge3 от (2) следва2n2+1=ppmn−4m>ppm(n−1)≥5n−1,2n^2+1=p^{p^m n-4m}\gt{}p^{p^m(n-1)}\ge5^{n-1},което е невъзможно, понеже 5n−1>2n2+15^{n-1}\gt{}2n^2+1 за n≥3n\ge3. Следователно n=1n=1 или n=2n=2, но тогава 2n2+12n^2+1 е съответно 33 или 99, което принуждава p=3p=3, противоречие. Значи няма решения с p≥5p\ge5. Нека p=3p=3. Ако m≥2m\ge2 и n≥2n\ge2, то 3m>4m3^m\gt{}4m и от (2) получаваме2n2+1=33mn−4m>33m(n−1)≥39(n−1)>2n2+1,2n^2+1=3^{3^m n-4m}\gt{}3^{3^m(n-1)}\ge3^{9(n-1)}\gt{}2n^2+1,противоречие. Значи при m≥2m\ge2 трябва n=1n=1. Тогава 3=33m−4m3=3^{3^m-4m}, тоест 3m−4m=13^m-4m=1, откъдето m=2m=2 и a=9a=9. Ако m=1m=1, то (2) става2n2+1=33n−4.2n^2+1=3^{3n-4}.За n≥3n\ge3 дясната страна е по-голяма от лявата, а проверката на n=1,2n=1,2 дава единствено n=2n=2, тоест a=6a=6. Ако m=0m=0, то2n2+1=3n.2n^2+1=3^n.Отново за n≥3n\ge3 дясната страна е по-голяма от лявата, а n=1,2n=1,2 дават a=1,2a=1,2. Проверка показва, че (1,3)(1,3), (2,3)(2,3), (6,3)(6,3) и (9,3)(9,3) наистина удовлетворяват условието. Това са всички решения.
Отвори задачатаMathNetISL 2023 N2Условие — източник

Задача N3

Пълен запис
Условие
За положителни цели числа nn и k≥2k\ge2 нека Ek(n)E_k(n) е най-големият показател rr, за който krk^r дели n!n!. Докажете, че има безкрайно много nn, за коитоE10(n)>E9(n),E_{10}(n)\gt{}E_9(n),и безкрайно много mm, за коитоE10(m)<E9(m).E_{10}(m)\lt{}E_9(m).
РешениеЩе използваме формулата на Льожандрvp(N!)=⌊Np⌋+⌊Np2⌋+⋯v_p(N!)=\left\lfloor\frac Np\right\rfloor+\left\lfloor\frac N{p^2}\right\rfloor+\cdotsза просто pp. ИмамеE9(N)=⌊v3(N!)2⌋,E_9(N)=\left\lfloor\frac{v_3(N!)}2\right\rfloor,а понеже v5(N!)≤v2(N!)v_5(N!)\le v_2(N!),E10(N)=v5(N!).E_{10}(N)=v_5(N!).Нека ll е произволно положително цяло число и поставимn=52l−1.n=5^{2l-1}.ТогаваE10(n)=v5(n!)=52l−2+52l−3+⋯+5+1=n−14.E_{10}(n)=v_5(n!)=5^{2l-2}+5^{2l-3}+\cdots+5+1=\frac{n-1}{4}.Понеже n≡2(mod3)n\equiv2\pmod3, имаме⌊n3⌋=n−23.\left\lfloor\frac n3\right\rfloor=\frac{n-2}{3}.Следователноv3(n!)<n−23+n32+n33+⋯=n2−23,v_3(n!)\lt{}\frac{n-2}{3}+\frac n{3^2}+\frac n{3^3}+\cdots=\frac n2-\frac23,и затоваE9(n)≤v3(n!)2<n4−13<n4−14=E10(n).E_9(n)\le\frac{v_3(n!)}2\lt{}\frac n4-\frac13\lt{}\frac n4-\frac14=E_{10}(n).Така получаваме безкрайно много стойности с E10(n)>E9(n)E_{10}(n)\gt{}E_9(n). Сега поставямеm=34l−2.m=3^{4l-2}.Тогаваv3(m!)=34l−3+34l−4+⋯+3+1=m−12.v_3(m!)=3^{4l-3}+3^{4l-4}+\cdots+3+1=\frac{m-1}{2}.Понеже m≡1(mod4)m\equiv1\pmod4, получавамеE9(m)=⌊v3(m!)2⌋=m−14.E_9(m)=\left\lfloor\frac{v_3(m!)}2\right\rfloor=\frac{m-1}{4}.От друга страна m≡4(mod5)m\equiv4\pmod5, така че⌊m5⌋=m−45.\left\lfloor\frac m5\right\rfloor=\frac{m-4}{5}.СледователноE10(m)=v5(m!)<E_{10}(m)=v_5(m!)\lt{}m−45+m52+m53+⋯=m4−45<m−14=E9(m).\frac{m-4}{5}+\frac m{5^2}+\frac m{5^3}+\cdots=\frac m4-\frac45\lt{}\frac{m-1}{4}=E_9(m).Има безкрайно много такива mm, което завършва доказателството.
Отвори задачатаMathNetISL 2023 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека a1,a2,…,an,b1,b2,…,bna_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n са 2n2n положителни цели числа, такива че n+1n+1 произведенияa1a2a3⋯an,b1a2a3⋯an,b1b2a3⋯an,⋮b1b2b3⋯bn\begin{gathered} a_1a_2a_3\cdots a_n,\\ b_1a_2a_3\cdots a_n,\\ b_1b_2a_3\cdots a_n,\\ \vdots\\ b_1b_2b_3\cdots b_n \end{gathered}образуват строго растяща аритметична прогресия в този ред. Да се определи най-малката положителна стойност, която може да има разликата на такава аритметична прогресия.
РешениеОтговорът е n!n!. Нека DD е общата разлика. Условието е еквивалентно наD=(b1−a1)a2a3⋯an=b1(b2−a2)a3⋯an=D=(b_1-a_1)a_2a_3\cdots a_n=b_1(b_2-a_2)a_3\cdots a_n=⋯=b1b2⋯bn−1(bn−an).\cdots=b_1b_2\cdots b_{n-1}(b_n-a_n).Понеже прогресията е строго растяща, D>0D\gt{}0, следователно bi>aib_i\gt{}a_i за всяко ii. Ако за някое ii числата aia_i и bib_i имат общ делител g>1g\gt{}1, то можем да заменим едновременно aia_i и bib_i с ai/ga_i/g и bi/gb_i/g. Всички членове на прогресията, а значи и общата разлика, се делят на gg. Затова при търсене на най-малката възможна разлика можем да приемем, чеgcd⁡(ai,bi)=1(1≤i≤n).\gcd(a_i,b_i)=1\qquad(1\le i\le n).От равенството на съседните изрази за DD получаваме(bi−ai)ai+1=bi(bi+1−ai+1)(b_i-a_i)a_{i+1}=b_i(b_{i+1}-a_{i+1})\qquad(1≤i≤n−1).(1)(1\le i\le n-1).\tag{1}Понежеgcd⁡(bi−ai,bi)=gcd⁡(ai,bi)=1\gcd(b_i-a_i,b_i)=\gcd(a_i,b_i)=1иgcd⁡(ai+1,bi+1−ai+1)=gcd⁡(ai+1,bi+1)=1,\gcd(a_{i+1},b_{i+1}-a_{i+1})=\gcd(a_{i+1},b_{i+1})=1,от (1) следва, че ai+1=bia_{i+1}=b_i и bi+1−ai+1=bi−aib_{i+1}-a_{i+1}=b_i-a_i. Следователноa1,b1=a2,b2=a3,…,bn−1=an,bna_1,b_1=a_2,b_2=a_3,\ldots,b_{n-1}=a_n,b_nе аритметична прогресия с положителна разлика. Понеже a1≥1a_1\ge1, получаваме ai≥ia_i\ge i за всяко 1≤i≤n1\le i\le n. ЗатоваD=(b1−a1)a2a3⋯an≥1⋅2⋅3⋯n=n!.D=(b_1-a_1)a_2a_3\cdots a_n\ge1\cdot2\cdot3\cdots n=n!.Равенство се достига при ai=ia_i=i и bi=i+1b_i=i+1 за всяко i=1,2,…,ni=1,2,\ldots,n. Тогава общата разлика е точно n!n!. Следователно най-малката възможна стойност е n!n!.
Отвори задачатаMathNetISL 2023 N4Условие — източник

Задача N5

Пълен запис
Условие
Некаa1<a2<a3<⋯a_1\lt{}a_2\lt{}a_3\lt{}\cdotsса положителни цели числа, такива че ak+1a_{k+1} дели 2(a1+a2+⋯+ak)2(a_1+a_2+\cdots+a_k) за всяко k≥1k\ge1. Да предположим, че за безкрайно много прости числа pp съществува kk, за което pp дели aka_k. Докажете, че за всяко положително цяло число nn съществува kk, за което nn дели aka_k.
РешениеЗа всяко k≥2k\ge2 дефинирамеbk=2(a1+a2+⋯+ak−1)ak.b_k=\frac{2(a_1+a_2+\cdots+a_{k-1})}{a_k}.По условие bkb_k е положително цяло число. Първо ще докажем две свойства на редицата (bk)(b_k). От равенстватаbkak=2(a1+⋯+ak−1),b_k a_k=2(a_1+\cdots+a_{k-1}),bk+1ak+1=2(a1+⋯+ak)b_{k+1}a_{k+1}=2(a_1+\cdots+a_k)получавамеbk+1ak+1=bkak+2ak=(bk+2)ak.b_{k+1}a_{k+1}=b_ka_k+2a_k=(b_k+2)a_k.Тъй като ak<ak+1a_k\lt{}a_{k+1}, следва bk+1<bk+2b_{k+1}\lt{}b_k+2, а понеже bk+1b_{k+1} е цяло,bk+1≤bk+1.(1)b_{k+1}\le b_k+1.\tag{1}Освен това редицата (bk)(b_k) е неограничена. Наистина, ако bk≤Bb_k\le B за всички kk, то отbk+1ak+1=(bk+2)akb_{k+1}a_{k+1}=(b_k+2)a_kследва, че всеки нов прост делител на ak+1a_{k+1} или вече дели aka_k, или дели някое число, ненадминаващо B+2B+2. Тогава простите делители на всички членове aka_k биха били измежду краен брой прости числа: тези, които делят a1a_1 или a2a_2, и простите числа не по-големи от B+2B+2. Това противоречи на условието, че безкрайно много прости числа делят някой член на редицата. Нека сега nn е произволно положително цяло число. Ако е нужно, заменяме nn с негово кратно, по-голямо от b2b_2; достатъчно е да докажем твърдението за това кратно. Понеже (bk)(b_k) е неограничена, съществува най-малък индекс kk, за койтоbk+1≥n.b_{k+1}\ge n.От n>b2n\gt{}b_2 следва k≥2k\ge2. По минималност bk<nb_k\lt{}n, а от (1) получаваме bk+1≤bk+1b_{k+1}\le b_k+1. Затова непременноbk=n−1,bk+1=n.b_k=n-1,\qquad b_{k+1}=n.Сега равенствотоbk+1ak+1=(bk+2)akb_{k+1}a_{k+1}=(b_k+2)a_kставаak+1=ak⋅n+1n.a_{k+1}=a_k\cdot\frac{n+1}{n}.Понеже gcd⁡(n,n+1)=1\gcd(n,n+1)=1, това е възможно само ако n∣akn\mid a_k. Следователно за всяко положително цяло число nn някой член aka_k се дели на nn.
Отвори задачатаMathNetISL 2023 N5Условие — източник

Задача N6

Пълен запис
Условие
Една редица от цели числа a0,a1,a2,…a_0,a_1,a_2,\ldots се нарича кавай, ако a0=0a_0=0, a1=1a_1=1 и за всяко положително цяло число nn е изпълнено(an+1−3an+2an−1)(an+1−4an+3an−1)=0.(a_{n+1}-3a_n+2a_{n-1})(a_{n+1}-4a_n+3a_{n-1})=0.Едно цяло число се нарича кавай, ако принадлежи на някоя кавай редица. Да предположим, че две последователни положителни цели числа mm и m+1m+1 са кавай, не непременно като членове на една и съща кавай редица. Докажете, че 33 дели mm и че m/3m/3 е кавай.
РешениеУсловието за кавай редица може да се запише катоan+1=3an−2an−1илиan+1=4an−3an−1.a_{n+1}=3a_n-2a_{n-1}\qquad\text{или}\qquad a_{n+1}=4a_n-3a_{n-1}.Оттук за всяко n≥1n\ge1 следваan+1≡an или an−1(mod2),a_{n+1}\equiv a_n\text{ или }a_{n-1}\pmod2,иan+1≡an−1 или an(mod3).a_{n+1}\equiv a_{n-1}\text{ или }a_n\pmod3.Понеже a0=0a_0=0 и a1=1a_1=1, всеки член на всяка кавай редица е сравним с 00 или 11 по модул 33. Щом mm и m+1m+1 са кавай числа, това принуждаваm≡0(mod3).m\equiv0\pmod3.Освен това a2a_2 е или 33, или 44. Ако a2=3a_2=3, то a1a_1 и a2a_2 са нечетни, а горното сравнение по модул 22 показва, че всички ana_n с n≥1n\ge1 са нечетни. Ако a2=4a_2=4, то a1a_1 и a2a_2 са сравними с 11 по модул 33, а горното сравнение по модул 33 показва, че всички ana_n с n≥1n\ge1 са сравними с 11 по модул 33. Понеже m≡0(mod3)m\equiv0\pmod3, всяка кавай редица, която съдържа mm, не може да е от втория тип; следователно е от първия тип и mm е нечетно. Значи m+1m+1 е четно. Вземаме кавай редица (an)(a_n), която съдържа m+1m+1, и нека at=m+1a_t=m+1 за някое t≥2t\ge2. Тази редица не може да е от първия тип, защото тогава всички нейни положителни членове биха били нечетни. Значи тя е от втория тип иan≡1(mod3)(n≥1).a_n\equiv1\pmod3\qquad(n\ge1).Дефинирамеan′=an+1−13(n≥0).a'_n=\frac{a_{n+1}-1}{3}\qquad(n\ge0).Тогава a0′=0a'_0=0, a1′=1a'_1=1, а за всяко n≥1n\ge1 имаме(an+1′−3an′+2an−1′)(an+1′−4an′+3an−1′)=\bigl(a'_{n+1}-3a'_n+2a'_{n-1}\bigr)\bigl(a'_{n+1}-4a'_n+3a'_{n-1}\bigr)=(an+2−3an+1+2an)(an+2−4an+1+3an)9=0.\frac{(a_{n+2}-3a_{n+1}+2a_n)(a_{n+2}-4a_{n+1}+3a_n)}{9}=0.Следователно (an′)(a'_n) е кавай редица. Накраяat−1′=at−13=m3,a'_{t-1}=\frac{a_t-1}{3}=\frac m3,така че m/3m/3 е кавай.
Отвори задачатаMathNetISL 2023 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека a,b,c,da,b,c,d са положителни цели числа, за коитоaba+b+cdc+d=(a+b)(c+d)a+b+c+d.\frac{ab}{a+b}+\frac{cd}{c+d}=\frac{(a+b)(c+d)}{a+b+c+d}.Да се определят всички възможни стойности на a+b+c+da+b+c+d.
РешениеОтговорът е: всички положителни цели числа, които не са квадратносвободни. Първо ще покажем, че всяко такова число се достига. Нека kk и ℓ\ell са положителни цели числа и поставимa=ℓ,b=kℓ,c=kℓ,d=k2ℓ.a=\ell,\qquad b=k\ell,\qquad c=k\ell,\qquad d=k^2\ell.Тогаваaba+b+cdc+d=kℓ2(k+1)ℓ+k3ℓ2k(k+1)ℓ=\frac{ab}{a+b}+\frac{cd}{c+d}=\frac{k\ell^2}{(k+1)\ell}+\frac{k^3\ell^2}{k(k+1)\ell}=kℓk+1+k2ℓk+1=kℓ,\frac{k\ell}{k+1}+\frac{k^2\ell}{k+1}=k\ell,а също(a+b)(c+d)a+b+c+d=\frac{(a+b)(c+d)}{a+b+c+d}=(k+1)ℓ⋅k(k+1)ℓ(k+1)2ℓ=kℓ.\frac{(k+1)\ell\cdot k(k+1)\ell}{(k+1)^2\ell}=k\ell.Следователно условието е изпълнено, аa+b+c+d=ℓ(k+1)2.a+b+c+d=\ell(k+1)^2.Така се получава всяко положително цяло число, което се дели на квадрат на число, по-голямо от 11. Остава да докажем, че други стойности не са възможни. НекаS=a+b+c+d.S=a+b+c+d.След умножаване на даденото равенство по (a+b)(c+d)S(a+b)(c+d)S получаваме(ab(c+d)+cd(a+b))S=(a+b)2(c+d)2.(1)\bigl(ab(c+d)+cd(a+b)\bigr)S=(a+b)^2(c+d)^2.\tag{1}Да допуснем, че SS е квадратносвободно. От (1) всеки прост делител на SS дели a+ba+b или c+dc+d. Но понежеc+d≡−(a+b)(modS),c+d\equiv-(a+b)\pmod S,всеки такъв прост делител всъщност дели и a+ba+b, и c+dc+d. Тъй като SS е квадратносвободно, произведението на всички негови прости делители е самото SS, следователноS∣a+b.S\mid a+b.Това е невъзможно, защото 0<a+b<S0\lt{}a+b\lt{}S. Значи SS не е квадратносвободно. Следователно възможните стойности на a+b+c+da+b+c+d са точно положителните цели числа, които не са квадратносвободни.
Отвори задачатаMathNetISL 2023 N7Условие — източник

Задача N8

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Да се намерят всички функции f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0}, за коитоfbf(a)(a+1)=(a+1)f(b)f^{bf(a)}(a+1)=(a+1)f(b)за всички a,b∈Z>0a,b\in\mathbb Z_{\gt{}0}, където fk(n)=f(f(⋯f(n)⋯ ))f^k(n)=f(f(\cdots f(n)\cdots)) означава kk-кратна композиция на ff със себе си.
РешениеОтговорът е единственоf(n)=n+1(n∈Z>0).f(n)=n+1\qquad(n\in\mathbb Z_{\gt{}0}).Тази функция наистина работи, защото ft(x)=x+tf^t(x)=x+t и тогава двете страни са равни на (a+1)(b+1)(a+1)(b+1). Нека P(a,b)P(a,b) означава даденото равенство. Първо ще докажем, че ff е инективна. От P(a,1)P(a,1) имамеff(a)(a+1)=(a+1)f(1),f^{f(a)}(a+1)=(a+1)f(1),така че множеството от стойности на ff е безкрайно. Ако a≥2a\ge2, то от P(a−1,b)P(a-1,b) следваfbf(a−1)(a)=af(b).f^{bf(a-1)}(a)=af(b).Когато bb се променя, дясната страна приема безкрайно много стойности, следователно орбитата a,f(a),f2(a),…a,f(a),f^2(a),\ldots е безкрайна за всяко a≥2a\ge2. В частностfr(a)≠a(a≥2,r≥1).(1)f^r(a)\ne a\qquad(a\ge2, r\ge1).\tag{1}Да допуснем, че f(b)=f(c)f(b)=f(c) за някои b<cb\lt{}c. Тогава за всяко aa имаме(a+1)f(c)=fcf(a)(a+1)=f(c−b)f(a)(fbf(a)(a+1))=f(c−b)f(a)((a+1)f(b))=f(c−b)f(a)((a+1)f(c)),\begin{aligned} (a+1)f(c)&=f^{cf(a)}(a+1)\\ &=f^{(c-b)f(a)}\bigl(f^{bf(a)}(a+1)\bigr)\\ &=f^{(c-b)f(a)}\bigl((a+1)f(b)\bigr)\\ &=f^{(c-b)f(a)}\bigl((a+1)f(c)\bigr), \end{aligned}което противоречи на (1), приложено към числото (a+1)f(c)≥2(a+1)f(c)\ge2. Значи ff е инективна. След това ще определим образа на ff. Числото 11 не е в образа: ако f(b)=1f(b)=1, то P(a,b)P(a,b) даваfbf(a)(a+1)=a+1,f^{bf(a)}(a+1)=a+1,противоречие с (1). Ще казваме, че xx е наследник на yy, ако x=fr(y)x=f^r(y) за някое r≥1r\ge1. От (1) следва, че две различни числа ≥2\ge2 не могат едновременно да са наследници едно на друго. Ще покажем, че за всеки a,b≥2a,b\ge2 орбитите им са сравними: или aa е наследник на bb, или bb е наследник на aa, или a=ba=b. Нека c≥2c\ge2 и поставимm=fcf(a−1)−1(a),n=fcf(b−1)−1(b).m=f^{cf(a-1)-1}(a),\qquad n=f^{cf(b-1)-1}(b).Тогава от P(a−1,c)P(a-1,c) и P(b−1,c)P(b-1,c) получавамеf(m)=af(c),f(n)=bf(c).f(m)=af(c),\qquad f(n)=bf(c).Сегаfnf(a−1)(a)=af(n)=f^{nf(a-1)}(a)=af(n)=abf(c)=bf(m)=fmf(b−1)(b).abf(c)=bf(m)=f^{mf(b-1)}(b).Понеже ff е инективна, среща на две орбити означава, че едното начално число е наследник на другото или двете са равни. Това доказва твърдението. Нека s=f(1)s=f(1). Тъй като 11 не е в образа, s≥2s\ge2. За произволно a≥2a\ge2 сравняваме aa и ss. Ако a=sa=s, то aa е в образа. Ако ss беше наследник на aa, то от s=f(1)s=f(1) и инективността бихме получили или a=1a=1, или 11 в образа, невъзможно. Значи aa е наследник на ss, а следователно е в образа на ff. Такаf(Z>0)=Z≥2.(2)f(\mathbb Z_{\gt{}0})=\mathbb Z_{\ge2}.\tag{2}Освен това (1) вече важи и за a=1a=1, защото 11 не е в образа. Дефинирамеg(a)=f(f(a)−1).g(a)=f(f(a)-1).Това е добре определено за всяко aa, понеже от (2) имаме f(a)≥2f(a)\ge2. За всички a,ba,b получавамеfbg(a)+1(a)=f^{bg(a)+1}(a)=fbf(f(a)−1)(f(a))=f(a)f(b),f^{bf(f(a)-1)}(f(a))=f(a)f(b),където последното равенство е P(f(a)−1,b)P(f(a)-1,b). Дясната страна е симетрична по aa и bb, следователноfbg(a)+1(a)=fag(b)+1(b).f^{bg(a)+1}(a)=f^{ag(b)+1}(b).От инективността на ff следваfbg(a)(a)=fag(b)(b).(3)f^{bg(a)}(a)=f^{ag(b)}(b).\tag{3}ПоставямеNa,b=bg(a)−ag(b).N_{a,b}=bg(a)-ag(b).От (3) следва, че за достатъчно голямо rr е изпълненоfr+Na,b(a)=fr(b).f^{r+N_{a,b}}(a)=f^r(b).Прилагайки това последователно за тройката a,b,ca,b,c, получавамеfr+Na,b+Nb,c+Nc,a(a)=fr(a)f^{r+N_{a,b}+N_{b,c}+N_{c,a}}(a)=f^r(a)за достатъчно голямо rr. Понеже няма периодични точки, сумата на трите индекса трябва да е 00. Значи(a−b)g(c)+(b−c)g(a)+(c−a)g(b)=0.(4)(a-b)g(c)+(b-c)g(a)+(c-a)g(b)=0.\tag{4}Слагайки в (4) съответно a=ta=t, b=t+1b=t+1, c=t+2c=t+2, намирамеg(t+2)−g(t+1)=g(t+1)−g(t),g(t+2)-g(t+1)=g(t+1)-g(t),тоест (g(t))(g(t)) е аритметична прогресия. От (2) и инективността ff е биекция от Z>0\mathbb Z_{\gt{}0} към Z≥2\mathbb Z_{\ge2}. Следователно f(t)−1f(t)-1 пробягва всички положителни цели числа, а g(t)=f(f(t)−1)g(t)=f(f(t)-1) пробягва всички цели числа, не по-малки от 22. Единствената аритметична прогресия с този образ еg(t)=t+1(t≥1).g(t)=t+1\qquad(t\ge1).Сега (3) даваfb(a+1)(a)=fa(b+1)(b).f^{b(a+1)}(a)=f^{a(b+1)}(b).След съкращаване на abab приложения на инективната функция ff получавамеfb(a)=fa(b).(5)f^b(a)=f^a(b).\tag{5}В (5) поставяме a=1a=1, b=nb=n:fn(1)=f(n).f^n(1)=f(n).Отново по инективностfn−1(1)=n.f^{n-1}(1)=n.Прилагайки последното равенство с n+1n+1, получаваме fn(1)=n+1f^n(1)=n+1, и следователноf(n)=fn(1)=n+1f(n)=f^n(1)=n+1за всяко положително цяло число nn.
Отвори задачатаMathNetISL 2023 N8Условие — източник