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

IMO Shortlisted Problems

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

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

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

2021

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

11-12

24 задачи

Задача A1

Пълен запис
Условие
Нека nn е положително цяло число и нека AA е подмножество на {0,1,2,…,5n}\{0,1,2,\ldots,5^n\}, състоящо се от 4n+24n+2 числа. Докажете, че съществуват a,b,c∈Aa,b,c\in A, за които a<b<ca\lt{}b\lt{}c и c+2a>3bc+2a\gt{}3b.
РешениеДа допуснем противното и нека елементите на AA саx0<x1<⋯<x4n+1.x_0\lt{}x_1\lt{}\cdots\lt{}x_{4n+1}.Тогава за всяко i=0,1,…,4n−1i=0,1,\ldots,4n-1 не може да имаме x4n+1+2xi>3xi+1x_{4n+1}+2x_i\gt{}3x_{i+1}, защото тройката (xi,xi+1,x4n+1)(x_i,x_{i+1},x_{4n+1}) би удовлетворявала условието. Следователноx4n+1+2xi≤3xi+1,x_{4n+1}+2x_i\le3x_{i+1},или еквивалентноx4n+1−xi≥32(x4n+1−xi+1).x_{4n+1}-x_i\ge\frac32\left(x_{4n+1}-x_{i+1}\right).По индукция получавамеx4n+1−xi≥(32)4n−i(x4n+1−x4n)x_{4n+1}-x_i\ge\left(\frac32\right)^{4n-i}(x_{4n+1}-x_{4n})за всяко i=0,1,…,4ni=0,1,\ldots,4n. При i=0i=0 това даваx4n+1−x0≥x_{4n+1}-x_0\ge(32)4n(x4n+1−x4n)=\left(\frac32\right)^{4n}(x_{4n+1}-x_{4n})=(8116)n(x4n+1−x4n)>\left(\frac{81}{16}\right)^n(x_{4n+1}-x_{4n})\gt{}5n,5^n,понеже x4n+1−x4n≥1x_{4n+1}-x_{4n}\ge1 и 81/16>581/16\gt{}5. От друга страна всички елементи на AA лежат между 00 и 5n5^n, така че x4n+1−x0≤5nx_{4n+1}-x_0\le5^n. Полученото противоречие доказва твърдението.
Отвори задачатаMathNetISL 2021 A1Условие — източник

Задача A2

Пълен запис
Условие
За всяко цяло число n≥1n\ge1 разглеждаме таблица n×nn\times n, в която на пресечната точка на ред ii и колона jj стои числото⌊ijn+1⌋\left\lfloor\frac{ij}{n+1}\right\rfloorза всички i=1,…,ni=1,\ldots,n и j=1,…,nj=1,\ldots,n. Да се определят всички цели числа n≥1n\ge1, за които сумата на n2n^2-те числа в таблицата е равна на 14n2(n−1)\frac14n^2(n-1).
РешениеОтговорът е: всички nn, за които n+1n+1 е просто число. Нека SS е сумата на всички числа в таблицата. Ще използваме следното просто наблюдение: ако x+yx+y е цяло число, тогава⌊x⌋+⌊y⌋≥x+y−1,\lfloor x\rfloor+\lfloor y\rfloor\ge x+y-1,като равенство има точно когато xx и yy не са едновременно цели числа. Събираме членовете по двойки с редове ii и n+1−in+1-i. Получаваме2S=∑i=1n∑j=1n(⌊ijn+1⌋+⌊(n+1−i)jn+1⌋)≥∑i=1n∑j=1n(j−1)=n⋅n(n−1)2.\begin{aligned} 2S&=\sum_{i=1}^n\sum_{j=1}^n\left(\left\lfloor\frac{ij}{n+1}\right\rfloor+\left\lfloor\frac{(n+1-i)j}{n+1}\right\rfloor\right)\\ &\ge\sum_{i=1}^n\sum_{j=1}^n(j-1)=n\cdot\frac{n(n-1)}2. \end{aligned}Следователно S≥14n2(n−1)S\ge\frac14n^2(n-1). Равенство има точно когато за нито една двойка 1≤i,j≤n1\le i,j\le n числото ij/(n+1)ij/(n+1) не е цяло. Ако n+1n+1 е просто, това условие е изпълнено. Ако n+1n+1 е съставно, нека n+1=abn+1=ab с 2≤a,b≤n2\le a,b\le n. Тогава при i=ai=a и j=bj=b числото ij/(n+1)ij/(n+1) е цяло и поне една от горните оценки е строга. Значи в този случай S>14n2(n−1)S\gt{}\frac14n^2(n-1). Следователно търсените стойности са точно тези, за които n+1n+1 е просто число.
Отвори задачатаMathNetISL 2021 A2Условие — източник

Задача A3

Пълен запис
Условие
За дадено положително цяло число nn да се намери най-малката възможна стойност на⌊a11⌋+⌊a22⌋+⋯+⌊ann⌋,\left\lfloor\frac{a_1}{1}\right\rfloor+\left\lfloor\frac{a_2}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_n}{n}\right\rfloor,където (a1,a2,…,an)(a_1,a_2,\ldots,a_n) пробягва всички пермутации на (1,2,…,n)(1,2,\ldots,n).
РешениеОтговорът е⌊log⁡2n⌋+1.\lfloor\log_2 n\rfloor+1.Нека 2k≤n<2k+12^k\le n\lt{}2^{k+1}. Първо ще построим пермутация, за която сумата е k+1k+1. Разделяме индексите на блокове[1,1], [2,3], [4,7], …,[1,1],\ [2,3],\ [4,7],\ \ldots, [2k−1,2k−1], [2k,n].\ [2^{k-1},2^k-1],\ [2^k,n].За всеки блок [p,q][p,q] поставямеap=q,ap+1=p, ap+2=p+1,…, aq=q−1.a_p=q,\qquad a_{p+1}=p,\ a_{p+2}=p+1,\ldots,\ a_q=q-1.Тъй като във всеки блок q<2pq\lt{}2p, приносът на блока е⌊qp⌋+∑i=p+1q⌊i−1i⌋=1.\left\lfloor\frac qp\right\rfloor+\sum_{i=p+1}^q\left\lfloor\frac{i-1}{i}\right\rfloor=1.Блоковете са k+1k+1 на брой, следователно сумата може да бъде k+1k+1. Остава да докажем долната оценка. За положителни цели числа a,ba,b имаме⌊ab⌋≥log⁡2a+1b.(1)\left\lfloor\frac ab\right\rfloor\ge\log_2\frac{a+1}{b}.\tag{1}Наистина, ако t=⌊a/b⌋t=\lfloor a/b\rfloor, то a+1≤b(t+1)a+1\le b(t+1), а 2t≥t+12^t\ge t+1; оттук следва (1). Прилагаме (1) за всяко събираемо:∑i=1n⌊aii⌋≥∑i=1nlog⁡2ai+1i.\sum_{i=1}^n\left\lfloor\frac{a_i}{i}\right\rfloor\ge\sum_{i=1}^n\log_2\frac{a_i+1}{i}.Понеже числата a1+1,a2+1,…,an+1a_1+1,a_2+1,\ldots,a_n+1 са пермутация на 2,3,…,n+12,3,\ldots,n+1, дясната страна еlog⁡22⋅3⋯(n+1)1⋅2⋯n=log⁡2(n+1)>k.\log_2\frac{2\cdot3\cdots(n+1)}{1\cdot2\cdots n}=\log_2(n+1)\gt{}k.Лявата страна е цяло число, следователно е поне k+1k+1. Това съвпада с построения пример и доказва отговора.
Отвори задачатаMathNetISL 2021 A3Условие — източник

Задача A4

Пълен запис
Условие
Докажете, че за всички реални числа x1,…,xnx_1,\ldots,x_n е изпълнено неравенството∑i=1n∑j=1nx2∣xi−xj∣≤\sum_{i=1}^n\sum_{j=1}^n\sqrt{\vphantom{x^2}|x_i-x_j|}\le∑i=1n∑j=1nx2∣xi+xj∣.\sum_{i=1}^n\sum_{j=1}^n\sqrt{\vphantom{x^2}|x_i+x_j|}.
РешениеЗа реално число pp разглеждаме интегралаI(p)=∫0∞1−cos⁡(pt)tt dt.I(p)=\int_0^\infty\frac{1-\cos(pt)}{t\sqrt t}\,dt.Той сходи и е положителен за p≠0p\ne0. След замяната u=∣p∣tu=|p|t получавамеI(p)=x2∣p∣ I(1).I(p)=\sqrt{\vphantom{x^2}|p|}\,I(1).Следователно за произволни реални a,ba,b имамеx2∣a+b∣−x2∣a−b∣=\sqrt{\vphantom{x^2}|a+b|}-\sqrt{\vphantom{x^2}|a-b|}=1I(1)∫0∞cos⁡((a−b)t)−cos⁡((a+b)t)tt dt.\frac1{I(1)}\int_0^\infty\frac{\cos((a-b)t)-\cos((a+b)t)}{t\sqrt t}\,dt.От тъждествотоcos⁡((a−b)t)−cos⁡((a+b)t)=2sin⁡(at)sin⁡(bt)\cos((a-b)t)-\cos((a+b)t)=2\sin(at)\sin(bt)следваx2∣a+b∣−x2∣a−b∣=\sqrt{\vphantom{x^2}|a+b|}-\sqrt{\vphantom{x^2}|a-b|}=1I(1)∫0∞2sin⁡(at)sin⁡(bt)tt dt.\frac1{I(1)}\int_0^\infty\frac{2\sin(at)\sin(bt)}{t\sqrt t}\,dt.Сега сумираме това равенство за всички двойки (a,b)=(xi,xj)(a,b)=(x_i,x_j). Получаваме∑i=1n∑j=1nx2∣xi+xj∣−∑i=1n∑j=1nx2∣xi−xj∣=2I(1)∫0∞(∑i=1nsin⁡(xit))2tt dt≥0.\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\sqrt{\vphantom{x^2}|x_i+x_j|}-\sum_{i=1}^n\sum_{j=1}^n\sqrt{\vphantom{x^2}|x_i-x_j|}\\ &=\frac2{I(1)}\int_0^\infty\frac{\left(\sum_{i=1}^n\sin(x_it)\right)^2}{t\sqrt t}\,dt\ge0. \end{aligned}Това е точно търсеното неравенство.
Отвори задачатаMathNetISL 2021 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число и нека a1,a2,…,ana_1,a_2,\ldots,a_n са положителни реални числа, за коитоa1+a2+⋯+an=1.a_1+a_2+\cdots+a_n=1.Докажете, че∑k=1nak1−ak(a1+a2+⋯+ak−1)2<13.\sum_{k=1}^n\frac{a_k}{1-a_k}(a_1+a_2+\cdots+a_{k-1})^2\lt{}\frac13.
РешениеНекаsk=a1+a2+⋯+ak(k=0,1,…,n),s_k=a_1+a_2+\cdots+a_k\qquad(k=0,1,\ldots,n),като s0=0s_0=0. За всяко kk ще докажемak1−aksk−12<sk3−sk−133.(1)\frac{a_k}{1-a_k}s_{k-1}^2\lt{}\frac{s_k^3-s_{k-1}^3}{3}.\tag{1}Понеже n≥2n\ge2 и всички aia_i са положителни, имаме 0<ak<10\lt{}a_k\lt{}1. След умножение на (1) с положителното число 3(1−ak)3(1-a_k) неравенството става еквивалентно на0<0\lt{}(1−ak)(sk−1+ak)3−(1−ak)sk−13−3aksk−12.(1-a_k)(s_{k-1}+a_k)^3-(1-a_k)s_{k-1}^3-3a_ks_{k-1}^2.Дясната страна се опростява до3(1−ak−sk−1)sk−1ak+(1−ak)ak2.3(1-a_k-s_{k-1})s_{k-1}a_k+(1-a_k)a_k^2.Тя е положителна, защото 1−ak−sk−1=1−sk≥01-a_k-s_{k-1}=1-s_k\ge0, sk−1≥0s_{k-1}\ge0 и 0<ak<10\lt{}a_k\lt{}1. Значи (1) е доказано. Сумирайки (1) за k=1,2,…,nk=1,2,\ldots,n, получаваме телескопична оценка∑k=1nak1−ak(a1+⋯+ak−1)2<\sum_{k=1}^n\frac{a_k}{1-a_k}(a_1+\cdots+a_{k-1})^2\lt{}sn3−s033=13,\frac{s_n^3-s_0^3}{3}=\frac13,както се искаше.
Отвори задачатаMathNetISL 2021 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека AA е крайно множество от цели числа, не непременно положителни, и нека m≥2m\ge2 е цяло число. Да предположим, че съществуват непразни подмножества B1,B2,B3,…,BmB_1,B_2,B_3,\ldots,B_m на AA, чиито елементи имат суми съответно m1,m2,m3,…,mmm^1,m^2,m^3,\ldots,m^m. Докажете, че AA съдържа поне m/2m/2 елемента.
РешениеНека A={a1,a2,…,ak}A=\{a_1,a_2,\ldots,a_k\} и да допуснем противното: k<m/2k\lt{}m/2. Нека sis_i е сумата на елементите на BiB_i. По условиеsi=mi(i=1,2,…,m).s_i=m^i\qquad(i=1,2,\ldots,m).Разглеждаме всички изразиc1s1+c2s2+⋯+cmsm,c_1s_1+c_2s_2+\cdots+c_ms_m,където ci∈{0,1,…,m−1}c_i\in\{0,1,\ldots,m-1\} за всяко ii. Те са общо mmm^m на брой и са различни, защото това са точно числатаc1m+c2m2+⋯+cmmmc_1m+c_2m^2+\cdots+c_mm^mс различни цифри в бройна система с основа mm. От друга страна, всеки такъв израз може да се запише във видаα1a1+α2a2+⋯+αkak,\alpha_1a_1+\alpha_2a_2+\cdots+\alpha_ka_k,където всяко αj\alpha_j е цяло число между 00 и m(m−1)m(m-1). Следователно възможните коефициентни kk-торки са най-много(m(m−1)+1)k<m2k<mm,(m(m-1)+1)^k\lt{}m^{2k}\lt{}m^m,понеже k<m/2k\lt{}m/2. Така получаваме по-малко от mmm^m възможности за mmm^m различни стойности, което е невъзможно. Следователно k≥m/2k\ge m/2, както трябваше да се докаже.
Отвори задачатаMathNetISL 2021 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека n≥1n\ge1 е цяло число и нека x0,x1,…,xn+1x_0,x_1,\ldots,x_{n+1} са n+2n+2 неотрицателни реални числа, за коитоxixi+1−xi−12≥1x_ix_{i+1}-x_{i-1}^2\ge1за всички i=1,2,…,ni=1,2,\ldots,n. Докажете, чеx0+x1+⋯+xn+xn+1>(2n3)3/2.x_0+x_1+\cdots+x_n+x_{n+1}\gt{}\left(\frac{2n}{3}\right)^{3/2}.
РешениеПърво ще използваме две леми. Лема 1. Ако a,b,ca,b,c са неотрицателни числа и ab−c2≥1ab-c^2\ge1, то(a+2b)2≥(b+2c)2+6.(a+2b)^2\ge(b+2c)^2+6.Наистина,(a+2b)2−(b+2c)2=(a+2b)^2-(b+2c)^2=(a−b)2+2(b−c)2+6(ab−c2)≥(a-b)^2+2(b-c)^2+6(ab-c^2)\ge6.6.Лема 2. За всяко положително цяло число nn имаме1+2+⋯+n>23n3/2.\sqrt1+\sqrt2+\cdots+\sqrt n\gt{}\frac23n^{3/2}.За доказателството използваме неравенството на Бернули(1+t)3/2>1+32t(−1≤t<0).(1+t)^{3/2}\gt{}1+\frac32t\qquad(-1\le t\lt{}0).При t=−1/kt=-1/k получаваме(k−1)3/2>k3/2−32k,(k-1)^{3/2}\gt{}k^{3/2}-\frac32\sqrt k,тоестk>23(k3/2−(k−1)3/2).\sqrt k\gt{}\frac23\left(k^{3/2}-(k-1)^{3/2}\right).Сумирането за k=1,2,…,nk=1,2,\ldots,n доказва лемата. Сега поставямеyi=2xi+xi+1(i=0,1,…,n).y_i=2x_i+x_{i+1}\qquad(i=0,1,\ldots,n).Прилагайки Лема 1 за a=xi+1a=x_{i+1}, b=xib=x_i, c=xi−1c=x_{i-1}, получавамеyi2≥yi−12+6(i=1,2,…,n).y_i^2\ge y_{i-1}^2+6\qquad(i=1,2,\ldots,n).Понеже y0≥0y_0\ge0, по индукция следваyi≥x26i(i=1,2,…,n).y_i\ge\sqrt{\vphantom{x^2}6i}\qquad(i=1,2,\ldots,n).От неотрицателността на всички xix_i имаме3(x0+x1+⋯+xn+1)≥y1+y2+⋯+yn.3(x_0+x_1+\cdots+x_{n+1})\ge y_1+y_2+\cdots+y_n.Следователно, по Лема 2,3(x0+x1+⋯+xn+1)≥3(x_0+x_1+\cdots+x_{n+1})\ge6(1+2+⋯+n)>6⋅23n3/2.\sqrt6(\sqrt1+\sqrt2+\cdots+\sqrt n)\gt{}\sqrt6\cdot\frac23n^{3/2}.Делим на 33 и получавамеx0+x1+⋯+xn+1>(2n3)3/2,x_0+x_1+\cdots+x_{n+1}\gt{}\left(\frac{2n}{3}\right)^{3/2},както се искаше.
Отвори задачатаMathNetISL 2021 A7Условие — източник

Задача A8

Пълен запис
Условие
Да се определят всички функции f:R→Rf:\mathbb R\to\mathbb R, за които(f(a)−f(b))(f(b)−f(c))(f(c)−f(a))=(f(a)-f(b))(f(b)-f(c))(f(c)-f(a))=f(ab2+bc2+ca2)−f(a2b+b2c+c2a)f(ab^2+bc^2+ca^2)-f(a^2b+b^2c+c^2a)за всички реални числа a,b,ca,b,c.
РешениеОтговорът еf(x)=αx+βилиf(x)=αx3+β,f(x)=\alpha x+\beta\quad\text{или}\quad f(x)=\alpha x^3+\beta,където α∈{−1,0,1}\alpha\in\{-1,0,1\} и β∈R\beta\in\mathbb R. Лесно се проверява, че всички тези функции работят. Добавянето на константа към ff не променя уравнението, затова първо ще считаме f(0)=0f(0)=0. Ще означаваме даденото уравнение с E(a,b,c)E(a,b,c). Лема. Или f≡0f\equiv0, или ff е инективна. Доказателство на лемата. НекаΘ={(u,v)∈R2:f(u)=f(v)}.\Theta=\{(u,v)\in\mathbb R^2:f(u)=f(v)\}.Ако (a,b)∈Θ(a,b)\in\Theta, то от E(a,b,x)E(a,b,x) следва, че за всяко реално xx двойкатаHa,b(x)=(ab2+bx2+xa2, a2b+b2x+x2a)H_{a,b}(x)=(ab^2+bx^2+xa^2,\ a^2b+b^2x+x^2a)също принадлежи на Θ\Theta. Да допуснем, че има (a,b)∈Θ(a,b)\in\Theta с a≠ba\ne b. За координатите на Ha,b(x)H_{a,b}(x) имамеg−(x)=(ab2+bx2+xa2)−(a2b+b2x+x2a)=g_-(x)=(ab^2+bx^2+xa^2)-(a^2b+b^2x+x^2a)=(a−b)(b−x)(x−a)(a-b)(b-x)(x-a)иg+(x)=(ab2+bx2+xa2)+(a2b+b2x+x2a)=g_+(x)=(ab^2+bx^2+xa^2)+(a^2b+b^2x+x^2a)=(x2+ab)(a+b)+x(a2+b2).(x^2+ab)(a+b)+x(a^2+b^2).Избираме xx, за което g−(x)≠0g_-(x)\ne0 и g+(x)≠0g_+(x)\ne0. Тогава получаваме двойка (α,β)∈Θ(\alpha,\beta)\in\Theta с α≠β\alpha\ne\beta и α≠−β\alpha\ne-\beta. Сравняваме E(α,1,0)E(\alpha,1,0) и E(β,1,0)E(\beta,1,0). Левите страни са равни, защото f(α)=f(β)f(\alpha)=f(\beta), и получаваме f(α2)=f(β2)f(\alpha^2)=f(\beta^2). Следователно (α2,β2)∈Θ(\alpha^2,\beta^2)\in\Theta и координатите са различни и неотрицателни. Повтаряйки повдигането на квадрат, получаваме двойка (γ,δ)∈Θ(\gamma,\delta)\in\Theta с δ>5γ≥0\delta\gt{}5\gamma\ge0. Ако γ=0\gamma=0, вече имаме двойка (0,r)∈Θ(0,r)\in\Theta с r≠0r\ne0. Ако γ>0\gamma\gt{}0, избираме реален корен xx наδγ2+γx2+xδ2=0,\delta\gamma^2+\gamma x^2+x\delta^2=0,който съществува, понеже δ>5γ\delta\gt{}5\gamma. Тогава първата координата на Hδ,γ(x)H_{\delta,\gamma}(x) е 00, а разликата на координатите е ненулева; отново получаваме (0,r)∈Θ(0,r)\in\Theta с r≠0r\ne0. От (0,r)∈Θ(0,r)\in\Theta следва чрез H0,r(x)H_{0,r}(x), чеf(rx2)=f(r2x)f(rx^2)=f(r^2x)за всяко xx. Заменяйки xx с −x-x, получаваме f(t)=f(−t)f(t)=f(-t) за всяко реално tt, тоест ff е четна. Тогава (a,−a)∈Θ(a,-a)\in\Theta за всяко aa, и от Ha,−a(x)H_{a,-a}(x) с x=1+52ax=\frac{1+\sqrt5}{2}a получавамеf((1+5)a3)=f(0)=0f((1+\sqrt5)a^3)=f(0)=0за всяко aa. Значи ff е тъждествено нулева. Лемата е доказана. Занапред нека ff е инективна и f(0)=0f(0)=0. От E(a,b,0)E(a,b,0) получавамеf(a)f(b)(f(a)−f(b))=f(a2b)−f(ab2).(1)f(a)f(b)(f(a)-f(b))=f(a^2b)-f(ab^2).\tag{1}Нека κ=f(1)\kappa=f(1). Понеже ff е инективна, κ≠0\kappa\ne0. При b=1b=1 в (1) имамеκf(a)(f(a)−κ)=f(a2)−f(a).(2)\kappa f(a)(f(a)-\kappa)=f(a^2)-f(a).\tag{2}Изваждаме (2), записано за −a-a, от (2), записано за aa. За a≠0a\ne0 инективността дава f(a)≠f(−a)f(a)\ne f(-a), така чеf(a)+f(−a)=κ−κ−1=λ.(3)f(a)+f(-a)=\kappa-\kappa^{-1}=\lambda.\tag{3}Сега вземаме ненулеви a≠ba\ne b. Записваме (1) за (a,b)(a,b) и за (−a,−b)(-a,-b) и ги събираме. Използвайки (3), получаваме(f(a)−f(b))(f(a)f(b)−f(−a)f(−b))=0.(f(a)-f(b))(f(a)f(b)-f(-a)f(-b))=0.Понеже f(a)≠f(b)f(a)\ne f(b), следваf(a)f(b)=f(−a)f(−b)=f(a)f(b)=f(-a)f(-b)=(λ−f(a))(λ−f(b)).(\lambda-f(a))(\lambda-f(b)).Ако λ≠0\lambda\ne0, то f(a)+f(b)=λf(a)+f(b)=\lambda за всички ненулеви a≠ba\ne b, което противоречи на инективността при фиксирано aa и променливо bb. Значи λ=0\lambda=0, откъдето κ=±1\kappa=\pm1, а ff е нечетна. Ако е нужно, заменяме ff с −f-f, което запазва уравнението, и приемаме f(1)=1f(1)=1. При това допускане (2) даваf(a2)=f(a)2.(4)f(a^2)=f(a)^2.\tag{4}Като съберем (1) за двойките (a,b)(a,b) и (a,−b)(a,-b) и използваме нечетността, получавамеf(a)f(b2)=f(ab2).f(a)f(b^2)=f(ab^2).От (4) следва, чеf(ax)=f(a)f(x)(5)f(ax)=f(a)f(x)\tag{5}за всяко реално aa и всяко x≥0x\ge0. Понеже ff е нечетна, (5) важи за всички реални a,xa,x. Освен това f(x)>0f(x)\gt{}0 за x>0x\gt{}0. Използваме стандартния факт, че положителна мултипликативна функция върху R>0\mathbb R_{\gt{}0} или е от вида f(x)=xτf(x)=x^\tau, или нейната графика е гъста в първия квадрант. Ако не сме в първия случай, можем да намерим 0<b<1/100\lt{}b\lt{}1/10 с f(b)>1f(b)\gt{}1. Същото е възможно и в случая f(x)=xτf(x)=x^\tau с τ<0\tau\lt{}0. За такова bb прилагаме E(1,b,x)E(1,b,x). Получавамеf(b2+bx2+x)=f(b^2+bx^2+x)=f(x2+b2x+b)f(x^2+b^2x+b)+(f(b)−1)(f(x)−f(b))(f(x)−1).+(f(b)-1)(f(x)-f(b))(f(x)-1).Числото x2+b2x+bx^2+b^2x+b е положително за всяко xx, следователно първият член вдясно е неотрицателен. Ако t=f(x)t=f(x) и B=f(b)>1B=f(b)\gt{}1, то(t−B)(t−1)≥−(B−1)24.(t-B)(t-1)\ge-\frac{(B-1)^2}{4}.Значи f(b2+bx2+x)f(b^2+bx^2+x) е ограничена отдолу с константа, независеща от xx. Изразът b2+bx2+xb^2+bx^2+x пробягва интервал от вида [b2−1/(4b),∞)[b^2-1/(4b),\infty), така че ff е ограничена отдолу на лъч. Понеже ff е нечетна, тя е ограничена отгоре на положителен интервал. Това противоречи както на гъстотата на графиката, така и на случая f(x)=xτf(x)=x^\tau с τ<0\tau\lt{}0. Следователно за x>0x\gt{}0 имаме f(x)=xτf(x)=x^\tau с някое τ>0\tau\gt{}0. Делим уравнението на(a−b)(b−c)(c−a)=(a-b)(b-c)(c-a)=(ab2+bc2+ca2)−(a2b+b2c+c2a)(ab^2+bc^2+ca^2)-(a^2b+b^2c+c^2a)и пускаме a,b,ca,b,c да клонят към 11. Лявата страна клони към τ3\tau^3, а дясната към τ 3τ−1\tau\,3^{\tau-1}. Значиτ2=3τ−1.\tau^2=3^{\tau-1}.Уравнението има положителни решения само τ=1\tau=1 и τ=3\tau=3: това следва от строгата изпъкналост на функцията 3(t−1)/2−t3^{(t-1)/2}-t, а двете стойности очевидно са корени. Така, при f(0)=0f(0)=0, инективните решения са f(x)=xf(x)=x, f(x)=−xf(x)=-x, f(x)=x3f(x)=x^3 и f(x)=−x3f(x)=-x^3, а заедно с неинективния случай имаме и f≡0f\equiv0. Накрая връщаме възможността за добавяне на произволна константа и получаваме точно посочените функции.
Отвори задачатаMathNetISL 2021 A8Условие — източник

Задача C1

Пълен запис
Условие
Нека SS е безкрайно множество от положителни цели числа, такова че съществуват четири различни по двойки числа a,b,c,d∈Sa,b,c,d\in S с gcd⁡(a,b)≠gcd⁡(c,d)\operatorname{gcd}(a,b)\ne\operatorname{gcd}(c,d). Докажете, че съществуват три различни по двойки числа x,y,z∈Sx,y,z\in S, за които gcd⁡(x,y)=gcd⁡(y,z)≠gcd⁡(z,x).\operatorname{gcd}(x,y)=\operatorname{gcd}(y,z)\ne\operatorname{gcd}(z,x).
РешениеИма число α∈S\alpha\in S, за което множеството {gcd⁡(α,s)∣s∈S, s≠α}\{\operatorname{gcd}(\alpha,s)\mid s\in S,\ s\ne\alpha\} съдържа поне два елемента. Наистина, ако това не беше вярно, то всички НОД-ове между различни елементи на SS биха били едни и същи, което противоречи на условието. Понеже α\alpha има краен брой делители, съществува делител d∣αd\mid\alpha, за който множеството B={β∈S∣gcd⁡(α,β)=d}B=\{\beta\in S\mid \operatorname{gcd}(\alpha,\beta)=d\} е безкрайно. Избираме γ∈S\gamma\in S така, че gcd⁡(α,γ)≠d\operatorname{gcd}(\alpha,\gamma)\ne d. Отново понеже γ\gamma има краен брой делители, можем да изберем две различни числа β1,β2∈B\beta_1,\beta_2\in B, различни и от α,γ\alpha,\gamma, такива че gcd⁡(β1,γ)=gcd⁡(β2,γ)=d′.\operatorname{gcd}(\beta_1,\gamma)=\operatorname{gcd}(\beta_2,\gamma)=d'.Ако d=d′d=d', то gcd⁡(α,β1)=gcd⁡(γ,β1)≠gcd⁡(α,γ),\operatorname{gcd}(\alpha,\beta_1)=\operatorname{gcd}(\gamma,\beta_1)\ne\operatorname{gcd}(\alpha,\gamma), така че тройката (x,y,z)=(α,β1,γ)(x,y,z)=(\alpha,\beta_1,\gamma) върши работа. Нека сега d≠d′d\ne d'. Тогава числото gcd⁡(β1,β2)\operatorname{gcd}(\beta_1,\beta_2) не може едновременно да е равно и на dd, и на d′d'. Ако gcd⁡(β1,β2)≠d\operatorname{gcd}(\beta_1,\beta_2)\ne d, вземаме (x,y,z)=(α,β1,β2)(x,y,z)=(\alpha,\beta_1,\beta_2), защото gcd⁡(α,β1)=gcd⁡(α,β2)=d.\operatorname{gcd}(\alpha,\beta_1)=\operatorname{gcd}(\alpha,\beta_2)=d. Ако пък gcd⁡(β1,β2)≠d′\operatorname{gcd}(\beta_1,\beta_2)\ne d', вземаме (x,y,z)=(γ,β1,β2)(x,y,z)=(\gamma,\beta_1,\beta_2), защото gcd⁡(γ,β1)=gcd⁡(γ,β2)=d′.\operatorname{gcd}(\gamma,\beta_1)=\operatorname{gcd}(\gamma,\beta_2)=d'. Във всички случаи получаваме търсената тройка.
Отвори задачатаMathNetISL 2021 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека n≥3n\ge3 е цяло число. Цяло число m≥n+1m\ge n+1 се нарича nn-цветно, ако при безкрайно много топчета от всеки от nn цвята C1,C2,…,CnC_1,C_2,\ldots,C_n можем да поставим mm от тях по окръжност така, че във всяка група от n+1n+1 последователни топчета да има поне по едно топче от цвят CiC_i за всяко i=1,2,…,ni=1,2,\ldots,n. Докажете, че има само краен брой положителни цели числа, които не са nn-цветни, и намерете най-голямото от тях.
РешениеОтговорът е n2−n−1.n^2-n-1.Първо ще покажем, че n(n−1)−1n(n-1)-1 не е nn-цветно. Да поставим толкова топчета по окръжност. За някой цвят, да кажем син, има най-много n−2n-2 топчета. Тези сини топчета разделят останалите, несини топчета на най-много n−2n-2 групи, а общият им брой е поне (n(n−1)−1)−(n−2)=(n−1)2.(n(n-1)-1)-(n-2)=(n-1)^2. Понеже (n−1)2>n(n−2)(n-1)^2\gt{}n(n-2), една от тези групи съдържа поне n+1n+1 последователни несини топчета. Тази група няма синьо топче, така че условието не е изпълнено. Сега ще докажем, че всяко m≥n(n−1)m\ge n(n-1) е nn-цветно. Записваме m=nk+j,m=nk+j, където k≥n−1k\ge n-1 и 0≤j≤n−10\le j\le n-1. Нареждаме около окръжност първо k−jk-j копия на цветовата последователност [1,2,3,…,n],[1,2,3,\ldots,n], а след това jj копия на последователността [1,1,2,3,…,n].[1,1,2,3,\ldots,n]. Общият брой топчета е (k−j)n+j(n+1)=nk+j=m(k-j)n+j(n+1)=nk+j=m. Остава да проверим условието. Всяка от използваните последователности съдържа всички цветове 1,2,…,n1,2,\ldots,n, а единственото повторение е допълнителният цвят 11 в блоковете [1,1,2,…,n][1,1,2,\ldots,n]. Понеже между два последователни блока никога не липсва нито един от цветовете 2,3,…,n2,3,\ldots,n, а цвят 11 се среща поне веднъж във всеки блок, всяка група от n+1n+1 последователни топчета съдържа всички nn цвята. Така всички m≥n(n−1)m\ge n(n-1) са nn-цветни. Следователно не-nn-цветните положителни цели числа са крайно много, а най-голямото от тях е n(n−1)−1=n2−n−1n(n-1)-1=n^2-n-1.
Отвори задачатаMathNetISL 2021 C2Условие — източник

Задача C3

Пълен запис
Условие
Фокусник има 20212021 напръстника, номерирани с числата от 11 до 20212021. Напръстниците са подредени по окръжност в произволен ред. Фокусникът прави последователност от 20212021 хода; на kk-тия ход той разменя местата на двата напръстника, съседни на напръстник kk. Докажете, че съществува стойност на kk, за която на kk-тия ход фокусникът разменя някакви напръстници aa и bb с a<k<ba\lt{}k\lt{}b.
РешениеДа допуснем противното. Ще наричаме напръстник kk централен напръстник на kk-тия ход, а позицията му в този момент - централна позиция на хода. Първа стъпка: черно-бяло оцветяване. Преди началото оцветяваме всички напръстници в бяло. След всеки ход оцветяваме централния напръстник на този ход в черно. Така в края всички напръстници са черни. По допускането ни на всеки ход kk двата разменени напръстника имат един и същи цвят: номерата им са или и двата по-малки от kk, или и двата по-големи от kk. Във всеки момент пренасяме цветовете на напръстниците върху текущите им позиции. Тогава при един ход единствената позиция, която променя цвета си, е централната позиция на този ход. Следователно всяка позиция е централна за точно един ход - този, при който се преоцветява в черно. Втора стъпка: червено-зелено оцветяване на позициите. Ако на kk-тия ход номерата на двата разменени напръстника са и двата по-малки от kk, оцветяваме централната позиция на хода в червено; иначе я оцветяваме в зелено. Така всяка позиция получава точно един от цветовете червено и зелено. Ще докажем, че всеки две съседни позиции получават различни цветове. Това ще е противоречие, защото окръжност с 20212021 позиции не може да се оцвети правилно с два цвята. Нека AA и BB са две съседни позиции, които са централни съответно в aa-тия и bb-тия ход, като a<ba\lt{}b. В aa-тия ход напръстникът на позиция BB е още бял, следователно номерът му е по-голям от aa. Заради допускането двата разменени напръстника в този ход са с номера по-големи от aa, така че позиция AA се оцветява в зелено. След aa-тия ход позиция AA съдържа черен напръстник и според първата стъпка оттук нататък на тази позиция винаги стоят само черни напръстници. Затова на bb-тия ход позиция AA съдържа черен напръстник, чийто номер е по-малък от bb, а напръстник bb се намира на позиция BB. Следователно при този ход разменените напръстници имат номера по-малки от bb, така че позиция BB се оцветява в червено. Получихме, че AA и BB имат различни цветове. Това важи за всяка двойка съседни позиции, невъзможно при нечетен брой позиции. Противоречието доказва твърдението.
Отвори задачатаMathNetISL 2021 C3Условие — източник

Задача C4

Пълен запис
Условие
Кралство Анизотропия се състои от nn града. Между всеки два града има точно един директен еднопосочен път. Път от XX до YY е редица от директни пътища, по която може да се стигне от XX до YY, без да се посещава вече посетен град. Колекция от пътища се нарича разнообразна, ако нито един директен път не участва в два или повече от пътищата в колекцията. Нека AA и BB са два различни града. Нека NABN_{AB} е максималният брой пътища в разнообразна колекция от пътища от AA до BB. Аналогично дефинираме NBAN_{BA}. Докажете, че NAB=NBAN_{AB}=N_{BA} тогава и само тогава, когато броят на директните пътища, излизащи от AA, е равен на броя на директните пътища, излизащи от BB.
РешениеЩе използваме езика на насочените графи: градовете са върхове, а директните пътища са насочени ребра. Разнообразна колекция е точно колекция от пътища без общи ребра. Ще използваме следната стандартна форма на теоремата на Менгер: максималният брой пътища без общи ребра от връх ss до връх tt е равен на минималния брой ребра в (s,t)(s,t)-разрез, тоест на минималния брой ребра, насочени от SS към TT при разлагане на множеството от върхове като S⊔TS\sqcup T, където s∈Ss\in S и t∈Tt\in T. Нека aa и bb са изходящите степени съответно на AA и BB. Ще докажем по-силното равенствоNBA−NAB=b−a,N_{BA}-N_{AB}=b-a,от което твърдението следва веднага. Вземаме произволен (A,B)(A,B)-разрез (SA,TA)(S_A,T_A), където A∈SAA\in S_A и B∈TAB\in T_A. От него строим (B,A)(B,A)-разрезSB=(SA∖{A})∪{B},TB=(TA∖{B})∪{A}.S_B=(S_A\setminus\{A\})\cup\{B\},\qquad T_B=(T_A\setminus\{B\})\cup\{A\}.Нека e(S,T)e(S,T) означава броя на ребрата, насочени от SS към TT. Ще покажем, чеe(SB,TB)=e(SA,TA)+(b−a).(1)e(S_B,T_B)=e(S_A,T_A)+(b-a).\tag{1}Нека cc е броят на ребрата от SA∖{A}S_A\setminus\{A\} към TA∖{B}T_A\setminus\{B\}. Те се броят по един и същи начин и в двата разреза. Нека asa_s и ata_t са съответно броят на ребрата от AA към SA∖{A}S_A\setminus\{A\} и към TAT_A; тогава a=as+ata=a_s+a_t. Нека bsb_s и btb_t са съответно броят на ребрата от BB към SA∖{A}S_A\setminus\{A\} и към (TA∖{B})∪{A}(T_A\setminus\{B\})\cup\{A\}; тогава b=bs+btb=b_s+b_t. В разреза (SA,TA)(S_A,T_A) освен ребрата, преброени в cc, имаме ata_t ребра, излизащи от AA, и още ∣SA∣−1−bs|S_A|-1-b_s ребра от SA∖{A}S_A\setminus\{A\} към BB, защото между BB и всеки връх от SA∖{A}S_A\setminus\{A\} има точно едно насочено ребро. Следователноe(SA,TA)=c+at+∣SA∣−1−bs.e(S_A,T_A)=c+a_t+|S_A|-1-b_s.Аналогично в разреза (SB,TB)(S_B,T_B) получавамеe(SB,TB)=c+bt+∣SA∣−1−as.e(S_B,T_B)=c+b_t+|S_A|-1-a_s.Изваждането на последните две равенства дава точно (1), понеже(bt+bs)−(at+as)=b−a.(b_t+b_s)-(a_t+a_s)=b-a.От (1) следва, че всеки (A,B)(A,B)-разрез поражда (B,A)(B,A)-разрез с размер, по-голям с b−ab-a. Затова минималният размер на (B,A)(B,A)-разрез е най-много NAB+b−aN_{AB}+b-a. Ако разменим ролите на AA и BB, получаваме обратното неравенство. По теоремата на Менгер следователноNBA=NAB+b−a.N_{BA}=N_{AB}+b-a.В частност NAB=NBAN_{AB}=N_{BA} точно когато a=ba=b, тоест точно когато от AA и от BB излизат равен брой директни пътища.
Отвори задачатаMathNetISL 2021 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека nn и kk са цели числа с n>k≥1n\gt{}k\ge1. На окръжност стоят 2n+12n+1 ученици. Всеки ученик SS има 2k2k съседи: kk-те най-близки ученици отдясно на SS и kk-те най-близки ученици отляво на SS. Да предположим, че n+1n+1 от учениците са момичета, а останалите nn са момчета. Докажете, че има момиче, сред чиито съседи има поне kk момичета.
РешениеЗаменяме момичетата с единици, а момчетата с нули. Получаваме числа a1,a2,…,a2n+1a_1,a_2,\ldots,a_{2n+1}, разположени по окръжност, и ги продължаваме периодично чрез ai+2n+1=aia_{i+2n+1}=a_i за всяко цяло число ii. Така ∑i=m+1m+2n+1ai=n+1\sum_{i=m+1}^{m+2n+1}a_i=n+1 за всяко цяло число mm. За всяко цяло число ii полагамеbi=ai+ai−k−1−1.b_i=a_i+a_{i-k-1}-1.Тогава bi∈{−1,0,1}b_i\in\{-1,0,1\} и за всяко цяло число mm имамеbm+1+bm+2+⋯+bm+2n+1=1.(1)b_{m+1}+b_{m+2}+\cdots+b_{m+2n+1}=1.\tag{1}В частност съществува индекс ii с bi=1b_i=1. Ще покажем, че съществува индекс ii, за койтоbi=1иbi+1+bi+2+⋯+bi+k≥0.(2)b_i=1\qquad\text{и}\qquad b_{i+1}+b_{i+2}+\cdots+b_{i+k}\ge0.\tag{2}Това веднага ще завърши доказателството. Наистина, от bi=1b_i=1 следва ai=1a_i=1, тоест на място ii стои момиче. Освен товаbi+1+⋯+bi+k=b_{i+1}+\cdots+b_{i+k}=(ai−k+⋯+ai−1)+(ai+1+⋯+ai+k)−k,(a_{i-k}+\cdots+a_{i-1})+(a_{i+1}+\cdots+a_{i+k})-k,така че (2) означава, че сред 2k2k-те съседи на това момиче има поне kk момичета. Да допуснем противното: за всеки индекс ii с bi=1b_i=1 е изпълненоbi+1+bi+2+⋯+bi+k<0.(3)b_{i+1}+b_{i+2}+\cdots+b_{i+k}\lt{}0.\tag{3}Избираме индекс i0i_0 с bi0=1b_{i_0}=1. Рекурсивно построяваме i0,i1,i2,…i_0,i_1,i_2,\ldots, като iji_j за j≥1j\ge1 е най-малкият индекс, за който ij>ij−1+ki_j\gt{}i_{j-1}+k и bij=1b_{i_j}=1. Такъв индекс винаги съществува поради периодичността и (1). Сред i0,i1,…,i2n+1i_0,i_1,\ldots,i_{2n+1} има два индекса, сравними по модул 2n+12n+1. Поради периодичността можем да преозначим началото така, че това да са i0i_0 и iTi_T, където T>0T\gt{}0. Тогава iT−i0=t(2n+1)i_T-i_0=t(2n+1) за някое положително цяло число tt. За j=0,1,…,T−1j=0,1,\ldots,T-1 полагамеSj=bij+bij+1+⋯+bij+1−1.S_j=b_{i_j}+b_{i_j+1}+\cdots+b_{i_{j+1}-1}.От минималността на ij+1i_{j+1} следва, че всички членове bij+k+1,…,bij+1−1b_{i_j+k+1},\ldots,b_{i_{j+1}-1} са най-много 00. Заедно с (3) и bij=1b_{i_j}=1 получавамеSj≤bij+bij+1+⋯+bij+k≤0.S_j\le b_{i_j}+b_{i_j+1}+\cdots+b_{i_j+k}\le0.Следователно S0+S1+⋯+ST−1≤0S_0+S_1+\cdots+S_{T-1}\le0. От друга страна, интервалът от i0i_0 до iT−1i_T-1 съдържа точно tt пълни периода на редицата bib_i. По (1)S0+S1+⋯+ST−1=t>0,S_0+S_1+\cdots+S_{T-1}=t\gt{}0,което е противоречие. Значи индекс с (2) съществува, а с това задачата е доказана.
Отвори задачатаMathNetISL 2021 C5Условие — източник

Задача C6

Пълен запис
Условие
Ловец и невидим заек играят игра върху безкрайна квадратна решетка. Първо ловецът фиксира оцветяване на клетките с краен брой цветове. След това заекът тайно избира клетка, от която да започне. Всяка минута заекът съобщава цвета на текущата си клетка на ловеца, а после тайно се премества в съседна клетка, която не е посещавал преди. Две клетки са съседни, ако имат обща страна. Ловецът печели, ако след крайно много време или заекът не може да се премести, или ловецът може да определи клетката, в която заекът е започнал. Да се реши дали съществува печеливша стратегия за ловеца.
РешениеОтговорът е да: съществува оцветяване, което дава печеливша стратегия за ловеца. Ще използваме следното наблюдение. Ако имаме краен брой оцветявания C1,C2,…,CsC_1,C_2,\ldots,C_s, можем да ги обединим в едно произведено оцветяване: цветът на клетката е наредената ss-торка от цветовете и в отделните оцветявания. Така ловецът получава едновременно цялата информация, която би получил от всяко от оцветяванията C1,C2,…,CsC_1,C_2,\ldots,C_s поотделно. Нека клетките имат цели координати (x,y)(x,y). Първото оцветяване C1C_1 оцветява клетката според остатъка на xx по модул 33. От две последователни съобщения по C1C_1 ловецът разбира дали заекът се е преместил наляво, надясно или вертикално. По същия начин второто оцветяване C2C_2, според остатъка на yy по модул 33, позволява да се разбере дали заекът се е преместил нагоре, надолу или хоризонтално. Следователно от C1C_1 и C2C_2 ловецът знае всички ходове на заека като вектори, но още не знае началната клетка. Ще добавим оцветяване, което определя точната стойност на xx, ако координатата xx на заека е неограничена. Избираме безкрайна редица от черни вертикални колони така, че разстоянията между две съседни черни колони да са различни по двойки; всички останали колони са бели. Това е оцветяването C3C_3. Ако координатата xx е неограничена, заекът рано или късно посещава две различни черни колони, между които няма друга посетена черна колона. От C1C_1 ловецът знае хоризонталното преместване между тези две посещения, а разстоянието между съседните черни колони определя еднозначно кои са тези колони. Затова ловецът научава точната стойност на xx в тези моменти, а от известните последващи ходове знае точната текуща стойност на xx. Симетрично построяваме оцветяване C4C_4, което определя точната стойност на yy, ако координатата yy е неограничена. Накрая построяваме оцветяване C5C_5 за диагоналите x+y=constx+y=\text{const}. Избираме безкрайна редица от черни диагонали така, че разстоянията между две съседни черни диагонали да са различни по двойки; останалите диагонали са бели. От C1C_1 и C2C_2 ловецът знае изменението на x+yx+y при всеки ход. Следователно, ако x+yx+y е неограничено, оцветяването C5C_5 позволява по същия начин да се определи точната стойност на x+yx+y. Ловецът взема произведеното оцветяване на C1,C2,C3,C4,C5C_1,C_2,C_3,C_4,C_5. Ако заекът някога не може да се премести, ловецът печели по условие. В противен случай заекът прави безкрайно много ходове без повторение на клетка. Тогава поне две от величините xx, yy и x+yx+y са неограничени; иначе две от тях биха били ограничени, следователно и третата, и заекът би останал в крайно множество от клетки. Следователно след крайно много време ловецът научава точните стойности на поне две от величините xx, yy и x+yx+y, а от тях намира и третата. Така той знае текущата клетка на заека. Понеже вече знае и всички направени ходове като вектори, ловецът проследява пътя назад и определя началната клетка. Значи описаното оцветяване е печеливша стратегия.
Отвори задачатаMathNetISL 2021 C6Условие — източник

Задача C8

Пълен запис
Условие
Да се намери най-голямото NN, за което съществува таблица TT от цели числа с NN реда и 100100 стълба, която има следните свойства: (i) всеки ред съдържа числата 1,2,…,1001,2,\ldots,100 в някакъв ред; (ii) за всеки два различни реда rr и ss съществува стълб cc, такъв че ∣T(r,c)−T(s,c)∣⩾2|T(r,c)-T(s,c)|\geqslant 2. Тук T(r,c)T(r,c) означава числото в пресечната клетка на ред rr и стълб cc.
РешениеОтговорът е100!250.\frac{100!}{2^{50}}.Първо ще докажем горната граница. В произволен ред заменяме за всяко k=1,2,…,50k=1,2,\ldots,50 двете числа 2k−12k-1 и 2k2k със символа xkx_k. Получава се наредба на символите x1,x2,…,x50x_1,x_2,\ldots,x_{50}, в която всеки символ се среща точно два пъти. Броят на тези наредби е100!250.\frac{100!}{2^{50}}.Ако два различни реда дават една и съща такава наредба, то във всеки стълб съответните им числа са или равни, или са съседни цели числа. Тогава ∣T(r,c)−T(s,c)∣⩽1|T(r,c)-T(s,c)|\leqslant 1 за всички cc, което противоречи на (ii). Следователно редовете дават различни наредби и N≤100!/250N\le 100!/2^{50}. Остава да построим таблица с толкова редове. Вземаме всички наредби на мултимножеството{x1,x1,x2,x2,…,x50,x50}.\{x_1,x_1,x_2,x_2,\ldots,x_{50},x_{50}\}.Ще превърнем всяка такава наредба в ред от числата 1,2,…,1001,2,\ldots,100. Двете срещания на x1x_1 заменяме отляво надясно с 11 и 22. За k≥2k\ge2 числото 2k−22k-2 вече е поставено. Двете срещания на xkx_k заменяме с 2k−12k-1 и 2k2k така, че относителният ред на тройката2k−2,2k−1,2k2k-2,\quad 2k-1,\quad 2kда бъде една от трите циклични наредби2k−2,2k−1,2k;2k,2k−2,2k−1;2k-2,2k-1,2k;\qquad 2k,2k-2,2k-1;2k−1,2k,2k−2.\qquad 2k-1,2k,2k-2.Това винаги е възможно според това дали вече поставеното 2k−22k-2 е преди, между или след двете места на xkx_k. Ще покажем, че получените редове удовлетворяват (ii). Нужна ни е следната проста лема. Нека π1\pi_1 и π2\pi_2 са две пермутации на {1,2,…,n}\{1,2,\ldots,n\}, за които ∣π1(i)−π2(i)∣⩽1|\pi_1(i)-\pi_2(i)|\leqslant 1 за всяко ii. Тогава π2\pi_2 се получава от π1\pi_1 чрез размени на няколко несъседни двойки стойности (j,j+1)(j,j+1). Доказателството на лемата е по индукция по nn. След преномериране можем да смятаме, че π1(i)=i\pi_1(i)=i. Ако π2(n)=n\pi_2(n)=n, прилагаме индукционното предположение към първите n−1n-1 стойности. Ако π2(n)=n−1\pi_2(n)=n-1, тогава стойността nn може да стои само на място n−1n-1, след което отново остава индукционното предположение за първите n−2n-2 стойности. Да допуснем, че два построени реда π1\pi_1 и π2\pi_2 не удовлетворяват (ii), тоест ∣π1(i)−π2(i)∣⩽1|\pi_1(i)-\pi_2(i)|\leqslant 1 за всички ii. По лемата π2\pi_2 се получава от π1\pi_1 чрез размени на двойки стойности (j,j+1)(j,j+1), като никои две от избраните стойности jj не са съседни. Нека rr е най-малката избрана стойност. Ако r=2k−1r=2k-1 е нечетна, то размяната на 2k−12k-1 и 2k2k сменя четността на относителната пермутация на тройката {2k−2,2k−1,2k}\{2k-2,2k-1,2k\}, а при k=1k=1 сменя реда на двойката {1,2}\{1,2\}. Това е невъзможно, защото при построяването всички такива тройки са в една от трите циклични наредби, тоест с една и съща четност, а 11 винаги е преди 22. Следователно r=2kr=2k е четна. Тогава, за да се запази четността на относителната пермутация на тройката {2k,2k+1,2k+2}\{2k,2k+1,2k+2\}, трябва да е избрана и размяната (2k+2,2k+3)(2k+2,2k+3). Същият довод после дава размяните с начални стойности 2k+4,2k+6,…2k+4,2k+6,\ldots, и накрая трябва да бъде избрана размяната (98,99)(98,99). Но тя сменя четността на тройката {98,99,100}\{98,99,100\}, противоречие. Значи за всеки два различни построени реда има стълб, в който числата се различават поне с 22. Така съществува таблица с 100!/250100!/2^{50} реда, а горната граница показва, че това е най-голямата възможна стойност на NN.
Отвори задачатаMathNetISL 2021 C8Условие — източник

Задача G2

Пълен запис
Условие
Версия 1. Нека nn е фиксирано положително цяло число и нека SS е множеството от точки (x,y)(x,y) в декартовата равнина, чиито две координати xx и yy са неотрицателни цели числа, по-малки от 2n2n (така че ∣S∣=4n2|S|=4n^2). Да предположим, че F\mathcal F е множество от n2n^2 четириъгълника, всички върхове на които лежат в SS, и всяка точка от SS е връх на точно един от четириъгълниците в F\mathcal F. Определете най-голямата възможна сума от лицата на всички n2n^2 четириъгълника в F\mathcal F. Версия 2. Нека nn е фиксирано положително цяло число и нека SS е множеството от точки (x,y)(x,y) в декартовата равнина, чиито две координати xx и yy са неотрицателни цели числа, по-малки от 2n2n (така че ∣S∣=4n2|S|=4n^2). Да предположим, че F\mathcal F е множество от многоъгълници, всички върхове на които лежат в SS, и всяка точка от SS е връх на точно един от многоъгълниците в F\mathcal F. Определете най-голямата възможна сума от лицата на всички многоъгълници в F\mathcal F.
РешениеОтговорът и за двете версии еΣ(n):=13n2(2n+1)(2n−1).\Sigma(n):=\frac13n^2(2n+1)(2n-1).В цялото решение лицето на многоъгълник PP ще означаваме с [P][P]. Ще наричаме многоъгълник допустим, ако всичките му върхове принадлежат на SS. НекаO=(n−12,n−12)O=\left(n-\frac12,n-\frac12\right)е центърът на SS. Ще наричаме допустим квадрат централен, ако центърът му е OO. Накрая, ще наричаме множество F\mathcal F от многоъгълници приемливо, ако удовлетворява условията на задачата, т.е. всички многоъгълници в F\mathcal F са допустими и всяка точка от SS е връх на точно един многоъгълник от F\mathcal F. За приемливо множество F\mathcal F ще означаваме с Σ(F)\Sigma(\mathcal F) сумата от лицата на многоъгълниците в F\mathcal F. Всяка точка от SS е връх на единствен централен квадрат. Затова множеството G\mathcal G от всички централни квадрати е приемливо. Ще докажем, чеΣ(F)≤Σ(G)=Σ(n),(1)\Sigma(\mathcal F)\le\Sigma(\mathcal G)=\Sigma(n),\tag{1}с което отговорът следва. Ще използваме следната ключова лема. Лема. Нека P=A1A2…AmP=A_1A_2\ldots A_m е многоъгълник, а OO е произволна точка в равнината. Тогава[P]≤12∑i=1mOAi2.(2)[P]\le\frac12\sum_{i=1}^m OA_i^2.\tag{2}Освен това, ако PP е квадрат с център OO, то в (2) имаме равенство. Доказателство. Полагаме Am+1=A1A_{m+1}=A_1. За всяко i=1,2,…,mi=1,2,\ldots,m имаме[OAiAi+1]≤OAi⋅OAi+12≤OAi2+OAi+124.[OA_iA_{i+1}]\le\frac{OA_i\cdot OA_{i+1}}2\le\frac{OA_i^2+OA_{i+1}^2}{4}.Следователно[P]≤∑i=1m[OAiAi+1]≤[P]\le\sum_{i=1}^m[OA_iA_{i+1}]\le14∑i=1m(OAi2+OAi+12)=\frac14\sum_{i=1}^m\left(OA_i^2+OA_{i+1}^2\right)=12∑i=1mOAi2,\frac12\sum_{i=1}^m OA_i^2,което доказва (2). Накрая, всички използвани неравенства стават равенства, когато PP е квадрат с център OO. Връщаме се към задачата и разглеждаме произволно приемливо множество F\mathcal F. Прилагайки лемата към всеки елемент на F\mathcal F и към всеки елемент на G\mathcal G (където има равенство), получавамеΣ(F)≤12∑A∈SOA2=Σ(G),\Sigma(\mathcal F)\le\frac12\sum_{A\in S}OA^2=\Sigma(\mathcal G),което доказва лявото неравенство в (1). Остава да пресметнем Σ(G)\Sigma(\mathcal G). ИмамеΣ(G)=12∑A∈SOA2=12∑i=02n−1∑j=02n−1((n−12−i)2+(n−12−j)2)=18⋅4⋅2n∑i=0n−1(2n−2i−1)2=n∑j=0n−1(2j+1)2=n(∑j=12nj2−∑j=1n(2j)2)=n(2n(2n+1)(4n+1)6−4⋅n(n+1)(2n+1)6)=n2(2n+1)(2n−1)3.\begin{aligned} \Sigma(\mathcal G)&=\frac12\sum_{A\in S}OA^2\\ &=\frac12\sum_{i=0}^{2n-1}\sum_{j=0}^{2n-1}\left(\left(n-\frac12-i\right)^2+\left(n-\frac12-j\right)^2\right)\\ &=\frac18\cdot4\cdot2n\sum_{i=0}^{n-1}(2n-2i-1)^2\\ &=n\sum_{j=0}^{n-1}(2j+1)^2\\ &=n\left(\sum_{j=1}^{2n}j^2-\sum_{j=1}^n(2j)^2\right)\\ &=n\left(\frac{2n(2n+1)(4n+1)}6-4\cdot\frac{n(n+1)(2n+1)}6\right)\\ &=\frac{n^2(2n+1)(2n-1)}3. \end{aligned}Това е точно Σ(n)\Sigma(n), както трябваше да се докаже.
Отвори задачатаMathNetISL 2021 G2Условие — източник

Задача N1

Пълен запис
Условие
Да се определят всички цели числа n≥1n\ge1, за които съществува двойка положителни цели числа (a,b)(a,b) такава, че кубът на никое просто число не дели a2+b+3a^2+b+3 иab+3b+8a2+b+3=n.\frac{ab+3b+8}{a^2+b+3}=n.
РешениеОтговорът е единствено n=2n=2. Понежеb≡−a2−3(moda2+b+3),b\equiv -a^2-3\pmod {a^2+b+3},за числителя получавамеab+3b+8≡ab+3b+8\equiva(−a2−3)+3(−a2−3)+8=−(a+1)3(moda2+b+3). a(-a^2-3)+3(-a^2-3)+8=-(a+1)^3\pmod {a^2+b+3}.Следователно a2+b+3a^2+b+3 дели (a+1)3(a+1)^3. Числото a2+b+3a^2+b+3 не се дели на куб на просто число, затова всеки прост делител участва в него най-много на втора степен. От делимостта към (a+1)3(a+1)^3 следва, че всъщностa2+b+3∣(a+1)2.a^2+b+3\mid (a+1)^2.От друга страна0<(a+1)2<2(a2+b+3),0\lt{}(a+1)^2\lt{}2(a^2+b+3),така че непременно(a+1)2=a2+b+3.(a+1)^2=a^2+b+3.Получаваме b=2(a−1)b=2(a-1) и тогаваab+3b+8=2(a+1)2,ab+3b+8=2(a+1)^2,тоест n=2n=2. Остава да проверим, че тази стойност наистина се достига. Например при (a,b)=(2,2)(a,b)=(2,2) имаме a2+b+3=9a^2+b+3=9, което не се дели на куб на просто число, и дробта е равна на 22.
Отвори задачатаMathNetISL 2021 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека n≥100n\ge100 е цяло число. Числата n,n+1,…,2nn,n+1,\ldots,2n са записани върху n+1n+1 карти, по едно число на карта. Картите са разбъркани и разделени на две купчини. Докажете, че една от купчините съдържа две карти, сборът на чиито числа е точен квадрат.
РешениеДостатъчно е да намерим три карти с числа a,b,ca,b,c, за които всички двойни сборове a+ba+b, b+cb+c и a+ca+c са точни квадрати. Тогава при разделяне на трите карти в две купчини две от тях попадат в една и съща купчина. Избираме трите последователни квадрата (2k−1)2(2k-1)^2, (2k)2(2k)^2, (2k+1)2(2k+1)^2 и решаваме систематаa+b=(2k−1)2,a+c=(2k)2,b+c=(2k+1)2.a+b=(2k-1)^2,\qquad a+c=(2k)^2,\qquad b+c=(2k+1)^2.Получаваме(a,b,c)=(2k2−4k, 2k2+1, 2k2+4k).(a,b,c)=(2k^2-4k,\ 2k^2+1,\ 2k^2+4k).Тези три числа лежат между nn и 2n2n, акоn≤2k2−4kи2k2+4k≤2n,n\le 2k^2-4k\qquad\text{и}\qquad 2k^2+4k\le2n,тоест акоk2+2k≤n≤2k2−4k.k^2+2k\le n\le2k^2-4k.За k≥9k\ge9 интервалитеIk=[k2+2k, 2k2−4k]I_k=[k^2+2k,\ 2k^2-4k]се застъпват, понеже(k+1)2+2(k+1)≤2k2−4k.(k+1)^2+2(k+1)\le2k^2-4k.Първият от тях започва от I9=[99,126]I_9=[99,126], следователно тези интервали покриват всички цели n≥99n\ge99. В частност за всяко n≥100n\ge100 съществува подходящо kk, а горната конструкция завършва доказателството.
Отвори задачатаMathNetISL 2021 N2Условие — източник

Задача N3

Пълен запис
Условие
Да се намерят всички положителни цели числа nn със следното свойство: ако положителните делители на nn са kk на брой, то те имат пермутация (d1,d2,…,dk)(d_1,d_2,\ldots,d_k) такава, че за всяко i=1,2,…,ki=1,2,\ldots,k числотоd1+d2+⋯+did_1+d_2+\cdots+d_iе точен квадрат.
РешениеОтговорът е n=1n=1 и n=3n=3. Некаd1+d2+⋯+di=si2(i=1,2,…,k)d_1+d_2+\cdots+d_i=s_i^2\qquad(i=1,2,\ldots,k)и да положим s0=0s_0=0. Тогава0=s0<s1<s2<⋯<sk,0=s_0\lt{}s_1\lt{}s_2\lt{}\cdots\lt{}s_k,така че si≥is_i\ge i иdi=si2−si−12=(si+si−1)(si−si−1)≥d_i=s_i^2-s_{i-1}^2=(s_i+s_{i-1})(s_i-s_{i-1})\gesi+si−1≥2i−1.(1) s_i+s_{i-1}\ge2i-1.\tag{1}Числото 11 е сред делителите did_i, а от (1) то може да бъде само d1d_1. Значи d1=1d_1=1 и s1=1s_1=1. Разглеждаме d2d_2. Имамеd2=s22−1=(s2−1)(s2+1).d_2=s_2^2-1=(s_2-1)(s_2+1).Следователно s2−1s_2-1 и s2+1s_2+1 са делители на nn. Нека dj=s2+1d_j=s_2+1. От (1) получавамеs2+1=dj≥sj+sj−1.s_2+1=d_j\ge s_j+s_{j-1}.Понеже редицата s0<s1<⋯<sks_0\lt{}s_1\lt{}\cdots\lt{}s_k е строго растяща, това е възможно само при j≤2j\le2. Значи двата делителя s2−1s_2-1 и s2+1s_2+1 са именно d1d_1 и d2d_2, откъдето s2−1=1s_2-1=1, s2=2s_2=2 и d2=3d_2=3. Ще докажем по индукция, чеdi=2i−1иsi=id_i=2i-1\qquad\text{и}\qquad s_i=iза всички i=1,2,…,ki=1,2,\ldots,k. Нека това вече е доказано до индекс ii. Тогаваdi+1=si+12−si2=si+12−i2=d_{i+1}=s_{i+1}^2-s_i^2=s_{i+1}^2-i^2=(si+1−i)(si+1+i).(s_{i+1}-i)(s_{i+1}+i).Числото si+1+is_{i+1}+i е делител на nn, да кажем dj=si+1+id_j=s_{i+1}+i. От (1) имамеsi+1+i=si+1+si=dj≥sj+sj−1,s_{i+1}+i=s_{i+1}+s_i=d_j\ge s_j+s_{j-1},което налага j≤i+1j\le i+1. Но dj=si+1+i>2i>di>di−1>⋯>d1d_j=s_{i+1}+i\gt{}2i\gt{}d_i\gt{}d_{i-1}\gt{}\cdots\gt{}d_1, така че j≤ij\le i е невъзможно. Следователно j=i+1j=i+1. Значиsi+1+i=di+1=si+12−i2,s_{i+1}+i=d_{i+1}=s_{i+1}^2-i^2,тоестsi+12−si+1=i(i+1).s_{i+1}^2-s_{i+1}=i(i+1).Оттук si+1=i+1s_{i+1}=i+1 и di+1=2i+1d_{i+1}=2i+1. Индукцията е завършена. Следователно положителните делители на nn са1,3,5,…,n−2,n.1,3,5,\ldots,n-2,n.В частност nn е нечетно, а вторият най-голям делител е n−2n-2. Понеже n−2∣n=(n−2)+2n-2\mid n=(n-2)+2, получаваме n−2∣2n-2\mid2. Така n=1n=1 или n=3n=3. И двете числа работят: при n=1n=1 имаме само d1=1=12d_1=1=1^2, а при n=3n=3 вземаме d1=1d_1=1, d2=3d_2=3 и d1+d2=4=22d_1+d_2=4=2^2.
Отвори задачатаMathNetISL 2021 N3Условие — източник

Задача N4

Пълен запис
Условие
На Алиса е дадено рационално число r>1r\gt{}1 и права с две точки B≠RB\ne R. В точката RR има червено мънисто, а в точката BB - синьо мънисто. Алиса играе пасианс, като извършва последователност от ходове. На всеки ход тя избира цяло число kk (не непременно положително) и едно от мънистата. Ако избраното мънисто се намира в точка XX, а другото - в точка YY, Алиса премества избраното мънисто в точка X′X' така, чеYX′→=rkYX→.\overrightarrow{YX'}=r^k\overrightarrow{YX}.Целта на Алиса е да премести червеното мънисто в точката BB. Да се намерят всички рационални числа r>1r\gt{}1, за които Алиса може да постигне целта си с най-много 20212021 хода.
РешениеОтговорът еr=b+1bза b=1,2,…,1010.r=\frac{b+1}{b}\qquad\text{за }b=1,2,\ldots,1010.Въвеждаме координати по правата така, че първоначално червеното мънисто да е в 00, а синьото - в 11. Редът на двете мъниста не се променя и разстоянието между тях винаги е степен rℓr^\ell с цяло ℓ\ell. Нека след mm-тия ход разстоянието еdm=rαm(m=0,1,2,…),d_m=r^{\alpha_m}\qquad(m=0,1,2,\ldots),като d0=1d_0=1. Ако едно и също мънисто се мести в два последователни хода, тези два хода могат да се заменят с един ход със същия краен ефект. Затова, без загуба на общност, можем да приемем, че Алиса мести мънистата редуващо се. Нека червеното мънисто е преместено общо tt пъти. Ако първо се мести червеното мънисто, общото му преместване е(d0−d1)+(d2−d3)+⋯+(d2t−2−d2t−1),(d_0-d_1)+(d_2-d_3)+\cdots+(d_{2t-2}-d_{2t-1}),а ако първо се мести синьото, то е(d1−d2)+(d3−d4)+⋯+(d2t−1−d2t).(d_1-d_2)+(d_3-d_4)+\cdots+(d_{2t-1}-d_{2t}).В първия случай t≤1011t\le1011, а във втория t≤1010t\le1010. Следователно достигането на целта е еквивалентно на съществуването на равенство∑i=1nrβi=∑i=1n−1rγi,\sum_{i=1}^{n} r^{\beta_i}=\sum_{i=1}^{n-1} r^{\gamma_i},βi,γi∈Z,(1)\qquad \beta_i,\gamma_i\in\mathbb Z,\tag{1}за някое n≤1011n\le1011. Ако такова равенство съществува за по-малко nn, можем да добавяме еднакви членове към двете страни, така че е достатъчно да разглеждаме n=1011n=1011. Обратно, от равенство от вида (1) Алиса може да построи съответната последователност от разстояния и да я реализира чрез ходове. Нека r=a/br=a/b е несъкратима дроб и да предположим, че (1) е изпълнено. След умножаване с общ знаменател и прехвърляне на всички членове вляво получаваме равенство от вида∑i=12n−1εiaμibN−μi=0,\sum_{i=1}^{2n-1}\varepsilon_i a^{\mu_i}b^{N-\mu_i}=0,където εi∈{−1,1}\varepsilon_i\in\{-1,1\}, μi∈{0,1,…,N}\mu_i\in\{0,1,\ldots,N\}, а сред показателите има и 00, и NN. Редуцираме по модул a−ba-b. Тогава a≡ba\equiv b и поради това лявата страна е сравнима с ±bN\pm b^N по модул a−ba-b. Понеже gcd⁡(a−b,b)=1\gcd(a-b,b)=1, получаваме a−b=1a-b=1. Сега редуцираме по модул a+ba+b. Тогава a≡−ba\equiv -b и равенството даваSbN≡0(moda+b),S b^N\equiv0\pmod {a+b},където SS е нечетно ненулево цяло число с ∣S∣≤2n−1|S|\le2n-1. От gcd⁡(a+b,b)=1\gcd(a+b,b)=1 следва a+b∣Sa+b\mid S, така че a+b≤2n−1a+b\le2n-1. Понеже вече знаем, че a=b+1a=b+1, получаваме2b+1≤2n−1,2b+1\le2n-1,тоест b≤n−1≤1010b\le n-1\le1010. Остава да покажем, че всички тези числа работят. Нека 1≤b≤10101\le b\le1010 и a=b+1a=b+1. В (1) вземаме n=an=a, всички βi=0\beta_i=0 и всички γi=1\gamma_i=1. Тогава1+1+⋯+1⏟a пъти=a=b⋅ab=r+r+⋯+r⏟b пъти.\underbrace{1+1+\cdots+1}_{a\text{ пъти}}=a=b\cdot\frac ab=\underbrace{r+r+\cdots+r}_{b\text{ пъти}}.При нужда добавяме еднакви членове към двете страни, за да стигнем до n=1011n=1011. Това дава стратегия с най-много 20212021 хода.
Отвори задачатаMathNetISL 2021 N4Условие — източник

Задача N5

Пълен запис
Условие
Докажете, че съществуват само краен брой четворки (a,b,c,n)(a,b,c,n) от положителни цели числа, за коитоn≠an−1+bn−1+cn−1.n\neq{}a^{n-1}+b^{n-1}+c^{n-1}.
РешениеЗа фиксирано nn решенията са краен брой, така че е достатъчно да докажем, че няма решения при n>100n\gt{}100. Нека n>100n\gt{}100. По неравенството между средно аритметично и средно геометрично,n≠2n(n−1)(n−2)(n−3)(3⋅4⋯(n−4))<n\neq{}2n(n-1)(n-2)(n-3)(3\cdot4\cdots(n-4))\lt{}(n−12)n−1.\left(\frac{n-1}{2}\right)^{n-1}.Следователноa,b,c<n−12.a,b,c\lt{}\frac{n-1}{2}.За просто число pp и ненулево цяло число mm означаваме с νp(m)\nu_p(m) pp-адичната валуация на mm. От формулата на Лежандр следва оценкатаνp(n!)=∑s≥1⌊nps⌋<np−1.(1)\nu_p(n!)=\sum_{s\ge1}\left\lfloor\frac n{p^s}\right\rfloor\lt{}\frac n{p-1}.\tag{1}Първо нека nn е нечетно. Тогава an−1a^{n-1}, bn−1b^{n-1} и cn−1c^{n-1} са квадрати. По модул 44 сбор от три квадрата може да е 00 само ако и трите квадрата са 00 по модул 44, затова a,b,ca,b,c са четни. Тогава 2n−1∣n!2^{n-1}\mid n!, което противоречи на (1) за p=2p=2. Оттук нататък нека nn е четно. Да предположим първо, че и трите числа a+ba+b, b+cb+c, c+ac+a са степени на 22. Тогава a,b,ca,b,c имат еднаква четност. Ако са нечетни, дясната страна на уравнението е нечетна, невъзможно. Ако всички се делят на 44, отново получаваме твърде висока 22-адична валуация на n!n!. Остава случаят, в който поне едно от тях, например aa, не се дели на 44. Тогава2a=(a+b)+(a+c)−(b+c)2a=(a+b)+(a+c)-(b+c)не се дели на 88, така че една от трите степени на 22 трябва да е равна на 44. Следователно две от числата a,b,ca,b,c са равни на 22; нека a=b=2a=b=2. Тогава c=2r−2c=2^r-2 за някое rr, а понеже c<nc\lt{}n, числото cc дели n!n!. От уравнението по модул cc следва c∣2nc\mid2^n, откъдето c=2c=2. Но тогава дясната страна е 3⋅2n−13\cdot2^{n-1}, което не е сравнимо с 00 по модул 55, докато 5∣n!5\mid n!. Противоречие. Значи поне един от сборовете, например a+ba+b, не е степен на 22. Нека pp е нечетен прост делител на a+ba+b. Тогава p≤a+b<np\le a+b\lt{}n, следователно p∣n!p\mid n!. Понеже n−1n-1 е нечетно,an−1+bn−1≡0(modp),a^{n-1}+b^{n-1}\equiv0\pmod p,а от уравнението получаваме p∣cp\mid c. Ако pp дели едновременно aa и bb, тогава pp дели и cc, така че pn−1∣n!p^{n-1}\mid n!, в противоречие с (1). Следователно можем да приложим лемата за повдигане на показателя:νp(n!)=νp(n!−cn−1)=\nu_p(n!)=\nu_p(n!-c^{n-1})=νp(an−1+bn−1)=νp(a+b)+νp(n−1).(2)\nu_p(a^{n-1}+b^{n-1})=\nu_p(a+b)+\nu_p(n-1).\tag{2}Равенството (2) означава, че сред числата 1,2,…,n1,2,\ldots,n кратните на pp могат да бъдат само a+ba+b и n−1n-1, като n−1>a+bn-1\gt{}a+b. От друга страна p∣cp\mid c и c<(n−1)/2c\lt{}(n-1)/2, затова p<n/2p\lt{}n/2 и сред 1,2,…,n1,2,\ldots,n има поне две кратни на pp. Следователно те трябва да са точно pp и 2p2p, т.е. a+b=pa+b=p и n−1=2pn-1=2p. Това е невъзможно, защото nn е четно и n−1n-1 е нечетно. Полученото противоречие показва, че решения при n>100n\gt{}100 няма. Следователно общият брой решения е краен.
Отвори задачатаMathNetISL 2021 N5Условие — източник

Задача N6

Пълен запис
Условие
Да се определят всички цели числа n≥2n\ge2 със следното свойство: всеки nn по двойки различни цели числа, чийто сбор не се дели на nn, могат да се подредят в някакъв ред a1,a2,…,ana_1,a_2,\ldots,a_n така, чеn∣1⋅a1+2⋅a2+⋯+n⋅an.n\mid 1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.
РешениеОтговорът е: всички нечетни цели числа и всички степени на 22. Първо изключваме останалите nn. Нека n=2kan=2^k a, където a≥3a\ge3 е нечетно, а k≥1k\ge1. Вземаме множество от nn различни цели числа, едно от които е сравнимо с 2k+12^k+1 по модул nn, а останалите n−1n-1 са сравними с 11 по модул nn. Сборът им е сравним с 2k2^k по модул nn, така че не се дели на nn. За всяка подредба обаче всички избрани числа са сравними с 11 по модул 2k2^k, следователно1a1+2a2+⋯+nan≡1a_1+2a_2+\cdots+na_n\equiv1+2+⋯+n=2k−1a(2ka+1)≢0(mod2k).1+2+\cdots+n=2^{k-1}a(2^ka+1)\not\equiv0\pmod {2^k}.Значи търсената делимост по модул nn е невъзможна. Остава да докажем, че всички нечетни nn и всички степени на 22 работят. Нека SS е даденото множество, а ss - сборът на елементите му. Лема 1. Ако съществува подредба (ai)(a_i) на SS, за която gcd⁡(n,s)\gcd(n,s) дели ∑i=1niai\sum_{i=1}^n ia_i, то съществува подредба (bi)(b_i) на SS, за която nn дели ∑i=1nibi\sum_{i=1}^n ib_i. Доказателство. Нека r=∑iair=\sum ia_i и разглеждаме цикличното преместване bi=ai+xb_i=a_{i+x}, където индексите са по модул nn. Тогава∑i=1nibi≡∑i=1n(i−x)ai≡r−sx(modn).\sum_{i=1}^n ib_i\equiv\sum_{i=1}^n (i-x)a_i\equiv r-sx\pmod n.Понеже gcd⁡(n,s)∣r\gcd(n,s)\mid r, сравнението r−sx≡0(modn)r-sx\equiv0\pmod n има решение за xx. Лемата е доказана. Лема 2. Всяко множество TT от kmkm цели числа, където m>1m\gt{}1, може да се разбие на mm множества по kk числа така, че във всяко от тях или сборът не се дели на kk, или всички елементи имат един и същи остатък по модул kk. Доказателство. Първо нека m=2m=2. Ако в TT има kk елемента с еднакъв остатък по модул kk, отделяме ги в множество AA, а останалите образуват BB. Ако сборът на BB не се дели на kk, сме готови. Иначе разменяме елемент от AA с елемент от BB с различен остатък; така сборовете и на двете множества стават неделими на kk. Това е невъзможно само ако всички елементи на TT са сравними по модул kk, а тогава всяко разбиване върши работа. Ако няма kk елемента с един и същи остатък по модул kk, има три елемента a,b,ca,b,c с различни по двойки остатъци. Нека tt е сборът на всички елементи на TT. Достатъчно е да намерим A⊂TA\subset T с ∣A∣=k|A|=k и∑x∈Ax≢0,t(modk),\sum_{x\in A}x\not\equiv0,t\pmod k,защото тогава нито AA, нито допълнението му има сбор, делящ се на kk. Вземаме произволно U⊂T∖{a,b,c}U\subset T\setminus\{a,b,c\} с ∣U∣=k−1|U|=k-1. Сборовете на U∪{a}U\cup\{a\}, U∪{b}U\cup\{b\} и U∪{c}U\cup\{c\} дават три различни остатъка по модул kk, така че поне един от тях не е нито 00, нито tt. За m>2m\gt{}2 доказваме с индукция. Ако има kk елемента с еднакъв остатък по модул kk, отделяме ги и прилагаме индукционното предположение към останалите k(m−1)k(m-1) елемента. Ако няма, избираме произволно U⊂TU\subset T с ∣U∣=k−1|U|=k-1. Останалите елементи не могат всички да имат един и същи остатък, затова можем да намерим a∈T∖Ua\in T\setminus U сa≢−∑x∈Ux(modk).a\not\equiv-\sum_{x\in U}x\pmod k.Тогава U∪{a}U\cup\{a\} има сбор, неделим на kk, и довършваме с индукция. Сега доказваме твърдението с индукция по nn. Ако nn е просто, то gcd⁡(n,s)=1\gcd(n,s)=1, така че Лема 1 веднага дава резултата. Нека nn е нечетно или степен на 22. Избираме просто число pp и цяло tt, за които pt∣np^t\mid n, но pt∤sp^t\nmid s. Пишем k=n/pk=n/p. Тогава gcd⁡(n,s)∣k\gcd(n,s)\mid k. По Лема 2 разбиваме SS на pp множества по kk елемента. За всяко множество от първия вид индукционното предположение дава подредба (ai)(a_i) сk∣∑i=1kiai.k\mid\sum_{i=1}^k ia_i.Ако nn е нечетно, тогава и kk е нечетно. За множество от втория вид произволна подредба (bi)(b_i) удовлетворява∑i=1kibi≡b1k(k+1)2≡0(modk).\sum_{i=1}^k ib_i\equiv b_1\frac{k(k+1)}2\equiv0\pmod k.Поставяйки получените блокове един след друг, получаваме подредба (ci)(c_i) на SS сk∣∑i=1nici.k\mid\sum_{i=1}^n ic_i.Понеже gcd⁡(n,s)∣k\gcd(n,s)\mid k, Лема 1 завършва нечетния случай. Остава n=2qn=2^q. Тогава p=2p=2 и k=2q−1k=2^{q-1}. За всяко от двете множества в разбиването има подредба (a1,…,ak)(a_1,\ldots,a_k), за която∑i=1kiai≡0(modk/2);\sum_{i=1}^k ia_i\equiv0\pmod {k/2};за множества от първия вид имаме дори делимост на kk, а за множества от втория вид това следва от∑i=1kiai≡a1k(k+1)2≡0(modk/2).\sum_{i=1}^k ia_i\equiv a_1\frac{k(k+1)}2\equiv0\pmod {k/2}.Следователно, ако поставим едната подредба на нечетните, а другата на четните места, съответните приноси са делими на kk:∑i=1k(2i−1)ai≡∑i=1k2iai≡\sum_{i=1}^k (2i-1)a_i\equiv\sum_{i=1}^k 2ia_i\equiv2∑i=1kiai≡0(modk).2\sum_{i=1}^k ia_i\equiv0\pmod k.Така отново намираме подредба (ci)(c_i) на SS с k∣∑icik\mid\sum ic_i, а Лема 1 завършва доказателството.
Отвори задачатаMathNetISL 2021 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека a1,a2,a3,…a_1,a_2,a_3,\ldots е безкрайна редица от положителни цели числа такава, че an+2ma_{n+2m} дели an+an+ma_n+a_{n+m} за всички положителни цели числа nn и mm. Докажете, че редицата е периодична от някой член нататък, т.е. съществуват положителни цели числа NN и dd такива, че an=an+da_n=a_{n+d} за всички n>Nn\gt{}N.
РешениеЩе използваме многократно следното просто наблюдение. Лема 1. Ако положително цяло число dd дели ana_n и an−ma_{n-m} за някои mm и n>2mn\gt{}2m, то dd дели an−2ma_{n-2m}. Ако dd дели ana_n и an−2ma_{n-2m}, то dd дели an−ma_{n-m}. Наистина, от условието an∣an−2m+an−ma_n\mid a_{n-2m}+a_{n-m}, и двете твърдения следват веднага. Първо ще докажем, че редицата е ограничена. Да допуснем противното. Тогава има безкрайно много индекси nn, за които ana_n е по-голямо от всички предишни членове. Нека an=ka_n=k е такъв член и n>10n\gt{}10. За всяко s<n/2s\lt{}n/2 числото k=ank=a_n дели an−s+an−2sa_{n-s}+a_{n-2s}, а този сбор е по-малък от 2k2k, следователноan−s+an−2s=k.a_{n-s}+a_{n-2s}=k.В частностan=an−1+an−2=an−2+an−4=an−4+an−8,a_n=a_{n-1}+a_{n-2}=a_{n-2}+a_{n-4}=a_{n-4}+a_{n-8},откъдето an−1=an−4a_{n-1}=a_{n-4} и an−2=an−8a_{n-2}=a_{n-8}. По Лема 1 числото an−1a_{n-1} дели всички an−1−3sa_{n-1-3s} с 3s<n−13s\lt{}n-1, а an−2a_{n-2} дели всички an−2−6sa_{n-2-6s} с 6s<n−26s\lt{}n-2. Поне едно от an−1a_{n-1} и an−2a_{n-2} е поне k/2k/2, затова някой от първите шест члена на редицата е поне k/2k/2. Понеже такива рекордни kk могат да бъдат произволно големи, получаваме противоречие. Значи редицата е ограничена. Следователно има краен брой стойности, които се срещат само краен брой пъти. Отрязваме начален сегмент на редицата така, че всяка стойност, която се среща след това, да се среща безкрайно много пъти. Условието се запазва, така че е достатъчно да докажем периодичност за тази опашка. Нека KK е най-голямата стойност в нея. Лема 2. Ако положително цяло число dd дели някой член на редицата, то индексите ii, за които d∣aid\mid a_i, образуват аритметична прогресия с нечетна разлика. Нека тези индекси саi1<i2<i3<⋯ .i_1\lt{}i_2\lt{}i_3\lt{}\cdots.Ако iji_j и ij+1i_{j+1} имат една и съща четност, Лема 1 дава делимост на междинния член a(ij+ij+1)/2a_{(i_j+i_{j+1})/2} от dd, което противоречи на последователността на списъка. Значи съседните индекси са с различна четност, а iji_j и ij+2i_{j+2} имат една и съща четност. Отново по Лема 1, dd дели a(ij+ij+2)/2a_{(i_j+i_{j+2})/2}, следователно този индекс е точно ij+1i_{j+1}. Така индексите образуват аритметична прогресия с нечетна разлика. Остава финалната стъпка. Броят на всички положителни делители на членовете на ограничената редица е краен. За всеки такъв делител ss нека δs\delta_s е разликата на аритметичната прогресия от Лема 2, т.е. s∣ais\mid a_i тогава и само тогава, когато s∣ai+δss\mid a_{i+\delta_s}. НекаD=∏sδs.D=\prod_s \delta_s.Тогава за всеки делител ss и всеки индекс ii имамеs∣ai⟺s∣ai+D.s\mid a_i\Longleftrightarrow s\mid a_{i+D}.Следователно aia_i и ai+Da_{i+D} имат едни и същи положителни делители. Значи ai=ai+Da_i=a_{i+D} за всяко ii в разглежданата опашка, което доказва евентуалната периодичност.
Отвори задачатаMathNetISL 2021 N7Условие — източник

Задача N8

Пълен запис
Условие
За полином P(x)P(x) с цели коефициенти нека P1(x)=P(x)P^1(x)=P(x) и Pk+1(x)=P(Pk(x))P^{k+1}(x)=P(P^k(x)) за k≥1k\ge1. Да се намерят всички положителни цели числа nn, за които съществува полином P(x)P(x) с цели коефициенти такъв, че за всяко цяло m≥1m\ge1 числатаPm(1),Pm(2),…,Pm(n)P^m(1),P^m(2),\ldots,P^m(n)дават точно ⌈n/2m⌉\left\lceil n/2^m\right\rceil различни остатъка при деление на nn.
РешениеОтговорът е: всички степени на 22 и всички прости числа. Означаваме множеството от остатъци по модул ℓ\ell с Zℓ\mathbb Z_\ell. Полиномът PP задава функция Zℓ→Zℓ\mathbb Z_\ell\to\mathbb Z_\ell за всяко положително цяло ℓ\ell. Некаfm,ℓ=∣Pm(Zℓ)∣.f_{m,\ell}=|P^m(\mathbb Z_\ell)|.Условието е еквивалентно наfm+1,n=⌈fm,n2⌉(m≥0),f_{m+1,n}=\left\lceil\frac{f_{m,n}}2\right\rceil\qquad(m\ge0),където f0,n=nf_{0,n}=n. Първо ще построим примери. Ако nn е степен на 22, върши работа P(x)=2xP(x)=2x. Ако n=pn=p е нечетно просто число, всяка функция Zp→Zp\mathbb Z_p\to\mathbb Z_p се задава от полином с цели коефициенти; избираме функцията, която на остатъка x∈{0,1,…,p−1}x\in\{0,1,\ldots,p-1\} съпоставя ⌊x/2⌋\lfloor x/2\rfloor. Тогава размерът на образа се дели на две със закръгляне нагоре при всяка итерация. Сега ще докажем, че други nn няма. Нека първо n=abn=ab, където a,b>1a,b\gt{}1 и gcd⁡(a,b)=1\gcd(a,b)=1. По Китайската теорема за остатъцитеfm,ab=fm,afm,b.f_{m,ab}=f_{m,a}f_{m,b}.Ако за някое ℓ\ell имаме fm,ℓ=fm+1,ℓf_{m,\ell}=f_{m+1,\ell}, тогава PP пермутира образа Pm(Zℓ)P^m(\mathbb Z_\ell) и оттук fs,ℓ=fm,ℓf_{s,\ell}=f_{m,\ell} за всички s>ms\gt{}m. Понеже fm,abf_{m,ab} накрая става 11, за всяко mm имаме или fm,a>fm+1,af_{m,a}\gt{}f_{m+1,a}, или fm,a=1f_{m,a}=1, и същото за bb. Избираме най-малкото mm, за което fm+1,a=1f_{m+1,a}=1 или fm+1,b=1f_{m+1,b}=1. Без ограничение нека fm+1,a=1f_{m+1,a}=1. Тогаваfm+1,ab=fm+1,b<fm,b≤fm,ab2≤fm+1,ab,f_{m+1,ab}=f_{m+1,b}\lt{}f_{m,b}\le\frac{f_{m,ab}}2\le f_{m+1,ab},противоречие. Значи nn трябва да е степен на просто число. Остава да изключим нечетните прости степени, които не са прости. Нека n=pkn=p^k, където p≥3p\ge3 е просто и k≥2k\ge2. За остатък rr по модул pp некаSr={x∈Zpk:x≡r(modp)}.S_r=\{x\in\mathbb Z_{p^k}:x\equiv r\pmod p\}.Ще използваме следното наблюдение. За всеки rr или ∣P(Sr)∣=pk−1|P(S_r)|=p^{k-1}, или ∣P(Sr)∣≤pk−2|P(S_r)|\le p^{k-2}. Наистина, ако p∣P′(r)p\mid P'(r), то за x=r+psx=r+ps имаме P(x)≡P(r)(modp2)P(x)\equiv P(r)\pmod {p^2}, така че образът има най-много pk−2p^{k-2} елемента. Ако p∤P′(r)p\nmid P'(r), то за x,y≡r(modp)x,y\equiv r\pmod p отP(x)−P(y)=(x−y)Q(x,y),P(x)-P(y)=(x-y)Q(x,y),Q(x,y)≡P′(r)≢0(modp)\qquad Q(x,y)\equiv P'(r)\not\equiv0\pmod pследва, че P(x)≡P(y)(modpk)P(x)\equiv P(y)\pmod {p^k} е възможно само при x≡y(modpk)x\equiv y\pmod {p^k}. Значи PP е инективен върху SrS_r и ∣P(Sr)∣=pk−1|P(S_r)|=p^{k-1}. Тъй като при достатъчно големи итерации образът има един елемент, съществува най-малко mm, за което за някое rr имаме ∣Pm−1(Sr)∣=pk−1|P^{m-1}(S_r)|=p^{k-1}, но ∣Pm(Sq)∣≤pk−2|P^m(S_q)|\le p^{k-2} за всеки остатък qq по модул pp. Фиксираме такива mm и rr и поставямеa=∣Pm(Zpk)∖Pm(Sr)∣.a=|P^m(\mathbb Z_{p^k})\setminus P^m(S_r)|.Образът на Pm−1(Zpk)∖Pm−1(Sr)P^{m-1}(\mathbb Z_{p^k})\setminus P^{m-1}(S_r) чрез PP съдържа Pm(Zpk)∖Pm(Sr)P^m(\mathbb Z_{p^k})\setminus P^m(S_r), следователноa≤∣Pm−1(Zpk)∖Pm−1(Sr)∣.a\le |P^{m-1}(\mathbb Z_{p^k})\setminus P^{m-1}(S_r)|.Затоваa+pk−1≤fm−1,pk≤2fm,pk≤2pk−2+2a,a+p^{k-1}\le f_{m-1,p^k}\le2f_{m,p^k}\le2p^{k-2}+2a,и получаваме(p−2)pk−2≤a.(1)(p-2)p^{k-2}\le a.\tag{1}Разглеждаме индуцираната функция по модул pp. Понеже образите и там накрая стават едноточкови, има единствен остатък tt с P(t)≡t(modp)P(t)\equiv t\pmod p. Освен това множествата{x∈Zp:Pi(x)≡t(modp)}\{x\in\mathbb Z_p:P^i(x)\equiv t\pmod p\}строго нарастват, докато станат цялото Zp\mathbb Z_p. Следователно или fm−1,p=1f_{m-1,p}=1, или има множество X⊂ZpX\subset\mathbb Z_p с ∣X∣≥m|X|\ge m, за което Pm−1(x)≡t(modp)P^{m-1}(x)\equiv t\pmod p за всички x∈Xx\in X. В първия случай Pm−1(Zpk)P^{m-1}(\mathbb Z_{p^k}) има най-много pk−1p^{k-1} елемента и всички са в един клас StS_t, докато Pm−1(Sr)P^{m-1}(S_r) вече има pk−1p^{k-1} елемента. Значи a=0a=0, което противоречи на (1). Във втория случай нека YY е обединението на класовете SxS_x за x∈Xx\in X, а Z=Zpk∖YZ=\mathbb Z_{p^k}\setminus Y. Тогава Pm−1(Y)⊂StP^{m-1}(Y)\subset S_t, а P(St)P(S_t) е собствено подмножество на StS_t, следователно ∣P(St)∣≤pk−2|P(S_t)|\le p^{k-2}. Освен това всеки от останалите класове има образ с най-много pk−2p^{k-2} елемента на тази стъпка. Така∣Pm(Y)∣≤pk−2,∣Pm(Z)∣≤(p−m)pk−2.|P^m(Y)|\le p^{k-2},\qquad |P^m(Z)|\le(p-m)p^{k-2}.Оттук и (1) дават(p−2)pk−2≤a<∣Pm(Zpk)∣≤(p−m+1)pk−2,(p-2)p^{k-2}\le a\lt{}|P^m(\mathbb Z_{p^k})|\le(p-m+1)p^{k-2},следователно m<3m\lt{}3. Значи ∣P2(Sq)∣≤pk−2|P^2(S_q)|\le p^{k-2} за всички qq, откъдетоpk4≤∣P2(Zpk)∣≤pk−1.\frac{p^k}{4}\le |P^2(\mathbb Z_{p^k})|\le p^{k-1}.Това е невъзможно за p≥5p\ge5. Остава случаят p=3p=3. Нека tt е единственият неподвижен остатък по модул 33. Ако 3∤P′(t)3\nmid P'(t), тогава по наблюдението P(St)=StP(S_t)=S_t, което е невъзможно. Значи 3∣P′(t)3\mid P'(t). От разлаганетоP(t+h)=P(t)+hP′(t)+h2Q(t,h)P(t+h)=P(t)+hP'(t)+h^2Q(t,h)с h=3ish=3^is следваP(t+3is)≡P(t)(mod3i+1).P(t+3^is)\equiv P(t)\pmod {3^{i+1}}.По индукция всички елементи на Pi(St)P^i(S_t) са сравними по модул 3i+13^{i+1}, така че ∣Pk−1(St)∣=1|P^{k-1}(S_t)|=1. Понеже f1,3≤2f_{1,3}\le2 и f2,3≤1f_{2,3}\le1, имаме P2(Z3)⊂StP^2(\mathbb Z_3)\subset S_t. Следователно∣Pk+1(Z3k)∣≤∣Pk−1(St)∣=1.|P^{k+1}(\mathbb Z_{3^k})|\le |P^{k-1}(S_t)|=1.Но условието би дало ⌈3k/2k+1⌉≤1\left\lceil 3^k/2^{k+1}\right\rceil\le1, тоест 3k≤2k+13^k\le2^{k+1}, което е невъзможно за k≥2k\ge2. Така нечетните съставни прости степени също са изключени.
Отвори задачатаMathNetISL 2021 N8Условие — източник