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

IMO Shortlisted Problems

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

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

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

2019

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

11-12

24 задачи

Задача A1

Пълен запис
Условие
Нека Z\mathbb Z е множеството на целите числа. Да се намерят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за които за всички цели числа aa и bb е изпълненоf(2a)+2f(b)=f(f(a+b)).f(2a)+2f(b)=f(f(a+b)).
РешениеОтговорът еf(n)=0(n∈Z)f(n)=0\qquad(n\in\mathbb Z)иf(n)=2n+K(n∈Z),f(n)=2n+K\qquad(n\in\mathbb Z),където K∈ZK\in\mathbb Z е произволна константа. Нека K=f(0)K=f(0). При a=0a=0 получавамеf(f(b))=2f(b)+K(1)f(f(b))=2f(b)+K\tag{1}за всяко b∈Zb\in\mathbb Z. При b=0b=0 и използвайки (1), имамеf(2a)+2K=f(f(a))=2f(a)+K,f(2a)+2K=f(f(a))=2f(a)+K,тоестf(2a)=2f(a)−K.(2)f(2a)=2f(a)-K.\tag{2}Сега заместваме (1) и (2) в даденото равенство:2f(a)−K+2f(b)=2f(a+b)+K.2f(a)-K+2f(b)=2f(a+b)+K.Следователноf(a)+f(b)=f(a+b)+K.f(a)+f(b)=f(a+b)+K.Ако положим g(n)=f(n)−Kg(n)=f(n)-K, то g(a+b)=g(a)+g(b)g(a+b)=g(a)+g(b) за всички цели a,ba,b. Оттук по индукция g(n)=Mng(n)=Mn за някое цяло число M=g(1)M=g(1), така чеf(n)=Mn+K.f(n)=Mn+K.Заместваме този вид в първоначалното уравнение. Получаваме2Ma+K+2(Mb+K)=M(M(a+b)+K)+K,2Ma+K+2(Mb+K)=M(M(a+b)+K)+K,или(M−2)(M(a+b)+K)=0(M-2)(M(a+b)+K)=0за всички a,b∈Za,b\in\mathbb Z. Затова или M=2M=2, или M(a+b)+K=0M(a+b)+K=0 за всички a,ba,b, което дава M=K=0M=K=0. Описаните функции се проверяват непосредствено.
Отвори задачатаMathNetISL 2019 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека u1,u2,…,u2019u_1,u_2,\ldots,u_{2019} са реални числа, за коитоu1+u2+⋯+u2019=0иu_1+u_2+\cdots+u_{2019}=0\qquad\text{и}\qquadu12+u22+⋯+u20192=1. u_1^2+u_2^2+\cdots+u_{2019}^2=1.Некаa=min⁡{u1,u2,…,u2019},a=\min\{u_1,u_2,\ldots,u_{2019}\},b=max⁡{u1,u2,…,u2019}.\qquad b=\max\{u_1,u_2,\ldots,u_{2019}\}.Докажете, чеab≤−12019.ab\le -\frac1{2019}.
РешениеПърво a<0<ba\lt{}0\lt{}b, защото числата uiu_i не са всички нули, а сборът им е 00. НекаP={i:ui>0},N={i:ui≤0},P=\{i:u_i\gt{}0\},\qquad N=\{i:u_i\le0\},и нека p=∣P∣p=|P|, n=∣N∣n=|N|. Тогава p+n=2019p+n=2019 и от условието за сбора следва∑i∈Pui=∑i∈N∣ui∣.(1)\sum_{i\in P}u_i=\sum_{i\in N}|u_i|.\tag{1}За положителните членове имаме∑i∈Pui2≤b∑i∈Pui=b∑i∈N∣ui∣≤\sum_{i\in P}u_i^2\le b\sum_{i\in P}u_i=b\sum_{i\in N}|u_i|\lebn∣a∣=−nab.(2) bn|a|=-nab.\tag{2}За неположителните членове аналогично∑i∈Nui2≤∣a∣∑i∈N∣ui∣=∣a∣∑i∈Pui≤\sum_{i\in N}u_i^2\le |a|\sum_{i\in N}|u_i|=|a|\sum_{i\in P}u_i\le∣a∣pb=−pab.(3) |a|pb=-pab.\tag{3}Сумирайки (2) и (3), получаваме1=∑i=12019ui2≤−(p+n)ab=−2019ab.1=\sum_{i=1}^{2019}u_i^2\le -(p+n)ab=-2019ab.Следователно ab≤−1/2019ab\le -1/2019, както се искаше.
Отвори задачатаMathNetISL 2019 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число и нека (a1,a2,…,an)(a_1,a_2,\ldots,a_n) е строго растяща редица от nn положителни реални числа със сбор 22. Нека XX е подмножество на {1,2,…,n}\{1,2,\ldots,n\}, за което стойността на∣1−∑i∈Xai∣\left|1-\sum_{i\in X}a_i\right|е минимална. Докажете, че съществува строго растяща редица от nn положителни реални числа (b1,b2,…,bn)(b_1,b_2,\ldots,b_n) със сбор 22, такава че∑i∈Xbi=1.\sum_{i\in X}b_i=1.
РешениеДа означим с XcX^c допълнението на XX в {1,2,…,n}\{1,2,\ldots,n\}. Понеже сборът на всички aia_i е 22, множествата XX и XcX^c дават една и съща стойност на израза в условието. Ако построим търсената редица за XcX^c, тогава тя работи и за XX, защото общият сбор е 22. Затова можем, ако е нужно, да заменим XX с XcX^c и да предполагаме∑i∈Xai<1;\sum_{i\in X}a_i\lt{}1;случаят на равенство е тривиален с bi=aib_i=a_i. Минимизиращото множество XX не е празно, понеже a1<1a_1\lt{}1 и едноелементното множество {1}\{1\} дава стойност, по-малка от тази на празното множество. ПоложимΔ=∑i∈Xcai−∑i∈Xai>0.\Delta=\sum_{i\in X^c}a_i-\sum_{i\in X}a_i\gt{}0.Тогава ∑i∈Xai=1−Δ/2\sum_{i\in X}a_i=1-\Delta/2. Първо да разгледаме случая, когато съществува j<nj\lt{}n с j∈Xj\in X и j+1∈Xcj+1\in X^c. От минималността следваaj+1−aj≥Δ,a_{j+1}-a_j\ge\Delta,защото иначе замяната на jj с j+1j+1 в XX би дала по-малка стойност на ∣1−∑i∈Xai∣|1-\sum_{i\in X}a_i|. Ако aj+1−aj>Δa_{j+1}-a_j\gt{}\Delta, задавамеbj=aj+Δ2,bj+1=aj+1−Δ2,b_j=a_j+\frac\Delta2,\qquad b_{j+1}=a_{j+1}-\frac\Delta2,а всички останали bib_i оставяме равни на aia_i. Тогава редицата остава строго растяща, общият сбор не се променя, а сборът по индексите от XX се увеличава с Δ/2\Delta/2, тоест става 11. Остава подслучаят aj+1−aj=Δa_{j+1}-a_j=\Delta. Избираме положително ε\varepsilon, по-малко от Δ/2\Delta/2, от a1a_1 и от всички разлики ai+1−aia_{i+1}-a_i. Ако ∣X∣≥2|X|\ge2, избираме k∈Xk\in X, k≠jk\ne j, и полагамеbj=aj+Δ2−ε,b_j=a_j+\frac\Delta2-\varepsilon,bj+1=aj+1−Δ2,bk=ak+ε,\qquad b_{j+1}=a_{j+1}-\frac\Delta2,\qquad b_k=a_k+\varepsilon,като другите членове не се променят. Ако ∣X∣=1|X|=1, тогава ∣Xc∣≥2|X^c|\ge2; избираме k∈Xck\in X^c, k≠j+1k\ne j+1, и полагамеbj=aj+Δ2,bj+1=aj+1−Δ2+ε,b_j=a_j+\frac\Delta2,\qquad b_{j+1}=a_{j+1}-\frac\Delta2+\varepsilon,bk=ak−ε.\qquad b_k=a_k-\varepsilon.И в двата случая изборът на ε\varepsilon запазва положителността и строгото нарастване, общият сбор остава 22, а сборът по XX става 11. Накрая нека няма индекс j<nj\lt{}n с j∈Xj\in X и j+1∈Xcj+1\in X^c. Тогава, понеже XX не е празно, XX е крайна опашка {k,k+1,…,n}\{k,k+1,\ldots,n\} с k>1k\gt{}1. От минималността следва a1>Δ/2a_1\gt{}\Delta/2, защото при a1≤Δ/2a_1\le\Delta/2 добавянето на индекса 11 към XX би намалило Δ\Delta. Сега задавамеb1=a1−Δ2,bn=an+Δ2,b_1=a_1-\frac\Delta2,\qquad b_n=a_n+\frac\Delta2,а останалите членове оставяме непроменени. Получената редица е строго растяща и положителна, сборът й е 22, а сборът на членовете с индекси от XX се увеличава точно с Δ/2\Delta/2 и става 11.
Отвори задачатаMathNetISL 2019 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число и нека a1,a2,…,ana_1,a_2,\ldots,a_n са реални числа, за коитоa1+a2+⋯+an=0.a_1+a_2+\cdots+a_n=0.Да се дефинира множествотоA={(i,j):1≤i<j≤n, ∣ai−aj∣≥1}.A=\{(i,j):1\le i\lt{}j\le n,\ |a_i-a_j|\ge1\}.Докажете, че ако AA не е празно, то∑(i,j)∈Aaiaj<0.\sum_{(i,j)\in A}a_ia_j\lt{}0.
РешениеДа въведем множествата от наредени двойкиB={(i,j):1≤i,j≤n, ∣ai−aj∣≥1},B=\{(i,j):1\le i,j\le n,\ |a_i-a_j|\ge1\},C={(i,j):1≤i,j≤n, ∣ai−aj∣<1}.C=\{(i,j):1\le i,j\le n,\ |a_i-a_j|\lt{}1\}.Тъй като в BB всяка двойка от AA се брои и в двата реда, имаме∑(i,j)∈Aaiaj=12∑(i,j)∈Baiaj.\sum_{(i,j)\in A}a_ia_j=\frac12\sum_{(i,j)\in B}a_ia_j.А понеже ∑iai=0\sum_i a_i=0,∑(i,j)∈Baiaj=−∑(i,j)∈Caiaj.\sum_{(i,j)\in B}a_ia_j=-\sum_{(i,j)\in C}a_ia_j.Достатъчно е да докажем, че при непразно AA е изпълнено∑(i,j)∈Caiaj>0.(1)\sum_{(i,j)\in C}a_ia_j\gt{}0.\tag{1}Разделяме индексите на четири множества:P={i:ai≤−1},Q={i:−1<ai≤0},P=\{i:a_i\le -1\},\quad Q=\{i:-1\lt{}a_i\le0\},R={i:0<ai<1},S={i:1≤ai}.\quad R=\{i:0\lt{}a_i\lt{}1\},\quad S=\{i:1\le a_i\}.В сумата по CC всички положителни членове от∑i∈P∪Sai2+∑i,j∈Q∪Raiaj\sum_{i\in P\cup S}a_i^2+\sum_{i,j\in Q\cup R}a_ia_jприсъстват, а всички отрицателни членове от сумата по CC също са включени в дясната страна. Затова∑(i,j)∈Caiaj≥\sum_{(i,j)\in C}a_ia_j\ge∑i∈P∪Sai2+∑i,j∈Q∪Raiaj= \sum_{i\in P\cup S}a_i^2+\sum_{i,j\in Q\cup R}a_ia_j=∑i∈P∪Sai2+(∑i∈Q∪Rai)2≥\sum_{i\in P\cup S}a_i^2+\left(\sum_{i\in Q\cup R}a_i\right)^2\ge0.0.Ако последното неравенство беше равенство, щеше да е P=S=∅P=S=\emptyset. Ако и първото беше равенство, тогава всички двойки индекси от Q∪RQ\cup R щяха да удовлетворяват ∣ai−aj∣<1|a_i-a_j|\lt{}1, което би означавало A=∅A=\emptyset. Следователно при непразно AA имаме строго неравенство в (1), а оттук∑(i,j)∈Aaiaj=−12∑(i,j)∈Caiaj<0.\sum_{(i,j)\in A}a_ia_j=-\frac12\sum_{(i,j)\in C}a_ia_j\lt{}0.
Отвори задачатаMathNetISL 2019 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека x1,x2,…,xnx_1,x_2,\ldots,x_n са различни реални числа. Докажете, че∑1≤i≤n∏j≠i1−xixjxi−xj={0,ако n е четно,1,ако n е нечетно.\sum_{1\le i\le n}\prod_{j\ne i}\frac{1-x_ix_j}{x_i-x_j}=\begin{cases}0,&\text{ако }n\text{ е четно},\\1,&\text{ако }n\text{ е нечетно}. \end{cases}
РешениеДостатъчно е да докажем тъждеството за случая xi≠±1x_i\ne\pm1, тъй като двете страни са рационални функции на x1,…,xnx_1,\ldots,x_n и после следва по непрекъснатост. НекаF(t)=∏i=1n(1−xit).F(t)=\prod_{i=1}^n(1-x_it).Ще интерполираме FF в точките x1,x2,…,xn,1,−1x_1,x_2,\ldots,x_n,1,-1. Полиномът FF има степен най-много nn, затова коефициентът пред tn+1t^{n+1} в интерполационната формула на Лагранж е 00. При точката xix_i имамеF(xi)=(1−xi2)∏j≠i(1−xixj),F(x_i)=(1-x_i^2)\prod_{j\ne i}(1-x_ix_j),а водещият коефициент на съответния базисен полином е1(xi−1)(xi+1)∏j≠i(xi−xj)=\frac1{(x_i-1)(x_i+1)\prod_{j\ne i}(x_i-x_j)}=−1(1−xi2)∏j≠i(xi−xj).-\frac1{(1-x_i^2)\prod_{j\ne i}(x_i-x_j)}.Затова приносът на всички точки xix_i е−∑1≤i≤n∏j≠i1−xixjxi−xj.-\sum_{1\le i\le n}\prod_{j\ne i}\frac{1-x_ix_j}{x_i-x_j}.При точката 11 приносът еF(1)2∏j=1n(1−xj)=12,\frac{F(1)}{2\prod_{j=1}^n(1-x_j)}=\frac12,а при точката −1-1 приносът еF(−1)(−2)∏j=1n(−1−xj)=(−1)n+12.\frac{F(-1)}{(-2)\prod_{j=1}^n(-1-x_j)}=\frac{(-1)^{n+1}}2.Следователно, ако означим лявата страна с GG, от коефициента пред tn+1t^{n+1} получаваме0=−G+12+(−1)n+12.0=-G+\frac12+\frac{(-1)^{n+1}}2.ТакаG=1+(−1)n+12,G=\frac{1+(-1)^{n+1}}2,което е 00 за четно nn и 11 за нечетно nn.
Отвори задачатаMathNetISL 2019 A5Условие — източник

Задача A6

Пълен запис
Условие
Полином P(x,y,z)P(x,y,z) на три променливи с реални коефициенти удовлетворява тъждестватаP(x,y,z)=P(x,y,xy−z)=P(x,y,z)=P(x,y,xy-z)=P(x,zx−y,z)=P(yz−x,y,z).P(x,zx-y,z)=P(yz-x,y,z).Докажете, че съществува полином F(t)F(t) на една променлива, такъв чеP(x,y,z)=F(x2+y2+z2−xyz).P(x,y,z)=F(x^2+y^2+z^2-xyz).
РешениеНекаQ=x2+y2+z2−xyz.Q=x^2+y^2+z^2-xyz.Първо отбелязваме, че QQ се запазва при трите преобразувания(x,y,z)↦(x,y,xy−z),(x,y,z)\mapsto(x,y,xy-z),(x,y,z)↦(x,zx−y,z),\quad (x,y,z)\mapsto(x,zx-y,z),(x,y,z)↦(yz−x,y,z).\quad (x,y,z)\mapsto(yz-x,y,z).Затова всеки полином от вида F(Q)F(Q) удовлетворява дадените тъждества. Трябва да докажем обратното. Ще използваме две прости наблюдения. Да наречем полином R(x,y,z)R(x,y,z) слабо симетричен по zz, акоR(x,y,z)=R(x,y,xy−z).R(x,y,z)=R(x,y,xy-z).Тогава RR е полином на xx, yy и z(xy−z)z(xy-z). Наистина, ако поставимR1(x,y,t)=R(x,y,t+xy2),R_1(x,y,t)=R\left(x,y,t+\frac{xy}{2}\right),то R1(x,y,t)=R1(x,y,−t)R_1(x,y,t)=R_1(x,y,-t), следователно R1R_1 съдържа само четни степени на tt. Значи RR е полином на xx, yy и\left(z- rac{xy}{2}\right)^2=-z(xy-z)+\frac{x^2y^2}{4},което доказва твърдението. От това представяне следва и следното: ако μxaybzc\mu x^ay^bz^c е едночлен от най-висока обща степен в слабо симетричен по zz полином, то a≥ca\ge c и b≥cb\ge c. Действително, в записR(x,y,z)=∑μijkxiyj(z(xy−z))kR(x,y,z)=\sum\mu_{ijk}x^iy^j\bigl(z(xy-z)\bigr)^kводещите по обща степен членове идват от максималните стойности на i+j+3ki+j+3k и имат вид μijkxi+kyj+kzk\mu_{ijk}x^{i+k}y^{j+k}z^k, без взаимно унищожаване. Сега доказваме задачата с индукция по степента на PP. При степен 00 е ясно. Нека PP е ненулев с положителна степен и удовлетворява всички тъждества. От слаба симетричност по всяка от трите променливи, приложена към водещите едночлени, получаваме едновременноa≥c,b≥c,a≥b,a\ge c,\quad b\ge c,\quad a\ge b,c≥b,b≥a,c≥a.\quad c\ge b,\quad b\ge a,\quad c\ge a.Следователно всеки водещ едночлен има a=b=ca=b=c; значи водещата хомогенна част е само един едночлен μ(xyz)c\mu(xyz)^c. Полиномът QcQ^c има водещ член (−1)c(xyz)c(-1)^c(xyz)^c. Избираме коефициент така, че вP0=P−μ(−1)cQcP_0=P-\mu(-1)^cQ^cводещият едночлен да се унищожи. Понеже QQ е инвариантен, P0P_0 също удовлетворява дадените тъждества и има по-малка степен. По индукционното предположение P0=F0(Q)P_0=F_0(Q) за някакъв полином F0F_0. ТогаваP=F0(Q)+μ(−1)cQc,P=F_0(Q)+\mu(-1)^cQ^c,тоест PP също е полином на QQ. Това завършва доказателството.
Отвори задачатаMathNetISL 2019 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека Z\mathbb Z е множеството на целите числа. Разглеждаме функции f:Z→Zf:\mathbb Z\to\mathbb Z, за коитоf(f(x+y)+y)=f(f(x)+y)f(f(x+y)+y)=f(f(x)+y)за всички цели числа xx и yy. За такава функция ще казваме, че цяло число vv е ff-рядко, ако множествотоXv={x∈Z:f(x)=v}X_v=\{x\in\mathbb Z:f(x)=v\}е крайно и непразно. (a) Докажете, че съществува такава функция ff, за която има ff-рядко цяло число. (b) Докажете, че никоя такава функция ff не може да има повече от едно ff-рядко цяло число.
Решение(a) Определяме f(0)=0f(0)=0, а за x≠0x\ne0 нека f(x)f(x) е най-голямата степен на 22, която дели 2x2x. Тогава X0={0}X_0=\{0\}, така че 00 е ff-рядко число. Остава да проверим уравнението. За всяко xx е вярно f(2x)=2f(x)f(2x)=2f(x). Затова, ако xx и yy са едновременно четни, уравнението се свежда след деление на двойка до същото уравнение за x/2x/2 и y/2y/2. Достатъчно е да разгледаме случая, когато поне едно от x,yx,y е нечетно. Ако yy е нечетно, тогава f(x+y)f(x+y) и f(x)f(x) са четни числа, следователно и f(x+y)+yf(x+y)+y, и f(x)+yf(x)+y са нечетни. За всяко нечетно цяло tt имаме f(t)=2f(t)=2, така че двете страни са равни на 22. Ако yy е четно, а xx е нечетно, тогава x+yx+y е нечетно и f(x+y)=f(x)=2f(x+y)=f(x)=2, откъдето равенството е очевидно. (b) Нека ff е произволна функция, удовлетворяваща уравнението. От него чрез индукция по kk следва, чеf(f(x+ky)+y)=f(f(x)+y)(1)f(f(x+ky)+y)=f(f(x)+y)\tag{1}за всички цели x,y,kx,y,k. Нека vv е ff-рядко число и нека aa и bb са съответно най-малкият и най-големият елемент на крайното непразно множество XvX_v. В (1) поставяме y=a−f(x)y=a-f(x). Получавамеf(f(x+k(a−f(x)))+a−f(x))=f(a)=v,f\bigl(f(x+k(a-f(x)))+a-f(x)\bigr)=f(a)=v,значиf(x+k(a−f(x)))+a−f(x)∈Xv.f(x+k(a-f(x)))+a-f(x)\in X_v.Понеже aa е най-малкият елемент на XvX_v, следваf(x+k(a−f(x)))≥f(x)(2)f(x+k(a-f(x)))\ge f(x)\tag{2}за всички x,kx,k. Аналогично, като поставим y=b−f(x)y=b-f(x) и използваме максималността на bb, получавамеf(x+k(b−f(x)))≤f(x)(3)f(x+k(b-f(x)))\le f(x)\tag{3}за всички x,kx,k. Числотоx+k(a−f(x))(b−f(x))x+k(a-f(x))(b-f(x))лежи едновременно в аритметичната прогресия през xx с разлика a−f(x)a-f(x) и в аритметичната прогресия през xx с разлика b−f(x)b-f(x). От (2) и (3) получавамеf(x+k(a−f(x))(b−f(x)))=f(x)(4)f\bigl(x+k(a-f(x))(b-f(x))\bigr)=f(x)\tag{4}за всички x,kx,k. Ако f(x)≠a,bf(x)\ne a,b, прогресията в (4) е недегенерирана, така че влакното Xf(x)X_{f(x)} е безкрайно. Следователно всяко ff-рядко число трябва да бъде измежду aa и bb. Прилагайки последното твърдение към самото vv, получаваме v∈{a,b}v\in\{a,b\}. Освен това a,b∈Xva,b\in X_v, т.е. f(a)=f(b)=vf(a)=f(b)=v. От друга страна, всяко ff-рядко число ww трябва да бъде фиксирана точка: ако приложим същото разсъждение към ww, то ww е един от крайните елементи на XwX_w, значи f(w)=wf(w)=w. Затова сред числата aa и bb само vv може да бъде ff-рядко. Следователно vv е единственото ff-рядко число.
Отвори задачатаMathNetISL 2019 A7Условие — източник

Задача C1

Пълен запис
Условие
Безкрайната редица a0,a1,a2,…a_0,a_1,a_2,\ldots от цели числа, не непременно различни, има следните свойства: 0≤ai≤i0\le a_i\le i за всяко цяло i≥0i\ge0 и(ka0)+(ka1)+⋯+(kak)=2k\binom{k}{a_0}+\binom{k}{a_1}+\cdots+\binom{k}{a_k}=2^kза всяко цяло k≥0k\ge0. Докажете, че всяко цяло число N≥0N\ge0 се среща в редицата, т.е. за всяко N≥0N\ge0 съществува i≥0i\ge0, за което ai=Na_i=N.
РешениеЩе докажем с индукция по kk, че началният отрязък a0,a1,…,aka_0,a_1,\ldots,a_k се състои, с кратности и не непременно в този ред, от числата0,1,…,ℓ−1,0,1,…,k−ℓ0,1,\ldots,\ell-1,\quad 0,1,\ldots,k-\ellза някое ℓ≥0\ell\ge0 с 2ℓ≤k+12\ell\le k+1. При k=0k=0 имаме a0=0a_0=0, така че твърдението е вярно. Нека то е доказано за k=mk=m. Тогава числата a0,a1,…,ama_0,a_1,\ldots,a_m са0,0,1,1,2,2,…,ℓ−1,0,0,1,1,2,2,\ldots,\ell-1,ℓ−1,ℓ,ℓ+1,…,m−ℓ\ell-1,\ell,\ell+1,\ldots,m-\ellза някое ℓ\ell с 0≤2ℓ≤m+10\le2\ell\le m+1. Прилагаме условието за k=m+1k=m+1. След замяна на вече известните членове получаваме∑i=0ℓ−1(m+1i)\sum_{i=0}^{\ell-1}\binom{m+1}{i}+∑i=0m−ℓ(m+1i)+(m+1am+1)=+\sum_{i=0}^{m-\ell}\binom{m+1}{i}+\binom{m+1}{a_{m+1}}=2m+1.2^{m+1}.Използвайки симетрията (m+1i)=(m+1m+1−i)\binom{m+1}{i}=\binom{m+1}{m+1-i} и тъждеството ∑i=0m+1(m+1i)=2m+1\sum_{i=0}^{m+1}\binom{m+1}{i}=2^{m+1}, оттук следва(m+1am+1)=(m+1ℓ).\binom{m+1}{a_{m+1}}=\binom{m+1}{\ell}.Биномните коефициенти на ред m+1m+1 нарастват до средата и после намаляват, затоваam+1=ℓилиam+1=m+1−ℓ.a_{m+1}=\ell\quad\text{или}\quad a_{m+1}=m+1-\ell.И в двата случая началният отрязък до m+1m+1 отново има описания вид, което завършва индукцията. От това описание, ако вземем k=2Nk=2N, числото NN се среща сред a0,a1,…,a2Na_0,a_1,\ldots,a_{2N}. Следователно всяко цяло N≥0N\ge0 се среща в редицата.
Отвори задачатаMathNetISL 2019 C1Условие — източник

Задача C2

Пълен запис
Условие
Дадени са nn блока, всеки с тегло поне 11, като общото им тегло е 2n2n. Докажете, че за всяко реално число rr с 0≤r≤2n−20\le r\le2n-2 може да се избере подмножество от блоковете, чието общо тегло е поне rr и най-много r+2r+2.
РешениеЩе докажем малко по-общо твърдение с индукция по nn. Твърдение. Ако имаме nn блока, всеки с тегло поне 11, и общото им тегло е s≤2ns\le2n, то за всяко rr с −2≤r≤s-2\le r\le s може да се изберат някои от блоковете с общо тегло между rr и r+2r+2. При n=1n=1 твърдението е очевидно. Нека xx е най-голямото тегло. Тогава x≥s/nx\ge s/n, следователноs−x≤n−1ns≤2(n−1).s-x\le\frac{n-1}{n}s\le2(n-1).Ако махнем блок с тегло xx, индукционното предположение се прилага към останалите блокове и покрива всички rr с −2≤r≤s−x-2\le r\le s-x. Като добавим махнатия блок към съответните подмножества, покриваме всички rr с x−2≤r≤sx-2\le r\le s. Остава да видим, че тези два интервала се застъпват. Понеже всички останали n−1n-1 блока имат тегло поне 11, имаме x≤s−(n−1)x\le s-(n-1). От s≤2ns\le2n следва и x≤n+1x\le n+1. Сумирайки двете оценки, получаваме 2x≤s+22x\le s+2, т.е. x−2≤s−xx-2\le s-x. Следователно твърдението е доказано. В първоначалната задача имаме s=2ns=2n и 0≤r≤2n−20\le r\le2n-2, което е частен случай на твърдението.
Отвори задачатаMathNetISL 2019 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека nn е положително цяло число. Хари има nn монети, подредени в редица на бюрото му, като всяка показва ези или тура. Той многократно извършва следната операция: ако има kk монети, показващи ези, и k>0k\gt{}0, той обръща kk-тата монета; иначе спира процеса. Например процесът, който започва от THTTHT, еTHT→HHT→HTT→TTT,THT\to HHT\to HTT\to TTT,и отнема три стъпки. Нека CC означава началната конфигурация, т.е. редица от nn символа HH и TT, и нека ℓ(C)\ell(C) е броят стъпки, нужни, докато всички монети покажат TT. Докажете, че ℓ(C)\ell(C) е краен, и намерете средната му стойност върху всички 2n2^n възможни начални конфигурации CC.
РешениеОтговорът еn(n+1)4.\frac{n(n+1)}4.Нека E(n)E(n) е търсената средна стойност за nn монети. Ще използваме следните наблюдения. Ако конфигурацията започва с HH, последните n−1n-1 монети следват същите правила, сякаш са всички монети, докато станат всички TT, а след това първата монета се обръща. Ако конфигурацията завършва с TT, последната монета никога не се обръща и първите n−1n-1 монети следват същите правила. Ако конфигурацията започва с TT и завършва с HH, средните n−2n-2 монети следват същите правила, докато станат всички TT; след това има още 2n−12n-1 стъпки: първо се обръщат монетите 1,2,…,n−11,2,\ldots,n-1 в този ред, а после монетите n,n−1,…,1n,n-1,\ldots,1 в този ред. Тези случаи покриват всички конфигурации, а за 00 или 11 монети краят е очевиден; следователно по индукция процесът винаги завършва. Да означим с EAB(n)E_{AB}(n) средния брой стъпки сред конфигурациите с дължина nn, които започват с AA, ако A≠∗A\ne *, и завършват с BB, ако B≠∗B\ne *, където ∗* означава произволен от двата символа. За n≥2n\ge2 наблюденията даватEH∗(n)=E(n−1)+1,E_{H*}(n)=E(n-1)+1,E∗T(n)=E(n−1),E_{*T}(n)=E(n-1),EHT(n)=E(n−2)+1,E_{HT}(n)=E(n-2)+1,ETH(n)=E(n−2)+2n−1.E_{TH}(n)=E(n-2)+2n-1.Понеже EH∗(n)=12(EHH(n)+EHT(n))E_{H*}(n)=\frac12(E_{HH}(n)+E_{HT}(n)), получавамеEHH(n)=2E(n−1)−E(n−2)+1.E_{HH}(n)=2E(n-1)-E(n-2)+1.Аналогично от E∗T(n)=12(EHT(n)+ETT(n))E_{*T}(n)=\frac12(E_{HT}(n)+E_{TT}(n)) следваETT(n)=2E(n−1)−E(n−2)−1.E_{TT}(n)=2E(n-1)-E(n-2)-1.ЗатоваE(n)=E(n)=14(EHT(n)+EHH(n)+ETT(n)+ETH(n))=\frac14\bigl(E_{HT}(n)+E_{HH}(n)+E_{TT}(n)+E_{TH}(n)\bigr)=E(n−1)+n2.E(n-1)+\frac n2.С начални стойности E(0)=0E(0)=0 и E(1)=12E(1)=\frac12 по индукция получавамеE(n)=12(1+2+⋯+n)=n(n+1)4.E(n)=\frac12(1+2+\cdots+n)=\frac{n(n+1)}4.
Отвори задачатаMathNetISL 2019 C3Условие — източник

Задача C4

Пълен запис
Условие
В равнината на Камелот крал Артур построява лабиринт LL, състоящ се от nn стени, всяка от които е безкрайна права. Никои две стени не са успоредни и никои три стени не минават през една точка. След това Мерлин боядисва едната страна на всяка стена изцяло в червено, а другата страна изцяло в синьо. В пресечната точка на две стени има четири ъгъла: два диагонално противоположни ъгъла, в които се срещат червена и синя страна, един ъгъл, в който се срещат две червени страни, и един ъгъл, в който се срещат две сини страни. Във всяка такава пресечна точка има двупосочна врата, свързваща двата диагонално противоположни ъгъла, в които се срещат страни с различни цветове. След като Мерлин боядиса стените, Моргана поставя няколко рицари в лабиринта. Рицарите могат да минават през врати, но не могат да минават през стени. Нека k(L)k(L) е най-голямото число kk със следното свойство: независимо как Мерлин боядиса лабиринта LL, Моргана винаги може да постави поне kk рицари така, че никои двама от тях никога да не могат да се срещнат. За всяко nn намерете всички възможни стойности на k(L)k(L), когато LL е лабиринт с nn стени.
РешениеЕдинствената възможна стойност еk(L)=n+1,k(L)=n+1,независимо от формата на лабиринта. Първо ще докажем, че nn прави в общо положение разделят равнината на(n+12)+1\binom{n+1}{2}+1области. Това е ясно за n=0n=0. При добавяне на nn-тата права тя пресича предишните n−1n-1 прави в различни точки, затова е разделена на nn части и разсича точно nn от старите области. Така броят на областите се увеличава с nn, което дава формулата по индукция. Построяваме граф GG, чиито върхове са областите, а две области са свързани с ребро, ако между тях има врата. Има точно (n2)\binom n2 пресечни точки на стени, т.е. точно толкова врати и ребра. При добавяне на ребрата едно по едно броят на свързаните компоненти намалява с най-много 11. Следователно броят на компонентите на GG е поне(n+12)+1−(n2)=n+1.\binom{n+1}{2}+1-\binom n2=n+1.Ако Моргана постави по един рицар в области от различни компоненти, никои двама от тези рицари не могат да се срещнат. Значи k(L)≥n+1k(L)\ge n+1. Остава да покажем, че Мерлин може да боядиса стените така, че компонентите да са точно n+1n+1. Избираме координатна система, в която никоя стена не е вертикална или хоризонтална. Мерлин боядисва западната страна на всяка стена червена, а източната - синя. На всяка област даваме етикет, равен на броя стени, спрямо които областта лежи от източната страна. Врата винаги свързва две области с един и същ етикет. Ще докажем, че за всеки i=0,1,…,ni=0,1,\ldots,n всички области с етикет ii са свързани помежду си. За всеки ii има единствена област с етикет ii, която е неограничена на север. Ако рицар стои в област с етикет ii и върви на север, като при нужда следва северните страни на областите, той не може да заседне: всяка област е изпъкнала, а ако е ограничена на север, има единствен най-северен връх и през вратата там се преминава в друга област със същия етикет, разположена по на север. Накрая рицарят достига единствената северно неограничена област с етикет ii. Следователно областите с един и същ етикет образуват една компонента, а различните етикети не се свързват с врати. Значи компонентите са точно n+1n+1, така че Моргана не може да гарантира повече от n+1n+1 рицари. Получаваме k(L)=n+1k(L)=n+1.
Отвори задачатаMathNetISL 2019 C4Условие — източник

Задача C5

Пълен запис
Условие
В една социална мрежа има 20192019 потребители, като някои двойки са приятели; приятелството е симетрична релация. Първоначално има 10101010 души с по 10091009 приятели и 10091009 души с по 10101010 приятели. Приятелствата обаче са нестабилни, така че многократно, едно по едно, могат да се случват събития от следния вид: Нека A,B,CA,B,C са хора, за които AA е приятел и с BB, и с CC, но BB и CC не са приятели. Тогава BB и CC стават приятели, а AA вече не е приятел с никого от тях. Докажете, че независимо от началните приятелства съществува редица от такива събития, след която всеки потребител е приятел с най-много един друг потребител.
РешениеЩе използваме графова формулировка. Имаме граф GG с 20192019 върха, като 10101010 върха са със степен 10091009, а 10091009 върха са със степен 10101010. Разрешената операция е: ако върхът AA е съседен на два различни върха BB и CC, които не са съседни, махаме ребрата ABAB и ACAC и добавяме реброто BCBC. Ще наричаме това преприятеляване. Началният граф е свързан: за всеки два върха сборът на степените им е поне 20182018, така че те или са съседни, или имат общ съсед. Освен това графът не е пълен и има върхове с нечетна степен. Първо ще покажем, че докато свързаният граф има цикъл, можем да направим преприятеляване, което запазва свързаността. Ако графът има триъгълник, вземаме максимална пълна подграфа KK. Понеже целият граф не е пълен, има връх CC извън KK, съседен на някой връх AA от KK; по максималността на KK има връх BB от KK, който не е съседен на CC. Избираме цикъл в KK, който минава през реброто ABAB, и правим операцията с ребрата ABAB и ACAC. Добавянето на BCBC запазва свързаността. Ако графът е без триъгълници, вземаме най-къс цикъл ZZ. Той не може да минава през всички върхове: иначе, по минималност, не би имало други ребра и всички степени щяха да са четни. Значи има връх CC извън ZZ, съседен на връх AA от ZZ. Ако BB е съсед на AA върху цикъла, то BB не е съседен на CC, защото няма триъгълници. Операцията с ABAB и ACAC отново запазва свързаността. Във всички случаи броят на ребрата намалява с 11, а паритетът на степента на всеки връх се запазва; графът остава непълен и с връх с нечетна степен. Повтаряме това, докато стигнем до дърво. Сега в дърво всяка разрешена операция запазва ацикличността: ако връх AA има съседи BB и CC, то BB и CC не са съседни; махането на ABAB и ACAC и добавянето на BCBC не създава цикъл и намалява броя на ребрата. Повтаряме, докато вече няма възможна операция. Тогава максималната степен е най-много 11, защото връх със степен поне 22 би имал два несъседни съседа и би позволил операция. Полученият граф е обединение на единични ребра и изолирани върхове. Това точно означава, че всеки потребител има най-много един приятел.
Отвори задачатаMathNetISL 2019 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека n>1n\gt{}1 е цяло число. Дадени са 2n2n точки в равнината, никои три от които не са колинеарни. Точките трябва да се означат с A1,A2,…,A2nA_1,A_2,\ldots,A_{2n} в някакъв ред. След това разглеждаме 2n2n-те ъгъла∠A1A2A3, ∠A2A3A4,\angle A_1A_2A_3,\ \angle A_2A_3A_4, …, ∠A2n−2A2n−1A2n,\ \ldots,\ \angle A_{2n-2}A_{2n-1}A_{2n}, ∠A2n−1A2nA1, ∠A2nA1A2.\ \angle A_{2n-1}A_{2n}A_1,\ \angle A_{2n}A_1A_2.Всеки ъгъл се измерва така, че да има най-малката положителна стойност, т.е. между 0∘0^\circ и 180∘180^\circ. Докажете, че съществува подредба на дадените точки, при която получените 2n2n ъгъла могат да се разделят на две групи с равни суми.
РешениеИзбираме права ℓ\ell, която разделя точките на две групи LL и RR с по nn точки от всяка страна. Означаваме точките A1,A2,…,A2nA_1,A_2,\ldots,A_{2n} така, чеL={A1,A3,…,A2n−1}.L=\{A_1,A_3,\ldots,A_{2n-1}\}.Ще докажем, че тази подредба работи. Нека първоначално ss е правата A2nA1A_{2n}A_1. Завъртаме ss около A1A_1, докато мине през A2A_2, като избираме посоката на въртене така, че ss никога да не става успоредна на ℓ\ell. После завъртаме новата права ss около A2A_2, докато мине през A3A_3, отново по същия начин. Продължаваме така още 2n−22n-2 стъпки, докато ss се върне в началното си положение. Общият ориентиран ъгъл на завъртане Θ\Theta е кратен на 180∘180^\circ, защото началната и крайната права съвпадат. Но по време на въртенето правата ss никога не е успоредна на ℓ\ell; това е възможно само ако Θ=0\Theta=0. На всяка стъпка абсолютната стойност на завъртането е съответният ъгъл от условието. Затова разделяме ъглите на две групи според това дали съответното завъртане е обратно на часовниковата стрелка или по часовниковата стрелка. Сумата на ориентираните завъртания е 00, следователно сумите на двете групи ъгли са равни.
Отвори задачатаMathNetISL 2019 C6Условие — източник

Задача C7

Пълен запис
Условие
На маса има 6060 празни кутии B1,B2,…,B60B_1,B_2,\ldots,B_{60}, подредени в редица, и неограничен запас от камъчета. За дадено положително цяло число nn Алис и Боб играят следната игра. В първия ход Алис взема nn камъчета и ги разпределя в 6060-те кутии както желае. Всеки следващ ход има две стъпки: (a) Боб избира цяло число kk с 1≤k≤591\le k\le59 и разделя кутиите на двете групи B1,…,BkB_1,\ldots,B_k и Bk+1,…,B60B_{k+1},\ldots,B_{60}. (b) Алис избира една от тези две групи, добавя по едно камъче във всяка кутия от нея и маха по едно камъче от всяка кутия в другата група. Боб печели, ако в края на някой ход някоя кутия не съдържа камъчета. Намерете най-малкото nn, за което Алис може да попречи на Боб да спечели.
РешениеОтговорът е 960960. За 1≤i≤601\le i\le60 нека ViV_i е конфигурацията, при която кутия BjB_j съдържа 1+∣j−i∣1+|j-i| камъчета. В частност V30V_{30} съдържа30+29+⋯+1+2+3+⋯+31=96030+29+\cdots+1+2+3+\cdots+31=960камъчета. Първо ще дадем стратегия на Алис с 960960 камъчета. Тя започва с конфигурация V30V_{30}. Да казваме, че една конфигурация доминира друга, ако във всяка кутия има поне толкова камъчета, колкото в другата. Ако текущата конфигурация доминира ViV_i и Боб направи разделяне след кутия BkB_k с k≥ik\ge i, Алис избира лявата група; получената конфигурация доминира Vi+1V_{i+1}. Ако k<ik\lt{}i, тя избира дясната група; получената конфигурация доминира Vi−1V_{i-1}. Понеже никоя от конфигурациите V1,V2,…,V60V_1,V_2,\ldots,V_{60} няма празна кутия, Алис може да играе безкрайно и Боб не печели. Остава да докажем, че при най-много 959959 камъчета Боб има печеливша стратегия. Ще използваме следното наблюдение. Ако за някое положително цяло qq има поне 2q2q кутии, в които има най-много qq камъчета, Боб може да спечели. Наистина, разглеждаме тези 2q2q кутии в реда им отляво надясно. Боб първо разделя така, че първите qq от тях да са вляво, а последните qq - вдясно. Без ограничение можем да приемем, че Алис избира лявата група. После Боб мести разделянето надясно през избраните кутии, една по една. Ако при такова преместване Алис избере дясната група, кутиите между старата и новата граница губят две камъчета, а останалите избрани кутии не получават предимство; това само помага на Боб. Затова е достатъчно да разгледаме случая, в който Алис всеки път избира лявата група. Тогава най-дясната от избраните 2q2q кутии губи по едно камъче в qq хода и става празна. Ако първоначално няма празна кутия и горното наблюдение не може да се приложи, то за всяко q=1,2,…,30q=1,2,\ldots,30 най-много 2q−12q-1 кутии имат най-много qq камъчета. Следователно поне 61−2q61-2q кутии имат поне q+1q+1 камъчета. Сумирайки по слоеве, общият брой камъчета е поне60+∑q=130(61−2q)=60+900=960.60+\sum_{q=1}^{30}(61-2q)=60+900=960.Така всяка конфигурация с по-малко от 960960 камъчета или вече има празна кутия, или позволява на Боб да приложи наблюдението. Следователно минималното nn е 960960.
Отвори задачатаMathNetISL 2019 C7Условие — източник

Задача C8

Пълен запис
Условие
Алис има карта на Страната на чудесата, държава с n≥2n\ge2 града. За всяка двойка градове има тесен път от единия към другия. Един ден всички пътища са обявени за еднопосочни. Алис няма информация за посоките на пътищата, но Кралят на сърцата предлага да й помогне. Тя може да му задава въпроси. При всеки въпрос Алис избира двойка градове, а Кралят на сърцата й казва посоката на пътя, който ги свързва. Алис иска да знае дали има поне един град в Страната на чудесата с най-много един изходящ път. Докажете, че тя винаги може да разбере това с най-много 4n4n въпроса.
РешениеЩе покажем стратегия с най-много 4n−74n-7 въпроса. Нека SS е множеството от градове, за които Алис все още не знае, че имат повече от един изходящ път; първоначално ∣S∣=n|S|=n. Фаза 1. Алис избира два града AA и BB. Без ограничение нека отговорът е, че пътят е от AA към BB. След тази фаза е зададен 11 въпрос. Фаза 2. Поддържаме един променлив град TT, за който е известно, че има поне един входящ път, но още няма известен изходящ път. Първоначално T=BT=B. Алис повтаря n−2n-2 пъти следното: избира град XX, за който още не е питала, и пита за посоката между TT и XX. Ако тя е от XX към TT, градът TT остава същият; ако е от TT към XX, новият град TT става XX, защото старият TT вече има известен изходящ път. В края са зададени общо n−1n-1 въпроса. Последният град TT няма известен изходящ път, а всеки друг град има точно един известен изходящ път. Неориентираният граф на пътищата с известна посока е дърво. Фаза 3. Алис пита за всички още непитани пътища между TT и друг град, като спира, ако намери два изходящи пътя от TT. Тази фаза има най-много n−2n-2 въпроса. Ако тя не намери два изходящи пътя от TT, вече знае отговора на първоначалния въпрос и е задала най-много 2n−3≤4n−72n-3\le4n-7 въпроса. Затова по-нататък приемаме, че са намерени два такива пътя; нека в тази фаза са зададени qq въпроса, където 2≤q≤n−22\le q\le n-2. При всеки от първите q−1q-1 въпроса от тази фаза, ако пътят е към TT, другият град отпада от SS, защото вече е имал един известен изходящ път. Последният въпрос премахва самия TT от SS. Значи в края ∣S∣=n−q+1|S|=n-q+1, а общият брой въпроси е n+q−1n+q-1. Освен това известният неориентиран граф вътре в SS е ацикличен, а всеки град от SS има точно един известен изходящ път, не непременно към град от SS. Фаза 4. Алис многократно избира двойка градове от SS, за която още не знае посоката на пътя между тях. Понеже всеки град от SS вече има точно един известен изходящ път, отговорът винаги премахва един от двата града от SS. Понеже известният граф вътре в SS е ацикличен, докато в SS има поне три града, винаги има двойка с неизвестна посока. Следователно процесът спира с t≤2t\le2 останали града. В тази фаза са зададени n−q+1−tn-q+1-t въпроса, т.е. общо са зададени 2n−t2n-t въпроса. Фаза 5. Алис пита за всички още непитани пътища от останалите градове в SS. Ако t=2t=2, пътят между тях вече е бил питан. Освен това поне един друг път, засягащ някой от тези градове, е бил питан в първите две фази, защото там се получи дърво с повече от два върха. Затова в тази фаза има най-много t(n−t)−1t(n-t)-1 въпроса. В края Алис знае дали някой град има най-много един изходящ път. Ако t=1t=1, общият брой въпроси е най-много 3n−3≤4n−73n-3\le4n-7. Ако t=2t=2, той е най-много 4n−74n-7. Това е достатъчно, понеже 4n−7<4n4n-7\lt{}4n.
Отвори задачатаMathNetISL 2019 C8Условие — източник

Задача C9

Пълен запис
Условие
За всеки две различни реални числа xx и yy дефинираме D(x,y)D(x,y) като единственото цяло число dd, за което2d≤∣x−y∣<2d+1.2^d\le |x-y|\lt{}2^{d+1}.Дадено е множество FF от реални числа и елемент x∈Fx\in F. Мащабите на xx във FF са стойностите на D(x,y)D(x,y) за y∈Fy\in F, x≠yx\ne y. Нека kk е дадено положително цяло число. Да предположим, че всеки елемент xx на FF има най-много kk различни мащаба във FF; тези мащаби може да зависят от xx. Какъв е най-големият възможен брой елементи на FF?
РешениеОтговорът е 2k2^k. Първо построяваме пример. НекаF={0,1,2,…,2k−1}.F=\{0,1,2,\ldots,2^k-1\}.Мащабът между два елемента на FF е измежду 0,1,…,k−10,1,\ldots,k-1, така че всеки елемент има най-много kk мащаба. Сега ще докажем горната граница. За всяко крайно множество SS от реални числа и всяко реално xx некаrS(x)=∣{D(x,y):y∈S, y≠x}∣r_S(x)=|\{D(x,y):y\in S,\ y\ne x\}|е броят на различните мащаби на xx в SS. Дефинирамеw(S)=∑x∈S2−rS(x).w(S)=\sum_{x\in S}2^{-r_S(x)}.Ще докажем лемата w(S)≤1w(S)\le1 за всяко крайно SS. Доказателството е с индукция по ∣S∣|S|. Ако S={x}S=\{x\}, тогава rS(x)=0r_S(x)=0 и w(S)=1w(S)=1. Нека ∣S∣=m≥2|S|=m\ge2 и некаx1<x2<⋯<xmx_1\lt{}x_2\lt{}\cdots\lt{}x_mса елементите на SS. Нека dd е минималният мащаб между две различни числа от SS. Тогава има съседни xt,xt+1x_t,x_{t+1} с D(xt,xt+1)=dD(x_t,x_{t+1})=d. Ако j−i>1j-i\gt{}1, то∣xi−xj∣=∣xi+1−xi∣+∣xj−xi+1∣≥|x_i-x_j|=|x_{i+1}-x_i|+|x_j-x_{i+1}|\ge2d+2d=2d+1,2^d+2^d=2^{d+1},следователно D(xi,xj)>dD(x_i,x_j)\gt{}d. Избираме минимално i≤ti\le t и максимално j≥t+1j\ge t+1, така чеD(xi,xi+1)=D(xi+1,xi+2)=D(x_i,x_{i+1})=D(x_{i+1},x_{i+2})=⋯=D(xj−1,xj)=d.\cdots=D(x_{j-1},x_j)=d.Нека EE е множеството от онези xsx_s с четен индекс ss и i≤s≤ji\le s\le j, нека OO е множеството от онези с нечетен индекс, а RR са останалите елементи. ПоставямеSO=R∪O,SE=R∪E.S_O=R\cup O,\qquad S_E=R\cup E.И двете множества имат по-малко елементи от SS, така че по индукционното предположение w(SO),w(SE)≤1w(S_O),w(S_E)\le1. За x∈Rx\in R имаме rSO(x)≤rS(x)r_{S_O}(x)\le r_S(x) и rSE(x)≤rS(x)r_{S_E}(x)\le r_S(x), откъдето2−rS(x)≤12(2−rSO(x)+2−rSE(x)).2^{-r_S(x)}\le\frac12\left(2^{-r_{S_O}(x)}+2^{-r_{S_E}(x)}\right).За x∈Ox\in O в множеството SOS_O няма елемент на мащаб dd от xx, защото всички такива кандидати са в EE. Следователно rSO(x)≤rS(x)−1r_{S_O}(x)\le r_S(x)-1 и2−rS(x)≤12 2−rSO(x).2^{-r_S(x)}\le\frac12\,2^{-r_{S_O}(x)}.Аналогично за x∈Ex\in E имаме2−rS(x)≤12 2−rSE(x).2^{-r_S(x)}\le\frac12\,2^{-r_{S_E}(x)}.Сумирайки трите оценки, получавамеw(S)≤12(w(SO)+w(SE))≤1.w(S)\le\frac12\bigl(w(S_O)+w(S_E)\bigr)\le1.Лемата е доказана. Прилагаме лемата за множеството FF от условието. За всеки x∈Fx\in F имаме rF(x)≤kr_F(x)\le k, следователно 2−rF(x)≥2−k2^{-r_F(x)}\ge2^{-k}. Така∣F∣2−k≤w(F)≤1,|F|2^{-k}\le w(F)\le1,тоест ∣F∣≤2k|F|\le2^k. Заедно с примера това доказва, че максималният размер е 2k2^k.
Отвори задачатаMathNetISL 2019 C9Условие — източник

Задача N1

Пълен запис
Условие
Да се намерят всички двойки (m,n)(m,n) от положителни цели числа, за които(2n−1)(2n−2)(2n−4)⋯(2n−2n−1)=m!.(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})=m!.
РешениеОтговорът е(m,n)=(1,1)или(m,n)=(3,2).(m,n)=(1,1)\quad\text{или}\quad(m,n)=(3,2).НекаLn=(2n−1)(2n−2)(2n−4)⋯(2n−2n−1).L_n=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}).ТогаваLn=L_n=21+2+⋯+(n−1)(2n−1)(2n−1−1)⋯(21−1),2^{1+2+\cdots+(n-1)}(2^n-1)(2^{n-1}-1)\cdots(2^1-1),следователноν2(Ln)=n(n−1)2.\nu_2(L_n)=\frac{n(n-1)}2.Ако Ln=m!L_n=m!, то по формулата на Лежандърν2(m!)=∑i≥1⌊m2i⌋<m,\nu_2(m!)=\sum_{i\ge1}\left\lfloor\frac m{2^i}\right\rfloor\lt{}m,и затоваn(n−1)2<m.(1)\frac{n(n-1)}2\lt{}m.\tag{1}От друга страна имаме грубата оценкаLn<(2n)n=2n2.L_n\lt{}(2^n)^n=2^{n^2}.За n≥6n\ge6 е вярно2n2<(n(n−1)2)!.2^{n^2}\lt{}\left(\frac{n(n-1)}2\right)!.При n=6n=6 това се проверява пряко, а за n≥7n\ge7 следва от(n(n−1)2)≠15!⋅16⋅17⋯n(n−1)2>\left(\frac{n(n-1)}2\right)\neq{}15!\cdot16\cdot17\cdots\frac{n(n-1)}2\gt{}236⋅16n(n−1)2−15>2n2.2^{36}\cdot16^{\frac{n(n-1)}2-15}\gt{}2^{n^2}.Сега от (1) получавамеLn<2n2<(n(n−1)2)!<m≠Ln,L_n\lt{}2^{n^2}\lt{}\left(\frac{n(n-1)}2\right)!\lt{}m\neq{}L_n,противоречие. Значи n≤5n\le5. Остава пряка проверка:L1=1=1!,L2=6=3!,L_1=1=1!,\qquad L_2=6=3!,докато5!<L3=168<6!,7!<L4=20160<8!,5!\lt{}L_3=168\lt{}6!,\qquad 7!\lt{}L_4=20160\lt{}8!,и10!<L5=9999360<11!.10!\lt{}L_5=9999360\lt{}11!.Следователно единствените решения са (1,1)(1,1) и (3,2)(3,2).
Отвори задачатаMathNetISL 2019 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се намерят всички тройки (a,b,c)(a,b,c) от положителни цели числа, за коитоa3+b3+c3=(abc)2.a^3+b^3+c^3=(abc)^2.
РешениеОтговорът е (1,2,3)(1,2,3) и всичките му пермутации. Уравнението е симетрично, затова можем да приемем, че a≥b≥ca\ge b\ge c. Ще докажем, че тогава единственото решение е (a,b,c)=(3,2,1)(a,b,c)=(3,2,1). Първо ще покажем, че c=1c=1. Имаме3a3≥a3+b3+c3=(abc)2>a3,3a^3\ge a^3+b^3+c^3=(abc)^2\gt{}a^3,откъдето3a≥b2c2>a.3a\ge b^2c^2\gt{}a.Понеже b2c2−ab^2c^2-a е положително цяло число,b3+c3=a2(b2c2−a)≥a2.b^3+c^3=a^2(b^2c^2-a)\ge a^2.Следователно18b3≥9(b3+c3)≥9a2≥b4c4≥b3c5,18b^3\ge9(b^3+c^3)\ge9a^2\ge b^4c^4\ge b^3c^5,така че c5≤18c^5\le18 и c=1c=1. При c=1c=1 уравнението ставаa3+b3+1=a2b2.a^3+b^3+1=a^2b^2.Случаят a=ba=b би дал 2b3+1=b42b^3+1=b^4, което няма положително целочислено решение, следователно a>ba\gt{}b. Тогава от2a3>a3+b3+1>a32a^3\gt{}a^3+b^3+1\gt{}a^3получаваме2a>b2>a.2a\gt{}b^2\gt{}a.Освен товаb3+1=a2(b2−a)≥a2,b^3+1=a^2(b^2-a)\ge a^2,а от 2a>b22a\gt{}b^2 следва 4a2>b44a^2\gt{}b^4. Значи4(b3+1)>b4,4(b^3+1)\gt{}b^4,или 4>b3(b−4)4\gt{}b^3(b-4), откъдето b≤4b\le4. Ако b=1b=1, то a3+2=a2a^3+2=a^2, невъзможно. За b=2,3,4b=2,3,4 получаваме съответноa3−4a2+9=0,a^3-4a^2+9=0,a3−9a2+28=0,a^3-9a^2+28=0,a3−16a2+65=0.a^3-16a^2+65=0.Единственото положително целочислено решение с a≥ba\ge b е a=3a=3, b=2b=2. Така, при подредбата a≥b≥ca\ge b\ge c, получаваме само (3,2,1)(3,2,1), а по симетрия всички решения са пермутациите на (1,2,3)(1,2,3).
Отвори задачатаMathNetISL 2019 N2Условие — източник

Задача N3

Пълен запис
Условие
Ще наричаме множество SS от цели числа кореново, ако за всяко положително цяло число nn и всички a0,a1,…,an∈Sa_0,a_1,\ldots,a_n\in S всички цели корени на полиномаa0+a1x+⋯+anxna_0+a_1x+\cdots+a_nx^nсъщо принадлежат на SS. Да се намерят всички коренови множества от цели числа, които съдържат всички числа от вида 2a−2b2^a-2^b, където aa и bb са положителни цели числа.
РешениеОтговорът е: единствено множеството Z\mathbb Z на всички цели числа. Ясно е, че Z\mathbb Z е кореново. Нека SS е кореново множество, което съдържа всички числа 2a−2b2^a-2^b с a,b∈Z>0a,b\in\mathbb Z_{\gt{}0}. Тогава0=21−21∈Sи2=22−21∈S.0=2^1-2^1\in S\qquad\text{и}\qquad2=2^2-2^1\in S.Числото −1-1 принадлежи на SS, защото е корен на 2x+22x+2, а 11 принадлежи на SS, защото е корен на 2x2−x−12x^2-x-1. Освен това, ако n∈Sn\in S, то −n-n е корен на x+nx+n, следователно −n∈S-n\in S. Затова е достатъчно да докажем, че всички положителни цели числа са в SS. Първо ще докажем, че всяко положително цяло число има кратно в SS. Некаn=2αt,n=2^\alpha t,където α≥0\alpha\ge0, а tt е нечетно. Понеже t∣2φ(t)−1t\mid 2^{\varphi(t)}-1, числото2α+φ(t)+1−2α+1=2α+1(2φ(t)−1)2^{\alpha+\varphi(t)+1}-2^{\alpha+1}=2^{\alpha+1}(2^{\varphi(t)}-1)е кратно на nn и принадлежи на SS. Вече знаем, че 1∈S1\in S. Сега ще докажем с индукция, че всяко цяло число n≥2n\ge2 принадлежи на SS. Да предположим, че 0,1,…,n−1∈S0,1,\ldots,n-1\in S, и нека N∈SN\in S е кратно на nn. Записваме NN в бройна система с основа nn:N=aknk+ak−1nk−1+⋯+a1n+a0,N=a_kn^k+a_{k-1}n^{k-1}+\cdots+a_1n+a_0,където 0≤ai<n0\le a_i\lt{}n. По индукционното предположение всички цифри aia_i са в SS, а a0=0a_0=0. Понеже −N∈S-N\in S, числото nn е корен на полиномаakxk+ak−1xk−1+⋯+a1x−N,a_kx^k+a_{k-1}x^{k-1}+\cdots+a_1x-N,чиито коефициенти са в SS. Следователно n∈Sn\in S. Индукцията е завършена и S=ZS=\mathbb Z.
Отвори задачатаMathNetISL 2019 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Дадена е положителна цяла константа CC. Да се намерят всички функции f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0}, за които за всички положителни цели числа aa и bb с a+b>Ca+b\gt{}C е изпълненоa+f(b)∣a2+bf(a).a+f(b)\mid a^2+bf(a).
РешениеОтговорът е: точно функциитеf(a)=ka,f(a)=ka,където k∈Z>0k\in\mathbb Z_{\gt{}0} е константа. Те очевидно работят, така че ще докажем обратното. Първо, като поставим a=1a=1, получаваме за достатъчно големи bb1+f(b)∣1+bf(1),1+f(b)\mid 1+bf(1),откъдетоf(b)≤bf(1).(1)f(b)\le bf(1).\tag{1}Ще докажем, чеb∣f(b)2b\mid f(b)^2за всяко положително цяло bb. Избираме достатъчно голямо nn и поставяме a=nb−f(b)a=nb-f(b). Тогава a+f(b)=nba+f(b)=nb и условието даваnb∣(nb−f(b))2+bf(nb−f(b)).nb\mid (nb-f(b))^2+b f(nb-f(b)).В частност, след редукция по модул bb, получаваме b∣f(b)2b\mid f(b)^2. Оттук за всяко просто pp имаме p∣f(p)p\mid f(p). Пишемf(p)=k(p)p.f(p)=k(p)p.От (1) следва, че за всички достатъчно големи прости pp числата k(p)k(p) са положителни цели и са не по-големи от f(1)f(1). Затова съществува положително цяло число kk, което се среща като стойност на k(p)k(p) за безкрайно много прости pp. Фиксираме произволно положително цяло число aa и вземаме достатъчно голямо просто pp с f(p)=kpf(p)=kp и p∤ap\nmid a. От условието с b=pb=p следваa+kp∣a2+pf(a).a+kp\mid a^2+p f(a).Изваждаме a(a+kp)a(a+kp) и получавамеa+kp∣p(f(a)−ka).a+kp\mid p(f(a)-ka).Понеже gcd⁡(a+kp,p)=gcd⁡(a,p)=1\gcd(a+kp,p)=\gcd(a,p)=1, имамеa+kp∣f(a)−ka.a+kp\mid f(a)-ka.Това е вярно за безкрайно много произволно големи такива прости pp, следователно непременно f(a)−ka=0f(a)-ka=0. Така f(a)=kaf(a)=ka за всяко a∈Z>0a\in\mathbb Z_{\gt{}0}.
Отвори задачатаMathNetISL 2019 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека aa е положително цяло число. Ще казваме, че положително цяло число bb е aa-добро, ако(anb)−1\binom{an}{b}-1се дели на an+1an+1 за всички положителни цели числа nn с an≥ban\ge b. Да предположим, че bb е положително цяло число, което е aa-добро, но b+2b+2 не е aa-добро. Докажете, че b+1b+1 е просто число.
РешениеЩе докажем следния критерий: bb е aa-добро тогава и само тогава, когато bb е четно и всяко просто число p≤bp\le b дели aa. Първо, нека съществува просто p≤bp\le b с p∤ap\nmid a. Нека t=νp(b!)t=\nu_p(b!). Избираме положително цяло cc сac≡1(modpt+1)ac\equiv1\pmod {p^{t+1}}и после достатъчно голямоn=(p−1)c.n=(p-1)c.Тогаваan≡p−1(modpt+1),an\equiv p-1\pmod {p^{t+1}},така че един от множителите в числителяan(an−1)⋯(an−b+1)an(an-1)\cdots(an-b+1)е an−p+1an-p+1 и се дели на pt+1p^{t+1}. Следователно pp дели (anb)\binom{an}{b}. От друга страна p∣an+1p\mid an+1, така че an+1an+1 не може да дели (anb)−1\binom{an}{b}-1. Значи bb не е aa-добро. Обратно, нека всяко просто p≤bp\le b дели aa. Тогава всяко просто число, което дели b!b!, дели aa и следователно е взаимнопросто с an+1an+1. Затова b!b! е обратимо по модул an+1an+1. Имамеan(an−1)⋯(an−b+1)≡an(an-1)\cdots(an-b+1)\equiv(−1)(−2)⋯(−b)=(−1)bb!(modan+1).(-1)(-2)\cdots(-b)=(-1)^b b!\pmod {an+1}.След деление по обратимото b!b! получаваме(anb)≡(−1)b(modan+1).\binom{an}{b}\equiv(-1)^b\pmod {an+1}.Така при четно bb числото bb е aa-добро, а при нечетно bb не е aa-добро за достатъчно големи nn. Сега, ако bb е aa-добро, то bb е четно и всички прости p≤bp\le b делят aa. Понеже b+2b+2 също е четно, но не е aa-добро, критерият показва, че има просто число q≤b+2q\le b+2, което не дели aa. То не може да е най-много bb, значи q=b+1q=b+1 или q=b+2q=b+2. Но b+2b+2 е четно и по-голямо от 22, следователно не е просто. Затова q=b+1q=b+1, тоест b+1b+1 е просто число.
Отвори задачатаMathNetISL 2019 N5Условие — източник

Задача N6

Пълен запис
Условие
НекаH={⌊i2⌋:i∈Z>0}={1,2,4,5,7,…},H=\{\lfloor i\sqrt2\rfloor:i\in\mathbb Z_{\gt{}0}\}=\{1,2,4,5,7,\ldots\},и нека nn е положително цяло число. Докажете, че съществува константа CC, за която, ако A⊂{1,2,…,n}A\subset\{1,2,\ldots,n\} и ∣A∣≥Cn|A|\ge C\sqrt n, то съществуват a,b∈Aa,b\in A такива, че a−b∈Ha-b\in H. Тук Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа, а ⌊z⌋\lfloor z\rfloor означава най-голямото цяло число, което не надминава zz.
РешениеЩе докажем контрапозицията. Нека AA е множество, за което никоя положителна разлика на два негови елемента не принадлежи на HH. Ще покажем, че ∣A∣<3n|A|\lt{}3\sqrt n, което е достатъчно. Първо отбелязваме, че за положително цяло число rr е вярноr∈H⟺{r2}>1−12,(1)r\in H\quad\Longleftrightarrow\quad \left\{\frac r{\sqrt2}\right\}\gt{}1-\frac1{\sqrt2},\tag{1}където {x}\{x\} означава дробната част на xx. Наистина, r=⌊i2⌋r=\lfloor i\sqrt2\rfloor е еквивалентно на 0<i2−r<10\lt{}i\sqrt2-r\lt{}1, тоест на 0<i−r/2<1/20\lt{}i-r/\sqrt2\lt{}1/\sqrt2. ПишемA={a1<a2<⋯<ak}.A=\{a_1\lt{}a_2\lt{}\cdots\lt{}a_k\}.Разликите не се променят при преместване на всички елементи с една и съща константа, затова можем да приемем, че a1=0a_1=0 и A⊂{0,1,…,n−1}A\subset\{0,1,\ldots,n-1\}. От (1), понеже ai−a1∉Ha_i-a_1\notin H за i>1i\gt{}1, имаме{ai2}<1−12.\left\{\frac{a_i}{\sqrt2}\right\}\lt{}1-\frac1{\sqrt2}.Освен това дробните части{a12},{a22},…,{ak2}\left\{\frac{a_1}{\sqrt2}\right\},\left\{\frac{a_2}{\sqrt2}\right\},\ldots,\left\{\frac{a_k}{\sqrt2}\right\}са строго растящи. Ако за някои i<ji\lt{}j това не беше вярно, тогава{aj−ai2}={aj2}−{ai2}+1>\left\{\frac{a_j-a_i}{\sqrt2}\right\}=\left\{\frac{a_j}{\sqrt2}\right\}-\left\{\frac{a_i}{\sqrt2}\right\}+1\gt{}12>1−12,\frac1{\sqrt2}\gt{}1-\frac1{\sqrt2},което по (1) би дало aj−ai∈Ha_j-a_i\in H, противоречие. Нека di=ai+1−aid_i=a_{i+1}-a_i за 1≤i<k1\le i\lt{}k. Тогава∑i=1k−1{di2}<1−12.(2)\sum_{i=1}^{k-1}\left\{\frac{d_i}{\sqrt2}\right\}\lt{}1-\frac1{\sqrt2}.\tag{2}Ще използваме оценката{d2}>12d2(3)\left\{\frac d{\sqrt2}\right\}\gt{}\frac1{2d\sqrt2}\tag{3}за всяко положително цяло dd. Ако h=⌊d/2⌋h=\lfloor d/\sqrt2\rfloor, то(d2−h)(d2+h)=d2−2h22≥12,\left(\frac d{\sqrt2}-h\right)\left(\frac d{\sqrt2}+h\right)=\frac{d^2-2h^2}{2}\ge\frac12,а вторият множител е по-малък от 2d/22d/\sqrt2; това дава (3). От (2), (3) и неравенството на Коши получаваме1−12>∑i=1k−1{di2}>1-\frac1{\sqrt2}\gt{}\sum_{i=1}^{k-1}\left\{\frac{d_i}{\sqrt2}\right\}\gt{}122∑i=1k−11di≥\frac1{2\sqrt2}\sum_{i=1}^{k-1}\frac1{d_i}\ge122⋅(k−1)2∑idi.\frac1{2\sqrt2}\cdot\frac{(k-1)^2}{\sum_i d_i}.Но ∑idi=ak<n\sum_i d_i=a_k\lt{}n, следователно(k−1)2<(22−2)n.(k-1)^2\lt{}(2\sqrt2-2)n.В частност k<3nk\lt{}3\sqrt n за всяко n≥1n\ge1. Така всяко множество с поне 3n3\sqrt n елемента има две числа с разлика от HH, както трябваше.
Отвори задачатаMathNetISL 2019 N6Условие — източник

Задача N7

Пълен запис
Условие
Докажете, че съществува константа c>0c\gt{}0 и безкрайно много положителни цели числа nn със следното свойство: има безкрайно много положителни цели числа, които не могат да се представят като сума на по-малко от cnlog⁡ncn\log n две по две взаимнопрости nn-ти степени.
РешениеЩе построим безкрайно много стойности на nn, за които твърдението е вярно. Нека за дадени nn и NN е изпълнено следното условие: nn се дели на φ(pe)\varphi(p^e) за всяка точна степен pep^e, която дели NN. Тогава всяка nn-та степен е сравнима с 00 или 11 по модул pep^e. Ако събираме rr две по две взаимнопрости nn-ти степени, то по модул всяка такава pep^e сумата е сравнима с rr или с r−1r-1, защото най-много един от членовете може да се дели на pp. Нека NN има kk различни прости делителя. По китайската теорема за остатъците всички суми на най-много mm две по две взаимнопрости nn-ти степени заемат най-много 2km2^k m остатъчни класа по модул NN. АкоN>2km,N\gt{}2^k m,поне един остатъчен клас по модул NN не се получава; в него има безкрайно много положителни цели числа, които не са такива суми. Остава да построим двойки (n,N)(n,N) с горното делимостно условие и с достатъчно голямо NN. Фиксираме положително цяло число tt. Избираме прости числаp∣22t−1+1иq∣22t+1,p\mid 2^{2^{t-1}}+1\qquad\text{и}\qquad q\mid 2^{2^t}+1,и полагаме N=pqN=pq. Тогава редът на 22 по модул pp дели 2t2^t, но не дели 2t−12^{t-1}, затова 2t∣p−12^t\mid p-1. Аналогично 2t+1∣q−12^{t+1}\mid q-1. Следователноn=(p−1)(q−1)2tn=\frac{(p-1)(q-1)}{2^t}е цяло число и се дели както на p−1=φ(p)p-1=\varphi(p), така и на q−1=φ(q)q-1=\varphi(q). Значи условието е изпълнено. Освен товаlog⁡2n≤2t−1+2t−t<2t+1<2Nn.\log_2 n\le 2^{t-1}+2^t-t\lt{}2^{t+1}\lt{}2\frac Nn.СледователноN>12nlog⁡2n=18log⁡2⋅22nlog⁡n,N\gt{}\frac12 n\log_2 n=\frac1{8\log2}\cdot 2^2 n\log n,където последният логаритъм е натурален. Тук k=2k=2, така че за всяка константа0<c<18log⁡20\lt{}c\lt{}\frac1{8\log2}и за всички построени достатъчно големи nn имаме N>2kcnlog⁡nN\gt{}2^k c n\log n. От предишния абзац следва, че има безкрайно много положителни цели числа, които не са суми на най-много cnlog⁡nc n\log n две по две взаимнопрости nn-ти степени. Понеже параметърът tt може да расте безкрайно, получаваме безкрайно много такива nn.
Отвори задачатаMathNetISL 2019 N7Условие — източник

Задача N8

Пълен запис
Условие
Нека aa и bb са положителни цели числа. Докажете, че числотоa2+⌈4a2b⌉a^2+\left\lceil\frac{4a^2}{b}\right\rceilне е точен квадрат. Тук ⌈z⌉\lceil z\rceil означава най-малкото цяло число, което е не по-малко от zz.
РешениеДа допуснем противното. Тогава за някое положително цяло kk имамеa2+⌈4a2b⌉=(a+k)2.a^2+\left\lceil\frac{4a^2}{b}\right\rceil=(a+k)^2.Ако положим c=2ac=2a, получаваме положително целочислено решение на⌈c2b⌉=(c+k)k.(1)\left\lceil\frac{c^2}{b}\right\rceil=(c+k)k.\tag{1}Избираме решение (c,k)(c,k) на (1) с минимално възможно kk; вече не изискваме cc да е четно. От (1) следваc2b>⌈c2b⌉−1=ck+k2−1≥ck,\frac{c^2}{b}\gt{}\left\lceil\frac{c^2}{b}\right\rceil-1=ck+k^2-1\ge ck,следователно c>bkc\gt{}bk. От друга страна(c−k)(c+k)b<c2b≤⌈c2b⌉=(c+k)k,\frac{(c-k)(c+k)}b\lt{}\frac{c^2}{b}\le\left\lceil\frac{c^2}{b}\right\rceil=(c+k)k,така че c−k<bkc-k\lt{}bk. Следователноc=bk+rc=bk+rза някое цяло rr с 0<r<k0\lt{}r\lt{}k. Замествайки в (1), получаваме⌈(bk+r)2b⌉=k2b+2kr+⌈r2b⌉,\left\lceil\frac{(bk+r)^2}{b}\right\rceil=k^2b+2kr+\left\lceil\frac{r^2}{b}\right\rceil,докато(bk+r+k)k=k2b+2kr+k(k−r).(bk+r+k)k=k^2b+2kr+k(k-r).Значи⌈r2b⌉=k(k−r).\left\lceil\frac{r^2}{b}\right\rceil=k(k-r).Това е същото уравнение (1) за новото решение(c′,k′)=(r,k−r),(c',k')=(r,k-r),където c′>0c'\gt{}0 и 0<k′<k0\lt{}k'\lt{}k. Това противоречи на минималността на kk. Следователно първоначалното число не може да бъде точен квадрат.
Отвори задачатаMathNetISL 2019 N8Условие — източник