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

IMO Shortlisted Problems

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

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

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

2018

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

11-12

21 задачи

Задача A1

Пълен запис
Условие
Нека Q>0\mathbb Q_{\gt{}0} означава множеството на положителните рационални числа. Да се намерят всички функции f:Q>0→Q>0f:\mathbb Q_{\gt{}0}\to\mathbb Q_{\gt{}0}, за коитоf(x2f(y)2)=f(x)2f(y)f\left(x^2f(y)^2\right)=f(x)^2f(y)за всички x,y∈Q>0x,y\in\mathbb Q_{\gt{}0}.
РешениеОтговорът еf(x)=1(x∈Q>0).f(x)=1\qquad(x\in\mathbb Q_{\gt{}0}).Нека a,b∈Q>0a,b\in\mathbb Q_{\gt{}0}. Замествайки в даденото равенство първо x=f(a),y=bx=f(a),y=b, а после x=f(b),y=ax=f(b),y=a, получавамеf(f(a)2f(b)2)=f(f(a)^2f(b)^2)=f(f(a))2f(b)=f(f(b))2f(a).f(f(a))^2f(b)=f(f(b))^2f(a).Следователно съществува константа C∈Q>0C\in\mathbb Q_{\gt{}0} такава, чеf(f(a))2f(a)=Cза всяко a∈Q>0.\frac{f(f(a))^2}{f(a)}=C\qquad\text{за всяко }a\in\mathbb Q_{\gt{}0}.Това е еквивалентно на(f(f(a))C)2=f(a)C.(1)\left(\frac{f(f(a))}{C}\right)^2=\frac{f(a)}C.\tag{1}Нека fnf^n означава nn-тата итерация на ff. От (1), приложено последователно към a,f(a),f2(a),…a,f(a),f^2(a),\ldots, следваf(a)C=(f2(a)C)2=\frac{f(a)}C=\left(\frac{f^2(a)}C\right)^2=(f3(a)C)4=⋯=(fn+1(a)C)2n\left(\frac{f^3(a)}C\right)^4=\cdots=\left(\frac{f^{n+1}(a)}C\right)^{2^n}за всяко положително цяло nn. Положителното рационално число f(a)/Cf(a)/C е 2n2^n-та степен на рационално число за всяко nn. Това е възможно само ако f(a)/C=1f(a)/C=1: иначе в разлагането му по прости множители някой показател няма да се дели на достатъчно голяма степен на 22. Значи f(a)=Cf(a)=C за всяко aa. Остава да заместим константната функция f≡Cf\equiv C в условието. Получаваме C=C3C=C^3, а понеже C>0C\gt{}0, следва C=1C=1. Проверката на f≡1f\equiv1 е непосредствена.
Отвори задачатаMathNetISL 2018 A1Условие — източник

Задача A2

Пълен запис
Условие
Да се намерят всички положителни цели числа n≥3n\ge3, за които съществуват реални числа a1,a2,…,ana_1,a_2,\ldots,a_n, an+1=a1a_{n+1}=a_1, an+2=a2a_{n+2}=a_2, такива чеaiai+1+1=ai+2a_ia_{i+1}+1=a_{i+2}за всички i=1,2,…,ni=1,2,\ldots,n.
РешениеОтговорът е: всички кратни на 33 положителни цели числа n≥3n\ge3. Ако 3∣n3\mid n, редицата−1,−1,2,−1,−1,2,…-1,-1,2,-1,-1,2,\ldotsс период 33 дава пример, защото (−1)(−1)+1=2(-1)(-1)+1=2, (−1)⋅2+1=−1(-1)\cdot2+1=-1 и 2⋅(−1)+1=−12\cdot(-1)+1=-1. Обратно, нека такава периодична редица с период nn съществува. Всички индекси по-долу се разглеждат циклично. От рекурентната връзка, приложена за ii и i+1i+1, имаме(ai+2−1)ai+2=aiai+1ai+2=ai(ai+3−1),(a_{i+2}-1)a_{i+2}=a_ia_{i+1}a_{i+2}=a_i(a_{i+3}-1),следователноai+22−aiai+3=ai+2−ai.a_{i+2}^2-a_ia_{i+3}=a_{i+2}-a_i.Сумираме за i=1,2,…,ni=1,2,\ldots,n. Дясната страна дава 00, а от периодичността получаваме∑i=1nai2=∑i=1naiai+3.\sum_{i=1}^n a_i^2=\sum_{i=1}^n a_ia_{i+3}.Затова∑i=1n(ai−ai+3)2=0,\sum_{i=1}^n (a_i-a_{i+3})^2=0,тоест ai=ai+3a_i=a_{i+3} за всяко ii. Редицата не може да е константна, защото уравнението x2+1=xx^2+1=x няма реален корен. Следователно най-малкият период е 33. Щом същата редица има период nn, необходимо е 3∣n3\mid n.
Отвори задачатаMathNetISL 2018 A2Условие — източник

Задача A3

Пълен запис
Условие
Дадено е произволно множество SS от положителни цели числа. Докажете, че поне едно от следните две твърдения е вярно: (1) съществуват различни крайни подмножества FF и GG на SS, за които∑x∈F1x=∑x∈G1x;\sum_{x\in F}\frac1x=\sum_{x\in G}\frac1x;(2) съществува положително рационално число r<1r\lt{}1 такова, че∑x∈F1x≠r\sum_{x\in F}\frac1x\ne rза всяко крайно подмножество FF на SS.
РешениеДа допуснем, че твърдение (1) не е вярно. Ще докажем (2). Ако SS е крайно, има само краен брой суми ∑x∈F1/x\sum_{x\in F}1/x, затова можем да изберем положително рационално r<1r\lt{}1, различно от всички тях. Значи можем да считаме, че SS е безкрайно. Освен това можем да премахнем числото 11, ако то принадлежи на SS. Наистина, ако S∖{1}S\setminus\{1\} удовлетворява (1), тогава и SS удовлетворява (1). Ако пък за S∖{1}S\setminus\{1\} съществува число r<1r\lt{}1 от (2), то същото rr не може да се представи чрез подмножество на SS, което съдържа 11, понеже тогава сумата би била поне 11. Затова е достатъчно да разгледаме случая, когато всички елементи на SS са по-големи от 11. Некаx1<x2<x3<⋯x_1\lt{}x_2\lt{}x_3\lt{}\cdotsса елементите на SS. Ако xn+1≥2xnx_{n+1}\ge2x_n за всяко nn, то∑n≥11xn≤2x1.\sum_{n\ge1}\frac1{x_n}\le\frac2{x_1}.Ако x1≥3x_1\ge3, или ако x1=2x_1=2 и някое от неравенствата xn+1≥2xnx_{n+1}\ge2x_n е строго, тази безкрайна сума е по-малка от 11; тогава избираме рационално rr между нея и 11. Ако пък x1=2x_1=2 и xn+1=2xnx_{n+1}=2x_n за всяко nn, всички крайни суми са двоични рационални числа, така че например r=1/3r=1/3 не се представя. И в двата случая получаваме (2). Остава да има индекс nn с xn+1<2xnx_{n+1}\lt{}2x_n. Положимr=1xn−1xn+1.r=\frac1{x_n}-\frac1{x_{n+1}}.Тогава 0<r<1/xn+1<10\lt{}r\lt{}1/x_{n+1}\lt{}1. Ако rr не се представя като крайна сума от реципрочни стойности на елементи на SS, сме готови. Иначе некаr=∑x∈F01xr=\sum_{x\in F_0}\frac1xза някое крайно F0⊂SF_0\subset S. Понеже r<1/xn+1r\lt{}1/x_{n+1}, множеството F0F_0 не съдържа xn+1x_{n+1}. Тогава крайните подмножестваF=F0∪{xn+1},G={xn}F=F_0\cup\{x_{n+1}\},\qquad G=\{x_n\}са различни и имат равни суми на реципрочните стойности. Това е твърдение (1), противоречие. Следователно (2) е вярно.
Отвори задачатаMathNetISL 2018 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека a0,a1,a2,…a_0,a_1,a_2,\ldots е редица от реални числа, за която a0=0a_0=0, a1=1a_1=1 и за всяко n≥2n\ge2 съществува 1≤k≤n1\le k\le n, така чеan=an−1+⋯+an−kk.a_n=\frac{a_{n-1}+\cdots+a_{n-k}}k.Да се намери най-голямата възможна стойност на a2018−a2017a_{2018}-a_{2017}.
РешениеОтговорът е201620172.\frac{2016}{2017^2}.Тази стойност се достига например приa1=a2=⋯=a2016=1,a_1=a_2=\cdots=a_{2016}=1,a2017=a2016+⋯+a02017=1−12017,a_{2017}=\frac{a_{2016}+\cdots+a_0}{2017}=1-\frac1{2017},a2018=a2017+⋯+a12017=1−120172.\qquad a_{2018}=\frac{a_{2017}+\cdots+a_1}{2017}=1-\frac1{2017^2}.Тогава a2018−a2017=2016/20172a_{2018}-a_{2017}=2016/2017^2. Ще докажем, че по-голяма стойност е невъзможна. За 0≤k≤n0\le k\le n положимS(n,k)=an−1+an−2+⋯+an−k,S(n,k)=a_{n-1}+a_{n-2}+\cdots+a_{n-k},като S(n,0)=0S(n,0)=0. За всяко n≥1n\ge1 дефинирамеMn=max⁡1≤k≤nS(n,k)k,M_n=\max_{1\le k\le n}\frac{S(n,k)}k,mn=min⁡1≤k≤nS(n,k)k,Δn=Mn−mn.\qquad m_n=\min_{1\le k\le n}\frac{S(n,k)}k,\qquad \Delta_n=M_n-m_n.Имаме an∈[mn,Mn]a_n\in[m_n,M_n] за n≥2n\ge2, а също an−1=S(n,1)∈[mn,Mn]a_{n-1}=S(n,1)\in[m_n,M_n]. Следователноa2018−a2017≤M2018−m2018=Δ2018.a_{2018}-a_{2017}\le M_{2018}-m_{2018}=\Delta_{2018}.Ще използваме оценкатаΔn≤n−1nΔn−1(n>2).(1)\Delta_n\le\frac{n-1}{n}\Delta_{n-1}\qquad(n\gt{}2).\tag{1}Нека Mn=S(n,k)/kM_n=S(n,k)/k и mn=S(n,ℓ)/ℓm_n=S(n,\ell)/\ell. ПонежеS(n,k)=an−1+S(n−1,k−1),S(n,k)=a_{n-1}+S(n-1,k-1),получавамеk(Mn−an−1)=S(n−1,k−1)−(k−1)an−1≤k(M_n-a_{n-1})=S(n-1,k-1)-(k-1)a_{n-1}\le(k−1)(Mn−1−an−1).(k-1)(M_{n-1}-a_{n-1}).Аналогичноℓ(an−1−mn)=(ℓ−1)an−1−S(n−1,ℓ−1)≤\ell(a_{n-1}-m_n)=(\ell-1)a_{n-1}-S(n-1,\ell-1)\le(ℓ−1)(an−1−mn−1).(\ell-1)(a_{n-1}-m_{n-1}).Тъй като k,ℓ≤nk,\ell\le n и mn−1≤an−1≤Mn−1m_{n-1}\le a_{n-1}\le M_{n-1}, следваMn−an−1≤n−1n(Mn−1−an−1),M_n-a_{n-1}\le\frac{n-1}{n}(M_{n-1}-a_{n-1}),an−1−mn≤n−1n(an−1−mn−1).a_{n-1}-m_n\le\frac{n-1}{n}(a_{n-1}-m_{n-1}).Събирането на тези две неравенства дава (1). По индукция всички an≤1a_n\le1. Ако an=1a_n=1 за всички 1≤n≤20171\le n\le2017, тогава a2018≤1a_{2018}\le1 и a2018−a2017≤0a_{2018}-a_{2017}\le0. Иначе нека qq е най-малкият индекс с 2≤q≤20172\le q\le2017 и aq<1a_q\lt{}1. Тогава a1=⋯=aq−1=1a_1=\cdots=a_{q-1}=1, затова S(q,i)=iS(q,i)=i за 1≤i≤q−11\le i\le q-1, а S(q,q)=q−1S(q,q)=q-1. За да бъде aq<1a_q\lt{}1, трябваaq=S(q,q)q=1−1q.a_q=\frac{S(q,q)}q=1-\frac1q.Сега за i=1,2,…,qi=1,2,\ldots,q имаме S(q+1,i)=i−1/qS(q+1,i)=i-1/q, а S(q+1,q+1)=q−1/qS(q+1,q+1)=q-1/q. Следователноmq+1=q−1q,Mq+1=q2−1q2,Δq+1=q−1q2.m_{q+1}=\frac{q-1}{q},\qquad M_{q+1}=\frac{q^2-1}{q^2},\qquad \Delta_{q+1}=\frac{q-1}{q^2}.Нека N=2017N=2017. Прилагайки (1) за n=q+2,q+3,…,N+1n=q+2,q+3,\ldots,N+1, получавамеΔN+1≤\Delta_{N+1}\leq−1q2⋅q+1q+2⋅q+2q+3⋯NN+1=\frac{q-1}{q^2}\cdot\frac{q+1}{q+2}\cdot\frac{q+2}{q+3}\cdots\frac{N}{N+1}=1N+1(1−1q2).\frac1{N+1}\left(1-\frac1{q^2}\right).Понеже q≤Nq\le N, това е най-много1N+1(1−1N2)=N−1N2=201620172.\frac1{N+1}\left(1-\frac1{N^2}\right)=\frac{N-1}{N^2}=\frac{2016}{2017^2}.Значи a2018−a2017≤2016/20172a_{2018}-a_{2017}\le2016/2017^2, както трябваше.
Отвори задачатаMathNetISL 2018 A4Условие — източник

Задача A5

Пълен запис
Условие
Да се намерят всички функции f:(0,∞)→Rf:(0,\infty)\to\mathbb R, за които(x+1x)f(y)=f(xy)+f(yx)\left(x+\frac1x\right)f(y)=f(xy)+f\left(\frac yx\right)за всички x,y>0x,y\gt{}0.
РешениеОтговорът еf(x)=C1x+C2x,f(x)=C_1x+\frac{C_2}{x},където C1C_1 и C2C_2 са произволни реални константи. Фиксираме число a>1a\gt{}1 и нека t>0t\gt{}0 е променлива. Прилагаме условието за четири избора на (x,y)(x,y):(t+1t)f(t)=f(t2)+f(1),(2a)\left(t+\frac1t\right)f(t)=f(t^2)+f(1),\tag{2a}(ta+at)f(at)=f(t2)+f(a2),(2b)\left(\frac ta+\frac at\right)f(at)=f(t^2)+f(a^2),\tag{2b}(a2t+1a2t)f(t)=f(a2t2)+f(1a2),(2c)\left(a^2t+\frac1{a^2t}\right)f(t)=f(a^2t^2)+f\left(\frac1{a^2}\right),\tag{2c}(at+1at)f(at)=f(a2t2)+f(1).(2d)\left(at+\frac1{at}\right)f(at)=f(a^2t^2)+f(1).\tag{2d}Изваждаме (2b) от (2a) и (2d) от (2c):(t+1t)f(t)−(ta+at)f(at)=f(1)−f(a2),\left(t+\frac1t\right)f(t)-\left(\frac ta+\frac at\right)f(at)=f(1)-f(a^2),(3)\tag{3}(a2t+1a2t)f(t)−(at+1at)f(at)=\left(a^2t+\frac1{a^2t}\right)f(t)-\left(at+\frac1{at}\right)f(at)=f(1a2)−f(1).(4)f\left(\frac1{a^2}\right)-f(1).\tag{4}Елиминираме f(at)f(at) от (3) и (4). Коефициентът пред f(t)f(t) е(at+1at)(t+1t)\left(at+\frac1{at}\right)\left(t+\frac1t\right)−(ta+at)(a2t+1a2t)=-\left(\frac ta+\frac at\right)\left(a^2t+\frac1{a^2t}\right)=a+1a−a3−1a3,a+\frac1a-a^3-\frac1{a^3},който е ненулев. Дясната страна след елиминирането има вида αt+β/t\alpha t+\beta/t, където α\alpha и β\beta зависят само от aa, f(1)f(1), f(a2)f(a^2) и f(1/a2)f(1/a^2). Следователноf(t)=C1t+C2tf(t)=C_1t+\frac{C_2}{t}за всички t>0t\gt{}0. Остава проверка. Ако f(x)=C1x+C2/xf(x)=C_1x+C_2/x, тогава(x+1x)f(y)=(x+1x)(C1y+C2y)=\left(x+\frac1x\right)f(y)=\left(x+\frac1x\right)\left(C_1y+\frac{C_2}{y}\right)=C1xy+C2xy+C1yx+C2xy,C_1xy+\frac{C_2}{xy}+C_1\frac yx+C_2\frac xy,което е точно f(xy)+f(y/x)f(xy)+f(y/x). Значи всички и само тези функции са решения.
Отвори задачатаMathNetISL 2018 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека m,n≥2m,n\ge2 са цели числа. Нека f(x1,…,xn)f(x_1,\ldots,x_n) е полином с реални коефициенти, такъв чеf(x1,…,xn)=⌊x1+⋯+xnm⌋f(x_1,\ldots,x_n)=\left\lfloor\frac{x_1+\cdots+x_n}{m}\right\rfloorза всички x1,…,xn∈{0,1,…,m−1}x_1,\ldots,x_n\in\{0,1,\ldots,m-1\}. Докажете, че пълната степен на ff е поне nn.
РешениеЩе използваме следната лема. Лема. Нека a1,…,ana_1,\ldots,a_n са неотрицателни цели числа, а G(x)G(x) е ненулев полином с deg⁡G≤a1+⋯+an\deg G\le a_1+\cdots+a_n. Ако полиномът F(x1,…,xn)F(x_1,\ldots,x_n) удовлетворяваF(x1,…,xn)=G(x1+⋯+xn)F(x_1,\ldots,x_n)=G(x_1+\cdots+x_n)за всички (x1,…,xn)∈{0,1,…,a1}×⋯×{0,1,…,an}(x_1,\ldots,x_n)\in\{0,1,\ldots,a_1\}\times\cdots\times\{0,1,\ldots,a_n\}, то FF не е нулевият полином и deg⁡F≥deg⁡G\deg F\ge\deg G. Доказателство на лемата. Доказваме с индукция по deg⁡G\deg G. При deg⁡G=0\deg G=0 имаме F(0,…,0)=G(0)≠0F(0,\ldots,0)=G(0)\ne0. Нека deg⁡G≥1\deg G\ge1. Поне едно aia_i е положително; без ограничение нека a1≥1a_1\ge1. Нека ΔG(x)=G(x+1)−G(x)\Delta G(x)=G(x+1)-G(x) и Δ1F=F(x1+1,x2,…,xn)−F(x1,x2,…,xn)\Delta_1F=F(x_1+1,x_2,\ldots,x_n)-F(x_1,x_2,\ldots,x_n). Върху по-малката решетка{0,…,a1−1}×{0,…,a2}×⋯×{0,…,an}\{0,\ldots,a_1-1\}\times\{0,\ldots,a_2\}\times\cdots\times\{0,\ldots,a_n\}имамеΔ1F(x1,…,xn)=ΔG(x1+⋯+xn).\Delta_1F(x_1,\ldots,x_n)=\Delta G(x_1+\cdots+x_n).Понеже GG не е константа, deg⁡ΔG=deg⁡G−1\deg\Delta G=\deg G-1, а тази степен е най-много (a1−1)+a2+⋯+an(a_1-1)+a_2+\cdots+a_n. По индукционното предположение Δ1F\Delta_1F не е нулев полином иdeg⁡Δ1F≥deg⁡ΔG=deg⁡G−1.\deg\Delta_1F\ge\deg\Delta G=\deg G-1.Следователно deg⁡F≥deg⁡Δ1F+1≥deg⁡G\deg F\ge\deg\Delta_1F+1\ge\deg G. Лемата е доказана. Сега нека g(x)g(x) е единственият полином със степен най-много n(m−1)n(m-1), за койтоg(x)=⌊xm⌋за x=0,1,…,n(m−1).g(x)=\left\lfloor\frac xm\right\rfloor\qquad\text{за }x=0,1,\ldots,n(m-1).От g(0)=g(1)=0g(0)=g(1)=0 и g(m)=1g(m)=1 следва deg⁡g≥2\deg g\ge2. Прилагаме лемата с a1=⋯=an=m−1a_1=\cdots=a_n=m-1, F=fF=f и G=gG=g. Получаваме deg⁡f≥deg⁡g\deg f\ge\deg g. Остава да оценим степента на gg отдолу. Разглеждамеh(x)=g(x+m)−g(x)−1.h(x)=g(x+m)-g(x)-1.Тъй като deg⁡g≥2\deg g\ge2, полиномът hh е ненулев и deg⁡h=deg⁡g−1\deg h=\deg g-1. За всякоx=0,1,…,n(m−1)−mx=0,1,\ldots,n(m-1)-mстойностите xx и x+mx+m са в интерполационния интервал, а⌊x+mm⌋−⌊xm⌋−1=0.\left\lfloor\frac{x+m}{m}\right\rfloor-\left\lfloor\frac xm\right\rfloor-1=0.Значи hh има поне (n−1)(m−1)(n-1)(m-1) корена. Следователноdeg⁡f≥deg⁡g=deg⁡h+1≥(n−1)(m−1)+1≥n,\deg f\ge\deg g=\deg h+1\ge(n-1)(m-1)+1\ge n,понеже m,n≥2m,n\ge2.
Отвори задачатаMathNetISL 2018 A6Условие — източник

Задача A7

Пълен запис
Условие
Да се намери най-голямата стойност наS=S=x2ab+73+x2bc+73\sqrt[3]{\vphantom{x^2}\frac a{b+7}}+\sqrt[3]{\vphantom{x^2}\frac b{c+7}}+x2cd+73+x2da+73,+\sqrt[3]{\vphantom{x^2}\frac c{d+7}}+\sqrt[3]{\vphantom{x^2}\frac d{a+7}},където a,b,c,da,b,c,d са неотрицателни реални числа и a+b+c+d=100a+b+c+d=100.
РешениеОтговорът е8x273,\frac8{\sqrt[3]{\vphantom{x^2}7}},като равенство се достига при цикличните пермутации на (1,49,1,49)(1,49,1,49). Ще докажем горната оценка. По неравенството на Хьолдер,S3=S^3=(∑cycx2a6x2a6x2b+73)3≤\left(\sum_{cyc}\frac{\sqrt[6]{\vphantom{x^2}a}\sqrt[6]{\vphantom{x^2}a}}{\sqrt[3]{\vphantom{x^2}b+7}}\right)^3\le(∑cyca)2(∑cyc1b+7).(1)\left(\sum_{cyc}\sqrt a\right)^2\left(\sum_{cyc}\frac1{b+7}\right).\tag{1}Нека T=∑cycaT=\sum_{cyc}\sqrt a. От Коши-Шварц имаме T≤x24(a+b+c+d)=20T\le\sqrt{\vphantom{x^2}4(a+b+c+d)}=20, така че 48−2T≥048-2T\ge0. За всяко x≥0x\ge0 е вярно(x−1)2(x−7)2x2+7≥0,\frac{(x-1)^2(x-7)^2}{x^2+7}\ge0,което е еквивалентно наx2−16x+71≥448x2+7.x^2-16x+71\ge\frac{448}{x^2+7}.При x=bx=\sqrt b получаваме1b+7≤b−16b+71448.\frac1{b+7}\le\frac{b-16\sqrt b+71}{448}.Сумирайки за a,b,c,da,b,c,d, намираме∑cyc1b+7≤\sum_{cyc}\frac1{b+7}\le100−16T+4⋅71448=48−2T56.(2)\frac{100-16T+4\cdot71}{448}=\frac{48-2T}{56}.\tag{2}От (1) и (2) следваS3≤T2(48−2T)56.S^3\le\frac{T^2(48-2T)}{56}.Понеже числата T,T,48−2TT,T,48-2T са неотрицателни и имат сума 4848, от AM-GMT2(48−2T)≤(483)3=4096.T^2(48-2T)\le\left(\frac{48}{3}\right)^3=4096.СледователноS3≤409656=5127,S^3\le\frac{4096}{56}=\frac{512}{7},тоестS≤8x273.S\le\frac8{\sqrt[3]{\vphantom{x^2}7}}.Посочената четворка (1,49,1,49)(1,49,1,49) дава равенство, така че това е търсената най-голяма стойност.
Отвори задачатаMathNetISL 2018 A7Условие — източник

Задача C1

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число. Докажете, че съществува множество SS от 2n2n положителни цели числа със следното свойство: за всяко m=2,3,…,nm=2,3,\ldots,n множеството SS може да се раздели на две подмножества с равни суми на елементите, като едното от подмножествата има мощност mm.
РешениеЩе построим пример. НекаS=S={3k,2⋅3k:k=1,2,…,n−1}∪{1,3n+92−1}.\{3^k,2\cdot3^k:k=1,2,\ldots,n-1\}\cup\left\{1,\frac{3^n+9}{2}-1\right\}.Всички тези числа са различни: първите 2n−22n-2 са кратни на 33, а последните две не са кратни на 33. Сумата на елементите на SS е1+(3n+92−1)+∑k=1n−1(3k+2⋅3k)=1+\left(\frac{3^n+9}{2}-1\right)+\sum_{k=1}^{n-1}(3^k+2\cdot3^k)=3n+92+∑k=1n−13k+1=2⋅3n.\frac{3^n+9}{2}+\sum_{k=1}^{n-1}3^{k+1}=2\cdot3^n.Затова е достатъчно за всяко m=2,3,…,nm=2,3,\ldots,n да намерим mm-елементно подмножество със сума 3n3^n. За това вземамеAm=A_m={2⋅3k:k=n−m+1,n−m+2,…,n−1}∪{3n−m+1}.\{2\cdot3^k:k=n-m+1,n-m+2,\ldots,n-1\}\cup\{3^{n-m+1}\}.Ясно е, че ∣Am∣=m|A_m|=m. Освен това∑a∈Ama=3n−m+1+∑k=n−m+1n−12⋅3k=\sum_{a\in A_m}a=3^{n-m+1}+\sum_{k=n-m+1}^{n-1}2\cdot3^k=3n−m+1+2⋅3n−2⋅3n−m+12=3n.3^{n-m+1}+\frac{2\cdot3^n-2\cdot3^{n-m+1}}{2}=3^n.Следователно AmA_m и допълнението му в SS имат равни суми, а AmA_m има исканата мощност.
Отвори задачатаMathNetISL 2018 C1Условие — източник

Задача C2

Пълен запис
Условие
Куини и Хорст играят игра върху шахматна дъска 20×2020\times20. В началото дъската е празна. На всеки ход Хорст поставя черен кон върху празно поле така, че новият му кон да не атакува никой от предишните коне. След това Куини поставя бяла царица върху празно поле. Играта приключва, когато някой от двамата не може да направи ход. Да се намери най-голямото положително цяло число KK, за което независимо от стратегията на Куини, Хорст може да постави поне KK коня на дъската.
РешениеОтговорът е K=100K=100. Първо ще дадем стратегия за Хорст, която му гарантира поне 100100 коня. Оцветяваме дъската шахматно в черно и бяло и нека Хорст поставя коне само върху черни полета, докато това е възможно. Два коня върху полета от един и същи цвят никога не се атакуват. Черните полета са 200200, а двамата играчи заемат по едно поле на ход, затова през първите 100100 хода на Хорст все още има празно черно поле. Остава да покажем, че Куини може да не позволи повече от 100100 коня. Разделяме дъската на 2525 блока 4×44\times4. Във всеки блок с координати (1,1),(1,2),…,(4,4)(1,1),(1,2),\ldots,(4,4) групираме полетата в следните четири цикъла на графа на конските ходове:(1,1),(2,3),(4,4),(3,2),(1,2),(3,1),(4,3),(2,4),(1,3),(3,4),(4,2),(2,1),(1,4),(2,2),(4,1),(3,3).\begin{aligned} &(1,1),(2,3),(4,4),(3,2),\\ &(1,2),(3,1),(4,3),(2,4),\\ &(1,3),(3,4),(4,2),(2,1),\\ &(1,4),(2,2),(4,1),(3,3). \end{aligned}Във всеки ред от този списък последователните полета, както и последното и първото, са свързани с ход на кон. Така всички 400400 полета са разделени на 100100 цикъла с дължина 44. Стратегията на Куини е следната. Ако Хорст постави кон върху поле AA от цикъл A−B−C−D−AA-B-C-D-A, тя поставя царицата си върху срещуположното поле CC от същия цикъл. От този момент Хорст не може да поставя кон върху AA или CC, защото са заети, нито върху BB или DD, защото се атакуват от коня на AA. Следователно във всеки от 100100-те цикъла може да се появи най-много един кон, т.е. Хорст може да постави най-много 100100 коня. Двете стратегии заедно дават максималната стойност K=100K=100.
Отвори задачатаMathNetISL 2018 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека nn е дадено положително цяло число. Сизиф извършва последователност от ходове върху дъска от n+1n+1 полета в редица, номерирани от 00 до nn отляво надясно. Първоначално в поле 00 има nn камъка, а останалите полета са празни. На всеки ход Сизиф избира непразно поле, нека в него има kk камъка, взема един от тези камъни и го премества надясно с най-много kk полета, като камъкът трябва да остане върху дъската. Целта на Сизиф е да премести всички nn камъка в поле nn. Докажете, че Сизиф не може да постигне целта за по-малко от⌈n1⌉+⌈n2⌉+⌈n3⌉+⋯+⌈nn⌉\left\lceil\frac n1\right\rceil+\left\lceil\frac n2\right\rceil+\left\lceil\frac n3\right\rceil+\cdots+\left\lceil\frac nn\right\rceilхода.
РешениеКамъните са неразличими, но за доказателството ще ги номерираме с числата 1,2,…,n1,2,\ldots,n. На всеки ход, след като Сизиф избере поле, ще смятаме, че от това поле се премества камъкът с най-голям номер. Да разгледаме камък с номер kk. Когато той бъде преместен от някое поле, в това поле няма камък с номер по-голям от kk, защото по правилото бихме преместили него вместо камък kk. Следователно в избраното поле има най-много kk камъка, а значи камък kk се премества с най-много kk полета на такъв ход. Камък kk трябва общо да измине разстояние nn, от поле 00 до поле nn. Понеже на всеки свой ход той се измества с най-много kk полета, той трябва да бъде местен поне ⌈n/k⌉\left\lceil n/k\right\rceil пъти. Сумирайки това за k=1,2,…,nk=1,2,\ldots,n, получаваме исканата долна граница за общия брой ходове.
Отвори задачатаMathNetISL 2018 C3Условие — източник

Задача C4

Пълен запис
Условие
Анти-Паскалова пирамида е краен набор от числа, поставени в триъгълна таблица така, че първият ред съдържа едно число, вторият ред съдържа две числа, третият ред съдържа три числа и т.н.; освен числата на най-долния ред, всяко число е равно на абсолютната стойност на разликата на двете числа под него. Например42657183109\begin{array}{c} 4\cr 2\quad6\cr 5\quad7\quad1\cr 8\quad3\quad10\quad9 \end{array}е анти-Паскалова пирамида с четири реда, в която всяко цяло число от 11 до 1+2+3+4=101+2+3+4=10 се среща точно веднъж. Възможно ли е да се образува анти-Паскалова пирамида с 20182018 реда, като се използва всяко цяло число от 11 до 1+2+⋯+20181+2+\cdots+2018 точно веднъж?
РешениеОтговорът е: не. Ще разгледаме по-общо анти-Паскалова пирамида TT с nn реда, в която са използвани точно числата от 11 до 1+2+⋯+n1+2+\cdots+n. Нека най-горното число е a1a_1. От двете числа под него едното означаваме с a2a_2, а другото с b2=a1+a2b_2=a_1+a_2; това е възможно, защото числата са положителни и a1=∣b2−a2∣a_1=|b_2-a_2|. После под b2b_2 избираме съседа a3a_3 така, че другият съсед да е b3=a1+a2+a3b_3=a_1+a_2+a_3. Продължаваме така до най-долния ред и получаваме числаa1,a2,…,ana_1,a_2,\ldots,a_nиbi=a1+a2+⋯+ai(2≤i≤n).b_i=a_1+a_2+\cdots+a_i\qquad(2\le i\le n).Числата a1,a2,…,ana_1,a_2,\ldots,a_n са различни положителни цели числа, а сумата им е bnb_n, което е число от пирамидата и следователно не надминава 1+2+⋯+n1+2+\cdots+n. Минималната възможна сума на nn различни положителни цели числа е 1+2+⋯+n1+2+\cdots+n, затова a1,a2,…,ana_1,a_2,\ldots,a_n са точно числата 1,2,…,n1,2,\ldots,n в някакъв ред. Сега гледаме двата триъгълни подмасива, които в долния ред лежат съответно вляво и вдясно от двойката an,bna_n,b_n. Поне един от тях има странаℓ≥⌈n−22⌉.\ell\ge\left\lceil\frac{n-2}{2}\right\rceil.Нека този подмасив е T′T'. В него можем да повторим същото построение: има различни положителни числа a1′,a2′,…,aℓ′a'_1,a'_2,\ldots,a'_{\ell}, за които съответното крайно число еbℓ′=a1′+a2′+⋯+aℓ′.b'_{\ell}=a'_1+a'_2+\cdots+a'_{\ell}.Тъй като числата a1,a2,…,ana_1,a_2,\ldots,a_n вече са точно 1,2,…,n1,2,\ldots,n и лежат извън T′T', всяко от числата a1′,…,aℓ′a'_1,\ldots,a'_{\ell} е по-голямо от nn. Следователноbℓ′≥b'_{\ell}\ge(n+1)+(n+2)+⋯+(n+ℓ)=ℓ(2n+ℓ+1)2.(n+1)+(n+2)+\cdots+(n+\ell)=\frac{\ell(2n+\ell+1)}2.За n=2018n=2018 имаме ℓ≥1008\ell\ge1008, откъдетоbℓ′≥1008(2⋅2018+1008+1)2=2542680.b'_{\ell}\ge\frac{1008(2\cdot2018+1008+1)}2=2542680.Но най-голямото позволено число в пирамидата е1+2+⋯+2018=2018⋅20192=2037171,1+2+\cdots+2018=\frac{2018\cdot2019}{2}=2037171,което е по-малко. Полученото противоречие показва, че такава анти-Паскалова пирамида с 20182018 реда не съществува.
Отвори задачатаMathNetISL 2018 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека kk е положително цяло число. Организационният комитет на тенис турнир трябва да изготви програма за 2k2k играчи така, че всеки двама играчи да играят по един път, всеки ден да се играе точно един мач, а всеки играч да пристига на мястото на турнира в деня на първия си мач и да си тръгва в деня на последния си мач. За всеки ден, в който даден играч присъства на турнира, комитетът плаща 11 монета на хотела. Организаторите искат да направят програмата така, че общата цена за престоя на всички играчи да е минимална. Определете тази минимална цена.
РешениеМинималната цена еk(4k2+k−1)2.\frac{k(4k^2+k-1)}2.Нека дните на турнира са номерирани от 11 до (2k2)\binom{2k}{2}. Некаb1≤b2≤⋯≤b2kb_1\le b_2\le\cdots\le b_{2k}са дните на пристигане на играчите, подредени във възходящ ред, аe1≥e2≥⋯≥e2ke_1\ge e_2\ge\cdots\ge e_{2k}са дните на заминаване, подредени в низходящ ред. Ако даден играч пристига на ден bb и заминава на ден ee, цената за него е e−b+1e-b+1, затова общата цена еΣ=∑i=12k(ei−bi+1).(1)\Sigma=\sum_{i=1}^{2k}(e_i-b_i+1).\tag{1}Ще оценим отдолу всяко ei+1−bi+1+1e_{i+1}-b_{i+1}+1, където 0≤i≤2k−10\le i\le2k-1. Преди ден bi+1b_{i+1} присъстват най-много ii играчи, така че могат да са изиграни най-много (i2)\binom i2 мача. Следователноbi+1≤(i2)+1.b_{i+1}\le\binom i2+1.По същия начин след ден ei+1e_{i+1} присъстват най-много ii играчи, така че след този ден могат да останат най-много (i2)\binom i2 мача. Значиei+1≥(2k2)−(i2).e_{i+1}\ge\binom{2k}{2}-\binom i2.Получавамеei+1−bi+1+1≥e_{i+1}-b_{i+1}+1\ge(2k2)−2(i2)=k(2k−1)−i(i−1).(2)\binom{2k}{2}-2\binom i2=k(2k-1)-i(i-1).\tag{2}За i>ki\gt{}k тази оценка може да се подобри. Разглеждаме първите ii пристигнали играчи и последните ii заминали играчи. Поне 2i−2k2i-2k играчи принадлежат и на двата списъка. Мачовете между тези общи играчи са отчетени два пъти в предходното броене, въпреки че всяка двойка е играла само веднъж. Затова за i>ki\gt{}k имамеei+1−bi+1+1≥e_{i+1}-b_{i+1}+1\ge(2k2)−2(i2)+(2i−2k2)=(2k−i)2.(3)\binom{2k}{2}-2\binom i2+\binom{2i-2k}{2}=(2k-i)^2.\tag{3}Сега ще опишем програма, в която всички тези оценки се достигат. Разделяме играчите на две групиX={S1,S2,…,Sk},Y={T1,T2,…,Tk}.X=\{S_1,S_2,\ldots,S_k\},\qquad Y=\{T_1,T_2,\ldots,T_k\}.В първата част играчите от XX пристигат един по един; всеки новопристигнал веднага играе с всички вече присъстващи играчи от XX. В последната част, след като всички играчи от XX вече са си тръгнали, играчите от YY си тръгват един по един; всеки играе с всички все още присъстващи играчи от YY непосредствено преди заминаването си. В средната част се играят всички мачове между XX и YY. Играчите T1,T2,…,TkT_1,T_2,\ldots,T_k пристигат в този ред; след пристигането на TjT_j той веднага играе с всички SiS_i за i>ji\gt{}j. После играчите Sk,Sk−1,…,S1S_k,S_{k-1},\ldots,S_1 си тръгват в този ред; всеки SiS_i играе с всички TjT_j за i≤ji\le j непосредствено преди заминаването си, като SkS_k си тръгва в деня, в който пристига TkT_k. Тази програма прави равенство в (2) за всички i≤ki\le k: преди пристигането на (i+1)(i+1)-вия играч са изиграни точно (i2)\binom i2 мача от първата част, а след заминаването на (i+1)(i+1)-вия от края остават точно (i2)\binom i2 мача от последната част. За i>ki\gt{}k също има равенство в (3). Наистина, ако i=k+si=k+s с 1≤s≤k−11\le s\le k-1, то между пристигането на Ts+1T_{s+1} и заминаването на Ss+1S_{s+1} се играят точно∑j=s+1k−1(k−j)+1+∑j=s+1k−1(k−j+1)=\sum_{j=s+1}^{k-1}(k-j)+1+\sum_{j=s+1}^{k-1}(k-j+1)=(k−s)2=(2k−i)2(k-s)^2=(2k-i)^2мача, както изисква (3). Следователно минималната цена е сумата на достигнатите долни граници:Σ=\Sigma=∑i=0k(k(2k−1)−i(i−1))\sum_{i=0}^{k}\bigl(k(2k-1)-i(i-1)\bigr)+∑i=k+12k−1(2k−i)2.+\sum_{i=k+1}^{2k-1}(2k-i)^2.Оценяваме тази сума:Σ=\Sigma=(k+1)k(2k−1)−∑i=0ki(i−1)+∑j=1k−1j2=(k+1)k(2k-1)-\sum_{i=0}^{k}i(i-1)+\sum_{j=1}^{k-1}j^2=k(4k2+k−1)2.\frac{k(4k^2+k-1)}2.Това доказва както долната граница, така и достижимостта и следователно дава търсения минимум.
Отвори задачатаMathNetISL 2018 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека aa и bb са различни положителни цели числа. Следният безкраен процес се извършва върху първоначално празна дъска. (i) Ако върху дъската има поне една двойка равни числа, избираме такава двойка и увеличаваме едното от числата с aa, а другото с bb. (ii) Ако няма такава двойка, записваме два пъти числото 00. Докажете, че независимо от изборите в (i), операция (ii) ще бъде извършена само краен брой пъти.
РешениеМожем да приемем, че gcd⁡(a,b)=1\gcd(a,b)=1, защото иначе всички числа върху дъската остават кратни на d=gcd⁡(a,b)d=\gcd(a,b) и можем да разделим целия процес на dd. Нека след NN операции от тип (ii) и някакъв брой операции от тип (i) отново се налага да добавим две нули. За всяко цяло число rr означаваме с f(r)f(r) броя пъти, в които числото rr се е появило върху дъската до този момент. Тогава f(0)=2Nf(0)=2N и f(r)=0f(r)=0 за r<0r\lt{}0. За r>0r\gt{}0 всяка поява на rr е получена или от двойка числа r−ar-a, или от двойка числа r−br-b. В момента няма две равни числа върху дъската, затова от всяка двойка появи на r−ar-a е получена по една поява на rr, и аналогично за r−br-b. Следователноf(r)=⌊f(r−a)2⌋+⌊f(r−b)2⌋,f(r)=\left\lfloor\frac{f(r-a)}2\right\rfloor+\left\lfloor\frac{f(r-b)}2\right\rfloor,а оттукf(r)≥f(r−a)+f(r−b)2−1.(1)f(r)\ge\frac{f(r-a)+f(r-b)}2-1.\tag{1}Понеже gcd⁡(a,b)=1\gcd(a,b)=1, всяко цяло число, по-голямо от ab−a−bab-a-b, може да се представи във вида sa+tbsa+tb с неотрицателни цели s,ts,t. Ще докажем с индукция по s+ts+t, че ако x=sa+tbx=sa+tb, тоf(x)>f(0)2s+t−2.(2)f(x)\gt{}\frac{f(0)}{2^{s+t}}-2.\tag{2}За s+t=0s+t=0 това е ясно. Ако s+t>0s+t\gt{}0, поне едно от s,ts,t е положително; например s>0s\gt{}0. Тогава от (1) и индукционното предположение получавамеf(sa+tb)≥f((s−1)a+tb)2−1>f(sa+tb)\ge\frac{f((s-1)a+tb)}2-1\gt{}12(f(0)2s+t−1−2)−1=f(0)2s+t−2.\frac12\left(\frac{f(0)}{2^{s+t-1}}-2\right)-1=\frac{f(0)}{2^{s+t}}-2.Да допуснем, че операция (ii) се извършва безкрайно много пъти. Нека без ограничение b>ab\gt{}a и положим q=ab−a−bq=ab-a-b. След достатъчно много операции от тип (ii) имаме f(0)f(0) толкова голямо, че от (2) следваf(q+r)≥2(r=1,2,…,b),f(q+r)\ge2\qquad(r=1,2,\ldots,b),защото всяко от числата q+1,q+2,…,q+bq+1,q+2,\ldots,q+b има представяне sa+tbsa+tb с 0≤s≤b0\le s\le b и 0≤t≤a0\le t\le a. Ще покажем, че тогава f(q+r)≥2f(q+r)\ge2 за всяко r≥1r\ge1, което е невъзможно след краен брой ходове. Вече го знаем за 1≤r≤b1\le r\le b. Ако r>br\gt{}b, то q+r−aq+r-a и q+r−bq+r-b са сред предходните числа от вида q+r′q+r' с r′≥1r'\ge1. По индукция те имат поне две появи, така че от точната формулаf(q+r)=⌊f(q+r−a)2⌋+⌊f(q+r−b)2⌋f(q+r)=\left\lfloor\frac{f(q+r-a)}2\right\rfloor+\left\lfloor\frac{f(q+r-b)}2\right\rfloorполучаваме f(q+r)≥1+1=2f(q+r)\ge1+1=2. Така функцията ff би имала ненулеви стойности в безкрайно много точки след краен брой операции, което е невъзможно. Следователно операция (ii) се извършва само краен брой пъти.
Отвори задачатаMathNetISL 2018 C6Условие — източник

Задача C7

Пълен запис
Условие
Разглеждаме 20182018 окръжности, всеки две от които се пресичат, и никои три от които не минават през една и съща точка. Тези окръжности разделят равнината на области, ограничени от дъгови ребра, които се срещат във върхове. Забележете, че върху всяка окръжност има четен брой върхове. За всяка окръжност оцветяваме върховете върху нея последователно в червено и синьо. Така всеки връх получава два цвята, по един от всяка от двете окръжности, които се пресичат в него. Ако двете оцветявания съвпадат в даден връх, той получава този цвят; иначе става жълт. Докажете, че ако някоя окръжност съдържа поне 20612061 жълти точки, то върховете на някоя област са всички жълти.
РешениеЩе докажем по-силно твърдение. Нека броят на окръжностите е n=2018n=2018. Ако няма област, чиито върхове са всички жълти, то всяка окръжност съдържа най-многоn+⌊x2n−2⌋−2=2018+44−2=2060n+\left\lfloor\sqrt{\vphantom{x^2}n-2}\right\rfloor-2=2018+44-2=2060жълти точки. Това ще противоречи на условието. Първо ще използваме две леми. Лема 1. Ако две окръжности се пресичат в точките xx и yy, то xx и yy са или и двете жълти, или и двете нежълти. Доказателство. Двете точки xx и yy разделят всяка от двете окръжности на две дъги. Всяка друга окръжност пресича затворения контур, съставен от една дъга на първата окръжност и една дъга на втората, четен брой пъти; тъй като няма три окръжности през една точка, броевете на вътрешните върхове по съответните две дъги имат еднаква четност. Затова съгласуваността на двата цвята при xx е същата като съгласуваността при yy. Значи двете точки са от един и същи тип: жълти или нежълти. Лема 2. Нека три различни окръжности се пресичат по двойки в точките x,y,zx,y,z, като трите избрани дъги xx до yy, yy до zz и zz до xx образуват затворен контур. Тогава сред x,y,zx,y,z има нечетен брой жълти точки. Доказателство. Нека окръжностите са C1,C2,C3C_1,C_2,C_3, като xx лежи на C2C_2 и C3C_3, yy лежи на C3C_3 и C1C_1, а zz лежи на C1C_1 и C2C_2. Нека k1,k2,k3k_1,k_2,k_3 са броевете вътрешни върхове по трите разглеждани дъги. Всяка друга окръжност пресича затворения контур четен брой пъти, а самопресичанията на контура се броят два пъти, затова k1+k2+k3k_1+k_2+k_3 е четно. Да означим с Z1Z_1 цвета, който точката zz получава от C1C_1, и аналогично да означим цветовете Y1,X2,Z2,Y3,X3Y_1,X_2,Z_2,Y_3,X_3. От четността на k1+k2+k3k_1+k_2+k_3 следва, че броят на смените на цвят в двойките (Z1,Y1)(Z_1,Y_1), (X2,Z2)(X_2,Z_2), (Y3,X3)(Y_3,X_3) е нечетен. Общият брой смени на цвят по цикълаZ1−Y1−Y3−X3−X2−Z2−Z1Z_1-Y_1-Y_3-X_3-X_2-Z_2-Z_1е четен, следователно броят на смените в двойките (X2,X3)(X_2,X_3), (Y1,Y3)(Y_1,Y_3), (Z1,Z2)(Z_1,Z_2) е нечетен. Точно тези смени означават, че съответните точки x,y,zx,y,z са жълти. Лемата е доказана. От лемите следва, че окръжностите се разделят на два класа. Фиксираме една окръжност CC. В първия клас поставяме CC и всички окръжности, които пресичат CC в жълти точки; във втория клас поставяме останалите окръжности. По лема 2 две окръжности от един и същи клас се пресичат в жълти точки, а две окръжности от различни класове се пресичат в нежълти точки. Нека тези класове имат съответно ww и bb окръжности, като w≥bw\ge b и w+b=nw+b=n. Да допуснем, че няма област с всички върхове жълти. Тогава b≥1b\ge1, иначе всички окръжности са в един клас и всички върхове са жълти. Окръжностите от по-големия клас разделят равнината наw(w−1)+2w(w-1)+2по-големи области. Всички върхове по границите на тези области са жълти, защото са пресичания на две окръжности от същия клас. Понеже няма изцяло жълта област, всяка от тези по-големи области съдържа поне една дъга от окръжност от другия клас. Окръжностите от втория клас се разделят от границите на по-големите области на общо 2wb2wb дъги. Нека tit_i е броят на такива дъги в ii-тата по-голяма област. Тогава∑iti=2wb.\sum_i t_i=2wb.В една такава област, ако има tt дъги от втория клас, броят на техните точки на пресичане е най-много t−1t-1. Наистина, ако построим мултиграф с върхове тези tt дъги и ребро за всяка тяхна точка на пресичане, повече от t−1t-1 ребра биха дали цикъл. Този цикъл би съответствал на затворен контур от дъги на окръжности от втория клас и би оградил област, чиито върхове са жълти, против допускането. Всички пресичания на две окръжности от втория клас са жълти, а броят им е 2(b2)=b(b−1)2\binom b2=b(b-1). От предходния абзац следваb(b−1)≤∑i(ti−1)=2wb−(w(w−1)+2).b(b-1)\le\sum_i(t_i-1)=2wb-\bigl(w(w-1)+2\bigr).Това е еквивалентно на(w−b)2≤w+b−2=n−2.(w-b)^2\le w+b-2=n-2.Понеже w≥bw\ge b, получавамеw−b≤⌊x2n−2⌋.w-b\le\left\lfloor\sqrt{\vphantom{x^2}n-2}\right\rfloor.Всяка окръжност от по-големия клас има жълти точки само при пресичанията си с останалите w−1w-1 окръжности от същия клас, т.е. най-много 2(w−1)2(w-1) жълти точки. Същото важи и за окръжностите от другия клас, понеже b≤wb\le w. Следователно всяка окръжност има най-много2(w−1)=w+b+(w−b)−2≤n+⌊x2n−2⌋−22(w-1)=w+b+(w-b)-2\le n+\left\lfloor\sqrt{\vphantom{x^2}n-2}\right\rfloor-2жълти точки. При n=2018n=2018 това е 20602060, което противоречи на наличието на окръжност с поне 20612061 жълти точки. Следователно някоя област има всички върхове жълти.
Отвори задачатаMathNetISL 2018 C7Условие — източник

Задача N1

Пълен запис
Условие
Да се определят всички наредени двойки (n,k)(n,k) от различни положителни цели числа, за които съществува положително цяло число ss такова, че броят на делителите на snsn е равен на броя на делителите на sksk.
РешениеОтговорът е: всички двойки (n,k)(n,k), за които n∤kn\nmid k и k∤nk\nmid n. Нека d(m)d(m) означава броя на положителните делители на mm. Ако n∣kn\mid k и n≠kn\ne k, то за всяко положително цяло число ss делителите на snsn образуват собствено подмножество на делителите на sksk. Следователно d(sn)<d(sk)d(sn)\lt{}d(sk) и такава двойка не върши работа. Случаят k∣nk\mid n е аналогичен. Нека вече n∤kn\nmid k и k∤nk\nmid n. Нека p1,…,ptp_1,\ldots,p_t са всички прости числа, които делят nknk, и некаn=∏i=1tpiαi,k=∏i=1tpiβi.n=\prod_{i=1}^t p_i^{\alpha_i},\qquad k=\prod_{i=1}^t p_i^{\beta_i}.Ще търсим ss във видаs=∏i=1tpiγi.s=\prod_{i=1}^t p_i^{\gamma_i}.Тогава трябва да изберем неотрицателни цели числа γi\gamma_i така, чеd(sn)d(sk)=\frac{d(sn)}{d(sk)}=∏i=1tαi+γi+1βi+γi+1=1.(1)\prod_{i=1}^t\frac{\alpha_i+\gamma_i+1}{\beta_i+\gamma_i+1}=1.\tag{1}Индексите с αi=βi\alpha_i=\beta_i дават множител 11 и можем да ги пренебрегнем. Ще използваме следната лема. Ако α>β\alpha\gt{}\beta са неотрицателни цели числа, то за всяко цяло число M≥β+1M\ge\beta+1 съществува неотрицателно цяло число γ\gamma, за коетоα+γ+1β+γ+1=1+1M=M+1M.\frac{\alpha+\gamma+1}{\beta+\gamma+1}=1+\frac1M=\frac{M+1}{M}.Наистина, достатъчно е да вземем\gamma=M(\alpha-eta)-(eta+1)\ge0.След преномериране можем да приемем, че αi>βi\alpha_i\gt{}\beta_i за i=1,2,…,ui=1,2,\ldots,u и αi<βi\alpha_i\lt{}\beta_i за i=u+1,…,ti=u+1,\ldots,t. Условията n∤kn\nmid k и k∤nk\nmid n дават 1≤u≤t−11\le u\le t-1. Избираме цяло число XX, по-голямо от всички αi\alpha_i и βi\beta_i. По лемата можем да изберем γi\gamma_i така, чеαi+γi+1βi+γi+1=uX+iuX+i−1\frac{\alpha_i+\gamma_i+1}{\beta_i+\gamma_i+1}=\frac{uX+i}{uX+i-1}\qquad(1≤i≤u),(1\le i\le u),а за i=1,2,…,t−ui=1,2,\ldots,t-u да имамеβu+i+γu+i+1αu+i+γu+i+1=\frac{\beta_{u+i}+\gamma_{u+i}+1}{\alpha_{u+i}+\gamma_{u+i}+1}=(t−u)X+i(t−u)X+i−1.\frac{(t-u)X+i}{(t-u)X+i-1}.Тогава вторите отношения влизат в (1) обърнати и получаваме телескопичноd(sn)d(sk)=\frac{d(sn)}{d(sk)}=∏i=1uuX+iuX+i−1⋅∏i=1t−u(t−u)X+i−1(t−u)X+i=\prod_{i=1}^u\frac{uX+i}{uX+i-1}\cdot\prod_{i=1}^{t-u}\frac{(t-u)X+i-1}{(t-u)X+i}=u(X+1)uX⋅(t−u)X(t−u)(X+1)=1.\frac{u(X+1)}{uX}\cdot\frac{(t-u)X}{(t-u)(X+1)}=1.Следователно за тези и само за тези двойки съществува търсеното ss.
Отвори задачатаMathNetISL 2018 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека n>1n\gt{}1 е положително цяло число. Във всяка клетка на таблица n×nn\times n е записано цяло число. Да предположим, че са изпълнени следните условия: (i) всяко число в таблицата е сравнимо с 11 по модул nn; (ii) сумата на числата във всеки ред, както и сумата на числата във всяка колона, е сравнима с nn по модул n2n^2. Нека RiR_i е произведението на числата в ii-тия ред, а CjC_j е произведението на числата в jj-тата колона. Докажете, че сумите R1+⋯+RnR_1+\cdots+R_n и C1+⋯+CnC_1+\cdots+C_n са сравними по модул n4n^4.
РешениеНека Ai,jA_{i,j} е числото в ii-тия ред и jj-тата колона, а PP е произведението на всички n2n^2 числа в таблицата. Полагамеai,j=Ai,j−1,ri=Ri−1.a_{i,j}=A_{i,j}-1,\qquad r_i=R_i-1.Ще докажем, че∑i=1nRi≡(n−1)+P(modn4).(1)\sum_{i=1}^n R_i\equiv (n-1)+P\pmod {n^4}.\tag{1}Поради симетрията на условията същото твърдение ще важи и за сумата на колонните произведения, откъдето ще следва задачата. От (i) имаме n∣ai,jn\mid a_{i,j} за всички i,ji,j. Затова всяко произведение на поне два от множителите ai,ja_{i,j} се дели на n2n^2. За всеки ред получавамеRi=∏j=1n(1+ai,j)≡R_i=\prod_{j=1}^n(1+a_{i,j})\equiv1+∑j=1nai,j=1−n+∑j=1nAi,j(modn2).1+\sum_{j=1}^n a_{i,j}=1-n+\sum_{j=1}^n A_{i,j}\pmod {n^2}.По (ii) последната сума е сравнима с nn по модул n2n^2, следователноRi≡1(modn2).R_i\equiv1\pmod {n^2}.Тоест n2∣rin^2\mid r_i за всяко ii. Сега разглеждаме произведението на всички редови произведения:P=∏i=1nRi=∏i=1n(1+ri).P=\prod_{i=1}^n R_i=\prod_{i=1}^n(1+r_i).Понеже всяко произведение на поне два от rir_i се дели на n4n^4, имамеP≡1+∑i=1nri(modn4).P\equiv1+\sum_{i=1}^n r_i\pmod {n^4}.Следователно∑i=1nRi=n+∑i=1nri≡\sum_{i=1}^n R_i=n+\sum_{i=1}^n r_i\equivn+(P−1)=(n−1)+P(modn4), n+(P-1)=(n-1)+P\pmod {n^4},което доказва (1). Същото разсъждение по колони дава∑j=1nCj≡(n−1)+P(modn4),\sum_{j=1}^n C_j\equiv(n-1)+P\pmod {n^4},и двете търсени суми са сравними по модул n4n^4.
Отвори задачатаMathNetISL 2018 N2Условие — източник

Задача N3

Пълен запис
Условие
Дефинираме редицата a0,a1,a2,…a_0,a_1,a_2,\ldots чрезan=2n+2⌊n/2⌋.a_n=2^n+2^{\lfloor n/2\rfloor}.Докажете, че безкрайно много членове на редицата могат да се представят като сума на два или повече различни члена на редицата, и също така безкрайно много членове не могат да се представят по такъв начин.
РешениеЩе наричаме едно неотрицателно цяло число представимо, ако е сума на някакво подмножество от членовете на редицата, като засега допускаме и празна сума или единствен член. Казваме, че две неотрицателни цели числа bb и cc са еквивалентни, и пишем b∼cb\sim c, ако са едновременно представими или едновременно непредставими. НекаSn−1=a0+a1+⋯+an−1.S_{n-1}=a_0+a_1+\cdots+a_{n-1}.Лесно се проверява по индукция, чеSn−1=2n+2⌈n/2⌉+2⌊n/2⌋−3.S_{n-1}=2^n+2^{\lceil n/2\rceil}+2^{\lfloor n/2\rfloor}-3.За n≥3n\ge3 имамеSn−1>an,Sn−1−an=2⌈n/2⌉−3<an.S_{n-1}\gt{}a_n,\qquad S_{n-1}-a_n=2^{\lceil n/2\rceil}-3\lt{}a_n.Първо, ако Sn−1−an<b<anS_{n-1}-a_n\lt{}b\lt{}a_n за някое n≥3n\ge3, тоb∼Sn−1−b.b\sim S_{n-1}-b.Наистина, всяко представяне на bb използва само членове измежду a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1}, защото b<anb\lt{}a_n. Тогава допълнителното подмножество от тези nn члена има сума Sn−1−bS_{n-1}-b. Обратната посока е същата. Второ, за n≥3n\ge3 членът ana_n е представим като сума на два или повече различни по-малки члена на редицата тогава и само тогава, когатоSn−1−an=2⌈n/2⌉−3S_{n-1}-a_n=2^{\lceil n/2\rceil}-3е представимо число. Ако ana_n е сума на някои от a0,…,an−1a_0,\ldots,a_{n-1}, допълнението им има горната сума. Обратно, представяне на това число чрез членове от a0,…,an−1a_0,\ldots,a_{n-1} дава чрез допълнение представяне на ana_n; то съдържа поне два члена, защото нито един по-малък член сам не е равен на ana_n. Остава да намерим безкрайно много представими и безкрайно много непредставими числа от вида 2t−32^t-3. Ще докажем, че за всяко t≥3t\ge32t−3∼24t−6−3,2^t-3\sim 2^{4t-6}-3,като второто число е по-голямо от първото. Прилагаме предното твърдение за еквивалентност два пъти. Първо,S2t−3−a2t−2=2t−1−3<2t−3<a2t−2,S_{2t-3}-a_{2t-2}=2^{t-1}-3\lt{}2^t-3\lt{}a_{2t-2},следователно2t−3∼S2t−3−(2t−3)=22t−2.2^t-3\sim S_{2t-3}-(2^t-3)=2^{2t-2}.Второ,S4t−7−a4t−6=22t−3−3<22t−2<a4t−6,S_{4t-7}-a_{4t-6}=2^{2t-3}-3\lt{}2^{2t-2}\lt{}a_{4t-6},следователно22t−2∼S4t−7−22t−2=24t−6−3.2^{2t-2}\sim S_{4t-7}-2^{2t-2}=2^{4t-6}-3.Така твърдението е доказано. Числото 23−3=52^3-3=5 е представимо, защото 5=a0+a15=a_0+a_1. Затова рекурсията t↦4t−6t\mapsto4t-6 дава безкрайна редица от представими числа23−3∼26−3∼218−3∼⋯ .2^3-3\sim2^6-3\sim2^{18}-3\sim\cdots.От друга страна, 27−3=1252^7-3=125 не е представимо. Наистина,125∼S6−125=24∼S4−24=17∼S3−17=4,125\sim S_6-125=24\sim S_4-24=17\sim S_3-17=4,а 44 очевидно не е представимо, тъй като първите членове са 2,3,6,…2,3,6,\ldots. Следователно същата рекурсия дава безкрайна редица от непредставими числа27−3∼222−3∼282−3∼⋯ .2^7-3\sim2^{22}-3\sim2^{82}-3\sim\cdots.Накрая, за всяко такова tt вземаме например n=2t−1n=2t-1. Тогава ⌈n/2⌉=t\lceil n/2\rceil=t, а вече доказаната връзка показва, че ana_n е представим в искания смисъл точно когато 2t−32^t-3 е представимо. Получаваме безкрайно много представими и безкрайно много непредставими членове на редицата.
Отвори задачатаMathNetISL 2018 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека a1,a2,…,an,…a_1,a_2,\ldots,a_n,\ldots е редица от положителни цели числа такава, чеa1a2+a2a3+⋯+an−1an+ana1\frac{a_1}{a_2}+\frac{a_2}{a_3}+\cdots+\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}е цяло число за всяко n≥kn\ge k, където kk е някое положително цяло число. Докажете, че съществува положително цяло число mm, за което an=an+1a_n=a_{n+1} за всяко n≥mn\ge m.
РешениеЩе използваме две прости наблюдения. Нека a,b,ca,b,c са положителни цели числа иN=bc+c−baN=\frac bc+\frac{c-b}{a}е цяло число. (1) Ако gcd⁡(a,c)=1\gcd(a,c)=1, то c∣bc\mid b. Наистина, от равенството получавамеab=c(aN+b−c),ab=c(aN+b-c),и понеже aa и cc са взаимнопрости, следва c∣bc\mid b. (2) Ако gcd⁡(a,b,c)=1\gcd(a,b,c)=1, то gcd⁡(a,b)=1\gcd(a,b)=1. От същото равенство следваc2−bc=a(cN−b).c^2-bc=a(cN-b).Ако d=gcd⁡(a,b)d=\gcd(a,b), то d∣c2d\mid c^2. Но dd е взаимнопросто с cc, понеже gcd⁡(a,b,c)=1\gcd(a,b,c)=1, следователно d=1d=1. Некаsn=a1a2+a2a3+⋯+an−1an+ana1.s_n=\frac{a_1}{a_2}+\frac{a_2}{a_3}+\cdots+\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}.За n≥kn\ge k числотоsn+1−sn=anan+1+an+1−ana1s_{n+1}-s_n=\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1}е цяло. Полагамеδn=gcd⁡(a1,an,an+1).\delta_n=\gcd(a_1,a_n,a_{n+1}).Тогаваsn+1−sn=s_{n+1}-s_n=an/δnan+1/δn+an+1/δn−an/δna1/δn.\frac{a_n/\delta_n}{a_{n+1}/\delta_n}+\frac{a_{n+1}/\delta_n-a_n/\delta_n}{a_1/\delta_n}.Понежеgcd⁡(a1δn,anδn,an+1δn)=1,\gcd\left(\frac{a_1}{\delta_n},\frac{a_n}{\delta_n},\frac{a_{n+1}}{\delta_n}\right)=1,от (2) следваgcd⁡(a1δn,anδn)=1.\gcd\left(\frac{a_1}{\delta_n},\frac{a_n}{\delta_n}\right)=1.Ако dn=gcd⁡(a1,an)d_n=\gcd(a_1,a_n), то оттук получаваме dn=δnd_n=\delta_n, следователно dn∣an+1d_n\mid a_{n+1} и значи dn∣dn+1d_n\mid d_{n+1}. И така, от някой индекс нататък числата dnd_n образуват ненамаляваща по делимост редица от делители на фиксираното число a1a_1. Затова съществуват ℓ\ell и dd, за коитоdn=d(n≥ℓ).d_n=d\qquad(n\ge\ell).За n≥ℓn\ge\ell имаме същоgcd⁡(a1d,an+1d)=1.\gcd\left(\frac{a_1}{d},\frac{a_{n+1}}d\right)=1.Прилагайки (1) къмan/dan+1/d+an+1/d−an/da1/d,\frac{a_n/d}{a_{n+1}/d}+\frac{a_{n+1}/d-a_n/d}{a_1/d},получавамеan+1d∣and.\frac{a_{n+1}}d\mid\frac{a_n}d.Следователно an+1≤ana_{n+1}\le a_n за всяко n≥ℓn\ge\ell. Опашката на редицата е невъзрастваща редица от положителни цели числа, затова от някой член нататък е константна. Това означава, че съществува mm, за което an=an+1a_n=a_{n+1} за всяко n≥mn\ge m.
Отвори задачатаMathNetISL 2018 N4Условие — източник

Задача N5

Пълен запис
Условие
Четири положителни цели числа x,y,z,tx,y,z,t удовлетворяват равенстватаxy−zt=x+y=z+t.xy-zt=x+y=z+t.Възможно ли е и xyxy, и ztzt да са точни квадрати?
РешениеОтговорът е: не. Да допуснем противното. Некаxy=a2,zt=c2,xy=a^2,\qquad zt=c^2,където a,ca,c са положителни цели числа. Ако x+y=z+tx+y=z+t е нечетно, то xx и yy са с различна четност, както и zz и tt. Тогава xyxy и ztzt са четни, следователно xy−ztxy-zt е четно, което противоречи на xy−zt=x+yxy-zt=x+y. Значи x+yx+y е четно иs=x+y2=z+t2s=\frac{x+y}{2}=\frac{z+t}{2}е положително цяло число. Полагамеb=∣x−y∣2,d=∣z−t∣2.b=\frac{|x-y|}{2},\qquad d=\frac{|z-t|}{2}.Тогаваs2=a2+b2=c2+d2(1)s^2=a^2+b^2=c^2+d^2\tag{1}и2s=a2−c2=d2−b2.(2)2s=a^2-c^2=d^2-b^2.\tag{2}От (2) следва, че a>0a\gt{}0 и d>0d\gt{}0. Ще използваме само (1), (2), както и факта, че a,d,sa,d,s са положителни цели числа, а b,cb,c са неотрицателни цели числа. Равенствата са симетрични при едновременната размяна a↔da\leftrightarrow d и b↔cb\leftrightarrow c, така че без ограничение приемаме b≥cb\ge c. Тогава b>0b\gt{}0 и от (2) имаме d2=b2+2s>c2d^2=b^2+2s\gt{}c^2, откъдетоd2>c2+d22=s22.(3)d^2\gt{}\frac{c^2+d^2}{2}=\frac{s^2}{2}.\tag{3}От (2) числата bb и dd са с еднаква четност. Понеже 0<b<d0\lt{}b\lt{}d, получаваме b≤d−2b\le d-2. Следователно2s=d2−b2≥d2−(d−2)2=4(d−1),2s=d^2-b^2\ge d^2-(d-2)^2=4(d-1),тоестd≤s2+1.(4)d\le\frac s2+1.\tag{4}От (3) и (4) следва2s2<4d2≤4(s2+1)2,2s^2\lt{}4d^2\le4\left(\frac s2+1\right)^2,или(s−2)2<8.(s-2)^2\lt{}8.Значи s≤4s\le4. За 1≤s≤41\le s\le4 числото s2s^2 има единствено представяне като сума на два квадрата на неотрицателни цели числа, а именно s2=s2+02s^2=s^2+0^2. От (1), понеже a>0a\gt{}0 и d>0d\gt{}0, следва едновременно b=0b=0 и c=0c=0, което е невъзможно, защото c2=zt>0c^2=zt\gt{}0. Полученото противоречие доказва отговора.
Отвори задачатаMathNetISL 2018 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека f:{1,2,3,…}→{2,3,…}f:\{1,2,3,\ldots\}\to\{2,3,\ldots\} е функция такава, чеf(m+n)∣f(m)+f(n)f(m+n)\mid f(m)+f(n)за всички двойки положителни цели числа m,nm,n. Докажете, че съществува положително цяло число c>1c\gt{}1, което дели всички стойности на ff.
РешениеЗа всяко положително цяло число mm дефинирамеSm={n:m∣f(n)}.S_m=\{n:m\mid f(n)\}.Ще ни трябва следната лема. Ако SmS_m е безкрайно множество, тоSm=d⋅Z>0={d,2d,3d,…}S_m=d\cdot\mathbb Z_{\gt{}0}=\{d,2d,3d,\ldots\}за някое положително цяло число dd. Нека d=min⁡Smd=\min S_m. Ако n∈Smn\in S_m и n>dn\gt{}d, то от условиетоf(n)∣f(n−d)+f(d).f(n)\mid f(n-d)+f(d).Понеже mm дели и f(n)f(n), и f(d)f(d), получаваме m∣f(n−d)m\mid f(n-d), т.е. n−d∈Smn-d\in S_m. Повтаряйки това, стигаме до положителния остатък на nn по модул dd; по минималността на dd този остатък трябва да е dd. Значи d∣nd\mid n за всяко n∈Smn\in S_m. Понеже SmS_m е безкрайно, от достатъчно голям негов елемент можем да слизаме през стъпки dd и така получаваме всички положителни кратни на dd. Лемата е доказана. Разглеждаме два случая. Първи случай: функцията ff е ограничена. Наричаме просто число pp често, ако SpS_p е безкрайно, и рядко в противен случай. Тъй като ff е ограничена, само краен брой прости числа делят поне една стойност на ff. Следователно има само краен брой индекси nn, за които f(n)f(n) има рядък прост делител. Избираме NN, по-голямо от всички тези индекси. Нека p1,…,pkp_1,\ldots,p_k са честите прости числа. По лематаSpi=di⋅Z>0S_{p_i}=d_i\cdot\mathbb Z_{\gt{}0}за някакви положителни цели числа did_i. Разглеждамеn=Nd1d2⋯dk+1.n=Nd_1d_2\cdots d_k+1.Понеже n>Nn\gt{}N, всички прости делители на f(n)f(n) са чести. Нека pip_i е такъв делител. Тогава n∈Spin\in S_{p_i}, следователно di∣nd_i\mid n. Но n≡1(moddi)n\equiv1\pmod {d_i}, откъдето di=1d_i=1. Значи Spi=Z>0S_{p_i}=\mathbb Z_{\gt{}0} и pip_i дели всички стойности на ff. Втори случай: функцията ff не е ограничена. Ще докажем, че f(1)f(1) дели всички стойности на ff. Нека a=f(1)a=f(1). Тъй като 1∈Sa1\in S_a, по лемата е достатъчно да докажем, че SaS_a е безкрайно. Наричаме положително цяло число pp връх, акоf(p)>max⁡(f(1),f(2),…,f(p−1)).f(p)\gt{}\max(f(1),f(2),\ldots,f(p-1)).Понеже ff не е ограничена, върховете са безкрайно много. Нека1=p1<p2<⋯1=p_1\lt{}p_2\lt{}\cdotsса всички върхове и нека hi=f(pi)h_i=f(p_i). Ако pip_i е връх и 1≤q<pi1\le q\lt{}p_i, тоf(pi)∣f(q)+f(pi−q)<2f(pi),f(p_i)\mid f(q)+f(p_i-q)\lt{}2f(p_i),следователноf(q)+f(pi−q)=f(pi)=hi.(1)f(q)+f(p_i-q)=f(p_i)=h_i.\tag{1}По принципа на Дирихле измежду числата h1,h2,…h_1,h_2,\ldots има безкрайно много, които са сравними по модул aa. Нека k0<k1<k2<⋯k_0\lt{}k_1\lt{}k_2\lt{}\cdots са такива индекси, чеhk0≡hk1≡hk2≡⋯(moda).h_{k_0}\equiv h_{k_1}\equiv h_{k_2}\equiv\cdots\pmod a.От (1), приложено към върха pkip_{k_i} и q=pk0q=p_{k_0}, получавамеf(pki−pk0)=f(pki)−f(pk0)=hki−hk0≡0(moda)f(p_{k_i}-p_{k_0})=f(p_{k_i})-f(p_{k_0})=h_{k_i}-h_{k_0}\equiv0\pmod aза всяко i≥1i\ge1. Значи SaS_a е безкрайно. По лемата и факта, че 1∈Sa1\in S_a, следва Sa=Z>0S_a=\mathbb Z_{\gt{}0}. Така a=f(1)a=f(1) дели всички стойности на ff. Понеже f(1)>1f(1)\gt{}1, това дава исканото число cc.
Отвори задачатаMathNetISL 2018 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека n≥2018n\ge2018 е цяло число, а a1,a2,…,an,b1,b2,…,bna_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n са две по две различни положителни цели числа, ненадминаващи 5n5n. Да предположим, че редицатаa1b1,a2b2,…,anbn\frac{a_1}{b_1},\frac{a_2}{b_2},\ldots,\frac{a_n}{b_n}е аритметична прогресия. Докажете, че всички членове на тази редица са равни.
РешениеДа допуснем, че аритметичната прогресия има ненулева разликаΔ=cd,\Delta=\frac cd,където d>0d\gt{}0 и c,dc,d са взаимнопрости цели числа. Ще получим противоречие, като покажем, че твърде много от знаменателите bib_i трябва да се делят на dd. За прост делител pp на dd наричаме индекс ii pp-лош, акоνp(bi)<νp(d).\nu_p(b_i)\lt{}\nu_p(d).Първо ще докажем, че за всяко просто pp всички pp-лоши индекси са сравними по модул pp. Нека α=νp(d)\alpha=\nu_p(d). Ако ii и jj са pp-лоши и i≢j(modp)i\not\equiv j\pmod p, то знаменателят на разликата на дробите ai/bia_i/b_i и aj/bja_j/b_j не може да се дели на pαp^\alpha. Но тази разлика е(i−j)Δ=(i−j)cd,(i-j)\Delta=\frac{(i-j)c}{d},където числителят е взаимнопрост с pp, а знаменателят се дели на pαp^\alpha. Противоречие. Следователно, ако p≥7p\ge7 е прост делител на dd, най-много n/p+1n/p+1 от индексите са pp-лоши. Значи pp дели понеp−1pn−1\frac{p-1}{p}n-1от различните знаменатели b1,…,bnb_1,\ldots,b_n. Най-големият от тези знаменатели е поне(p−1pn−1)p=(p−1)(n−1)−1≥6(n−1)−1>5n,\left(\frac{p-1}{p}n-1\right)p=(p-1)(n-1)-1\ge6(n-1)-1\gt{}5n,което е невъзможно. Значи простите делители на dd са само измежду 2,3,52,3,5. Сега разглеждаме произволни 3030 последователни индекса. Множествата от 22-лоши, 33-лоши и 55-лоши индекси се съдържат съответно в по една аритметична прогресия с разлика 22, 33 и 55. Във всеки блок от 3030 последователни индекса имаφ(30)=(2−1)(3−1)(5−1)=8\varphi(30)=(2-1)(3-1)(5-1)=8индекса, които не попадат в нито една от тези три забранени прогресии. За всеки такъв индекс нито един прост делител на dd не е лош, следователно d∣bid\mid b_i. Така във всеки блок от 3030 последователни индекса поне 88 от знаменателите се делят на dd. Ще оценим и самата разлика. Премахваме всички дроби със знаменател bi<n/2b_i\lt{}n/2. Такива знаменатели са по-малко от n/2n/2, понеже са различни положителни цели числа. Следователно остават поне n/2n/2 дроби. Всяка от тях е положителна и не надминава5nn/2=10.\frac{5n}{n/2}=10.Значи имаме поне n/2n/2 члена на ненулева аритметична прогресия в интервала (0,10](0,10], откъдето∣Δ∣<10n/2−1=20n−2.|\Delta|\lt{}\frac{10}{n/2-1}=\frac{20}{n-2}.Понеже ∣Δ∣=∣c∣/d≥1/d|\Delta|=|c|/d\ge1/d, получавамеd>n−220.(1)d\gt{}\frac{n-2}{20}.\tag{1}От предишното броене по блокове има поне 8⌊n/30⌋8\left\lfloor n/30\right\rfloor различни знаменатели, които се делят на dd. Затова най-големият от тях е поне8⌊n30⌋d.8\left\lfloor\frac n{30}\right\rfloor d.С помощта на (1) намираме5n≥8⌊n30⌋d>8(n30−1)n−220>5n,5n\ge8\left\lfloor\frac n{30}\right\rfloor d\gt{}8\left(\frac n{30}-1\right)\frac{n-2}{20}\gt{}5n,където последното неравенство е вярно за n≥2018n\ge2018. Противоречието показва, че разликата на прогресията не може да е ненулева. Следователно всички нейни членове са равни.
Отвори задачатаMathNetISL 2018 N7Условие — източник