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

IMO Shortlisted Problems

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

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

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

2020

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

11-12

23 задачи

Задача A1

Пълен запис
Условие
Версия 1. Нека nn е положително цяло число и нека N=2nN=2^n. Да се намери най-малкото реално число ana_n, за което за всяко реално xx е изпълненоx2x2N+12N≤an(x−1)2+x.\sqrt[N]{\vphantom{x^2}\frac{x^{2N}+1}{2}}\le a_n(x-1)^2+x.Версия 2. За всяко положително цяло число NN да се намери най-малкото реално число bNb_N, за което за всяко реално xx е изпълненоx2x2N+12N≤bN(x−1)2+x.\sqrt[N]{\vphantom{x^2}\frac{x^{2N}+1}{2}}\le b_N(x-1)^2+x.
РешениеОтговорът еan=2n−1иbN=N2.a_n=2^{n-1}\quad\text{и}\quad b_N=\frac N2.Първо доказваме долната граница. Нека a<N2a\lt{}\frac N2 и положим x=1+tx=1+t, където t>0t\gt{}0 е достатъчно малко. Ако неравенството беше вярно, след повдигане на степен NN бихме получили(1+t)2N+12≤(1+t+at2)N.\frac{(1+t)^{2N}+1}{2}\le (1+t+at^2)^N.Но разликата между дясната и лявата страна има вид(Na−N22)t2+c3t3+⋯+c2Nt2N,(Na-\frac{N^2}{2})t^2+c_3t^3+\cdots+c_{2N}t^{2N},което е отрицателно за достатъчно малко tt, понеже a<N/2a\lt{}N/2. Следователно всяка допустима константа е поне N/2N/2. За Версия 1 остава да докажем, че при N=2nN=2^n константата N/2N/2 работи. Ще докажем по индукция по N=2rN=2^r неравенствотоx21+x2N2N≤x+N2(x−1)2.(1)\sqrt[N]{\vphantom{x^2}\frac{1+x^{2N}}2}\le x+\frac N2(x-1)^2.\tag{1}При N=1N=1 то е равенство. Нека (1) е вярно за NN. Тогава за всяко реално xx имаме(x+N(x−1)2)2=x2+N2(x2−1)2+(N2−N2)(x−1)4≥x2+N2(x2−1)2≥x21+x4N2N,\begin{aligned} \left(x+N(x-1)^2\right)^2 &=x^2+\frac N2(x^2-1)^2+\left(N^2-\frac N2\right)(x-1)^4 \\ &\ge x^2+\frac N2(x^2-1)^2 \\ &\ge \sqrt[N]{\vphantom{x^2}\frac{1+x^{4N}}2}, \end{aligned}като последната стъпка е индукционното предположение, приложено за x2x^2. Освен товаx+N(x−1)2≥x+(x−1)22=x2+12≥0,x+N(x-1)^2\ge x+\frac{(x-1)^2}{2}=\frac{x^2+1}{2}\ge0,така че след коренуване получаваме (1) за 2N2N. Индукцията е завършена. За Версия 2 ще докажем по-силно, че N/2N/2 работи за всяко положително цяло NN. При N=1N=1 отново имаме равенство. Нека N>1N\gt{}1. За x=0x=0 неравенството е очевидно; а за x<0x\lt{}0 лявата страна е същата като при −x-x, докато дясната страна е по-голяма с 2(−x)(N−1)≥02(-x)(N-1)\ge0. Затова е достатъчно да разгледаме x>0x\gt{}0. ПоложимF(x)=(x2N+12)1/N−N2(x−1)2−x.F(x)=\left(\frac{x^{2N}+1}{2}\right)^{1/N}-\frac N2(x-1)^2-x.Тогава F(1)=F′(1)=F′′(1)=0F(1)=F'(1)=F''(1)=0, а пряко диференциране даваF′′′(x)=F'''(x)=12(1−N)(1−2N)(x2N+12)1/N−3x2N−3(1−x2N).\frac12(1-N)(1-2N)\left(\frac{x^{2N}+1}{2}\right)^{1/N-3}x^{2N-3}(1-x^{2N}).Следователно F′′′(x)>0F'''(x)\gt{}0 за 0<x<10\lt{}x\lt{}1 и F′′′(x)<0F'''(x)\lt{}0 за x>1x\gt{}1. Оттук F′′(x)<0F''(x)\lt{}0 за x≠1x\ne1, значи F′(x)>0F'(x)\gt{}0 за x<1x\lt{}1 и F′(x)<0F'(x)\lt{}0 за x>1x\gt{}1. Така FF достига максимум в x=1x=1, откъдето F(x)≤0F(x)\le0 за всички x>0x\gt{}0. Това доказва търсеното неравенство и завършва решението.
Отвори задачатаMathNetISL 2020 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека A\mathcal A е множеството от всички полиноми на три променливи x,y,zx,y,z с цели коефициенти. Нека B\mathcal B е подмножеството на A\mathcal A, съставено от всички полиноми, които могат да се представят във вида(x+y+z)P(x,y,z)(x+y+z)P(x,y,z)+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),+(xy+yz+zx)Q(x,y,z)+xyzR(x,y,z),където P,Q,R∈AP,Q,R\in\mathcal A. Да се намери най-малкото неотрицателно цяло число nn, за което xiyjzk∈Bx^iy^jz^k\in\mathcal B за всички неотрицателни цели числа i,j,ki,j,k с i+j+k≥ni+j+k\ge n.
РешениеОтговорът еn=4.n=4.Некаp=x+y+z,q=xy+yz+zx,r=xyz.p=x+y+z,\qquad q=xy+yz+zx,\qquad r=xyz.Първо ще докажем, че всеки моном от обща степен поне 44 принадлежи на B\mathcal B. По симетрия можем да приемем i≥j≥ki\ge j\ge k за монома xiyjzkx^iy^jz^k. Имаме0=(x−x)(x−y)(x−z)=x3−px2+qx−r,0=(x-x)(x-y)(x-z)=x^3-px^2+qx-r,следователно x3∈Bx^3\in\mathcal B. Освен товаx2y2=xyq−(x+y)r∈B.x^2y^2=xyq-(x+y)r\in\mathcal B.Ако k≥1k\ge1, тогава xyzxyz дели xiyjzkx^iy^jz^k, значи мономът е в B\mathcal B. Ако k=0k=0 и j≥2j\ge2, тогава x2y2x^2y^2 дели монома, така че отново сме готови. Накрая, ако k=0k=0 и j≤1j\le1, от условието i+j+k≥4i+j+k\ge4 следва i≥3i\ge3, така че x3x^3 дели монома. Следователно всички мономи от степен поне 44 са в B\mathcal B. Остава да покажем, че n=3n=3 не е достатъчно. Ще докажем, че x2y∉Bx^2y\notin\mathcal B. Да допуснем противното. Тогава за някои P,Q,R∈AP,Q,R\in\mathcal A имамеx2y=pP+qQ+rR.(1)x^2y=pP+qQ+rR.\tag{1}Достатъчно е да сравним хомогенните части от степен 33. Ако PP съдържа моном x2x^2 с ненулев коефициент, тогава pPpP съдържа моном x3x^3 със същия ненулев коефициент, който не може да бъде унищожен от другите членове от същата степен по начина, нужен за (1). Аналогично PP не може да съдържа y2y^2 или z2z^2. Затова хомогенните части от степен 22 на PP, от степен 11 на QQ и от степен 00 на RR можем да запишем съответно катоaxy+byz+czx,dx+ey+fz,g.axy+byz+czx,\qquad dx+ey+fz,\qquad g.Сравнявайки коефициентите от степен 33 в (1), получавамеx2y=x^2y=(x+y+z)(axy+byz+czx)(x+y+z)(axy+byz+czx)+(xy+yz+zx)(dx+ey+fz)+gxyz.+(xy+yz+zx)(dx+ey+fz)+gxyz.От коефициентите пред xy2xy^2, y2zy^2z, yz2yz^2, z2xz^2x, zx2zx^2 и x2zx^2z следваe=−a,e=−b,f=−b,e=-a,\quad e=-b,\quad f=-b,f=−c,d=−c,d=−a.\quad f=-c,\quad d=-c,\quad d=-a.Значи a=b=ca=b=c и d=e=f=−ad=e=f=-a. Но тогава коефициентът пред x2yx^2y в дясната страна е a+d=0a+d=0, противоречие. Следователно x2y∉Bx^2y\notin\mathcal B, и най-малкото nn е 44.
Отвори задачатаMathNetISL 2020 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека a,b,c,da,b,c,d са положителни реални числа, за които(a+c)(b+d)=ac+bd.(a+c)(b+d)=ac+bd.Да се намери най-малката възможна стойност наS=ab+bc+cd+da.S=\frac ab+\frac bc+\frac cd+\frac da.
РешениеОтговорът е8.8.По неравенството между средно аритметично и средно геометрично имамеS=(ab+cd)+(bc+da)≥2x2acbd+2x2bdac=2(ac+bd)x2abcd.\begin{aligned} S&=\left(\frac ab+\frac cd\right)+\left(\frac bc+\frac da\right) \\ &\ge 2\sqrt{\vphantom{x^2}\frac{ac}{bd}}+2\sqrt{\vphantom{x^2}\frac{bd}{ac}} =\frac{2(ac+bd)}{\sqrt{\vphantom{x^2}abcd}}. \end{aligned}От условието ac+bd=(a+c)(b+d)ac+bd=(a+c)(b+d), затоваS≥2(a+c)(b+d)x2abcd≥S\ge \frac{2(a+c)(b+d)}{\sqrt{\vphantom{x^2}abcd}}\ge2⋅2x2ac⋅2x2bdx2abcd=8. \frac{2\cdot2\sqrt{\vphantom{x^2}ac}\cdot2\sqrt{\vphantom{x^2}bd}}{\sqrt{\vphantom{x^2}abcd}}=8.Остава да видим, че равенството се достига. В горните две приложения на AM-GM равенство има, когато a=ca=c и b=db=d. Тогава условието става4ab=a2+b2,4ab=a^2+b^2,или, след деление на b2b^2,(ab)2−4ab+1=0.\left(\frac ab\right)^2-4\frac ab+1=0.Това е изпълнено например при a=c=1a=c=1 и b=d=2+3b=d=2+\sqrt3. За тези стойности S=8S=8, следователно минималната възможна стойност е 88.
Отвори задачатаMathNetISL 2020 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека a,b,c,da,b,c,d са реални числа, за които a≥b≥c≥d>0a\ge b\ge c\ge d\gt{}0 и a+b+c+d=1a+b+c+d=1. Докажете, че(a+2b+3c+4d)aabbccdd<1.(a+2b+3c+4d)a^ab^bc^cd^d\lt{}1.
РешениеПо претегленото неравенство между средно аритметично и средно геометрично с тегла a,b,c,da,b,c,d имамеaabbccdd≤a^ab^bc^cd^d\lea⋅a+b⋅b+c⋅c+d⋅d=a2+b2+c2+d2. a\cdot a+b\cdot b+c\cdot c+d\cdot d=a^2+b^2+c^2+d^2.Затова е достатъчно да докажем, че(a+2b+3c+4d)(a2+b2+c2+d2)<(a+2b+3c+4d)(a^2+b^2+c^2+d^2)\lt{}1=(a+b+c+d)3.1=(a+b+c+d)^3.Но(a+b+c+d)3>a2(a+3b+3c+3d)+b2(3a+b+3c+3d)+c2(3a+3b+c+3d)+d2(3a+3b+3c+d),\begin{aligned} (a+b+c+d)^3&\gt{}a^2(a+3b+3c+3d)+b^2(3a+b+3c+3d)\\ &\quad+c^2(3a+3b+c+3d)+d^2(3a+3b+3c+d), \end{aligned}защото в пълното развиване остават положителни смесени членове от вида 6abc6abc. От друга страна, понеже a≥b≥c≥da\ge b\ge c\ge d, имамеa+3b+3c+3d≥a+2b+3c+4d,3a+b+3c+3d≥a+2b+3c+4d,3a+3b+c+3d≥a+2b+3c+4d,3a+3b+3c+d≥a+2b+3c+4d.\begin{aligned} a+3b+3c+3d&\ge a+2b+3c+4d,\\ 3a+b+3c+3d&\ge a+2b+3c+4d,\\ 3a+3b+c+3d&\ge a+2b+3c+4d,\\ 3a+3b+3c+d&\ge a+2b+3c+4d. \end{aligned}Умножавайки тези четири неравенства съответно по a2,b2,c2,d2a^2,b^2,c^2,d^2 и събирайки, получаваме(a+b+c+d)3>(a2+b2+c2+d2)(a+2b+3c+4d).(a+b+c+d)^3\gt{}(a^2+b^2+c^2+d^2)(a+2b+3c+4d).Следователно(a+2b+3c+4d)aabbccdd<1,(a+2b+3c+4d)a^ab^bc^cd^d\lt{}1,както се искаше.
Отвори задачатаMathNetISL 2020 A4Условие — източник

Задача A5

Пълен запис
Условие
Една магьосница възнамерява да изпълни следния трик. Тя обявява на публиката положително цяло число nn и 2n2n реални числа x1<…<x2nx_1\lt{}\ldots\lt{}x_{2n}. След това човек от публиката тайно избира полином P(x)P(x) от степен nn с реални коефициенти, пресмята 2n2n-те стойности P(x1),…,P(x2n)P(x_1),\ldots,P(x_{2n}) и ги записва на дъската в ненамаляващ ред. След това магьосницата обявява тайния полином на публиката. Може ли магьосницата да намери стратегия, с която да изпълни такъв трик?
РешениеОтговорът е: не, не може. Нека x1<x2<⋯<x2nx_1\lt{}x_2\lt{}\cdots\lt{}x_{2n} са реалните числа, избрани от магьосницата. Ще построим два различни полинома P(x)P(x) и Q(x)Q(x), всеки от степен nn, които дават един и същ списък от стойности след подреждане. Тогава магьосницата няма как да различи двата полинома. Твърдение. Съществува полином P(x)P(x) от степен nn, за койтоP(x2i−1)+P(x2i)=0(i=1,2,…,n).P(x_{2i-1})+P(x_{2i})=0\qquad(i=1,2,\ldots,n).Доказателство. Търсим полиномanxn+an−1xn−1+⋯+a1x+a0,a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,чиито коефициенти удовлетворяват уравненията(x2i−1n+x2in)an+(x2i−1n−1+x2in−1)an−1+⋯+2a0=0(i=1,2,…,n).\begin{aligned} &(x_{2i-1}^n+x_{2i}^n)a_n+(x_{2i-1}^{n-1}+x_{2i}^{n-1})a_{n-1}\\ &\qquad+\cdots+2a_0=0\qquad(i=1,2,\ldots,n). \end{aligned}Това е хомогенна система от nn линейни уравнения с n+1n+1 неизвестни, следователно има ненулево решение. Получаваме ненулев полином PP от степен не по-голяма от nn, за който P(x2i−1)+P(x2i)=0P(x_{2i-1})+P(x_{2i})=0 за всяко ii. От теоремата за междинната стойност PP има корен във всеки от интервалите [x2i−1,x2i][x_{2i-1},x_{2i}]. Тези nn интервала са непресичащи се, така че корените са различни. Понеже PP е ненулев и има степен най-много nn, следва, че всъщност deg⁡P=n\deg P=n. Твърдението е доказано. Сега вземаме този полином PP и полагаме Q(x)=−P(x)Q(x)=-P(x). Тогава P≠QP\ne Q и deg⁡Q=deg⁡P=n\deg Q=\deg P=n. Освен това от P(x2i−1)+P(x2i)=0P(x_{2i-1})+P(x_{2i})=0 следваP(x2i−1)=Q(x2i)иQ(x2i−1)=P(x2i)P(x_{2i-1})=Q(x_{2i})\qquad\text{и}\qquad Q(x_{2i-1})=P(x_{2i})за всяко i=1,2,…,ni=1,2,\ldots,n. Значи двете множества от стойностиP(x1),P(x2),…,P(x2n)P(x_1),P(x_2),\ldots,P(x_{2n})иQ(x1),Q(x2),…,Q(x2n)Q(x_1),Q(x_2),\ldots,Q(x_{2n})са едни и същи с точност до разместване. След записване в ненамаляващ ред на дъската те изглеждат еднакво, но тайният полином може да е PP или QQ. Следователно такава стратегия не съществува.
Отвори задачатаMathNetISL 2020 A5Условие — източник

Задача A6

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за които за всички a,b∈Za,b\in\mathbb Z е изпълненоfa2+b2(a+b)=af(a)+bf(b).f^{a^2+b^2}(a+b)=af(a)+bf(b).Тук fnf^n означава nn-тата итерация на ff, тоест f0(x)=xf^0(x)=x и fn+1(x)=f(fn(x))f^{n+1}(x)=f(f^n(x)) за всички n≥0n\ge0.
РешениеОтговорът е:f(x)≡0илиf(x)=x+1.f(x)\equiv0\qquad\text{или}\qquad f(x)=x+1.И двете функции се проверяват непосредствено. Нека E(a,b)E(a,b) означава даденото равенство. От E(0,b)E(0,b) имамеfb2(b)=bf(b).f^{b^2}(b)=bf(b).При b=−1b=-1 това дава f(−1)=0f(-1)=0. От E(a,−1)E(a,-1) и от предното равенство, приложено за b=ab=a, получавамеfa2+1(a−1)=af(a)=fa2(a).(1)f^{a^2+1}(a-1)=af(a)=f^{a^2}(a).\tag{1}За цяло число xx да означим сO(x)={x,f(x),f(f(x)),…}O(x)=\{x,f(x),f(f(x)),\ldots\}орбитата на xx. Равенство (1) показва, че орбитите O(a−1)O(a-1) и O(a)O(a) имат обща опашка, след като се изтрият краен брой начални членове. Следователно всяко две орбити се различават само с краен брой членове. Значи или всички орбити са крайни, или всички са безкрайни. Първи случай: всички орбити са крайни. От E(a,−a)E(a,-a) следваa(f(a)−f(−a))=f2a2(0)∈O(0).(2)a(f(a)-f(-a))=f^{2a^2}(0)\in O(0).\tag{2}Понеже O(0)O(0) е крайно, за достатъчно големи ∣a∣|a| лявата страна не може да е ненулево кратно на aa. Затова за такива aa имаме f(a)=f(−a)f(a)=f(-a) и f2a2(0)=0f^{2a^2}(0)=0. Следователно орбитата на 00 е чисто периодична; ако TT е нейният минимален период, то T∣2a2T\mid2a^2 и също T∣2(a+1)2T\mid2(a+1)^2 за достатъчно голямо aa. Оттук T∣2T\mid2. Връщайки се към (2), вече получаваме f(a)=f(−a)f(a)=f(-a) за всяко a≠0a\ne0, а в частност f(1)=f(−1)=0f(1)=f(-1)=0. Сега от E(n,1−n)E(n,1-n) имамеnf(n)+(1−n)f(1−n)=f2n2−2n(0)=0.(3)nf(n)+(1-n)f(1-n)=f^{2n^2-2n}(0)=0.\tag{3}Ако съществува m≠0m\ne0 с f(m)≠0f(m)\ne0, избираме такова mm с минимално ∣m∣|m|. Понеже f(1)=f(−1)=0f(1)=f(-1)=0 и f(a)=f(−a)f(a)=f(-a), числото r=∣m∣r=|m| е по-голямо от 11 и f(r)≠0f(r)\ne0. От (3) при n=rn=r следва f(1−r)≠0f(1-r)\ne0, което противоречи на минималността, защото ∣1−r∣<r|1-r|\lt{}r. Значи f(n)=0f(n)=0 за всички n≠0n\ne0. Накрая f(0)=f3(0)=f4(2)=2f(2)=0f(0)=f^3(0)=f^4(2)=2f(2)=0, така че получаваме нулевата функция. Втори случай: всички орбити са безкрайни. Тогава всяко две орбити имат безкрайно много общи членове. Фиксираме a,b∈Za,b\in\mathbb Z. Ще покажем, че ако fn(a)=fm(b)f^n(a)=f^m(b), то разликата n−mn-m не зависи от избраната двойка (n,m)(n,m). Ако имахме още fp(a)=fq(b)f^p(a)=f^q(b) с n−m>p−qn-m\gt{}p-q, тогава за всички достатъчно големи индекси орбитата на bb би се повтаряла с положителен период (n−m)−(p−q)(n-m)-(p-q), противоречие с безкрайността ѝ. Нека X(a,b)X(a,b) е тази обща разлика n−mn-m. От (1) следва X(a−1,a)=1X(a-1,a)=1, а очевидноX(a,b)+X(b,c)=X(a,c).X(a,b)+X(b,c)=X(a,c).Следователно X(a,b)=b−aX(a,b)=b-a за всички цели a,ba,b. Прилагаме ff към двете страни на (1) и получавамеfa2+1(f(a−1))=fa2(f(a)).f^{a^2+1}(f(a-1))=f^{a^2}(f(a)).Затова1=X(f(a−1),f(a))=f(a)−f(a−1)1=X(f(a-1),f(a))=f(a)-f(a-1)за всяко a∈Za\in\mathbb Z. Понеже f(−1)=0f(-1)=0, с индукция в двете посоки следва f(x)=x+1f(x)=x+1 за всяко цяло xx. Така единствените решения са двете функции от отговора.
Отвори задачатаMathNetISL 2020 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека nn и kk са положителни цели числа. Докажете, че за a1,…,an∈[1,2k]a_1,\ldots,a_n\in[1,2^k] е изпълнено∑i=1naix2a12+⋯+ai2≤4x2kn.\sum_{i=1}^n\frac{a_i}{\sqrt{\vphantom{x^2}a_1^2+\cdots+a_i^2}}\le 4\sqrt{\vphantom{x^2}kn}.
РешениеРазпределяме индексите 1,2,…,n1,2,\ldots,n в непресичащи се множества M1,M2,…,MkM_1,M_2,\ldots,M_k така, че ако ℓ∈Mj\ell\in M_j, то 2j−1≤aℓ≤2j2^{j-1}\le a_\ell\le2^j. Нека ∣Mj∣=pj|M_j|=p_j. Фиксираме jj и изброяваме елементите на MjM_j в нарастващ ред. Ако ℓ\ell е ii-тият такъв индекс, то знаменателят x2a12+⋯+aℓ2\sqrt{\vphantom{x^2}a_1^2+\cdots+a_\ell^2} съдържа поне ii събираеми, всяко не по-малко от (2j−1)2(2^{j-1})^2. Освен това aℓ≤2ja_\ell\le2^j. Затова∑ℓ∈Mjaℓx2a12+⋯+aℓ2≤\sum_{\ell\in M_j}\frac{a_\ell}{\sqrt{\vphantom{x^2}a_1^2+\cdots+a_\ell^2}} \le∑i=1pj2j2j−1i=2∑i=1pj1i. \sum_{i=1}^{p_j}\frac{2^j}{2^{j-1}\sqrt i}=2\sum_{i=1}^{p_j}\frac1{\sqrt i}.Понежеi−x2i−1=1i+x2i−1≥12i,\sqrt i-\sqrt{\vphantom{x^2}i-1}=\frac1{\sqrt i+\sqrt{\vphantom{x^2}i-1}}\ge\frac1{2\sqrt i},имаме2∑i=1pj1i≤2\sum_{i=1}^{p_j}\frac1{\sqrt i}\le4∑i=1pj(i−x2i−1)=4x2pj.4\sum_{i=1}^{p_j}(\sqrt i-\sqrt{\vphantom{x^2}i-1})=4\sqrt{\vphantom{x^2}p_j}.Сумирайки по j=1,2,…,kj=1,2,\ldots,k и прилагайки неравенството на Коши-Шварц, получаваме∑i=1naix2a12+⋯+ai2≤\sum_{i=1}^n\frac{a_i}{\sqrt{\vphantom{x^2}a_1^2+\cdots+a_i^2}} \le4∑j=1kx2pj≤4x2k∑j=1kpj=4x2kn,4\sum_{j=1}^k\sqrt{\vphantom{x^2}p_j}\le4\sqrt{\vphantom{x^2}k\sum_{j=1}^k p_j}=4\sqrt{\vphantom{x^2}kn},както се искаше.
Отвори задачатаMathNetISL 2020 A7Условие — източник

Задача A8

Пълен запис
Условие
Нека R+\mathbb R^+ е множеството на положителните реални числа. Да се намерят всички функции f:R+→R+f:\mathbb R^+\to\mathbb R^+, за които за всички положителни реални числа xx и yy е изпълненоf(x+f(xy))+y=f(x)f(y)+1.f(x+f(xy))+y=f(x)f(y)+1.
РешениеОтговорът еf(x)=x+1.f(x)=x+1.Проверката е непосредствена. Остава да докажем, че друго решение няма. Първо ще покажем, че ff е инективна. При x=1x=1 даденото равенство се преписва катоy=f(1)f(y)+1−f(1+f(y)).y=f(1)f(y)+1-f(1+f(y)).Следователно от f(y1)=f(y2)f(y_1)=f(y_2) веднага следва y1=y2y_1=y_2. Сега ще докажем, че ff е строго растяща. За фиксирано y>0y\gt{}0 функциятаg(x)=f(x+f(xy))=f(x)f(y)+1−yg(x)=f(x+f(xy))=f(x)f(y)+1-yе инективна, понеже ff е инективна и f(y)>0f(y)\gt{}0. Затова при x1≠x2x_1\ne x_2 имамеx1+f(x1y)≠x2+f(x2y).x_1+f(x_1y)\ne x_2+f(x_2y).Пишейки zi=xiyz_i=x_iy, получаваме за всички y>0y\gt{}0 и z1≠z2z_1\ne z_2z1−z2y≠f(z2)−f(z1),\frac{z_1-z_2}{y}\ne f(z_2)-f(z_1),тоест1y≠f(z2)−f(z1)z1−z2.\qquad\text{тоест}\qquad \frac1y\ne\frac{f(z_2)-f(z_1)}{z_1-z_2}.Тъй като 1/y1/y може да бъде произволно положително реално число, последната дроб не може да бъде положителна. Следователно ff е ненамаляваща, а от инективността следва, че е строго растяща. Понеже ff е растяща и ограничена отдолу с 00, съществуват десни граници. Некаp=lim⁡x↘0f(x),q=lim⁡x↘pf(x).p=\lim_{x\searrow0}f(x),\qquad q=\lim_{x\searrow p}f(x).Фиксираме y>0y\gt{}0 и пускаме x↘0x\searrow0 в даденото равенство. Тогава f(xy)↘pf(xy)\searrow p и x+f(xy)↘px+f(xy)\searrow p, откъдетоq+y=pf(y)+1.q+y=pf(y)+1.Ако p=0p=0, това би дало q+y=1q+y=1 за всяко y>0y\gt{}0, невъзможно. Следователно p>0p\gt{}0 иf(y)=q+y−1p.f(y)=\frac{q+y-1}{p}.Значи ff е линейна: f(y)=ay+bf(y)=ay+b за някои константи a,ba,b. Замествайки f(x)=ax+bf(x)=ax+b в уравнението, получавамеa(x+axy+b)+b+y=(ax+b)(ay+b)+1.a(x+axy+b)+b+y=(ax+b)(ay+b)+1.След съкращаване това е(a−ab)x+(1−ab)y+ab+b−b2−1=0(a-ab)x+(1-ab)y+ab+b-b^2-1=0за всички x,y>0x,y\gt{}0. Следователно всички коефициенти са нули, откъдето a=b=1a=b=1. Така f(x)=x+1f(x)=x+1, както твърдяхме.
Отвори задачатаMathNetISL 2020 A8Условие — източник

Задача C1

Пълен запис
Условие
Нека nn е положително цяло число. Намерете броя на пермутациите a1,a2,…,ana_1,a_2,\ldots,a_n на редицата 1,2,…,n1,2,\ldots,n, за коитоa1≤2a2≤3a3≤⋯≤nan.a_1\le 2a_2\le 3a_3\le\cdots\le na_n.
РешениеНека PnP_n е броят на търсените пермутации. Ясно е, че P1=1P_1=1 и P2=2P_2=2. Ще докажем лема. Нека n≥3n\ge3 и нека пермутацията a1,…,ana_1,\ldots,a_n удовлетворява условието. Тогава или an=na_n=n, или an−1=na_{n-1}=n и an=n−1a_n=n-1. Нека kk е индексът, за който ak=na_k=n. Ако k=nk=n, няма какво да доказваме. Ако k=n−1k=n-1, то от условието(n−1)an−1≤nan(n-1)a_{n-1}\le na_nследва n(n−1)≤nann(n-1)\le na_n, тоест an≥n−1a_n\ge n-1. Понеже an≠an−1=na_n\ne a_{n-1}=n, получаваме an=n−1a_n=n-1. Остава да изключим случая k≤n−2k\le n-2. За всяко ii с k<i<nk\lt{}i\lt{}n имамеkn=kak≤iai<nai,kn=ka_k\le ia_i\lt{}na_i,следователно ai≥k+1a_i\ge k+1. Освен товаnan≥(n−1)an−1≥na_n\ge(n-1)a_{n-1}\ge(n−1)(k+1)=nk+(n−1−k)>nk,(n-1)(k+1)=nk+(n-1-k)\gt{}nk,така че an≥k+1a_n\ge k+1. Значи числата ak,ak+1,…,ana_k,a_{k+1},\ldots,a_n са общо n−k+1n-k+1 на брой и всички са по-големи от kk, но такива стойности има само n−kn-k. Противоречие. Лемата е доказана. Сега броенето става непосредствено. Ако an=na_n=n, то a1,…,an−1a_1,\ldots,a_{n-1} е допустима пермутация на 1,…,n−11,\ldots,n-1, а последното неравенство е автоматично изпълнено. Това дава Pn−1P_{n-1} възможности. Ако (an−1,an)=(n,n−1)(a_{n-1},a_n)=(n,n-1), то a1,…,an−2a_1,\ldots,a_{n-2} е допустима пермутация на 1,…,n−21,\ldots,n-2, а последните две неравенства са автоматични, понеже(n−2)an−2≤(n−2)2<(n-2)a_{n-2}\le(n-2)^2\lt{}n(n−1)=(n−1)an−1=nan.n(n-1)=(n-1)a_{n-1}=na_n.Това дава Pn−2P_{n-2} възможности. СледователноPn=Pn−1+Pn−2(n≥3).P_n=P_{n-1}+P_{n-2}\quad(n\ge3).При начални стойности P1=1=F2P_1=1=F_2 и P2=2=F3P_2=2=F_3 получаваме по индукцияPn=Fn+1,P_n=F_{n+1},където F0=0F_0=0, F1=1F_1=1 и Fm+1=Fm+Fm−1F_{m+1}=F_m+F_{m-1} са числата на Фибоначи.
Отвори задачатаMathNetISL 2020 C1Условие — източник

Задача C2

Пълен запис
Условие
В правилен 100100-ъгълник 4141 върха са оцветени в черно, а останалите 5959 върха - в бяло. Докажете, че съществуват 2424 изпъкнали четириъгълника Q1,…,Q24Q_1,\ldots,Q_{24} с върхове измежду върховете на 100100-ъгълника, така че четириъгълниците да са два по два без общи върхове и всеки QiQ_i да има три върха от единия цвят и един връх от другия цвят.
РешениеЩе наричаме един четириъгълник смесен, ако има три върха от единия цвят и един връх от другия цвят. Ще докажем следното твърдение. Твърдение. Ако върховете на изпъкнал (4k+1)(4k+1)-ъгълник са оцветени в черно и бяло и всеки от двата цвята се среща поне kk пъти, тогава съществуват kk смесени четириъгълника, два по два без общи върхове, чиито върхове са върхове на многоъгълника. Един връх остава неизползван. От твърдението задачата следва веднага: махаме произволни 33 върха от 100100-ъгълника и го прилагаме към останалите 97=4⋅24+197=4\cdot24+1 върха с k=24k=24. И двата цвята още се срещат поне 2424 пъти. Доказваме твърдението с индукция по kk. При k=1k=1 имаме петоъгълник, в който има поне един черен и поне един бял връх. Ако броят на черните върхове е четен, махаме един черен връх; иначе махаме един бял връх. В останалия четириъгълник и броят на черните, и броят на белите върхове е нечетен, следователно той е смесен. Нека k≥2k\ge2 и нека bb и ww са съответно броят на черните и белите върхове. Имаме b,w≥kb,w\ge k и b+w=4k+1b+w=4k+1. Без ограничение нека w≥bw\ge b; тогаваk≤b≤2k,2k+1≤w≤3k+1.k\le b\le 2k,\qquad 2k+1\le w\le3k+1.Ще намерим четири последователни върха, от които три са бели, а един е черен. Номерираме върховете V1,V2,…,V4k+1V_1,V_2,\ldots,V_{4k+1} обратно на часовниковата стрелка така, че V4k+1V_{4k+1} да е черен. Разглеждаме kk-те групи(V1,V2,V3,V4),(V5,V6,V7,V8),(V_1,V_2,V_3,V_4),(V_5,V_6,V_7,V_8),…,(V4k−3,V4k−2,V4k−1,V4k).\ldots,(V_{4k-3},V_{4k-2},V_{4k-1},V_{4k}).В тези групи има ww бели и b−1b-1 черни върха. Понеже w>b−1w\gt{}b-1, някоя група съдържа повече бели, отколкото черни върхове. Ако в нея има три бели и един черен връх, готови сме. Ако четирите върха в групата са бели, нека VjV_j е първият черен връх след нея сред Vi+4,…,V4k+1V_{i+4},\ldots,V_{4k+1}; такъв има, защото V4k+1V_{4k+1} е черен. Тогава Vj−3,Vj−2,Vj−1V_{j-3},V_{j-2},V_{j-1} са бели, а VjV_j е черен. Използваме тези четири последователни върха като един смесен четириъгълник. Останалите върхове образуват изпъкнал (4k−3)(4k-3)-ъгълник, в който белите върхове са w−3w-3, а черните са b−1b-1. Имаме b−1≥k−1b-1\ge k-1 иw−3≥(2k+1)−3>k−1,w-3\ge(2k+1)-3\gt{}k-1,така че можем да приложим индукционното предположение с k−1k-1. Получаваме още k−1k-1 смесени четириъгълника без общи върхове, което заедно с първия дава нужните kk.
Отвори задачатаMathNetISL 2020 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. На склон на планина са отбелязани n2n^2 спирки, номерирани от 11 до n2n^2 отдолу нагоре. Всяка от две лифтови компании AA и BB обслужва kk лифта, номерирани от 11 до kk; всеки лифт превозва от някоя спирка до по-висока спирка. За всяка компания и за всякакви i,ji,j с 1≤i<j≤k1\le i\lt{}j\le k началната спирка на лифт jj е по-висока от началната спирка на лифт ii; също така крайната спирка на лифт jj е по-висока от крайната спирка на лифт ii. Казваме, че две спирки са свързани от дадена компания, ако от по-ниската може да се стигне до по-високата, използвайки един или повече лифтове на тази компания, без ходене пеша. Да се намери най-малкото kk, за което винаги може да се гарантира, че има две спирки, свързани и от двете компании.
РешениеОтговорът е k=n2−n+1k=n^2-n+1. Първо ще покажем, че при k≤n2−nk\le n^2-n гаранцията може да липсва. Достатъчно е да дадем пример за k=n2−nk=n^2-n. Нека компания AA свързва двойките спирки (i,i+1)(i,i+1) за всички ii, които не се делят на nn. Тогава всяка двойка спирки, свързана от AA, лежи в един и същ блок{1,…,n},{n+1,…,2n},\{1,\ldots,n\},\{n+1,\ldots,2n\},…,{n2−n+1,…,n2}.\ldots,\{n^2-n+1,\ldots,n^2\}.Нека компания BB свързва двойките (i,i+n)(i,i+n) за 1≤i≤n2−n1\le i\le n^2-n. Тогава всяка двойка спирки, свързана от BB, има еднакви остатъци при деление на nn. Няма две различни спирки, които едновременно да са в един и същ блок и да имат еднакъв остатък по модул nn, така че общо свързана двойка няма. Остава да докажем, че k=n2−n+1k=n^2-n+1 винаги стига. Ще разгледаме компания AA. Понеже началните спирки на нейните лифтове са различни и крайните спирки също са различни, а всички лифтове водят нагоре, насоченият граф на нейните лифтове се разпада на непресичащи се вериги. Наричаме такава максимална верига AA-верига. Аналогично определяме BB-веригите. Ако в един насочен граф с n2n^2 върха има kk ребра и той е обединение на непресичащи се вериги, броят на веригите е n2−kn^2-k. Следователно при нашето kk има точно n−1n-1 AA-вериги и точно n−1n-1 BB-вериги. На всяка спирка съпоставяме двойката, съставена от AA-веригата и BB-веригата, към които тя принадлежи. Възможните такива двойки са само (n−1)2(n-1)^2, а спирките са n2n^2. По принципа на Дирихле две различни спирки съответстват на една и съща двойка вериги. Те лежат в една и съща AA-верига, следователно са свързани от AA, и лежат в една и съща BB-верига, следователно са свързани и от BB. Значи минималната стойност е n2−n+1n^2-n+1.
Отвори задачатаMathNetISL 2020 C3Условие — източник

Задача C4

Пълен запис
Условие
Числата на Фибоначи F0,F1,F2,…F_0,F_1,F_2,\ldots са зададени с F0=0F_0=0, F1=1F_1=1 и Fm+1=Fm+Fm−1F_{m+1}=F_m+F_{m-1} за m≥1m\ge1. За дадено цяло число n≥2n\ge2 да се намери най-малката възможна големина на множество SS от цели числа със следното свойство: за всяко k=2,3,…,nk=2,3,\ldots,n съществуват x,y∈Sx,y\in S, за които x−y=Fkx-y=F_k.
РешениеОтговорът е ⌈n2⌉+1\left\lceil\frac n2\right\rceil+1. Нека d=⌈n2⌉d=\left\lceil\frac n2\right\rceil. Първо ще докажем, че са нужни поне d+1d+1 елемента. Да построим граф с върхове елементите на SS. За всяко 1≤k≤d1\le k\le d избираме два елемента x,y∈Sx,y\in S с x−y=F2k−1x-y=F_{2k-1} и ги свързваме с ребро. За k=1k=1 използваме равенството F1=F2F_1=F_2, а за останалите kk имаме 3≤2k−1≤n3\le2k-1\le n. Ще покажем, че този граф няма цикъл. Да допуснем обратното и да вземем цикъл, в който най-дългото ребро има дължина F2m+1F_{2m+1}. Всички останали ребра в цикъла са с различни дължини, по-малки от F2m+1F_{2m+1}, следователно тези дължини са измеждуF1,F3,…,F2m−1.F_1,F_3,\ldots,F_{2m-1}.От неравенството на триъгълника получавамеF2m+1≤F1+F3+⋯+F2m−1.F_{2m+1}\le F_1+F_3+\cdots+F_{2m-1}.НоF1+F3+⋯+F2m−1=F_1+F_3+\cdots+F_{2m-1}=F2+(F4−F2)+⋯+(F2m−F2m−2)=F2m,F_2+(F_4-F_2)+\cdots+(F_{2m}-F_{2m-2})=F_{2m},което е противоречие. Значи графът с dd ребра е ацикличен и затова има поне d+1d+1 върха. Следователно ∣S∣≥d+1|S|\ge d+1. Сега даваме конструкция с d+1d+1 числа:S={F0,F2,F4,…,F2d}.S=\{F_0,F_2,F_4,\ldots,F_{2d}\}.За всяко 1≤k≤d1\le k\le d числата F0,F2k−2,F2kF_0,F_{2k-2},F_{2k} принадлежат на SS иF2k−F2k−2=F2k−1,F2k−F0=F2k.F_{2k}-F_{2k-2}=F_{2k-1},\qquad F_{2k}-F_0=F_{2k}.Следователно всяко от числата F1,F2,…,F2dF_1,F_2,\ldots,F_{2d} се получава като разлика на два елемента на SS. Понеже n≤2dn\le2d, това множество удовлетворява условието. Минималната големина е d+1=⌈n2⌉+1d+1=\left\lceil\frac n2\right\rceil+1.
Отвори задачатаMathNetISL 2020 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека pp е нечетно просто число и некаN=p3−p4−1.N=\frac{p^3-p}{4}-1.Числата 1,2,…,N1,2,\ldots,N са оцветени произволно в два цвята, червено и синьо. За всяко положително цяло число n≤Nn\le N означаваме с r(n)r(n) дела на червените числа измежду 1,2,…,n1,2,\ldots,n. Докажете, че съществува положително цяло число a∈{1,2,…,p−1}a\in\{1,2,\ldots,p-1\}, за което r(n)≠apr(n)\ne\frac{a}{p} за всички n=1,2,…,Nn=1,2,\ldots,N.
РешениеНека R(n)R(n) е броят на червените числа измежду 1,2,…,n1,2,\ldots,n. Аналогично нека B(n)B(n) е броят на сините числа. Тогава R(n)+B(n)=nR(n)+B(n)=n, а твърдението не се променя, ако разменим двата цвята. Да допуснем противното. За всяко a∈{1,2,…,p−1}a\in\{1,2,\ldots,p-1\} избираме положително цяло число nan_a, за коетоr(na)=ap.r(n_a)=\frac{a}{p}.Тогава p∣nap\mid n_a, затова пишем na=pman_a=pm_a. ИмамеR(na)=ama.R(n_a)=am_a.Без ограничение можем да приемем, че m1<mp−1m_1\lt{}m_{p-1}; ако не е така, разменяме цветовете. Освен товаma≤Np<p2−14(a=1,2,…,p−1).(1)m_a\le\frac{N}{p}\lt{}\frac{p^2-1}{4}\qquad(a=1,2,\ldots,p-1).\tag{1}Ще използваме следното просто наблюдение. Ако ma<mbm_a\lt{}m_b, тоmb≥abmaиmb≥p−ap−bma.m_b\ge\frac{a}{b}m_a\qquad\text{и}\qquad m_b\ge\frac{p-a}{p-b}m_a.Първото неравенство следва от R(nb)≥R(na)R(n_b)\ge R(n_a), тоест bmb≥amabm_b\ge am_a. Второто се получава по същия начин за сините числа:(p−b)mb=B(nb)≥B(na)=(p−a)ma.(p-b)m_b=B(n_b)\ge B(n_a)=(p-a)m_a.Нека q=p−12q=\frac{p-1}{2}. Разглеждаме два случая. Първи случай: всички числа m1,m2,…,mqm_1,m_2,\ldots,m_q са по-малки от mp−1m_{p-1}. Нека mam_a е най-голямото сред тях. Тези qq числа са различни положителни цели числа, така че ma≥qm_a\ge q. По наблюдението, приложено към ma<mp−1m_a\lt{}m_{p-1}, получавамеmp−1≥(p−a)ma≥(p−q)q=p2−14,m_{p-1}\ge(p-a)m_a\ge(p-q)q=\frac{p^2-1}{4},което противоречи на (1). Втори случай: съществува k≤qk\le q, за което mk>mp−1m_k\gt{}m_{p-1}. Избираме най-малкото такова kk. Тогава 1<k≤q1\lt{}k\le q, а всички m1,…,mk−1m_1,\ldots,m_{k-1} са по-малки от mp−1m_{p-1}. Нека mam_a е най-голямото сред тях. Тогава a≤k−1a\le k-1, ma≥k−1m_a\ge k-1 и ma<mp−1<mkm_a\lt{}m_{p-1}\lt{}m_k. От наблюдението първо за ma<mp−1m_a\lt{}m_{p-1} и после за mp−1<mkm_{p-1}\lt{}m_k следваmk≥p−1kmp−1≥p−1k(p−a)ma.m_k\ge\frac{p-1}{k}m_{p-1}\ge\frac{p-1}{k}(p-a)m_a.Понеже a≤k−1a\le k-1 и ma≥k−1m_a\ge k-1, получавамеmk≥p−1k(p−k+1)(k−1).m_k\ge\frac{p-1}{k}(p-k+1)(k-1).А от 2≤k≤q2\le k\le q имамеk−1k≥12иp−k+1≥p−q=p+12.\frac{k-1}{k}\ge\frac12\qquad\text{и}\qquad p-k+1\ge p-q=\frac{p+1}{2}.Следователноmk≥p2−14,m_k\ge\frac{p^2-1}{4},което отново противоречи на (1). И в двата случая стигаме до противоречие, следователно исканото число aa съществува.
Отвори задачатаMathNetISL 2020 C5Условие — източник

Задача C6

Пълен запис
Условие
Дадени са 4n4n монети с тегла 1,2,3,…,4n1,2,3,\ldots,4n. Всяка монета е оцветена в един от nn цвята и от всеки цвят има точно четири монети. Докажете, че всички монети могат да се разделят на две множества с равно общо тегло, така че всяко от двете множества да съдържа по две монети от всеки цвят.
РешениеСдвояваме монетите така, че теглата във всяка двойка да имат сбор 4n+14n+1:{1,4n},{2,4n−1},…,{2n,2n+1}.\{1,4n\},\{2,4n-1\},\ldots,\{2n,2n+1\}.Нека SS е множеството от тези 2n2n двойки. Достатъчно е да разделим SS на две групи от по nn двойки, така че във всяка група да има по две монети от всеки цвят. Тогава двете групи монети ще имат равно общо тегло, защото всяка от тях съдържа nn двойки със сбор 4n+14n+1. Построяваме мултиграф GG с nn върха, по един за всеки цвят. За всяка двойка монети от SS добавяме ребро между върховете, съответстващи на цветовете на двете монети; ако цветовете съвпадат, получаваме примка. Всеки връх има степен 44, като примките се броят два пъти. Желаното разделяне на монетите е същото като оцветяване на ребрата на GG в два цвята, да кажем червено и синьо, така че във всеки връх червената и синята степен да са равни на 22. Това ще означава, че всяка от двете групи съдържа точно две монети от всеки първоначален цвят. Остава да покажем, че такова оцветяване винаги съществува. Разглеждаме произволна свързана компонента G′G' на GG. Всички степени в нея са четни, следователно G′G' има Ейлеров цикъл CC, който минава през всяко ребро точно веднъж. Броят на ребрата в CC е четен, защото той е половината от сумата на степените в компонентата, тоест е два пъти броя на върховете в нея. Оцветяваме ребрата по Ейлеровия цикъл последователно в червено и синьо. Понеже дължината на цикъла е четна, това е съгласувано при връщането в началото. При всяко посещение на връх в цикъла едно влизащо и едно излизащо ребро получават различни цветове; същото е вярно и за примките в стандартното броене на степените. Затова във всеки връх на G′G' червената и синята степен са равни. Понеже общата степен е 44, всяка от тях е 22. Прилагаме това за всяка компонента на GG и получаваме исканото оцветяване, а оттам и исканото разделяне на монетите.
Отвори задачатаMathNetISL 2020 C6Условие — източник

Задача C7

Пълен запис
Условие
Разглеждаме произволна правоъгълна таблица с краен брой редове и стълбове, като в клетката на ред rr и стълб cc е записано реално число a(r,c)a(r,c). Двойка (R,C)(R,C), където RR е множество от редове, а CC е множество от стълбове, се нарича седлова двойка, ако са изпълнени следните две условия: (i) за всеки ред r′r' съществува ред r∈Rr\in R, такъв че a(r,c)≥a(r′,c)a(r,c)\ge a(r',c) за всички c∈Cc\in C; (ii) за всеки стълб c′c' съществува стълб c∈Cc\in C, такъв че a(r,c)≤a(r,c′)a(r,c)\le a(r,c') за всички r∈Rr\in R. Седлова двойка (R,C)(R,C) се нарича минимална, ако за всяка седлова двойка (R′,C′)(R',C') с R′⊆RR'\subseteq R и C′⊆CC'\subseteq C имаме R′=RR'=R и C′=CC'=C. Докажете, че които и да са две минимални двойки съдържат един и същ брой редове.
РешениеЩе докажем следното по-силно твърдение. Нека (R1,C1)(R_1,C_1) и (R2,C2)(R_2,C_2) са две седлови двойки с ∣R1∣>∣R2∣|R_1|\gt{}|R_2|. Тогава съществува седлова поддвойка (R′,C′)(R',C') на (R1,C1)(R_1,C_1), за която ∣R′∣≤∣R2∣|R'|\le |R_2|. Ако (R1,C1)(R_1,C_1) беше минимална, това би било невъзможно, защото ∣R′∣<∣R1∣|R'|\lt{}|R_1|. Следователно две минимални двойки не могат да имат различен брой редове. Наричаме (R′,C′)(R',C') поддвойка на (R,C)(R,C), ако R′⊆RR'\subseteq R и C′⊆CC'\subseteq C. Поддвойката е същинска, ако поне едно от включванията е строго. Първа стъпка. Ще построим изображения ρ:R1→R1\rho:R_1\to R_1 и σ:C1→C1\sigma:C_1\to C_1, такива че∣ρ(R1)∣≤∣R2∣|\rho(R_1)|\le |R_2|иa(ρ(r1),c1)≥a(r1,σ(c1))a(\rho(r_1),c_1)\ge a(r_1,\sigma(c_1))\qquad(r1∈R1,c1∈C1).(1)(r_1\in R_1, c_1\in C_1).\tag{1}Понеже (R1,C1)(R_1,C_1) и (R2,C2)(R_2,C_2) са седлови двойки, можем да изберем изображенияρ1:R2→R1,a(ρ1(r2),c1)≥a(r2,c1)(r2∈R2,c1∈C1),ρ2:R1→R2,a(ρ2(r1),c2)≥a(r1,c2)(r1∈R1,c2∈C2),σ1:C2→C1,a(r1,σ1(c2))≤a(r1,c2)(r1∈R1,c2∈C2),σ2:C1→C2,a(r2,σ2(c1))≤a(r2,c1)(r2∈R2,c1∈C1).\begin{align*} &\rho_1:R_2\to R_1, &&a(\rho_1(r_2),c_1)\ge a(r_2,c_1) &&(r_2\in R_2, c_1\in C_1),\\ &\rho_2:R_1\to R_2, &&a(\rho_2(r_1),c_2)\ge a(r_1,c_2) &&(r_1\in R_1, c_2\in C_2),\\ &\sigma_1:C_2\to C_1, &&a(r_1,\sigma_1(c_2))\le a(r_1,c_2) &&(r_1\in R_1, c_2\in C_2),\\ &\sigma_2:C_1\to C_2, &&a(r_2,\sigma_2(c_1))\le a(r_2,c_1) &&(r_2\in R_2, c_1\in C_1). \end{align*}Полагаме ρ=ρ1∘ρ2\rho=\rho_1\circ\rho_2 и σ=σ1∘σ2\sigma=\sigma_1\circ\sigma_2. Тогава∣ρ(R1)∣=∣ρ1(ρ2(R1))∣≤|\rho(R_1)|=|\rho_1(\rho_2(R_1))|\le∣ρ1(R2)∣≤∣R2∣. |\rho_1(R_2)|\le |R_2|.Освен това за r1∈R1r_1\in R_1 и c1∈C1c_1\in C_1 имамеa(ρ(r1),c1)=a(ρ1(ρ2(r1)),c1)≥a(ρ2(r1),c1)≥a(ρ2(r1),σ2(c1))≥a(r1,σ2(c1))≥a(r1,σ1(σ2(c1)))=a(r1,σ(c1)),\begin{align*} a(\rho(r_1),c_1)&=a(\rho_1(\rho_2(r_1)),c_1)\\ &\ge a(\rho_2(r_1),c_1)\\ &\ge a(\rho_2(r_1),\sigma_2(c_1))\\ &\ge a(r_1,\sigma_2(c_1))\\ &\ge a(r_1,\sigma_1(\sigma_2(c_1)))=a(r_1,\sigma(c_1)), \end{align*}което доказва (1). Втора стъпка. От (1) по индукция следва, че за всяко положително цяло число ii,a(ρi(r1),c1)≥a(ρi−1(r1),σ(c1))≥a(\rho^i(r_1),c_1)\ge a(\rho^{i-1}(r_1),\sigma(c_1))\ge⋯≥a(r1,σi(c1)).(2)\cdots\ge a(r_1,\sigma^i(c_1)).\tag{2}Нека Ri=ρi(R1)R^i=\rho^i(R_1) и Ci=σi(C1)C^i=\sigma^i(C_1). Имаме низходящи веригиR1=R0⊇R1⊇R2⊇⋯ ,C1=C0⊇C1⊇C2⊇⋯ .R_1=R^0\supseteq R^1\supseteq R^2\supseteq\cdots,\qquad C_1=C^0\supseteq C^1\supseteq C^2\supseteq\cdots.Понеже множествата са крайни, съществува индекс mm, след който и двете вериги се стабилизират: Rm=Rm+1=⋯R^m=R^{m+1}=\cdots и Cm=Cm+1=⋯C^m=C^{m+1}=\cdots. Тогава ρm\rho^m е биекция на RmR^m върху себе си, а σm\sigma^m е биекция на CmC^m върху себе си. Следователно съществува положително цяло число tt, за което ρmt\rho^{mt} е тъждественото изображение върху RmR^m, а σmt\sigma^{mt} е тъждественото изображение върху CmC^m. Ще докажем, че (Rm,Cm)(R^m,C^m) е седлова поддвойка на (R1,C1)(R_1,C_1). Първо,∣Rm∣≤∣R1∣=∣ρ(R1)∣≤∣R2∣.|R^m|\le |R^1|=|\rho(R_1)|\le |R_2|.Да проверим условие (i). Вземаме произволен ред r′r'. Тъй като (R1,C1)(R_1,C_1) е седлова двойка, съществува r1∈R1r_1\in R_1, такъв чеa(r1,c1)≥a(r′,c1)(c1∈C1).a(r_1,c_1)\ge a(r',c_1)\qquad(c_1\in C_1).Полагаме r∗=ρmt(r1)∈Rmr_* = \rho^{mt}(r_1)\in R^m. Ако c∈Cmc\in C^m, то c=σmt(c)c=\sigma^{mt}(c), и от (2) получавамеa(r∗,c)=a(ρmt(r1),c)≥a(r_*,c)=a(\rho^{mt}(r_1),c)\gea(r1,σmt(c))=a(r1,c)≥a(r′,c). a(r_1,\sigma^{mt}(c))=a(r_1,c)\ge a(r',c).Това е точно условие (i) за двойката (Rm,Cm)(R^m,C^m). Условие (ii) се проверява аналогично. Нека c′c' е произволен стълб. Избираме c1∈C1c_1\in C_1, такъв чеa(r1,c1)≤a(r1,c′)(r1∈R1),a(r_1,c_1)\le a(r_1,c')\qquad(r_1\in R_1),и полагаме c∗=σmt(c1)∈Cmc_* = \sigma^{mt}(c_1)\in C^m. Ако r∈Rmr\in R^m, то r=ρmt(r)r=\rho^{mt}(r), и от (2), приложено към rr и c1c_1, имамеa(r,c1)=a(ρmt(r),c1)≥a(r,c_1)=a(\rho^{mt}(r),c_1)\gea(r,σmt(c1))=a(r,c∗). a(r,\sigma^{mt}(c_1))=a(r,c_*).Следователно a(r,c∗)≤a(r,c1)≤a(r,c′)a(r,c_*)\le a(r,c_1)\le a(r,c') за всички r∈Rmr\in R^m, което е условие (ii). Значи (Rm,Cm)(R^m,C^m) е седлова поддвойка на (R1,C1)(R_1,C_1) и има най-много ∣R2∣|R_2| реда. По доказаното в началото това изключва възможността две минимални седлови двойки да имат различен брой редове.
Отвори задачатаMathNetISL 2020 C7Условие — източник

Задача C8

Пълен запис
Условие
Играчите A и B играят игра на черна дъска, на която първоначално са записани 2020 копия на числото 11. Във всеки ход A изтрива две числа xx и yy от дъската, а след това B записва едно от числата x+yx+y и ∣x−y∣|x-y|. Играта приключва веднага щом в края на някой ход е изпълнено едно от следните две условия: (1) едно от числата на дъската е по-голямо от сбора на всички останали; (2) на дъската има само нули. Тогава B трябва да даде на A толкова бисквити, колкото числа има на дъската. A иска да получи възможно най-много бисквити, а B иска да даде възможно най-малко. Определете броя бисквити, които A получава, ако и двамата играчи играят оптимално.
РешениеОтговорът е 77. За положително цяло число nn означаваме с S2(n)S_2(n) сбора на цифрите в двоичния му запис. Ще докажем по-общо, че ако първоначално на дъската има четен брой n>1n\gt{}1 единици, то A може да си гарантира S2(n)S_2(n) бисквити, но не повече. Понеже 2020=(11111100100)22020=(11111100100)_2, имаме S2(2020)=7S_2(2020)=7, откъдето следва отговорът. Стратегия за A. Във всеки ход, докато това е възможно, A избира две равни ненулеви числа. Докато A може да направи такъв избор, играта не е приключила, защото никое от тези две равни ненулеви числа не може да е по-голямо от сбора на всички останали числа. От друга страна, ако A винаги избира две равни ненулеви числа, то всяко число, което се появява на дъската, е или 00, или степен на 22 с неотрицателен цял показател; това се доказва веднага с индукция по броя ходове. В момента, в който A вече не може да следва стратегията, всички ненулеви числа на дъската са различни степени на 22. Ако има поне едно такова число, най-голямата степен е по-голяма от сбора на останалите; ако няма, на дъската има само нули. И в двата случая играта приключва. За всяко число на дъската ще наричаме негов обхват броя на първоначалните единици, от които е получено. С индукция по ходовете се доказва, че всяко ненулево число kk, записано от B, има обхват kk, а всяка нула, записана от B, има обхват степен на 22. Следователно в края на всеки ход всички обхвати са степени на 22 и сборът им е nn. Понеже S2(a+b)≤S2(a)+S2(b)S_2(a+b)\le S_2(a)+S_2(b) за всички положителни цели числа aa и bb, числото nn не може да се представи като сбор на по-малко от S2(n)S_2(n) степени на 22. Значи в края на всеки ход, докато A следва описаната стратегия, на дъската има поне S2(n)S_2(n) числа. Така A може да си гарантира поне S2(n)S_2(n) бисквити. Стратегия за B. Нека s=S2(n)s=S_2(n). Да разгледаме момент след ход на B, или началния момент, и нека числата на дъската са x1,x2,…,xkx_1,x_2,\ldots,x_k. Ще наричаме избор на знаци ε1,ε2,…,εk∈{+1,−1}\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_k\in\{+1,-1\} балансиран, ако∑i=1kεixi=0.\sum_{i=1}^k \varepsilon_i x_i=0.Ще казваме, че ситуацията на дъската е добра, ако 2s+12^{s+1} не дели броя на балансираните избори на знаци. B ще играе така, че след всеки негов ход ситуацията да остане добра. За положително цяло число mm нека ν2(m)\nu_2(m) е показателят на най-голямата степен на 22, която дели mm. По формулата на Лежандрν2(m!)=m−S2(m)\nu_2(m!)=m-S_2(m)за всяко положително цяло число mm. Лема 1. Началната ситуация е добра. В началото броят на балансираните избори е (nn/2)\binom{n}{n/2}. Имамеν2(nn/2)=ν2(n!)−2ν2((n/2)!)=\nu_2\binom{n}{n/2}=\nu_2(n!)-2\nu_2((n/2)!)=n−S2(n)−2(n2−S2(n2))=S2(n)=s,n-S_2(n)-2\left(\frac n2-S_2\left(\frac n2\right)\right)=S_2(n)=s,защото nn е четно и делението на 22 само премества двоичния запис с една позиция надясно. Следователно 2s+12^{s+1} не дели броя на балансираните избори, както трябва. Лема 2. B може да играе така, че след всеки ход ситуацията да остане добра. Нека преди даден ход ситуацията (x1,x2,…,xk)(x_1,x_2,\ldots,x_k) е добра и A изтрива числата xpx_p и xqx_q. Нека NN е броят на всички балансирани избори, N+N_+ е броят на онези от тях, за които εp=εq\varepsilon_p=\varepsilon_q, а N−N_- е броят на останалите. Тогава N=N++N−N=N_+ + N_-. Ако B замени xpx_p и xqx_q с xp+xqx_p+x_q, броят на балансираните избори става N+N_+. Ако ги замени с ∣xp−xq∣|x_p-x_q|, този брой става N−N_-. Понеже 2s+12^{s+1} не дели NN, то не дели поне едно от числата N+N_+ и N−N_-. B избира съответния ход и получава добра ситуация. Лема 3. Ако играта приключи при добра ситуация, на дъската има най-много ss числа. Ако едно от числата е по-голямо от сбора на всички останали, балансирани избори няма, тоест броят им е 00, а 00 се дели на 2s+12^{s+1}. Такава ситуация не е добра. Следователно при приключване в добра ситуация на дъската има само нули. Ако те са kk на брой, броят на балансираните избори е 2k2^k. Понеже ситуацията е добра, 2s+1∤2k2^{s+1}\nmid 2^k, откъдето k≤sk\le s. По леми 1 и 2 B може да запазва ситуацията добра през цялата игра. По лема 3, когато играта приключи, на дъската има най-много s=S2(n)s=S_2(n) числа. Значи B може да гарантира, че няма да даде повече от S2(n)S_2(n) бисквити. Двете стратегии показват, че при оптимална игра броят бисквити е точно S2(n)S_2(n); за n=2020n=2020 това е 77.
Отвори задачатаMathNetISL 2020 C8Условие — източник

Задача N1

Пълен запис
Условие
Дадено е положително цяло число kk. Докажете, че съществува просто число pp, за което могат да се изберат различни цели числаa1,a2,…,ak+3∈{1,2,…,p−1}a_1,a_2,\ldots,a_{k+3}\in\{1,2,\ldots,p-1\}така, чеp∣aiai+1ai+2ai+3−ip\mid a_i a_{i+1}a_{i+2}a_{i+3}-iза всички i=1,2,…,ki=1,2,\ldots,k.
РешениеПърво ще построим рационални числа. Избираме три различни прости числа x,y,z>kx,y,z\gt{}k и полагамеr1=x,r2=y,r3=z,r4=1xyz.r_1=x,\quad r_2=y,\quad r_3=z,\quad r_4=\frac1{xyz}.За i≥1i\ge1 дефинирамеri+4=i+1iri.r_{i+4}=\frac{i+1}{i}r_i.Тогава непосредствено по индукцияriri+1ri+2ri+3=ir_i r_{i+1}r_{i+2}r_{i+3}=iза всяко i=1,2,…,ki=1,2,\ldots,k. Ще проверим, че числата r1,r2,…,rk+3r_1,r_2,\ldots,r_{k+3} са различни. Във всяка от четирите подредици с еднакъв индекс по модул 44 имаме ri+4>rir_{i+4}\gt{}r_i. Освен това, тъй като x,y,z>kx,y,z\gt{}k, при съкращаване на дробите не се губят множителите x,y,zx,y,z: числителите на членовете с индекси съответно 1,2,31,2,3 по модул 44 се делят на x,y,zx,y,z, а тези с индекс 00 по модул 44 не се делят на нито едно от тях. Следователно членове от различни такива подредици също не съвпадат. Пишем ri=ui/vir_i=u_i/v_i в несъкратим вид. Избираме просто число pp, което не дели нито един от крайните ненулеви цели множители uiu_i, viv_i и uivj−ujviu_i v_j-u_j v_i за i≠ji\ne j, 1≤i,j≤k+31\le i,j\le k+3. Това е възможно, понеже забранените прости делители са краен брой. За всяко ii избираме ai∈{1,2,…,p−1}a_i\in\{1,2,\ldots,p-1\} така, чеaivi≡ui(modp).a_i v_i\equiv u_i\pmod p.Изборът на pp гарантира, че всички aia_i са ненулеви и различни по модул pp. От равенството за произведението на рационалните числа следваuiui+1ui+2ui+3=i vivi+1vi+2vi+3.u_i u_{i+1}u_{i+2}u_{i+3}=i\,v_i v_{i+1}v_{i+2}v_{i+3}.След заместване uj≡ajvj(modp)u_j\equiv a_jv_j\pmod p и съкращаване на ненулевите знаменатели получавамеaiai+1ai+2ai+3≡i(modp)a_i a_{i+1}a_{i+2}a_{i+3}\equiv i\pmod pза всички i=1,2,…,ki=1,2,\ldots,k. Това е търсеното.
Отвори задачатаMathNetISL 2020 N1Условие — източник

Задача N2

Пълен запис
Условие
За всяко просто число pp има кралство pp-Ландия, състоящо се от pp острова, номерирани с 1,2,…,p1,2,\ldots,p. Два различни острова с номера nn и mm са свързани с мост тогава и само тогава, когатоp∣(n2−m+1)(m2−n+1).p\mid (n^2-m+1)(m^2-n+1).Мостовете могат да минават един над друг, но не могат да се пресичат. Докажете, че за безкрайно много pp има два острова в pp-Ландия, които не са свързани с верига от мостове.
РешениеЩе докажем, че всяко просто число p>3p\gt{}3, което дели число от вида x2−x+1x^2-x+1, върши работа. Разглеждаме граф с върхове островите 1,2,…,p1,2,\ldots,p. Ако m2+1≡n(modp)m^2+1\equiv n\pmod p и m≠nm\ne n, насочваме стрелка от mm към nn. Един мост съществува точно когато има стрелка в поне една от двете посоки, затова броят на мостовете не надминава броя на стрелките. Нека x2−x+1≡0(modp)x^2-x+1\equiv0\pmod p. Тогава x2+1≡x(modp)x^2+1\equiv x\pmod p, така че от острова xx не излиза стрелка. Също(1−x)2−(1−x)+1=x2−x+1,(1-x)^2-(1-x)+1=x^2-x+1,затова и от острова с номер p+1−xp+1-x не излиза стрелка. Тези два острова са различни: ако x≡1−x(modp)x\equiv1-x\pmod p, то x≡(p+1)/2(modp)x\equiv (p+1)/2\pmod p и от x2−x+1≡0x^2-x+1\equiv0 би следвало p∣3p\mid3, противоречие на p>3p\gt{}3. Следователно има най-много p−2p-2 стрелки и значи най-много p−2p-2 моста. Граф с pp върха и по-малко от p−1p-1 ребра не е свързан, така че има два острова, които не са свързани с верига от мостове. Остава да видим, че има безкрайно много такива прости числа. Нека p1,p2,…,psp_1,p_2,\ldots,p_s са краен списък от прости делители на числа от вида x2−x+1x^2-x+1 и нека M=p1p2⋯psM=p_1p_2\cdots p_s. ЧислотоM2−M+1>1M^2-M+1\gt{}1не се дели на нито едно от p1,p2,…,psp_1,p_2,\ldots,p_s, но всеки негов прост делител отново дели число от вида x2−x+1x^2-x+1. Така винаги може да се намери ново просто число с това свойство, а следователно има безкрайно много подходящи pp.
Отвори задачатаMathNetISL 2020 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. Съществува ли редица (a1,…,an)(a_1,\ldots,a_n) от положителни цели числа, чиито членове не са всички равни, такава че средното аритметично на всеки два нейни члена да е равно на средното геометрично на някои един или повече членове на редицата?
РешениеОтговорът е отрицателен. Да допуснем, че такава редица съществува. Ако всички членове имат общ делител d>1d\gt{}1, можем да ги разделим на dd; всички аритметични и геометрични средни също се делят на dd, така че свойството се запазва. Затова можем да приемем, чеgcd⁡(a1,a2,…,an)=1.\gcd(a_1,a_2,\ldots,a_n)=1.Избираме am=max⁡(a1,…,an)a_m=\max(a_1,\ldots,a_n). Понеже членовете не са всички равни, имаме am≥2a_m\ge2. Нека pp е прост делител на ama_m. Понеже общият най-голям делител е 11, има член, който не се дели на pp; избираме aka_k максимален сред тези членове. Тогава am>aka_m\gt{}a_k. Некаb=am+ak2.b=\frac{a_m+a_k}{2}.Ще покажем, че bb не може да бъде средно геометрично на никоя непразна група членове на редицата. Ако всички избрани членове не се делят на pp, всеки от тях е най-много aka_k, следователно средното им геометрично е най-много ak<ba_k\lt{}b. Ако пък поне един избран член се дели на pp, и ако средното геометрично е gg, то 2g2g или не е цяло число, или се дели на pp. От друга страна2b=am+ak2b=a_m+a_kе цяло число, което не се дели на pp, защото p∣amp\mid a_m и p∤akp\nmid a_k. Значи и в този случай g≠bg\ne b. Така средното аритметично на членовете ama_m и aka_k не може да бъде средно геометрично на членове на редицата, противоречие.
Отвори задачатаMathNetISL 2020 N3Условие — източник

Задача N4

Пълен запис
Условие
За всяко нечетно просто число pp и всяко цяло число nn нека dp(n)∈{0,1,…,p−1}d_p(n)\in\{0,1,\ldots,p-1\} е остатъкът при деление на nn на pp. Ще казваме, че (a0,a1,a2,…)(a_0,a_1,a_2,\ldots) е pp-редица, ако a0a_0 е положително цяло число, взаимнопросто с pp, иan+1=an+dp(an)a_{n+1}=a_n+d_p(a_n)за n≥0n\ge0. (a) Съществуват ли безкрайно много прости числа pp, за които има pp-редици (a0,a1,a2,…)(a_0,a_1,a_2,\ldots) и (b0,b1,b2,…)(b_0,b_1,b_2,\ldots) такива, че an>bna_n\gt{}b_n за безкрайно много nn и bn>anb_n\gt{}a_n за безкрайно много nn? (b) Съществуват ли безкрайно много прости числа pp, за които има pp-редици (a0,a1,a2,…)(a_0,a_1,a_2,\ldots) и (b0,b1,b2,…)(b_0,b_1,b_2,\ldots) такива, че a0<b0a_0\lt{}b_0, но an>bna_n\gt{}b_n за всички n≥1n\ge1?
РешениеОтговорът е положителен и за двете части. Фиксираме нечетно просто число pp и нека TT е редът на 22 по модул pp. За произволна pp-редица (xn)(x_n) имамеxn+1≡2xn(modp),x_{n+1}\equiv2x_n\pmod p,следователно xn≡2nx0(modp)x_n\equiv2^n x_0\pmod p. Значи остатъците се повтарят с период TT. АкоSp(x0)=∑i=0T−1dp(2ix0),S_p(x_0)=\sum_{i=0}^{T-1} d_p(2^i x_0),тоxn+T=xn+Sp(x0)x_{n+T}=x_n+S_p(x_0)за всяко n≥0n\ge0. Освен това Sp(x0)=Sp(2tx0)S_p(x_0)=S_p(2^t x_0) за всяко цяло t≥0t\ge0. (a) Нека q>3q\gt{}3 е просто число и нека p>3p\gt{}3 е прост делител на 2q+12^q+1. Такъв делител съществува, понеже 3∣2q+13\mid 2^q+1, но 9∤2q+19\nmid 2^q+1. Тогава редът на 22 по модул pp е T=2qT=2q, а 2q≡−1(modp)2^q\equiv-1\pmod p. ЗатоваSp(1)=Sp(−1).S_p(1)=S_p(-1).Вземаме редиците с начални членове a0=p+1a_0=p+1 и b0=p−1b_0=p-1. Тогава a0>b0a_0\gt{}b_0, ноa1=p+2<2p−2=b1.a_1=p+2\lt{}2p-2=b_1.Понеже за двете начални остатъчни класи периодичният прираст е един и същ, получавамеa2qj>b2qjиa2qj+1<b2qj+1a_{2qj}\gt{}b_{2qj}\quad\text{и}\quad a_{2qj+1}\lt{}b_{2qj+1}за всички j≥0j\ge0. Има безкрайно много такива pp: за различни нечетни прости qq числата 2q+12^q+1 имат общ делител само 33, а всяко от тях с q>3q\gt{}3 има прост делител, различен от 33. (b) Нека qq е нечетно просто число и нека pp е прост делител на 2q−12^q-1. Тогава T=qT=q. За всяко ii имамеdp(2i)+dp(−2i)=p,d_p(2^i)+d_p(-2^i)=p,затоваSp(1)+Sp(−1)=pq.S_p(1)+S_p(-1)=pq.Това число е нечетно, следователно Sp(1)≠Sp(−1)S_p(1)\ne S_p(-1). Избираме две pp-редици (xn)(x_n) и (yn)(y_n) така, че x0<y0x_0\lt{}y_0, но Sp(x0)>Sp(y0)S_p(x_0)\gt{}S_p(y_0): ако Sp(1)>Sp(−1)S_p(1)\gt{}S_p(-1), вземаме x0=1x_0=1, y0=p−1y_0=p-1, а иначе вземаме x0=p−1x_0=p-1, y0=p+1y_0=p+1. За достатъчно голямо MM разликата след MM периода става положителна за всички остатъци в един период, понеже редицата (xn)(x_n) нараства с по-голям периодичен прираст от (yn)(y_n). Следователно съществува най-голям индекс n0n_0, за който xn0<yn0x_{n_0}\lt{}y_{n_0}. Двете редици никога не са равни, защото равенство в някой момент би дало еднакви стойности на SpS_p. Затова редицитеan=xn0+n,bn=yn0+na_n=x_{n_0+n},\qquad b_n=y_{n_0+n}удовлетворяват a0<b0a_0\lt{}b_0 и an>bna_n\gt{}b_n за всички n≥1n\ge1. Накрая, за различни нечетни прости qq числата 2q−12^q-1 са две по две взаимнопрости, понежеgcd⁡(2q−1,2r−1)=2gcd⁡(q,r)−1=1.\gcd(2^q-1,2^r-1)=2^{\gcd(q,r)}-1=1.Затова получаваме безкрайно много подходящи прости числа pp.
Отвори задачатаMathNetISL 2020 N4Условие — източник

Задача N5

Пълен запис
Условие
Да се намерят всички функции ff, дефинирани върху множеството на положителните цели числа и приемащи неотрицателни цели стойности, които удовлетворяват трите условия: (i) f(n)≠0f(n)\ne0 за поне едно nn; (ii) f(xy)=f(x)+f(y)f(xy)=f(x)+f(y) за всички положителни цели числа xx и yy; (iii) съществуват безкрайно много положителни цели числа nn, такива че f(k)=f(n−k)f(k)=f(n-k) за всички k<nk\lt{}n.
РешениеОтговорът еf(n)=cνp(n),f(n)=c\nu_p(n),където pp е просто число, cc е положително цяло число, а νp(n)\nu_p(n) е показателят на pp в каноничното разлагане на nn. Първо, от (ii) следва f(1)=0f(1)=0 иf(n)=∑r∣n, r простоνr(n)f(r).f(n)=\sum_{r\mid n,\ r\text{ просто}} \nu_r(n)f(r).В частност, ако f(n)=0f(n)=0, то f(r)=0f(r)=0 за всеки прост делител rr на nn. Да наречем положително цяло число nn добро, ако f(k)=f(n−k)f(k)=f(n-k) за всички 0<k<n0\lt{}k\lt{}n. Ако n=dmn=dm е добро, то dd също е добро, защото за 0<k<d0\lt{}k\lt{}d имамеf(k)=f(mk)−f(m)=f(n−mk)−f(m)=f(k)=f(mk)-f(m)=f(n-mk)-f(m)=f(m(d−k))−f(m)=f(d−k).f(m(d-k))-f(m)=f(d-k).Нека pp е най-малкото просто число, за което f(p)>0f(p)\gt{}0. Тогава f(r)=0f(r)=0 за всяко r<pr\lt{}p. Ако добро число n>pn\gt{}p не се дели на pp, пишем n=pt+rn=pt+r с 0<r<p0\lt{}r\lt{}p. От добротата получавамеf(pt)=f(n−pt)=f(r)=0,f(pt)=f(n-pt)=f(r)=0,което е невъзможно, понеже f(pt)=f(p)+f(t)>0f(pt)=f(p)+f(t)\gt{}0. Значи всяко добро число n>pn\gt{}p се дели на pp. Понеже делителите на добро число също са добри, всеки делител на добро число, който не се дели на pp, е по-малък от pp. Следователно добрите числа са от вида rpsrp^s с r<pr\lt{}p. Условието (iii) дава добри числа с неограничено големи показатели ss, а оттук всички степени pmp^m са добри. Нека q≠pq\ne p е просто число. Числото pq−1p^{q-1} е добро, а по малката теорема на Ферма q∣pq−1−1q\mid p^{q-1}-1. От добротата при k=1k=1 следваf(pq−1−1)=f(1)=0,f(p^{q-1}-1)=f(1)=0,следователно f(q)=0f(q)=0. Така единственото просто число, върху което ff може да е ненулева, е pp, и получаваме f(n)=cνp(n)f(n)=c\nu_p(n) с c=f(p)>0c=f(p)\gt{}0. Обратно, всяка такава функция удовлетворява (i) и (ii). Ако n=pmn=p^m и 0<k<pm0\lt{}k\lt{}p^m, тоνp(k)=νp(pm−k),\nu_p(k)=\nu_p(p^m-k),затова (iii) е изпълнено за безкрайно много nn.
Отвори задачатаMathNetISL 2020 N5Условие — източник

Задача N6

Пълен запис
Условие
За положително цяло число nn нека d(n)d(n) е броят на положителните делители на nn, а φ(n)\varphi(n) - броят на положителните цели числа, които не надминават nn и са взаимнопрости с nn. Съществува ли константа CC, такава чеφ(d(n))d(φ(n))≤C\frac{\varphi(d(n))}{d(\varphi(n))}\le Cза всяко n≥1n\ge1?
РешениеОтговорът е отрицателен. Ще покажем, че отношението може да бъде произволно голямо. Фиксираме цяло число N>1N\gt{}1. Нека p1,…,pkp_1, \ldots,p_k са всички прости числа, които не надминават NN, а pk+1,…,pk+sp_{k+1},\ldots,p_{k+s} - всички прости числа в интервала (N,2N](N,2N]. Всеки прост делител на pj−1p_j-1 за j≤k+sj\le k+s не надминава NN, затова∏j=1k+s(pj−1)=∏i=1kpici\prod_{j=1}^{k+s}(p_j-1)=\prod_{i=1}^k p_i^{c_i}за някои цели числа ci≥0c_i\ge0. Избираме голямо просто число qq и разглеждамеn=(p1p2⋯pk)q−1(pk+1pk+2⋯pk+s).n=(p_1p_2\cdots p_k)^{q-1}(p_{k+1}p_{k+2}\cdots p_{k+s}).Тогаваd(n)=qk2s,d(n)=q^k2^s,следователноφ(d(n))=qk−1(q−1)2s−1.\varphi(d(n))=q^{k-1}(q-1)2^{s-1}.От друга странаφ(n)=∏i=1kpiq−2∏j=1k+s(pj−1)=\varphi(n)=\prod_{i=1}^k p_i^{q-2}\prod_{j=1}^{k+s}(p_j-1)=∏i=1kpiq−2+ci,\prod_{i=1}^k p_i^{q-2+c_i},така чеd(φ(n))=∏i=1k(q−1+ci).d(\varphi(n))=\prod_{i=1}^k(q-1+c_i).Следователноφ(d(n))d(φ(n))=\frac{\varphi(d(n))}{d(\varphi(n))}=2s−1⋅q−1q∏i=1kqq−1+ci,2^{s-1}\cdot\frac{q-1}{q}\prod_{i=1}^k\frac{q}{q-1+c_i},което клони към 2s−12^{s-1}, когато qq расте. Остава само да отбележим, че ss не е ограничено. Ако броят на простите числа във всеки интервал (N,2N](N,2N] беше ограничен с една и съща константа, тогава сумата на реципрочните стойности на простите числа щеше да е сходяща, което противоречи на класическата теорема на Ойлер∑p просто1p=∞.\sum_{p\text{ просто}}\frac1p=\infty.Затова можем да изберем NN с произволно голямо ss, а после qq достатъчно голямо. Отношението е неограничено и такава константа CC не съществува.
Отвори задачатаMathNetISL 2020 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека SS е множество от n≥3n\ge3 положителни цели числа, никое от които не е сума на два други различни елемента на SS. Докажете, че елементите на SS могат да се подредят като a1,a2,…,ana_1,a_2,\ldots,a_n така, чеai∤ai−1+ai+1a_i\nmid a_{i-1}+a_{i+1}за всички i=2,3,…,n−1i=2,3,\ldots,n-1.
РешениеЩе докажем малко по-силно твърдение: елементите на всяко такова множество с поне 22 елемента могат да се подредят така, че за всеки вътрешен член aia_i да е вярно едновременноai∤ai−1+ai+1иai∤ai−1−ai+1.a_i\nmid a_{i-1}+a_{i+1}\quad\text{и}\quad a_i\nmid a_{i-1}-a_{i+1}.Ще използваме следното просто наблюдение. Ако a,b,ca,b,c са различни елементи на SS и b>a,cb\gt{}a,c, то b∤a+cb\nmid a+c. Наистина, при делимост би трябвало или b=a+cb=a+c, което е забранено, или 2b≤a+c2b\le a+c, което е невъзможно при a,c<ba,c\lt{}b. Доказваме силното твърдение с индукция по броя на елементите. За n=2n=2 няма вътрешни членове. Нека n≥3n\ge3, нека a=max⁡Sa=\max S и нека T=S∖{a}T=S\setminus\{a\}. По индукционното предположение елементите на TT имат добра подредбаb1,b2,…,bn−1.b_1,b_2,\ldots,b_{n-1}.Ще покажем, че aa може да се вмъкне в някое от nn-те възможни места. За място jj разглеждаме подредбата(b1,…,bj−1,a,bj,…,bn−1).(b_1,\ldots,b_{j-1},a,b_j, \ldots,b_{n-1}).Ако тя не е добра, новото нарушение трябва да включва някой от съседите на вмъкнатото aa, тоест един от bj−1b_{j-1} или bjb_j (когато съществува). Самото aa не може да е причината: то не дели разлика на два по-малки положителни елемента, а по наблюдението не дели и тяхната сума. Да допуснем, че нито едно място за вмъкване не работи. Тогава на всяко място можем да съпоставим един от елементите b1,…,bn−1b_1, \ldots,b_{n-1}, който създава нарушение. Понеже местата са nn, а тези елементи са n−1n-1, някой bkb_k се съпоставя на две места. Това може да са само двете места непосредствено преди и след bkb_k. Следователно за някои знаци ε1,ε2∈{−1,1}\varepsilon_1, \varepsilon_2\in\{-1,1\} имамеbk∣bk−1+ε1aиbk∣a+ε2bk+1,b_k\mid b_{k-1}+\varepsilon_1 a\quad\text{и}\quad b_k\mid a+\varepsilon_2 b_{k+1},като липсващи крайни членове просто не се появяват. Изваждането на тези две делимости даваbk∣bk−1−ε1ε2bk+1,b_k\mid b_{k-1}-\varepsilon_1\varepsilon_2 b_{k+1},което противоречи на добрата подредба на TT. Значи поне едно място за вмъкване работи и индукцията е завършена. Силното твърдение веднага дава исканото подреждане.
Отвори задачатаMathNetISL 2020 N7Условие — източник