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

IMO Shortlisted Problems

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

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

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

2015

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

11-12

20 задачи

Задача A1

Пълен запис
Условие
Нека редицата a1,a2,…a_1,a_2,\ldots от положителни реални числа удовлетворяваak+1≥kakak2+k−1a_{k+1}\ge\frac{k a_k}{a_k^2+k-1}за всяко положително цяло число kk. Докажете, че a1+a2+⋯+an≥na_1+a_2+\cdots+a_n\ge n за всяко n≥2n\ge2.
РешениеОт условието получавамеkak+1≤ak2+k−1ak=ak+k−1ak,\frac{k}{a_{k+1}}\le\frac{a_k^2+k-1}{a_k}=a_k+\frac{k-1}{a_k},следователноak≥kak+1−k−1ak.a_k\ge\frac{k}{a_{k+1}}-\frac{k-1}{a_k}.Сумирайки за k=1,2,…,mk=1,2,\ldots,m, намираме телескопичноa1+a2+⋯+am≥mam+1.(1)a_1+a_2+\cdots+a_m\ge\frac{m}{a_{m+1}}.\tag{1}Ще докажем твърдението по индукция. За n=2n=2 имаме a2≥1/a1a_2\ge1/a_1, откъдето a1+a2≥2a_1+a_2\ge2. Нека твърдението е вярно за някое n≥2n\ge2. Ако an+1≥1a_{n+1}\ge1, веднага получавамеa1+⋯+an+an+1≥n+1.a_1+\cdots+a_n+a_{n+1}\ge n+1.Ако an+1<1a_{n+1}\lt{}1, то от (1) с m=nm=n следваa1+⋯+an+an+1≥nan+1+an+1>n−1+2=n+1,a_1+\cdots+a_n+a_{n+1}\ge\frac n{a_{n+1}}+a_{n+1}\gt{}n-1+2=n+1,понеже an+1+1/an+1>2a_{n+1}+1/a_{n+1}\gt{}2. Индукцията е завършена.
Отвори задачатаMathNetISL 2015 A1Условие — източник

Задача A2

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за коитоf(x−f(y))=f(f(x))−f(y)−1f(x-f(y))=f(f(x))-f(y)-1за всички x,y∈Zx,y\in\mathbb Z.
РешениеОтговорът е: константната функция f(x)=−1f(x)=-1 и функцията f(x)=x+1f(x)=x+1. Директно се проверява, че и двете работят. Нека ff е произволно решение. Поставяйки x=0x=0 и y=f(0)y=f(0), получавамеf(−f(f(0)))=−1,f(-f(f(0)))=-1,т.е. съществува цяло число zz с f(z)=−1f(z)=-1. При y=zy=z в даденото уравнение следваf(x+1)=f(f(x))(1)f(x+1)=f(f(x))\tag{1}за всяко x∈Zx\in\mathbb Z. Затова началното уравнение се свежда доf(x−f(y))=f(x+1)−f(y)−1.(2)f(x-f(y))=f(x+1)-f(y)-1.\tag{2}Прилагаме (2) с y=xy=x и после (1):f(x+1)−f(x)=f(x−f(x))+1=f(x+1)-f(x)=f(x-f(x))+1=f(f(x−1−f(x)))+1.f(f(x-1-f(x)))+1.От (2), приложено към x−1x-1 и y=xy=x, имамеf(x−1−f(x))=f(x)−f(x)−1=−1.f(x-1-f(x))=f(x)-f(x)-1=-1.Следователноf(x+1)=f(x)+A,f(x+1)=f(x)+A,където A=f(−1)+1A=f(-1)+1 е константа. Значи по индукция в двете посокиf(x)=Ax+B(x∈Z)f(x)=Ax+B\qquad(x\in\mathbb Z)за някои цели числа A,BA,B. Замяната в (1) даваAx+A+B=A2x+AB+BAx+A+B=A^2x+AB+Bза всяко цяло xx. Следователно A2=AA^2=A и A=ABA=AB. Ако A=1A=1, получаваме B=1B=1 и f(x)=x+1f(x)=x+1. Ако A=0A=0, функцията е константна; замяната в началното уравнение дава единствено стойността −1-1. Така решенията са точно посочените две функции.
Отвори задачатаMathNetISL 2015 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека nn е фиксирано положително цяло число. Да се намери най-голямата възможна стойност на∑1≤r<s≤2n(s−r−n)xrxs,\sum_{1\le r\lt{}s\le2n}(s-r-n)x_rx_s,където −1≤xi≤1-1\le x_i\le1 за всички i=1,2,…,2ni=1,2,\ldots,2n.
РешениеОтговорът е n(n−1)n(n-1). Нека ZZ е разглежданият израз. Той е линеен по всяка от променливите xix_i, затова максимумът върху куба [−1,1]2n[-1,1]^{2n} се достига във връх. Достатъчно е да разгледаме случая xi∈{−1,1}x_i\in\{-1,1\}. За i=1,2,…,2ni=1,2,\ldots,2n полагамеyi=∑r=1ixr−∑r=i+12nxr.y_i=\sum_{r=1}^i x_r-\sum_{r=i+1}^{2n}x_r.При повдигане на квадрат коефициентът на xrxsx_rx_s в yi2y_i^2 е 22 за i<ri\lt{}r и за i≥si\ge s, а е −2-2 за r≤i<sr\le i\lt{}s. Следователно след сумиране по i=1,2,…,2ni=1,2,\ldots,2n коефициентът на xrxsx_rx_s е2(2n−s+r)−2(s−r)=4(n−s+r).2(2n-s+r)-2(s-r)=4(n-s+r).Така∑i=12nyi2=4n2−4Z.(1)\sum_{i=1}^{2n}y_i^2=4n^2-4Z.\tag{1}Понеже xi∈{−1,1}x_i\in\{-1,1\}, всяко yiy_i е четно цяло число, а съседните yi−1y_{i-1} и yiy_i се различават с 22 или −2-2. Затова за всяко j=1,2,…,nj=1,2,\ldots,n имамеy2j−12+y2j2≥4,y_{2j-1}^2+y_{2j}^2\ge4,и следователно∑i=12nyi2≥4n.(2)\sum_{i=1}^{2n}y_i^2\ge4n.\tag{2}От (1) и (2) получаваме 4n≤4n2−4Z4n\le4n^2-4Z, тоест Z≤n(n−1)Z\le n(n-1). Равенство се достига например при xi=1x_i=1 за нечетни ii и xi=−1x_i=-1 за четни ii. Следователно максималната стойност е n(n−1)n(n-1).
Отвори задачатаMathNetISL 2015 A3Условие — източник

Задача A4

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, удовлетворяващиf(x+f(x+y))+f(xy)=x+f(x+y)+yf(x)f(x+f(x+y))+f(xy)=x+f(x+y)+yf(x)за всички реални числа xx и yy.
РешениеОтговорът еf(x)=xилиf(x)=2−x.f(x)=x\qquad\text{или}\qquad f(x)=2-x.И двете функции се проверяват директно. Нека ff е решение. При y=1y=1 получавамеf(x+f(x+1))=x+f(x+1),(1)f(x+f(x+1))=x+f(x+1),\tag{1}т.е. всяко число от вида x+f(x+1)x+f(x+1) е неподвижна точка на ff. Първи случай: f(0)≠0f(0)\ne0. При x=0x=0 началното уравнение даваf(f(y))+f(0)=f(y)+yf(0).f(f(y))+f(0)=f(y)+yf(0).Ако y0y_0 е неподвижна точка, тогава f(0)=y0f(0)f(0)=y_0f(0), откъдето y0=1y_0=1. От (1) следва x+f(x+1)=1x+f(x+1)=1 за всяко xx, т.е. f(x)=2−xf(x)=2-x. Втори случай: f(0)=0f(0)=0. От уравнението при y=0y=0, с xx заменено от x+1x+1, следваf(x+1+f(x+1))=x+1+f(x+1).(2)f(x+1+f(x+1))=x+1+f(x+1).\tag{2}При x=1x=1 имамеf(1+f(y+1))+f(y)=1+f(y+1)+yf(1).(3)f(1+f(y+1))+f(y)=1+f(y+1)+yf(1).\tag{3}От (1) с x=−1x=-1 получаваме f(−1)=−1f(-1)=-1, а после от (3) с y=−1y=-1 следва f(1)=1f(1)=1. Затова (3) ставаf(1+f(y+1))+f(y)=1+f(y+1)+y.(4)f(1+f(y+1))+f(y)=1+f(y+1)+y.\tag{4}Ако две последователни числа uu и u+1u+1 са неподвижни точки, то от (4) с y=uy=u следва, че u+2u+2 също е неподвижна точка. По (1) и (2) числата x+f(x+1)x+f(x+1) и x+f(x+1)+1x+f(x+1)+1 са неподвижни, следователно x+f(x+1)+2x+f(x+1)+2 също е неподвижно. След замяна на xx с x−2x-2 получавамеf(x+f(x−1))=x+f(x−1).(5)f(x+f(x-1))=x+f(x-1).\tag{5}От друга страна, при y=−1y=-1 в началното уравнение имамеf(x+f(x−1))=x+f(x−1)−f(x)−f(−x).f(x+f(x-1))=x+f(x-1)-f(x)-f(-x).Сравнявайки с (5), получаваме f(−x)=−f(x)f(-x)=-f(x) за всяко xx. Накрая заместваме (x,y)(x,y) с (−1,−y)(-1,-y) в началното уравнение и използваме f(−1)=−1f(-1)=-1 и нечетността на ff:−f(1+f(y+1))+f(y)=−1−f(y+1)+y.-f(1+f(y+1))+f(y)=-1-f(y+1)+y.Събираме това равенство с (4) и намираме 2f(y)=2y2f(y)=2y. Значи f(y)=yf(y)=y за всяко реално yy.
Отвори задачатаMathNetISL 2015 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека 2Z+12\mathbb Z+1 означава множеството на нечетните цели числа. Да се намерят всички функции f:Z→2Z+1f:\mathbb Z\to2\mathbb Z+1, за коитоf(x+f(x)+y)+f(x−f(x)−y)=f(x+y)+f(x−y)f(x+f(x)+y)+f(x-f(x)-y)=f(x+y)+f(x-y)за всички x,y∈Zx,y\in\mathbb Z.
РешениеОтговорът е следният. Избираме нечетно положително цяло число dd, цяло число kk и нечетни цели числа ℓ0,ℓ1,…,ℓd−1\ell_0,\ell_1,\ldots,\ell_{d-1}. Тогаваf(md+i)=2kmd+ℓidf(md+i)=2kmd+\ell_i d\qquad(m∈Z,i=0,1,…,d−1)(m\in\mathbb Z,\quad i=0,1,\ldots,d-1)дава решение, и всички решения са от този вид. За функция gg и ненулево цяло tt пишемΔtg(x)=g(x+t)−g(x).\Delta_tg(x)=g(x+t)-g(x).Ще използваме, че операторите Δa\Delta_a и Δb\Delta_b комутират. Казваме, че gg е tt-квазипериодична, ако Δtg\Delta_tg е константна функция; най-малкият положителен квазипериод дели всеки друг положителен квазипериод. Поставяме a=x+ya=x+y в условието. То се записва катоΔf(x)f(a)=Δf(x)f(2x−a−f(x))\Delta_{f(x)}f(a)=\Delta_{f(x)}f(2x-a-f(x))\qquad(x,a∈Z).(1)(x,a\in\mathbb Z).\tag{1}Ако M≠0M\ne0 се дели на f(x)f(x), сумирането на (1) по последователни стойности на aa даваΔMf(b)=ΔMf(2x−b−M).(2)\Delta_Mf(b)=\Delta_Mf(2x-b-M).\tag{2}Лема 1. Ако x≠yx\ne y и L=lcm⁡(∣f(x)∣,∣f(y)∣)L=\operatorname{lcm}(|f(x)|,|f(y)|), то ΔLf\Delta_Lf е 2(y−x)2(y-x)-периодична. Доказателство. От (2), приложено първо за xx, а после за yy, получавамеΔLf(b)=ΔLf(2x−b−L)=ΔLf(b+2(y−x)).\Delta_Lf(b)=\Delta_Lf(2x-b-L)=\Delta_Lf(b+2(y-x)).Лема 2. Ако за функция gg и ненулеви цели t,st,s са изпълнени Δtsg=0\Delta_{ts}g=0 и ΔtΔtg=0\Delta_t\Delta_tg=0, то Δtg=0\Delta_tg=0. Доказателство. Можем да приемем s>0s\gt{}0. От ΔtΔtg=0\Delta_t\Delta_tg=0 стойноститеΔtg(a),Δtg(a+t),…,Δtg(a+(s−1)t)\Delta_tg(a),\Delta_tg(a+t),\ldots,\Delta_tg(a+(s-1)t)са равни. Сборът им е Δtsg(a)=0\Delta_{ts}g(a)=0, следователно всяка от тях е нула. Стъпка 1. Функцията ff е квазипериодична. Нека Q=lcm⁡(∣f(0)∣,∣f(1)∣)Q=\operatorname{lcm}(|f(0)|,|f(1)|). По лема 1 функцията ΔQf\Delta_Qf е 22-периодична. От (2) при M=QM=Q и x=b=0x=b=0 следва ΔQf(0)=ΔQf(−Q)\Delta_Qf(0)=\Delta_Qf(-Q). Понеже QQ е нечетно, тези две точки имат различна четност; значи ΔQf\Delta_Qf е константна. Стъпка 2. Нека TT е най-малкият положителен квазипериод на ff. Ще докажем, че T∣f(u)T\mid f(u) за всяко цяло uu. Понеже QQ е нечетно, и TT е нечетно. Да допуснем, че за някое нечетно просто pp и някое α≥1\alpha\ge1 имаме pα∣Tp^\alpha\mid T, но pα∤f(u)p^\alpha\nmid f(u). От условието при x=u,y=0x=u,y=0 получавамеf(u+f(u))+f(u−f(u))=2f(u),f(u+f(u))+f(u-f(u))=2f(u),така че за една от точките v=u+f(u)v=u+f(u) или v=u−f(u)v=u-f(u) е вярно pα∤f(v)p^\alpha\nmid f(v). Нека L=lcm⁡(∣f(u)∣,∣f(v)∣)L=\operatorname{lcm}(|f(u)|,|f(v)|). Тогава pα∤Lp^\alpha\nmid L. От лема 1 функцията ΔLf\Delta_Lf е 2f(u)2f(u)-периодична, а от квазипериодичността тя е и TT-периодична. СледователноΔgcd⁡(T,2f(u))ΔLf=0.\Delta_{\gcd(T,2f(u))}\Delta_Lf=0.По същия начин Δgcd⁡(T,2f(u))f\Delta_{\gcd(T,2f(u))}f е едновременно LL- и TT-периодична, откъдетоΔgcd⁡(T,L)Δgcd⁡(T,2f(u))f=0.\Delta_{\gcd(T,L)}\Delta_{\gcd(T,2f(u))}f=0.Двата индекса в последното равенство делят T/pT/p, затоваΔT/pΔT/pf=0,\Delta_{T/p}\Delta_{T/p}f=0,а оттук и ΔT/pΔT/pΔ1f=0\Delta_{T/p}\Delta_{T/p}\Delta_1f=0. Освен това ΔTΔ1f=0\Delta_T\Delta_1f=0, защото TT е квазипериод. Прилагаме лема 2 за функцията Δ1f\Delta_1f, с t=T/pt=T/p и s=ps=p, и получаваме ΔT/pΔ1f=0\Delta_{T/p}\Delta_1f=0. Това означава, че T/pT/p е положителен квазипериод, противоречие. Значи T∣f(u)T\mid f(u) за всяко uu. Стъпка 3. Описание на решенията. Нека dd е най-големият общ делител на всички стойности на ff. Тогава dd е нечетно положително число. От стъпка 2 имаме T∣dT\mid d, следователно dd също е квазипериод и Δdf\Delta_df е константна функция. Тази константа е четна и се дели на dd, затова е от вида 2dk2dk с k∈Zk\in\mathbb Z. Ако ℓi=f(i)/d\ell_i=f(i)/d за i=0,1,…,d−1i=0,1,\ldots,d-1, то всяко ℓi\ell_i е нечетно иf(md+i)=f(i)+mΔdf(i)=ℓid+2kmd.f(md+i)=f(i)+m\Delta_df(i)=\ell_i d+2kmd.Така всяко решение има посочения вид. Обратно, всяка функция от този вид приема само нечетни цели стойности. Освен това всяка стойност f(x)f(x) се дели на dd, а за всяко кратно на dd операторът Δtf\Delta_t f е константен. Затова двете страни на (1) са равни, което е еквивалентно на началното условие. Следователно всички посочени функции наистина са решения.
Отвори задачатаMathNetISL 2015 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека n≥2n\ge2 е фиксирано цяло число. Казваме, че два полинома PP и QQ с реални коефициенти са блоково подобни, ако за всяко i∈{1,2,…,n}i\in\{1,2,\ldots,n\} редицитеP(2015i),P(2015i−1),…,P(2015i−2014)P(2015i),P(2015i-1),\ldots,P(2015i-2014)иQ(2015i),Q(2015i−1),…,Q(2015i−2014)Q(2015i),Q(2015i-1),\ldots,Q(2015i-2014)са пермутации една на друга. (a) Докажете, че съществуват различни блоково подобни полиноми от степен n+1n+1. (b) Докажете, че не съществуват различни блоково подобни полиноми от степен nn.
РешениеПишем k=2015=2ℓ+1k=2015=2\ell+1. (a) РазглеждамеP(x)=∏i=0n(x−ik),P(x)=\prod_{i=0}^n(x-ik),Q(x)=∏i=0n(x−ik−1)=P(x−1).\qquad Q(x)=\prod_{i=0}^n(x-ik-1)=P(x-1).Тези полиноми са различни и са от степен n+1n+1. Във всеки блок стойностите на QQ са стойностите на PP в същия блок, изместени с една позиция; липсващата стойност е заменена с друга нулева стойност, защото P((i−1)k)=P(ik)=0P((i-1)k)=P(ik)=0. Следователно PP и QQ са блоково подобни. (b) Да допуснем противното: нека PP и QQ са различни блоково подобни полиноми от степен nn. За полином FF дефинирамеΣF(m)=∑j=1mF(j)\Sigma_F(m)=\sum_{j=1}^m F(j)за неотрицателни цели mm и разглеждаме ΣF\Sigma_F като полиномната му продължена сума. Понеже във всеки блок стойностите на PP и QQ са пермутации, полиномите ΣP−Q\Sigma_{P-Q} и ΣP2−Q2\Sigma_{P^2-Q^2} имат корени в точките0,k,2k,…,nk.0,k,2k,\ldots,nk.Ще използваме лема. Нека F≠0F\ne0 и ΣF\Sigma_F има корени 0,k,2k,…,nk0,k,2k,\ldots,nk. Тогава deg⁡F≥n\deg F\ge n и заT(x)=∏i=0n(x−ik)T(x)=\prod_{i=0}^n(x-ik)съществува полином GG със deg⁡G=deg⁡F−n\deg G=\deg F-n, за койтоF(x)=T(x)G(x)−T(x−1)G(x−1).(1)F(x)=T(x)G(x)-T(x-1)G(x-1).\tag{1}Наистина, ако deg⁡F<n\deg F\lt{}n, тогава ΣF\Sigma_F има повече корени от степента си и следователно F=0F=0, противоречие. Значи deg⁡F≥n\deg F\ge n. От корените имаме ΣF(x)=T(x)G(x)\Sigma_F(x)=T(x)G(x) за подходящ GG. Полиномът отдясно на (1) има същата сумова функция, защото сборът му от 11 до mm телескопира до T(m)G(m)T(m)G(m). Следователно той съвпада с FF. Прилагаме лемата към R1=P−QR_1=P-Q. Понеже R1≠0R_1\ne0 и deg⁡R1≤n\deg R_1\le n, получаваме deg⁡R1=n\deg R_1=n иR1(x)=α(T(x)−T(x−1))(2)R_1(x)=\alpha\bigl(T(x)-T(x-1)\bigr)\tag{2}за някоя ненулева константа α\alpha. Ще докажем, че S=P+QS=P+Q е константен. Ако не е, то R2=P2−Q2=R1SR_2=P^2-Q^2=R_1S е ненулев полином със степен между n+1n+1 и 2n2n. Лемата даваR2(x)=T(x)G(x)−T(x−1)G(x−1)R_2(x)=T(x)G(x)-T(x-1)G(x-1)за някой неконстантен полином GG със deg⁡G≤n\deg G\le n. От (2) следва, че R1R_1 дели R2R_2. НоR2(x)=R_2(x)=T(x)(G(x)−G(x−1))+G(x−1)(T(x)−T(x−1)).T(x)(G(x)-G(x-1))+G(x-1)(T(x)-T(x-1)).Понеже T(x)T(x) и T(x−1)T(x-1) нямат общ корен, имаме gcd⁡(T,R1)=1\gcd(T,R_1)=1. Затова R1R_1 трябва да дели G(x)−G(x−1)G(x)-G(x-1), което е невъзможно: този полином е ненулев и има степен по-малка от n=deg⁡R1n=\deg R_1. Следователно SS е константа, да кажем S=βS=\beta. Заменяме P,QP,Q с\frac{2P-eta}{\alpha},\qquad \frac{2Q-eta}{\alpha}.Те пак са различни и блоково подобни, а сега имамеP(x)=−Q(x)=T(x)−T(x−1).(3)P(x)=-Q(x)=T(x)-T(x-1).\tag{3}Ще покажем, че това е невъзможно. За всяко i=1,2,…,ni=1,2,\ldots,n числата T(ik−k+1)T(ik-k+1) и T(ik−1)T(ik-1) имат един и същ знак. От (3) следва, че P(ik−k+1)=T(ik−k+1)P(ik-k+1)=T(ik-k+1) и P(ik)=−T(ik−1)P(ik)=-T(ik-1) са с противоположни знаци. Значи PP има корен във всеки от nn-те интервала [ik−k+1,ik][ik-k+1,ik], а понеже deg⁡P=n\deg P=n, има точно по един такъв корен. В частност редицата P(1),P(2),…,P(k)P(1),P(2),\ldots,P(k) сменя знак точно веднъж. Но PP и −P-P трябва да бъдат блоково подобни, следователно в този блок броят на положителните и отрицателните стойности трябва да е еднакъв. Тъй като k=2ℓ+1k=2\ell+1 е нечетно, средната стойност трябва да е нула: P(ℓ+1)=0P(\ell+1)=0. Това означаваT(ℓ+1)=T(ℓ).T(\ell+1)=T(\ell).Но∣T(ℓ+1)∣=∣ℓ+1∣ ∣ℓ∣∏i=2n∣ℓ+1−ik∣<|T(\ell+1)|=|\ell+1|\,|\ell|\prod_{i=2}^n|\ell+1-ik|\lt{}∣ℓ∣ ∣ℓ+1∣∏i=2n∣ℓ−ik∣=∣T(ℓ)∣,|\ell|\,|\ell+1|\prod_{i=2}^n|\ell-ik|=|T(\ell)|,понеже n≥2n\ge2. Противоречието доказва, че различни блоково подобни полиноми от степен nn не съществуват.
Отвори задачатаMathNetISL 2015 A6Условие — източник

Задача C1

Пълен запис
Условие
В Линеландия има n≥1n\ge1 града, разположени по път отляво надясно. Всеки град има ляв булдозер, поставен отляво на града и обърнат наляво, и десен булдозер, поставен отдясно на града и обърнат надясно. Размерите на всичките 2n2n булдозера са различни. Всеки път, когато десен и ляв булдозер се срещнат челно, по-големият избутва по-малкия извън пътя. От друга страна, булдозерите са съвсем незащитени отзад: ако един булдозер достигне задния край на друг, първият избутва втория извън пътя независимо от размерите им. Нека AA и BB са два града, като BB е вдясно от AA. Казваме, че град AA може да помете град BB, ако десният булдозер на AA може да се придвижи до BB, избутвайки извън пътя всички булдозери, които срещне. Аналогично, BB може да помете AA, ако левият булдозер на BB може да се придвижи до AA, избутвайки извън пътя всички булдозери на всички градове по пътя си. Докажете, че съществува точно един град, който не може да бъде пометен от никой друг град.
РешениеНека T1,T2,…,TnT_1,T_2,\ldots,T_n са градовете, номерирани отляво надясно. Първо отбелязваме, че ако град TiT_i може да помете град TjT_j, то TiT_i може да помете и всеки град, разположен между TiT_i и TjT_j. Ще докажем твърдението със силна индукция по nn. При n=1n=1 то е очевидно. За индукционната стъпка забелязваме, че левият булдозер в T1T_1 и десният булдозер в TnT_n са напълно безполезни, така че можем да ги забравим. Измежду останалите 2n−22n-2 булдозера избираме най-големия. Без ограничение той е десният булдозер на някой град TkT_k с k<nk\lt{}n; другият случай е симетричен. С този голям булдозер TkT_k със сигурност може да помете всички градове вдясно от него. Освен това никой от тези градове не може да помете TkT_k, а следователно не може да помете и никой град вляво от TkT_k. Значи ако премахнем градовете Tk+1,Tk+2,…,TnT_{k+1},T_{k+2},\ldots,T_n, за никой от останалите градове не се променя дали може да бъде пометен от друг град. По индукционното предположение сред градовете T1,T2,…,TkT_1,T_2,\ldots,T_k има единствен град, който не може да бъде пометен. По казаното по-горе той е и единственият такъв град в първоначалната конфигурация. Това завършва индукционната стъпка.
Отвори задачатаMathNetISL 2015 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека V\mathcal V е крайно множество от точки в равнината. Ще казваме, че V\mathcal V е балансирано, ако за всеки две различни точки A,B∈VA,B\in\mathcal V съществува точка C∈VC\in\mathcal V, за която AC=BCAC=BC. Ще казваме, че V\mathcal V е безцентрово, ако за всеки три различни точки A,B,C∈VA,B,C\in\mathcal V не съществува точка P∈VP\in\mathcal V, за която PA=PB=PCPA=PB=PC. (a) Докажете, че за всяко n≥3n\ge3 съществува балансирано множество от nn точки. (b) За кои n≥3n\ge3 съществува балансирано безцентрово множество от nn точки?
РешениеПърво доказваме (a). Нека nn е нечетно. Вземаме правилен nn-ъгълник и означаваме върховете му с A1,A2,…,AnA_1,A_2,\ldots,A_n в посока, обратна на часовниковата стрелка. Нека V={A1,A2,…,An}\mathcal V=\{A_1,A_2,\ldots,A_n\}. За всеки два различни върха AiA_i и AjA_j избираме k∈{1,2,…,n}k\in\{1,2,\ldots,n\}, за което2k≡i+j(modn).2k\equiv i+j\pmod n.Такова kk съществува и е единствено, защото nn е нечетно. От k−i≡j−k(modn)k-i\equiv j-k\pmod n следва AiAk=AjAkA_iA_k=A_jA_k, така че V\mathcal V е балансирано. Нека сега nn е четно. Вземаме правилен (3n−6)(3n-6)-ъгълник с център OO и означаваме върховете му с A1,A2,…,A3n−6A_1,A_2,\ldots,A_{3n-6} в посока, обратна на часовниковата стрелка. ПолагамеV={O,A1,A2,…,An−1}.\mathcal V=\{O,A_1,A_2,\ldots,A_{n-1}\}.Да проверим, че това множество е балансирано. За всеки два различни върха AiA_i и AjA_j имаме OAi=OAjOA_i=OA_j. Остава да разгледаме двойка от вида O,AiO,A_i. Ако i≤n/2i\le n/2, то триъгълникът OAiAn/2−1+iOA_iA_{n/2-1+i} е равностранен, следователноOAn/2−1+i=AiAn/2−1+i.OA_{n/2-1+i}=A_iA_{n/2-1+i}.Ако i>n/2i\gt{}n/2, аналогичноOAi−n/2+1=AiAi−n/2+1.OA_{i-n/2+1}=A_iA_{i-n/2+1}.И в двата случая намираме точка от V\mathcal V, еднакво отдалечена от OO и AiA_i, с което (a) е доказано. За (b) отговорът е: всички нечетни цели числа n≥3n\ge3. Ако nn е нечетно, вземаме множеството от върховете на правилен nn-ъгълник. Вече доказахме, че то е балансирано. То е и безцентрово: ако точка PP е на равни разстояния от три различни върха A,B,CA,B,C, то PP е центърът на описаната около тези три точки окръжност, тоест центърът на правилния nn-ъгълник, а този център не е връх. Остава да покажем, че при четно nn такова множество не съществува. Нека V\mathcal V е балансирано множество с четен брой nn точки. За двойка различни точки A,B∈VA,B\in\mathcal V ще казваме, че точка P∈VP\in\mathcal V е свързана с двойката {A,B}\{A,B\}, ако PA=PBPA=PB. Понеже двойките точки са n(n−1)2\frac{n(n-1)}2, съществува точка P∈VP\in\mathcal V, която е свързана с поне⌈n(n−1)2n⌉=n2\left\lceil \frac{\frac{n(n-1)}2}{n}\right\rceil=\frac n2двойки. Нито една от тези двойки не съдържа PP, защото PP=0PP=0, а разстоянието от PP до всяка друга точка е положително. Следователно обединението на тези n/2n/2 двойки се съдържа в множеството V∖{P}\mathcal V\setminus\{P\}, което има само n−1n-1 точки. Ако всички двойки бяха несвързани помежду си, те щяха да съдържат общо nn различни точки, невъзможно. Значи две от тях имат обща точка; нека са {A,B}\{A,B\} и {A,C}\{A,C\}. Тогава PA=PB=PCPA=PB=PC, което противоречи на безцентровостта. Следователно балансирано безцентрово множество с четен брой точки не съществува, а при нечетен брой съществува.
Отвори задачатаMathNetISL 2015 C2Условие — източник

Задача C3

Пълен запис
Условие
За крайно множество AA от положителни цели числа наричаме едно разбиване на AA на две непресичащи се непразни подмножества A1A_1 и A2A_2 добро, ако най-малкото общо кратно на елементите на A1A_1 е равно на най-големия общ делител на елементите на A2A_2. Да се намери най-малката стойност на nn, за която съществува множество от nn положителни цели числа с точно 20152015 добри разбивания.
РешениеОтговорът е 30243024. Нека A={a1,a2,…,an}A=\{a_1,a_2,\ldots,a_n\}, където a1<a2<⋯<ana_1\lt{}a_2\lt{}\cdots\lt{}a_n. Да разгледаме произволно добро разбиване (A1,A2)(A_1,A_2) и да означим общата стойност на най-малкото общо кратно на A1A_1 и най-големия общ делител на A2A_2 с dd. Ако ai∈A1a_i\in A_1 и aj∈A2a_j\in A_2, то ai∣da_i\mid d и d∣ajd\mid a_j, следователно ai≤d≤aja_i\le d\le a_j. Значи A1A_1 непременно се състои от някакъв начален отрязък {a1,a2,…,ak}\{a_1,a_2,\ldots,a_k\}, а A2A_2 - от останалите елементи {ak+1,ak+2,…,an}\{a_{k+1},a_{k+2},\ldots,a_n\}, където 1≤k<n1\le k\lt{}n. Ще казваме, че aka_k е разделящ елемент, ако това разбиване след aka_k е добро. За 1≤k≤n−11\le k\le n-1 нека LkL_k е най-малкото общо кратно на a1,a2,…,aka_1,a_2,\ldots,a_k, а GkG_k е най-големият общ делител на ak+1,ak+2,…,ana_{k+1},a_{k+2},\ldots,a_n. Тогава aka_k е разделящ точно когато Lk=GkL_k=G_k. Ще използваме следното наблюдение. Ако ak−1a_{k-1} и aka_k са разделящи, където 2≤k≤n−12\le k\le n-1, то Gk−1=Gk=akG_{k-1}=G_k=a_k. Наистина, от Lk−1=Gk−1L_{k-1}=G_{k-1} следва Lk−1∣akL_{k-1}\mid a_k, затова най-малкото общо кратно на Lk−1L_{k-1} и aka_k е aka_k, тоест Lk=akL_k=a_k. Понеже aka_k е разделящ, получаваме Gk=Lk=akG_k=L_k=a_k, а после Gk−1=gcd⁡(ak,Gk)=akG_{k-1}=\gcd(a_k,G_k)=a_k. Оттук следват две ограничения. Първо, сред всеки три последователни елемента ak−1,ak,ak+1a_{k-1},a_k,a_{k+1} с 2≤k≤n−22\le k\le n-2 поне един не е разделящ, защото иначе наблюдението би дало едновременно Gk=akG_k=a_k и Gk=ak+1G_k=a_{k+1}. Второ, a1a_1 и a2a_2 не могат едновременно да са разделящи: тогава наблюдението дава a2=G1=L1=a1a_2=G_1=L_1=a_1. По същия начин an−2a_{n-2} и an−1a_{n-1} не могат едновременно да са разделящи. Следователно сред двойките {a1,a2}\{a_1,a_2\} и {an−2,an−1}\{a_{n-2},a_{n-1}\} има най-много по един разделящ елемент, а сред a3,a4,…,an−3a_3,a_4,\ldots,a_{n-3} поне ⌊n−53⌋\left\lfloor\frac{n-5}{3}\right\rfloor елемента не са разделящи. Броят на разделящите елементи е най-многоn−1−2−⌊n−53⌋=⌈2(n−2)3⌉.n-1-2-\left\lfloor\frac{n-5}{3}\right\rfloor=\left\lceil\frac{2(n-2)}3\right\rceil.Ако има точно 20152015 добри разбивания, трябва⌈2(n−2)3⌉≥2015,\left\lceil\frac{2(n-2)}3\right\rceil\ge2015,откъдето n≥3024n\ge3024. Остава да дадем пример с 30243024 елемента. НекаA={2⋅6i,3⋅6i,6i+1∣0≤i≤1007}.A=\{2\cdot6^i,3\cdot6^i,6^{i+1}\mid 0\le i\le1007\}.В това множество разделящи са точно елементите 3⋅6i3\cdot6^i за 0≤i≤10070\le i\le1007 и елементите 6i6^i за 1≤i≤10071\le i\le1007. Наистина, след 3⋅6i3\cdot6^i най-малкото общо кратно на всички предишни елементи е 6i+16^{i+1}, а най-големият общ делител на всички следващи елементи също е 6i+16^{i+1}; след 6i6^i за 1≤i≤10071\le i\le1007 и двете стойности са 6i6^i. След елемент от вида 2⋅6i2\cdot6^i тези две стойности са различни, а след последния елемент няма разбиване. Така получаваме 1008+1007=20151008+1007=2015 добри разбивания с 30243024 елемента. Следователно минималната стойност е 30243024.
Отвори задачатаMathNetISL 2015 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека nn е положително цяло число. Двама играчи AA и BB играят игра, в която се редуват да избират положителни цели числа k≤nk\le n. Правилата са следните: (i) Играч не може да избере число, което вече е било избрано от някой от двамата играчи. (ii) Играч не може да избере число, съседно на число, което самият той вече е избрал в предишен ход. (iii) Играта завършва без победител, ако всички числа са избрани; иначе губи играчът, който не може да избере число. Играчът AA започва. Да се определи изходът от играта, ако и двамата играят оптимално.
РешениеИграта завършва без победител при n=1,2,4,6n=1,2,4,6. При всички останали стойности на nn печели BB. Първо ще докажем, че BB печели при n≠1,2,4,6n\ne1,2,4,6. Ще използваме следната лема. Лема. Нека първият ход на BB е числото nn. Ако AA е направил своя kk-ти ход за някое k≥2k\ge2, то BB също може да направи своя kk-ти ход. Доказателство. Нека SS е множеството от първите kk числа, избрани от AA. В SS няма две съседни числа. Затова множеството {1,2,…,n}∖S\{1,2,\ldots,n\}\setminus S се състои от kk последователни компоненти, ако 1∈S1\in S, и от k+1k+1 такива компоненти иначе. Досега BB е избрал само k−1k-1 числа, следователно поне една от тези компоненти не съдържа число, избрано от BB. Всяко още неизбрано число от тази компонента е допустим ход за BB. Лемата е доказана. По симетрия можем да приемем, че първият ход на AA не надвишава n+12\frac{n+1}{2}. Тогава първият ход на BB ще бъде nn. Ако nn е нечетно и n≥3n\ge3, то играта може да завърши без победител само ако AA в крайна сметка избере всички нечетни числа. Но BB вече е избрал нечетното число nn, така че това е невъзможно. По лемата BB може да отговаря след всеки ход на AA, докато AA остане без ход; значи BB печели. Нека сега nn е четно и n≥8n\ge8. След като BB е избрал nn, играта може да завърши без победител само ако AA в крайна сметка избере всички нечетни числа от {1,2,…,n−1}\{1,2,\ldots,n-1\}. На втория си ход BB избира нечетно число от множеството {1,3,5,…,n−3}\{1,3,5,\ldots,n-3\}, което още не е избрано от AA. Това е възможно, защото в това множество има поне 33 числа, а AA е избрал само две числа. Така равният изход отново става невъзможен, а лемата гарантира, че BB може да продължи да отговаря до победа. Остават случаите n=1,2,4,6n=1,2,4,6. При n=1n=1 и n=2n=2 равният изход е очевиден. При n=4n=4 директна проверка показва, че оптималната игра е AA да избере краен елемент, а BB - другия краен елемент; тогава всички останали ходове са принудени и играта завършва без победител. При n=6n=6 играчът BB има поне равен изход, например чрез лемата или чрез огледална стратегия. Играчът AA също има поне равен изход: на първия ход избира 11. Ако отговорът на BB е bb, играчът AA избира съсед cc на bb, различен от 11 и 22, и запазва cc за третия си ход. На втория си ход AA може да избере число, различно от 1,2,c−1,c,c+11,2,c-1,c,c+1. Тогава BB не може да избере cc, понеже то е съседно на неговото число bb, а третият ход cc остава допустим за AA. Следователно AA не губи. Така при n=6n=6 изходът също е равен. Следователно точно при n=1,2,4,6n=1,2,4,6 играта завършва без победител, а във всички други случаи печели BB.
Отвори задачатаMathNetISL 2015 C4Условие — източник

Задача C5

Пълен запис
Условие
Да разгледаме безкрайна редица a1,a2,…a_1,a_2,\ldots от положителни цели числа, като ai≤2015a_i\le2015 за всяко i≥1i\ge1. Да предположим, че за всеки два различни индекса ii и jj имаме i+ai≠j+aji+a_i\ne j+a_j. Докажете, че съществуват положителни цели числа bb и NN, такива че∣∑i=m+1n(ai−b)∣≤10072\left|\sum_{i=m+1}^n(a_i-b)\right|\le1007^2за всички n>m≥Nn\gt{}m\ge N.
РешениеПолагаме sn=n+ans_n=n+a_n за всяко положително цяло число nn. От условието имамеn+1≤sn≤n+2015,n+1\le s_n\le n+2015,а числата s1,s2,…s_1,s_2,\ldots са две по две различни. НекаM=Z>0∖{s1,s2,…}.M=\mathbb Z_{\gt{}0}\setminus\{s_1,s_2,\ldots\}.Ще докажем, че в MM има най-много 20152015 числа. Ако това не е вярно, избираме m1<m2<⋯<m2016m_1\lt{}m_2\lt{}\cdots\lt{}m_{2016} от MM и полагаме n=m2016n=m_{2016}. Тогава{s1,s2,…,sn}∪{m1,m2,…,m2016}⊆{1,2,…,n+2015},\{s_1,s_2,\ldots,s_n\}\cup\{m_1,m_2,\ldots,m_{2016}\}\subseteq\{1,2,\ldots,n+2015\},като обединението вляво е непресичащо се и съдържа n+2016n+2016 елемента. Това е невъзможно, защото множеството вдясно има само n+2015n+2015 елемента. Освен това 1∈M1\in M, така че MM е непразно. Нека b=∣M∣b=|M| и нека N=max⁡MN=\max M. Ще покажем, че тези bb и NN вършат работа. За r≥Nr\ge N разглеждаме множествотоBr=M∪{s1,s2,…,sr}.B_r=M\cup\{s_1,s_2,\ldots,s_r\}.То е подмножество на {1,2,…,r+2015}\{1,2,\ldots,r+2015\} и има точно b+rb+r елемента. От определенията на MM и NN следва още, че {1,2,…,r+1}⊆Br\{1,2,\ldots,r+1\}\subseteq B_r. Затова съществува множество Cr⊆{1,2,…,2014}C_r\subseteq\{1,2,\ldots,2014\} с ∣Cr∣=b−1|C_r|=b-1, за коетоBr={1,2,…,r+1}∪{r+1+x∣x∈Cr}.B_r=\{1,2,\ldots,r+1\}\cup\{r+1+x\mid x\in C_r\}.Сравнявайки сумите на елементите в двете описания на BrB_r, получаваме∑u∈Mu+∑i=1rsi=\sum_{u\in M}u+\sum_{i=1}^r s_i=∑i=1ri+b(r+1)+∑x∈Crx.\sum_{i=1}^r i+b(r+1)+\sum_{x\in C_r}x.Понеже si=i+ais_i=i+a_i, това е еквивалентно на∑u∈Mu+∑i=1r(ai−b)=b+∑x∈Crx.(1)\sum_{u\in M}u+\sum_{i=1}^r(a_i-b)=b+\sum_{x\in C_r}x.\tag{1}Нека сега n>m≥Nn\gt{}m\ge N. Прилагаме (1) за r=nr=n и r=mr=m и изваждаме. Получаваме∑i=m+1n(ai−b)=∑x∈Cnx−∑x∈Cmx.\sum_{i=m+1}^n(a_i-b)=\sum_{x\in C_n}x-\sum_{x\in C_m}x.Двете множества CnC_n и CmC_m са подмножества на {1,2,…,2014}\{1,2,\ldots,2014\} с по b−1b-1 елемента. Най-голямата възможна разлика между сумите на две такива множества е(b−1)(2015−b),(b-1)(2015-b),която се получава, ако едното множество е {1,2,…,b−1}\{1,2,\ldots,b-1\}, а другото е {2016−b,2017−b,…,2014}\{2016-b,2017-b,\ldots,2014\}. Следователно∣∑i=m+1n(ai−b)∣≤(b−1)(2015−b)≤\left|\sum_{i=m+1}^n(a_i-b)\right|\le(b-1)(2015-b)\le((b−1)+(2015−b)2)2=10072.\left(\frac{(b-1)+(2015-b)}2\right)^2=1007^2.Това доказва твърдението.
Отвори задачатаMathNetISL 2015 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека SS е непразно множество от положителни цели числа. Ще казваме, че положителното цяло число nn е чисто, ако има единствено представяне като сума на нечетен брой различни елементи от SS. Докажете, че съществуват безкрайно много положителни цели числа, които не са чисти.
РешениеЩе наричаме едно представяне на число като сума на различни елементи от SS нечетно или четно според четността на броя събираеми. Да допуснем противното: само краен брой положителни цели числа не са чисти. Тогава съществува положително цяло число NN, такова че всяко n>Nn\gt{}N има точно едно нечетно представяне. Ясно е, че SS е безкрайно. Свойство 1. Всяко положително цяло число има най-много едно нечетно и най-много едно четно представяне. Първо ще докажем твърдението за четните представяния. Избираме x∈Sx\in S с x>max⁡{n,N}x\gt{}\max\{n,N\}. Ако nn имаше две различни четни представяния, то като добавим xx към всяко от тях, бихме получили две различни нечетни представяния на n+xn+x, което е невъзможно. Аналогично, ако nn имаше две различни нечетни представяния, избираме две различни числа y,z∈Sy,z\in S с y,z>max⁡{n,N}y,z\gt{}\max\{n,N\} и добавяме y+zy+z към двете представяния. Така получаваме две различни нечетни представяния на n+y+zn+y+z, отново противоречие. Свойство 2. Нека s∈Ss\in S. Ако число n>Nn\gt{}N няма четно представяне, то n+2asn+2as има четно представяне, съдържащо ss, за всяко цяло a≥1a\ge1. Достатъчно е да докажем следната стъпка: ако nn няма четно представяне без ss, то n+2sn+2s има четно представяне, което съдържа ss. Нечетното представяне на n+sn+s не съдържа ss, защото иначе след премахване на ss бихме получили четно представяне на nn без ss. Добавяйки ss към това нечетно представяне на n+sn+s, получаваме четно представяне на n+2sn+2s, съдържащо ss. Повтарянето на тази стъпка доказва свойството. Свойство 3. Всяко достатъчно голямо положително цяло число има четно представяне. Фиксираме s∈Ss\in S. За всяко r∈{1,2,…,2s}r\in\{1,2,\ldots,2s\} разглеждаме прогресията Zr={r+2as∣a≥0}Z_r=\{r+2as\mid a\ge0\}. От свойство 2 следва, че във всяка такава прогресия има най-много едно число, по-голямо от NN, което няма четно представяне. Понеже положителните цели числа са обединение на тези 2s2s прогресии, само краен брой положителни цели числа нямат четно представяне. Увеличаваме NN при нужда така, че всяко n>Nn\gt{}N да има точно едно нечетно и точно едно четно представяне. В частност всеки елемент s>Ns\gt{}N от SS има четно представяне. Свойство 4. Ако s,t∈Ss,t\in S и N<s<tN\lt{}s\lt{}t, то четното представяне на tt съдържа ss. Ако не, тогава s+ts+t има две различни нечетни представяния: едното се получава, като добавим ss към четното представяне на tt, а другото - като добавим tt към четното представяне на ss. Това противоречи на свойство 1. Нека s1<s2<⋯s_1\lt{}s_2\lt{}\cdots са всички елементи на SS и нека σn=s1+s2+⋯+sn\sigma_n=s_1+s_2+\cdots+s_n, като σ0=0\sigma_0=0. Избираме kk, за което sk>Ns_k\gt{}N. По свойство 4, за всяко i>ki\gt{}k четното представяне на sis_i съдържа всички числа sk,sk+1,…,si−1s_k,s_{k+1},\ldots,s_{i-1}. Следователноsi=sk+sk+1+⋯+si−1+Ri=σi−1−σk−1+Ri,s_i=s_k+s_{k+1}+\cdots+s_{i-1}+R_i=\sigma_{i-1}-\sigma_{k-1}+R_i,(1)\tag{1}където RiR_i е сума на някои от числата s1,s2,…,sk−1s_1,s_2,\ldots,s_{k-1}. В частност 0≤Ri≤σk−10\le R_i\le\sigma_{k-1}. Избираме j0>kj_0\gt{}k така, че σj0>2σk−1\sigma_{j_0}\gt{}2\sigma_{k-1}. От (1) следва, че за всяко j>j0j\gt{}j_0 имамеsj+1≥σj−σk−1>σj2.(2)s_{j+1}\ge\sigma_j-\sigma_{k-1}\gt{}\frac{\sigma_j}{2}.\tag{2}Сега избираме индекс p>j0+1p\gt{}j_0+1, за който RpR_p е минимално сред всички RiR_i с i>j0+1i\gt{}j_0+1. Тогаваsp+1=sk+sk+1+⋯+sp+Rp+1=s_{p+1}=s_k+s_{k+1}+\cdots+s_p+R_{p+1}=(sp−Rp)+sp+Rp+1≥(s_p-R_p)+s_p+R_{p+1}\ge2sp.2s_p.Значи в SS няма елемент, който е по-голям от sps_p и по-малък от 2sp2s_p. Числото 2sp2s_p е достатъчно голямо, следователно има четно представяне. Това представяне не може да съдържа елемент на SS, по-голям от sps_p, защото такъв елемент би бил поне 2sp2s_p. От друга страна, от (2), приложено за j=p−1j=p-1, имаме 2sp>σp−12s_p\gt{}\sigma_{p-1}. Затова четното представяне на 2sp2s_p не може да използва само елементи измежду s1,s2,…,sp−1s_1,s_2,\ldots,s_{p-1}; то трябва да съдържа sps_p. Премахвайки sps_p от това четно представяне на 2sp2s_p, получаваме нечетно представяне на sps_p, което не съдържа самото sps_p. Но sps_p само по себе си също е нечетно представяне на sps_p. Това противоречи на свойство 1. Следователно предположението е невярно и има безкрайно много положителни цели числа, които не са чисти.
Отвори задачатаMathNetISL 2015 C6Условие — източник

Задача N1

Пълен запис
Условие
Да се определят всички положителни цели числа MM, за които редицата a0,a1,a2,…a_0,a_1,a_2,\ldots, зададена сa0=2M+12,a_0=\frac{2M+1}{2},ak+1=ak⌊ak⌋(k=0,1,2,…),\qquad a_{k+1}=a_k\lfloor a_k\rfloor\quad(k=0,1,2,\ldots),съдържа поне един цял член.
РешениеОтговорът е: всички цели числа M≥2M\ge2. Полагаме bk=2akb_k=2a_k за всяко k≥0k\ge0. Тогаваbk+1=2ak+1=2ak⌊ak⌋=bk⌊bk2⌋.b_{k+1}=2a_{k+1}=2a_k\lfloor a_k\rfloor=b_k\left\lfloor\frac{b_k}{2}\right\rfloor.Понеже b0b_0 е цяло число, всички bkb_k са цели. Да допуснем, че редицата a0,a1,a2,…a_0,a_1,a_2,\ldots няма цял член. Тогава всяко bkb_k е нечетно иbk+1=bkbk−12.(1)b_{k+1}=b_k\frac{b_k-1}{2}.\tag{1}Следователноbk+1−3=bk(bk−1)2−3=(bk−3)(bk+2)2.(2)b_{k+1}-3=\frac{b_k(b_k-1)}2-3=\frac{(b_k-3)(b_k+2)}2.\tag{2}Ако b0−3>0b_0-3\gt{}0, то от (2) следва bk−3>0b_k-3\gt{}0 за всяко k≥0k\ge0. Нека ck=v2(bk−3)c_k=v_2(b_k-3) е показателят на най-високата степен на 22, която дели bk−3b_k-3. Тъй като bk−3b_k-3 е положително четно число, ckc_k е положително цяло число. Но bk+2b_k+2 е нечетно, така че от (2) получавамеck+1=ck−1,c_{k+1}=c_k-1,което е невъзможно за безкрайна редица от положителни цели числа. Значи b0−3≤0b_0-3\le0, откъдето M=1M=1. При M=1M=1 имаме a0=3/2a_0=3/2 и редицата е константна: ak=3/2a_k=3/2 за всяко k≥0k\ge0, така че тя не съдържа цял член. Следователно точно за M≥2M\ge2 в редицата има поне един цял член.
Отвори задачатаMathNetISL 2015 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека aa и bb са положителни цели числа, за които a!b!a!b! се дели на a!+b!a!+b!. Докажете, че3a≥2b+2.3a\ge2b+2.
РешениеАко a>ba\gt{}b, неравенството 3a≥2b+23a\ge2b+2 следва веднага. Ако a=ba=b, то то е еквивалентно на a≥2a\ge2, а двойката (a,b)=(1,1)(a,b)=(1,1) не удовлетворява условието. Затова можем да приемем, че a<ba\lt{}b. Полагаме c=b−ac=b-a. Тогава трябва да докажем a≥2c+2a\ge2c+2. Да допуснем противното, т.е. a≤2c+1a\le2c+1. НекаM=b!a!=(a+1)(a+2)⋯(a+c).M=\frac{b!}{a!}=(a+1)(a+2)\cdots(a+c).От делимостта a!+b!∣a!b!a!+b!\mid a!b! следва1+M∣a!M.1+M\mid a!M.Понеже gcd⁡(1+M,M)=1\gcd(1+M,M)=1, получаваме 1+M∣a!1+M\mid a!. Не може да е c≥ac\ge a, защото тогава 1+M>a!1+M\gt{}a!. Значи c<ac\lt{}a. Произведението MM е от cc последователни цели числа, следователно c!∣Mc!\mid M. Оттук gcd⁡(1+M,c!)=1\gcd(1+M,c!)=1 и затова1+M∣a!c!=(c+1)(c+2)⋯a.(1)1+M\mid\frac{a!}{c!}=(c+1)(c+2)\cdots a.\tag{1}Ако a≤2ca\le2c, то a!/c!a!/c! е произведение на a−c≤ca-c\le c числа, всяко от които не надминава aa, докато MM е произведение на cc числа, всяко от които е по-голямо от aa. Следователно 1+M>a!/c!1+M\gt{}a!/c!, което противоречи на (1). Остава случаят a=2c+1a=2c+1. Тогава a+1=2(c+1)a+1=2(c+1), така че c+1∣Mc+1\mid M. От (1) и gcd⁡(1+M,c+1)=1\gcd(1+M,c+1)=1 получаваме1+M∣(c+2)(c+3)⋯a.1+M\mid(c+2)(c+3)\cdots a.Дясната страна е произведение на cc числа, които не надминават aa, и е по-малка от 1+M1+M. Това е ново противоречие. Следователно предположението a≤2c+1a\le2c+1 е невъзможно и a≥2c+2a\ge2c+2, което е точно 3a≥2b+23a\ge2b+2.
Отвори задачатаMathNetISL 2015 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека mm и nn са положителни цели числа, като m>nm\gt{}n. За k=1,2,…,n+1k=1,2,\ldots,n+1 дефинирамеxk=m+kn+k.x_k=\frac{m+k}{n+k}.Докажете, че ако всички числа x1,x2,…,xn+1x_1,x_2,\ldots,x_{n+1} са цели, то x1x2⋯xn+1−1x_1x_2\cdots x_{n+1}-1 се дели на нечетно просто число.
РешениеДа предположим, че x1,x2,…,xn+1x_1,x_2,\ldots,x_{n+1} са цели. Некаak=xk−1=m+kn+k−1=m−nn+k>0a_k=x_k-1=\frac{m+k}{n+k}-1=\frac{m-n}{n+k}\gt{}0за k=1,2,…,n+1k=1,2,\ldots,n+1. ПишемP=x1x2⋯xn+1−1.P=x_1x_2\cdots x_{n+1}-1.Достатъчно е да докажем, че PP не е степен на 22. Нека 2d2^d е най-голямата степен на 22, която дели m−nm-n, а 2c2^c е най-голямата степен на 22, която не надминава 2n+12n+1. Тогава2n+1≤2c+1−1,2n+1\le2^{c+1}-1,откъдето n+1≤2cn+1\le2^c. Следователно 2c2^c е едно от числата n+1,n+2,…,2n+1n+1,n+2,\ldots,2n+1, и то е единственото кратно на 2c2^c сред тях. Нека ℓ\ell е такова, чеn+ℓ=2c.n+\ell=2^c.Понеже aℓ=(m−n)/(n+ℓ)a_\ell=(m-n)/(n+\ell) е цяло число, имаме d≥cd\ge c. Числото aℓa_\ell се дели точно на 2d−c2^{d-c}, а за всяко k≠ℓk\ne\ell числото aka_k се дели на 2d−c+12^{d-c+1}. Затова, работейки по модул 2d−c+12^{d-c+1}, получавамеP=(a1+1)(a2+1)⋯(an+1+1)−1≡P=(a_1+1)(a_2+1)\cdots(a_{n+1}+1)-1\equiv(aℓ+1)−1=aℓ≢0(mod2d−c+1).(a_\ell+1)-1=a_\ell\not\equiv0\pmod {2^{d-c+1}}.Значи 2d−c+1∤P2^{d-c+1}\nmid P. От друга страна, за всяко k≠ℓk\ne\ell имаме 2d−c+1∣ak2^{d-c+1}\mid a_k, а същоP=(a1+1)⋯(an+1+1)−1≥ak.P=(a_1+1)\cdots(a_{n+1}+1)-1\ge a_k.Следователно P≥2d−c+1P\ge2^{d-c+1}. Ако PP беше степен на 22, от 2d−c+1∤P2^{d-c+1}\nmid P щеше да следва P<2d−c+1P\lt{}2^{d-c+1}, противоречие. Така PP не е степен на 22, а значи има нечетен прост делител.
Отвори задачатаMathNetISL 2015 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека a0,a1,…a_0,a_1,\ldots и b0,b1,…b_0,b_1,\ldots са две редици от положителни цели числа, за които a0,b0≥2a_0,b_0\ge2 иan+1=gcd⁡(an,bn)+1,bn+1=lcm⁡(an,bn)−1a_{n+1}=\gcd(a_n,b_n)+1,\qquad b_{n+1}=\operatorname{lcm}(a_n,b_n)-1за всяко n≥0n\ge0. Докажете, че редицата (an)(a_n) е периодична от някое място нататък; с други думи, съществуват цели числа N≥0N\ge0 и t>0t\gt{}0, за които an+t=ana_{n+t}=a_n за всяко n≥Nn\ge N.
РешениеНека sn=an+bns_n=a_n+b_n. Ако an∣bna_n\mid b_n, тоan+1=an+1,bn+1=bn−1,sn+1=sn.a_{n+1}=a_n+1,\qquad b_{n+1}=b_n-1,\qquad s_{n+1}=s_n.Така ana_n се увеличава с 11, а sns_n не се променя, докато стигнем до първи индекс, при който an∤sna_n\nmid s_n. ДефинирамеWn={m∈Z>0:m≥an и m∤sn},wn=min⁡Wn.W_n=\{m\in\mathbb Z_{\gt{}0}:m\ge a_n\text{ и }m\nmid s_n\},\qquad w_n=\min W_n.Множеството WnW_n е непразно, защото всички достатъчно големи mm не делят sns_n. Първо ще докажем, че редицата (wn)(w_n) е невъзрастваща. Ако an∣bna_n\mid b_n, то an∣sna_n\mid s_n, an+1=an+1a_{n+1}=a_n+1 и sn+1=sns_{n+1}=s_n; понеже an∉Wna_n\notin W_n, получаваме Wn+1=WnW_{n+1}=W_n и wn+1=wnw_{n+1}=w_n. Ако an∤bna_n\nmid b_n, то an∤sna_n\nmid s_n, следователно wn=anw_n=a_n. Освен това an+1=gcd⁡(an,bn)+1≤ana_{n+1}=\gcd(a_n,b_n)+1\le a_n иsn+1=gcd⁡(an,bn)+lcm⁡(an,bn).s_{n+1}=\gcd(a_n,b_n)+\operatorname{lcm}(a_n,b_n).В тази сума вторият член се дели на ana_n, а първият не се дели на ana_n, така че an∤sn+1a_n\nmid s_{n+1}. Значи an∈Wn+1a_n\in W_{n+1} и wn+1≤an=wnw_{n+1}\le a_n=w_n. Нека ww е най-малката стойност на редицата (wn)(w_n) и нека NN е индекс, за който wN=ww_N=w. Тогава wn=ww_n=w за всяко n≥Nn\ge N. Полагамеgn=gcd⁡(w,sn).g_n=\gcd(w,s_n).От произволен индекс n≥Nn\ge N нататък числата an,an+1,…a_n,a_{n+1},\ldots се увеличават с 11, докато стигнат до ww, което е първата стойност, неделяща sns_n; след това редицата пада доgcd⁡(w,sn)+1=gn+1.\gcd(w,s_n)+1=g_n+1.Ще докажем, че gng_n е константно за n≥Nn\ge N. Ако an∣bna_n\mid b_n, то sn+1=sns_{n+1}=s_n и gn+1=gng_{n+1}=g_n. Ако an∤bna_n\nmid b_n, тогава, понеже n≥Nn\ge N, имаме an=wa_n=w. Следователноgcd⁡(an,bn)=gcd⁡(w,sn)=gn\gcd(a_n,b_n)=\gcd(w,s_n)=g_nиsn+1=gcd⁡(an,bn)+lcm⁡(an,bn)=s_{n+1}=\gcd(a_n,b_n)+\operatorname{lcm}(a_n,b_n)=gn+w(sn−w)gn.g_n+\frac{w(s_n-w)}{g_n}.Затоваgn+1=gcd⁡(w,sn+1)=g_{n+1}=\gcd(w,s_{n+1})=gcd⁡(w,gn+sn−wgnw)=gcd⁡(w,gn)=gn.\gcd\left(w,g_n+\frac{s_n-w}{g_n}w\right)=\gcd(w,g_n)=g_n.Нека g=gNg=g_N. Доказахме, че от някое място нататък редицата (an)(a_n) повтаря цикълаg+1, g+2, …, w, g+1.g+1,\ g+2,\ \ldots,\ w,\ g+1.Следователно (an)(a_n) е периодична от някое място нататък.
Отвори задачатаMathNetISL 2015 N4Условие — източник

Задача N5

Пълен запис
Условие
Да се определят всички тройки (a,b,c)(a,b,c) от положителни цели числа, за които ab−cab-c, bc−abc-a и ca−bca-b са степени на 22. Тук степен на 22 означава цяло число от вида 2n2^n, където nn е неотрицателно цяло число.
РешениеОтговорът е: (2,2,2)(2,2,2), трите пермутации на (2,2,3)(2,2,3) и шестте пермутации на всяка от тройките (2,6,11)(2,6,11) и (3,5,7)(3,5,7). Тези тройки се проверяват непосредствено. Нека (a,b,c)(a,b,c) е произволна тройка с исканото свойство. Ако например a=1a=1, то b−cb-c и c−bc-b трябва да са степени на 22, което е невъзможно, понеже сумата им е 00. По симетрия a,b,c≥2a,b,c\ge2. Първи случай: поне две от числата са равни. Без ограничение нека a=ba=b. Тогава a2−ca^2-c и a(c−1)a(c-1) са степени на 22. От второто следва, че aa и c−1c-1 са степени на 22, т.е.a=2α,c=2γ+1a=2^\alpha,\qquad c=2^\gamma+1за някои неотрицателни цели α\alpha и γ\gamma. Числотоa2−c=22α−2γ−1a^2-c=2^{2\alpha}-2^\gamma-1е степен на 22, следователно не е сравнимо с −1-1 по модул 44; затова γ≤1\gamma\le1. Но числата 22α−22^{2\alpha}-2 и 22α−32^{2\alpha}-3 могат да бъдат степени на 22 само при α=1\alpha=1. Получаваме тройките (2,2,2)(2,2,2) и (2,2,3)(2,2,3), заедно с пермутациите. Втори случай: a,b,ca,b,c са различни. По симетрия приемаме2≤a<b<c.(1)2\le a\lt{}b\lt{}c.\tag{1}Трябва да докажем, че (a,b,c)(a,b,c) е (2,6,11)(2,6,11) или (3,5,7)(3,5,7). Некаbc−a=2α,ac−b=2β,ab−c=2γ.bc-a=2^\alpha,\qquad ac-b=2^\beta,\qquad ab-c=2^\gamma.От (1) веднага следваα>β>γ.(2)\alpha\gt{}\beta\gt{}\gamma.\tag{2}Подслучай 2.1: a=2a=2. Ще докажем, че γ=0\gamma=0. Ако γ>0\gamma\gt{}0, от 2b−c=2γ2b-c=2^\gamma следва, че cc е четно, а от 2c−b=2β2c-b=2^\beta и (2) следва, че bb е четно. Тогава bc−2≡2(mod4)bc-2\equiv2\pmod4, така че степента bc−2=2αbc-2=2^\alpha трябва да е равна на 22, което противоречи на b<cb\lt{}c и b>2b\gt{}2. Значи γ=0\gamma=0 иc=2b−1.c=2b-1.От 2c−b=2β2c-b=2^\beta получаваме3b−2=2β.3b-2=2^\beta.Понеже b>2b\gt{}2, това е възможно само при β≥4\beta\ge4. Ако β=4\beta=4, намираме b=6b=6 и c=11c=11, което дава решение. Остава да изключим β≥5\beta\ge5. Тогава от bc−2=2αbc-2=2^\alpha следва9⋅2α=9b(2b−1)−18=9\cdot2^\alpha=9b(2b-1)-18=(3b−2)(6b+1)−16=2β(2β+1+5)−16.(3b-2)(6b+1)-16=2^\beta(2^{\beta+1}+5)-16.При β≥5\beta\ge5 дясната страна не се дели на 3232, следователно α≤4\alpha\le4, което противоречи на α>β\alpha\gt{}\beta. Подслучай 2.2: a≥3a\ge3. Избираме ϑ∈{−1,1}\vartheta\in\{-1,1\} така, че c−ϑc-\vartheta да не се дели на 44. Тогава2α+ϑ2β=(bc−aϑ2)+ϑ(ca−b)=2^\alpha+\vartheta2^\beta=(bc-a\vartheta^2)+\vartheta(ca-b)=(b+aϑ)(c−ϑ).(b+a\vartheta)(c-\vartheta).Лявата страна се дели на 2β2^\beta, а c−ϑc-\vartheta не се дели на 44, следователно b+aϑb+a\vartheta се дели на 2β−12^{\beta-1}. От друга страна2β=ac−b>(a−1)c≥2c,2^\beta=ac-b\gt{}(a-1)c\ge2c,така че aa и bb са по-малки от 2β−12^{\beta-1}. Това е възможно само ако ϑ=1\vartheta=1 иa+b=2β−1.a+b=2^{\beta-1}.Тогава от ac−b=2βac-b=2^\beta получавамеac−b=2(a+b),ac-b=2(a+b),тоестa(c−1)=a+3b.a(c-1)=a+3b.Понеже a<b<ca\lt{}b\lt{}c, имаме a+3b<4ba+3b\lt{}4b и a(c−1)≥aba(c-1)\ge ab, откъдето ab<4bab\lt{}4b. Следователно a=3a=3. Сега равенството ac−b=2(a+b)ac-b=2(a+b) дава c=b+2c=b+2. От bc−a=2αbc-a=2^\alpha получавамеb(b+2)−3=(b−1)(b+3),b(b+2)-3=(b-1)(b+3),което е степен на 22. Значи и двата множителя b−1b-1 и b+3b+3 са степени на 22; разликата им е 44, затова b=5b=5 и c=7c=7. Така в случая на различни числа получаваме само (2,6,11)(2,6,11) и (3,5,7)(3,5,7), а заедно с пермутациите и първия случай това са точно изброените тройки.
Отвори задачатаMathNetISL 2015 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Разглеждаме функция f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0}. За m,n∈Z>0m,n\in\mathbb Z_{\gt{}0} означаваме с fn(m)f^n(m) nn-кратното прилагане на ff върху mm. Да предположим, че ff има следните две свойства: (i) ако m,n∈Z>0m,n\in\mathbb Z_{\gt{}0}, тоfn(m)−mn∈Z>0;\frac{f^n(m)-m}{n}\in\mathbb Z_{\gt{}0};(ii) множеството Z>0∖{f(n)∣n∈Z>0}\mathbb Z_{\gt{}0}\setminus\{f(n)\mid n\in\mathbb Z_{\gt{}0}\} е крайно. Докажете, че редицатаf(1)−1, f(2)−2, f(3)−3,…f(1)-1,\ f(2)-2,\ f(3)-3,\ldotsе периодична.
РешениеЩе докажем твърдението в три стъпки. Първо ще покажем, че ff е инективна. Нека f(m)=f(k)f(m)=f(k). Тогава за всяко положително цяло число nn имаме fn(m)=fn(k)f^n(m)=f^n(k) и по условиеk−mn=fn(m)−mn−fn(k)−kn\frac{k-m}{n}=\frac{f^n(m)-m}{n}-\frac{f^n(k)-k}{n}е цяло число. При n=∣k−m∣+1n=|k-m|+1 това е възможно само ако k=mk=m. По условие (ii) има краен брой положителни цели числа a1,a2,…,ara_1,a_2,\ldots,a_r, които не са стойности на ff. От условие (i) при n=1n=1 следва f(m)>mf(m)\gt{}m за всяко mm. Ще докажем, че всяко положително цяло число се записва еднозначно във видаfj(ai)f^j(a_i)за някои j≥0j\ge0 и 1≤i≤r1\le i\le r. Единствеността следва от инективността. Съществуването се доказва с индукция по числото: ако то не е сред aia_i, то е равно на f(n1)f(n_1) за някое n1<nn_1\lt{}n, към което прилагаме индукционното предположение. Следователно всички положителни цели числа се появяват точно по веднъж в таблицатаa1f(a1)f2(a1)f3(a1)⋯a2f(a2)f2(a2)f3(a2)⋯⋮⋮⋮⋮arf(ar)f2(ar)f3(ar)⋯\begin{array}{ccccc} a_1&f(a_1)&f^2(a_1)&f^3(a_1)&\cdots\cr a_2&f(a_2)&f^2(a_2)&f^3(a_2)&\cdots\cr \vdots&\vdots&\vdots&\vdots&\cr a_r&f(a_r)&f^2(a_r)&f^3(a_r)&\cdots \end{array}Втората стъпка е да докажем, че всеки ред на тази таблица е аритметична прогресия. Да допуснем противното. След евентуално пренареждане на редовете нека точно първите tt реда са аритметични прогресии, с разлики T1,T2,…,TtT_1,T_2,\ldots,T_t, където 0≤t<r0\le t\lt{}r. Ако t>0t\gt{}0, полагамеT=lcm⁡(T1,T2,…,Tt),T=\operatorname{lcm}(T_1,T_2,\ldots,T_t),A=max⁡{a1,a2,…,at};\qquad A=\max\{a_1,a_2,\ldots,a_t\};ако t=0t=0, полагаме T=1T=1 и A=0A=0. За всяко цяло n≥An\ge A интервалътΔn=[n+1,n+T]\Delta_n=[n+1,n+T]съдържа точно T/TiT/T_i елемента от ii-тия ред за 1≤i≤t1\le i\le t. Затова броят на елементите от последните r−tr-t реда в Δn\Delta_n не зависи от n≥An\ge A. Той не може да е 00, понеже тези редове съдържат безкрайно много числа. Значи всеки такъв интервал съдържа поне един елемент от последните r−tr-t реда. Следователно за всяко положително цяло число dd интервалът[A+1,A+(d+1)(r−t)T][A+1,A+(d+1)(r-t)T]съдържа поне (d+1)(r−t)(d+1)(r-t) елемента от последните r−tr-t реда. По принципа на Дирихле за някой индекс xx с t+1≤x≤rt+1\le x\le r имамеfd(ax)≤A+(d+1)(r−t)T.f^d(a_x)\le A+(d+1)(r-t)T.Понеже има само краен брой възможности за xx, съществува индекс x≥t+1x\ge t+1, за който множествотоX={d∈Z>0:fd(ax)≤A+(d+1)(r−t)T}X=\{d\in\mathbb Z_{\gt{}0}:f^d(a_x)\le A+(d+1)(r-t)T\}е безкрайно. За d∈Xd\in X числотоβd=fd(ax)−axd\beta_d=\frac{f^d(a_x)-a_x}{d}е положително цяло и е ограничено отгоре, например с A+2(r−t)TA+2(r-t)T. Затова за някое положително цяло число TxT_x множествотоY={d∈X:βd=Tx}Y=\{d\in X:\beta_d=T_x\}е безкрайно. Тоестfd(ax)=ax+dTx(d∈Y).f^d(a_x)=a_x+dT_x\qquad(d\in Y).Сега фиксираме произволно положително цяло число jj. Избираме y∈Yy\in Y така, чеy−j>∣fj(ax)−(ax+jTx)∣.y-j\gt{}|f^j(a_x)-(a_x+jT_x)|.Двете числаfy(ax)−fj(ax)=fy−j(fj(ax))−fj(ax)f^y(a_x)-f^j(a_x)=f^{y-j}(f^j(a_x))-f^j(a_x)иfy(ax)−(ax+jTx)=(y−j)Txf^y(a_x)-(a_x+jT_x)=(y-j)T_xсе делят на y−jy-j. Разликата им също се дели на y−jy-j, но по избора на yy абсолютната и стойност е по-малка от y−jy-j. Значи тази разлика е 00, тоестfj(ax)=ax+jTx.f^j(a_x)=a_x+jT_x.Това е вярно за всяко jj, така че xx-тият ред е аритметична прогресия - противоречие. Следователно всички редове са аритметични прогресии. Накрая, нека TiT_i е разликата на ii-тия ред иT=lcm⁡(T1,T2,…,Tr).T=\operatorname{lcm}(T_1,T_2,\ldots,T_r).Ако числото nn лежи в ii-тия ред, тоfj(n)=n+jTi(j≥0).f^j(n)=n+jT_i\qquad(j\ge0).Следователноf(n+T)−f(n)=f1+T/Ti(n)−f(n)=f(n+T)-f(n)=f^{1+T/T_i}(n)-f(n)=(n+T+Ti)−(n+Ti)=T.(n+T+T_i)-(n+T_i)=T.Такаf(n+T)−(n+T)=f(n)−nf(n+T)-(n+T)=f(n)-nза всяко положително цяло число nn. Редицата f(1)−1,f(2)−2,f(3)−3,…f(1)-1,f(2)-2,f(3)-3,\ldots е периодична с период TT.
Отвори задачатаMathNetISL 2015 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. За положително цяло число kk ще наричаме функция f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0} kk-добра, акоgcd⁡(f(m)+n,f(n)+m)≤k\gcd(f(m)+n,f(n)+m)\le kза всички m≠nm\ne n. Да се намерят всички kk, за които съществува kk-добра функция.
РешениеОтговорът е: всички k≥2k\ge2. Ако една функция е kk-добра, тя е и (k+1)(k+1)-добра. Затова е достатъчно да докажем, че не съществува 11-добра функция, и да построим 22-добра функция. Първо да допуснем, че съществува функция ff сgcd⁡(f(m)+n,f(n)+m)=1\gcd(f(m)+n,f(n)+m)=1за всички m≠nm\ne n. Ако има две различни четни числа mm и nn, за които f(m)f(m) и f(n)f(n) са четни, тогава и двете числа f(m)+nf(m)+n и f(n)+mf(n)+m са четни - противоречие. Аналогично не може да има две различни нечетни числа mm и nn, за които f(m)f(m) и f(n)f(n) са нечетни. Следователно можем да изберем четно mm с f(m)f(m) нечетно и нечетно nn с f(n)f(n) четно. Тогава отново и f(m)+nf(m)+n, и f(n)+mf(n)+m са четни, противоречие. Значи 11-добра функция няма. Остава да построим 22-добра функция. Дефинирамеf(n)=2g(n)+1−n−1,f(n)=2^{g(n)+1}-n-1,където gg е зададена рекурентно чрезg(1)=1,g(n+1)=(2g(n)+1)!.g(1)=1,\qquad g(n+1)=\left(2^{g(n)+1}\right)!.Нека m>nm\gt{}n и положимA=f(m)+n=2g(m)+1−m+n−1,A=f(m)+n=2^{g(m)+1}-m+n-1,B=f(n)+m=2g(n)+1−n+m−1.B=f(n)+m=2^{g(n)+1}-n+m-1.Ще докажем, че gcd⁡(A,B)≤2\gcd(A,B)\le2. ИмамеA+B=2g(m)+1+2g(n)+1−2,A+B=2^{g(m)+1}+2^{g(n)+1}-2,което не се дели на 44. Следователно 4∤gcd⁡(A,B)4\nmid\gcd(A,B). Да допуснем, че нечетно просто число pp дели gcd⁡(A,B)\gcd(A,B). Първо ще използваме оценката2g(m−1)+1≥B.2^{g(m-1)+1}\ge B.Наистина, g(k+1)>g(k)g(k+1)\gt{}g(k), откъдето2g(k+1)+1≥2g(k)+1+12^{g(k+1)+1}\ge2^{g(k)+1}+1за всяко kk. Повтаряйки това от nn до m−1m-1, получаваме2g(m−1)+1≥2g(n)+1+m−1−n=B.2^{g(m-1)+1}\ge2^{g(n)+1}+m-1-n=B.Понеже p∣Bp\mid B, имаме p−1<B≤2g(m−1)+1p-1\lt{}B\le2^{g(m-1)+1}, следователноp−1∣(2g(m−1)+1)≠g(m).p-1\mid\left(2^{g(m-1)+1}\right)\neq{}g(m).По малката теорема на Ферма 2g(m)≡1(modp)2^{g(m)}\equiv1\pmod p. От p∣Ap\mid A и p∣Bp\mid B следва A+B≡0(modp)A+B\equiv0\pmod p, но тогава0≡A+B=2g(m)+1+2g(n)+1−2≡2g(n)+1(modp),0\equiv A+B=2^{g(m)+1}+2^{g(n)+1}-2\equiv2^{g(n)+1}\pmod p,което е невъзможно за нечетно просто pp. Значи няма нечетен прост делител на gcd⁡(A,B)\gcd(A,B), а понеже 4∤gcd⁡(A,B)4\nmid\gcd(A,B), получаваме gcd⁡(A,B)≤2\gcd(A,B)\le2. Така построената функция е 22-добра, а от началото следва, че търсените стойности са точно k≥2k\ge2.
Отвори задачатаMathNetISL 2015 N7Условие — източник

Задача N8

Пълен запис
Условие
За всяко положително цяло число nn с разлагане на прости множителиn=∏i=1kpiαin=\prod_{i=1}^k p_i^{\alpha_i}дефинирамеΩ>10100(n)=∑i:pi>10100αi.\Omega_{\gt{}10^{100}}(n)=\sum_{i:p_i\gt{}10^{100}}\alpha_i.Тоест Ω>10100(n)\Omega_{\gt{}10^{100}}(n) е броят на простите множители на nn, по-големи от 1010010^{100}, броени с кратност. Да се намерят всички строго растящи функции f:Z→Zf:\mathbb Z\to\mathbb Z, за коитоΩ>10100(f(a)−f(b))≤Ω>10100(a−b)\Omega_{\gt{}10^{100}}(f(a)-f(b))\le\Omega_{\gt{}10^{100}}(a-b)за всички цели числа aa и bb с a>ba\gt{}b.
РешениеОтговорът еf(x)=Ax+B,f(x)=Ax+B,където BB е произволно цяло число, а AA е произволно положително цяло число с Ω>10100(A)=0\Omega_{\gt{}10^{100}}(A)=0. Посочените функции очевидно удовлетворяват условието. Остава да докажем обратното. Функцията g(x)=f(x)−f(0)g(x)=f(x)-f(0) има същото свойство, затова можем да приемем, че f(0)=0f(0)=0. Тогава f(n)>0f(n)\gt{}0 за всяко положително цяло число nn. Ще докажем, че f(n)=Anf(n)=An за всички цели nn, където AA е положително цяло число без прости делители, по-големи от 1010010^{100}. Нека N=10100N=10^{100}. Ще наричаме простото число pp голямо, ако p>Np\gt{}N, и малко иначе. Нека S\mathcal S е множеството на всички малки прости числа. Положително цяло число ще наричаме голямо, ако всичките му прости делители са големи, и малко, ако всичките му прости делители са малки; числото 11 е и голямо, и малко. За положително цяло число kk означаваме с L(k)L(k) най-големия голям делител на kk, а с S(k)S(k) най-големия малък делител на kk. Тогава k=L(k)S(k)k=L(k)S(k). Първа стъпка. Ще докажем, че за всяко голямо kk е вярноk∣f(a)−f(b)точно когатоk∣a−b.k\mid f(a)-f(b)\quad\text{точно когато}\quad k\mid a-b.С други думи,L(f(a)−f(b))=L(a−b)L(f(a)-f(b))=L(a-b)за всички цели a>ba\gt{}b. Доказателството е с индукция по kk. Случаят k=1k=1 е ясен. Нека k0k_0 е голямо число и твърдението е доказано за всички големи k<k0k\lt{}k_0. Първо ще покажем, че ако 0<x−y<k00\lt{}x-y\lt{}k_0, то k0∤f(x)−f(y)k_0\nmid f(x)-f(y). Да допуснем противното. Нека ℓ=L(x−y)\ell=L(x-y). Тогава ℓ≤x−y<k0\ell\le x-y\lt{}k_0 и по индукционното предположение ℓ∣f(x)−f(y)\ell\mid f(x)-f(y). Следователноlcm⁡(k0,ℓ)∣f(x)−f(y).\operatorname{lcm}(k_0,\ell)\mid f(x)-f(y).Числото lcm⁡(k0,ℓ)\operatorname{lcm}(k_0,\ell) е голямо и е по-голямо от ℓ\ell, така чеΩ>N(f(x)−f(y))≥Ω>N(lcm⁡(k0,ℓ))>\Omega_{\gt{}N}(f(x)-f(y))\ge\Omega_{\gt{}N}(\operatorname{lcm}(k_0,\ell))\gt{}Ω>N(ℓ)=Ω>N(x−y),\Omega_{\gt{}N}(\ell)=\Omega_{\gt{}N}(x-y),противоречие. Сега фиксираме цяло число aa. От току-що доказаното следва, че числатаf(a),f(a+1),…,f(a+k0−1)f(a),f(a+1),\ldots,f(a+k_0-1)образуват пълна система от остатъци по модул k0k_0, както и числатаf(a+1),f(a+2),…,f(a+k0).f(a+1),f(a+2),\ldots,f(a+k_0).Двете системи имат общи k0−1k_0-1 члена, следователноf(a)≡f(a+k0)(modk0).f(a)\equiv f(a+k_0)\pmod {k_0}.Така a≡b(modk0)a\equiv b\pmod {k_0} води до f(a)≡f(b)(modk0)f(a)\equiv f(b)\pmod {k_0}. Ако a≢b(modk0)a\not\equiv b\pmod {k_0}, избираме b′b' с b′≡b(modk0)b'\equiv b\pmod {k_0} и ∣a−b′∣<k0|a-b'|\lt{}k_0. Тогава f(b′)≡f(b)(modk0)f(b')\equiv f(b)\pmod {k_0}, а от предходния абзац с разлика под k0k_0 имаме f(a)≢f(b′)(modk0)f(a)\not\equiv f(b')\pmod {k_0}. Следователно f(a)≢f(b)(modk0)f(a)\not\equiv f(b)\pmod {k_0}. Индукционната стъпка е доказана. Втора стъпка. Ще докажем, че за някое малко положително цяло число AA има безкрайно много положителни цели числа nn, за коитоf(n)=An.f(n)=An.Първо доказваме, че съществува константа CC, за коятоf(t)<Ctf(t)\lt{}Ctза всяко положително цяло число t>Nt\gt{}N. Нека dd е произведението на всички малки прости числа и нека α\alpha е положително цяло число с 2α>f(N)2^\alpha\gt{}f(N). За всяко p∈Sp\in\mathcal S числатаf(0),f(1),…,f(N)f(0),f(1),\ldots,f(N)са различни по модул pαp^\alpha. ПолагамеP=dα,C=P+f(N).P=d^\alpha,\qquad C=P+f(N).Нека t>Nt\gt{}N. За всяко p∈Sp\in\mathcal S има най-много едно j∈{0,1,…,N}j\in\{0,1,\ldots,N\}, за което pα∣f(t)−f(j)p^\alpha\mid f(t)-f(j). Понеже малките прости числа са по-малко от N+1N+1 на брой, можем да изберем j∈{0,1,…,N}j\in\{0,1,\ldots,N\} така, чеpα∤f(t)−f(j)p^\alpha\nmid f(t)-f(j)за всяко p∈Sp\in\mathcal S. ТогаваS(f(t)−f(j))<P.S(f(t)-f(j))\lt{}P.От първата стъпка пъкL(f(t)−f(j))=L(t−j)≤t−j.L(f(t)-f(j))=L(t-j)\le t-j.Затоваf(t)=f(j)+L(f(t)−f(j))S(f(t)−f(j))<f(t)=f(j)+L(f(t)-f(j))S(f(t)-f(j))\lt{}f(N)+(t−j)P≤Ct.f(N)+(t-j)P\le Ct.Нека T\mathcal T е множеството на големите прости числа. За t∈Tt\in\mathcal T първата стъпка даваL(f(t))=L(t)=t,L(f(t))=L(t)=t,така че f(t)/tf(t)/t е положително цяло число. От оценката f(t)<Ctf(t)\lt{}Ct следва, че това частно приема само краен брой стойности. Затова съществуват безкрайно множество T′⊆T\mathcal T'\subseteq\mathcal T и положително цяло число AA, за коитоf(t)=At(t∈T′).f(t)=At\qquad(t\in\mathcal T').От равенството L(f(t))=tL(f(t))=t за безкрайно много големи прости tt следва L(A)=1L(A)=1, т.е. AA е малко число. Трета стъпка. Ще докажем, че f(x)=Axf(x)=Ax за всяко цяло число xx. За всяко цяло ii некаRi={x∈Z:x≡i(modN!)}.R_i=\{x\in\mathbb Z:x\equiv i\pmod {N!}\}.Ще използваме следното твърдение: ако за някое rr има безкрайно много n∈Rrn\in R_r с f(n)=Anf(n)=An, то f(x)=Axf(x)=Ax за всяко x∈Rr+1x\in R_{r+1}. Наистина, фиксираме x∈Rr+1x\in R_{r+1}. Избираме n∈Rrn\in R_r така, че f(n)=Anf(n)=An и∣n−x∣>∣f(x)−Ax∣.|n-x|\gt{}|f(x)-Ax|.Понеже n−x≡−1(modN!)n-x\equiv -1\pmod {N!}, числото ∣n−x∣|n-x| е голямо. По първата стъпкаf(x)≡f(n)=An≡Ax(mod∣n−x∣).f(x)\equiv f(n)=An\equiv Ax\pmod {|n-x|}.Значи ∣n−x∣∣f(x)−Ax|n-x|\mid f(x)-Ax. От избора на nn следва f(x)−Ax=0f(x)-Ax=0. Множеството T′\mathcal T' от втората стъпка има безкрайно много елементи в някой клас RiR_i. Прилагайки последното твърдение последователно за класовете Ri+1,Ri+2,…,Ri+N!=RiR_{i+1},R_{i+2},\ldots,R_{i+N!}=R_i, получаваме f(x)=Axf(x)=Ax за всички цели xx. Връщайки извадената в началото константа f(0)f(0), получаваме общия видf(x)=Ax+B,f(x)=Ax+B,където B∈ZB\in\mathbb Z, A>0A\gt{}0 и Ω>10100(A)=0\Omega_{\gt{}10^{100}}(A)=0.
Отвори задачатаMathNetISL 2015 N8Условие — източник