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

IMO Shortlisted Problems

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

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

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

2017

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

11-12

24 задачи

Задача A1

Пълен запис
Условие
Нека a1,a2,…,an,ka_1,a_2,\ldots,a_n,k и MM са положителни цели числа, за които1a1+1a2+⋯+1an=kиa1a2⋯an=M.\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}=k\qquad\text{и}\qquad a_1a_2\cdots a_n=M.Ако M>1M\gt{}1, докажете, че полиномътP(x)=M(x+1)k−(x+a1)(x+a2)⋯(x+an)P(x)=M(x+1)^k-(x+a_1)(x+a_2)\cdots(x+a_n)няма положителни корени.
РешениеЩе докажем, че всъщност P(x)<0P(x)\lt{}0 за всяко x>0x\gt{}0. За всяко ii имамеai(x+1)1/ai≤x+ai.(1)a_i(x+1)^{1/a_i}\le x+a_i.\tag{1}Ако ai=1a_i=1, това е равенство. Ако ai>1a_i\gt{}1, прилагаме неравенството между средно аритметично и средно геометрично към числата x+1,1,1,…,1x+1,1,1,\ldots,1, където единиците са ai−1a_i-1 на брой. Получавамеx+1+(ai−1)ai≥((x+1)⋅1ai−1)1/ai,\frac{x+1+(a_i-1)}{a_i}\ge ((x+1)\cdot1^{a_i-1})^{1/a_i},тоест (1). Понеже x+1>1x+1\gt{}1, равенството в този случай е невъзможно. Умножавайки (1) за i=1,2,…,ni=1,2,\ldots,n, получавамеa1a2⋯an (x+1)1a1+⋯+1an≤a_1a_2\cdots a_n\,(x+1)^{\frac1{a_1}+\cdots+\frac1{a_n}}\le(x+a1)(x+a2)⋯(x+an), (x+a_1)(x+a_2)\cdots(x+a_n),илиM(x+1)k≤(x+a1)(x+a2)⋯(x+an).M(x+1)^k\le (x+a_1)(x+a_2)\cdots(x+a_n).Равенство би имало само ако a1=a2=⋯=an=1a_1=a_2=\cdots=a_n=1, но тогава M=1M=1, което противоречи на условието. Следователно неравенството е строго и P(x)<0P(x)\lt{}0 за всяко x>0x\gt{}0. Значи PP няма положителни корени.
Отвори задачатаMathNetISL 2017 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека qq е реално число. Гугу има салфетка, върху която са написани десет различни реални числа, и записва на дъската следните три реда от реални числа: - На първия ред Гугу записва всяко число от вида a−ba-b, където aa и bb са две, не непременно различни, числа от салфетката. - На втория ред Гугу записва всяко число от вида qabqab, където aa и bb са две, не непременно различни, числа от първия ред. - На третия ред Гугу записва всяко число от вида a2+b2−c2−d2a^2+b^2-c^2-d^2, където a,b,c,da,b,c,d са четири, не непременно различни, числа от първия ред. Да се определят всички стойности на qq, за които, независимо от числата върху салфетката на Гугу, всяко число от втория ред се среща и на третия ред.
РешениеОтговорът еq∈{−2,0,2}.q\in\{-2,0,2\}.Ще казваме, че qq е добро, ако условието е изпълнено за всяка възможна салфетка. Числото 00 е добро, защото третият ред винаги съдържа 00. Нека aa и bb са числа от първия ред. Тогава a=x−ya=x-y и b=u−vb=u-v за някои числа x,y,u,vx,y,u,v от салфетката. Имаме тъждеството2ab=2(x−y)(u−v)=2ab=2(x-y)(u-v)=(x−v)2+(y−u)2−(x−u)2−(y−v)2.(x-v)^2+(y-u)^2-(x-u)^2-(y-v)^2.Следователно 2ab2ab е число от третия ред, т.е. 22 е добро. Като сменим ролите на първите две и последните две квадратични събираеми, получаваме и −2ab-2ab, така че −2-2 също е добро. Остава да докажем, че други добри числа няма. Да допуснем, че qq е добро и q∉{−2,0,2}q\notin\{-2,0,2\}. Нека върху салфетката са числата 1,2,…,101,2,\ldots,10. Тогава първият ред съдържа всички цели числа от −9-9 до 99, а вторият ред съдържа qq и 81q81q. Третият ред съдържа само цели числа, следователно qq е цяло. Освен това числата на третия ред са между −162-162 и 162162, понеже всяка разлика на две числа от салфетката е по абсолютна стойност най-много 99. Значи−162≤81q≤162,-162\le81q\le162,така че при вече изключените −2,0,2-2,0,2 остават само q=±1q=\pm1. Нека сега върху салфетката са числата0,1,4,8,12,16,20,24,28,32.0,1,4,8,12,16,20,24,28,32.Първият ред съдържа ±1\pm1 и ±4\pm4, затова при q=±1q=\pm1 вторият ред съдържа ±4\pm4. Но всяко число aa от първия ред не е сравнимо с 22 по модул 44, следователно a2≡0a^2\equiv0 или 1(mod8)1\pmod8. Значи всяко число от третия ред е сравнимо с едно от−2,−1,0,1,2(mod8),-2,-1,0,1,2\pmod8,а ±4≡4(mod8)\pm4\equiv4\pmod8 не може да се получи. Това противоречие изключва q=±1q=\pm1. Следователно единствените добри стойности са −2,0,2-2,0,2.
Отвори задачатаMathNetISL 2017 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека SS е крайно множество и нека A\mathcal A е множеството от всички функции от SS в SS. Нека f∈Af\in\mathcal A и нека T=f(S)T=f(S) е образът на SS при ff. Да се предположи, чеf∘g∘f≠g∘f∘gf\circ g\circ f\ne g\circ f\circ gза всяко g∈Ag\in\mathcal A с g≠fg\ne f. Докажете, че f(T)=Tf(T)=T.
РешениеЩе използваме означението fnf^n за nn-кратната композиция на ff със себе си. Условието казва, че ако за някое g∈Ag\in\mathcal A е изпълненоf∘g∘f=g∘f∘g,f\circ g\circ f=g\circ f\circ g,то непременно g=fg=f. Първо ще докажем следното. Ако за някое n≥3n\ge3 имамеfn+2=f2n+1,(1)f^{n+2}=f^{2n+1},\tag{1}то ограничението f:T→Tf:T\to T е биекция. Наистина, (1) може да се запише катоf∘fn∘f=fn∘f∘fn,f\circ f^n\circ f=f^n\circ f\circ f^n,следователно от условието получаваме fn=ff^n=f. Тъй като n−2≥1n-2\ge1, функцията fn−2f^{n-2} изпраща TT в TT. За t=f(s)∈Tt=f(s)\in T имамеfn−2(f(t))=fn(s)=f(s)=tf^{n-2}(f(t))=f^n(s)=f(s)=tи същоf(fn−2(t))=fn(s)=t.f(f^{n-2}(t))=f^n(s)=t.Значи fn−2:T→Tf^{n-2}:T\to T е обратна на f:T→Tf:T\to T, така че ff е биекция върху TT. Остава да намерим такова nn. НекаSm=fm(S)(m≥0).S_m=f^m(S)\qquad(m\ge0).ТогаваS⊇S1⊇S2⊇⋯S\supseteq S_1\supseteq S_2\supseteq\cdotsе низходяща верига от подмножества на крайното множество SS, затова се стабилизира: съществува k≥1k\ge1, за коетоSk=Sk+1=Sk+2=⋯=:S∞.S_k=S_{k+1}=S_{k+2}=\cdots=:S_\infty.Ограничението на ff върху S∞S_\infty е сюрекция от крайно множество в себе си, следователно е биекция. Значи за някое r≥1r\ge1 имаме fr=id⁡f^r=\operatorname{id} върху S∞S_\infty. Оттукfm+r=fmза всички m≥k.(2)f^{m+r}=f^m\qquad\text{за всички }m\ge k.\tag{2}Избираме n=2kr+1n=2kr+1. Тогава n≥3n\ge3, n+2=2kr+3≥kn+2=2kr+3\ge k, а(2n+1)−(n+2)=2kr(2n+1)-(n+2)=2krе кратно на rr. От (2) следва fn+2=f2n+1f^{n+2}=f^{2n+1}. По доказаното по-горе f:T→Tf:T\to T е биекция, т.е. f(T)=Tf(T)=T.
Отвори задачатаMathNetISL 2017 A3Условие — източник

Задача A4

Пълен запис
Условие
Редица от реални числа a1,a2,…a_1,a_2,\ldots удовлетворява равенствотоan=−max⁡i+j=n(ai+aj)за всички n>2017.a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{за всички }n\gt{}2017.Докажете, че тази редица е ограничена, т.е. съществува константа MM, за която ∣an∣≤M|a_n|\le M за всяко положително цяло число nn.
РешениеПолагаме D=2017D=2017 и за n≥2n\ge2 означавамеMn=max⁡k<nak,mn=−min⁡k<nak=max⁡k<n(−ak).M_n=\max_{k\lt{}n}a_k,\qquad m_n=-\min_{k\lt{}n}a_k=\max_{k\lt{}n}(-a_k).Редиците (Mn)(M_n) и (mn)(m_n) са ненамаляващи. Ще докажем, че и двете са ограничени. Нека n>Dn\gt{}D. От дефиницията на ana_n съществуват p,qp,q с p+q=np+q=n иan=−(ap+aq).a_n=-(a_p+a_q).Понеже ap,aq≤Mna_p,a_q\le M_n, получавамеan≥−2Mn.(1)a_n\ge -2M_n.\tag{1}От друга страна, ако k<nk\lt{}n е такова, че ak=Mna_k=M_n, тогаваan≤−(an−k+ak)=−an−k−Mn≤mn−Mn.(2)a_n\le -(a_{n-k}+a_k)=-a_{n-k}-M_n\le m_n-M_n.\tag{2}От (1) и (2) следва−2Mn≤an≤mn−Mn.-2M_n\le a_n\le m_n-M_n.Затоваmn≤mn+1≤max⁡{mn,2Mn},m_n\le m_{n+1}\le\max\{m_n,2M_n\},Mn≤Mn+1≤max⁡{Mn,mn−Mn}.(3)\qquad M_n\le M_{n+1}\le\max\{M_n,m_n-M_n\}.\tag{3}Ще наричаме индекс n>Dn\gt{}D добър, ако mn≤2Mnm_n\le2M_n. Ако съществува добър индекс nn, то от (3) имаме mn+1≤2Mnm_{n+1}\le2M_n иMn+1≤max⁡{Mn,mn−Mn}≤Mn.M_{n+1}\le\max\{M_n,m_n-M_n\}\le M_n.Понеже (Mn)(M_n) е ненамаляваща, получаваме Mn+1=MnM_{n+1}=M_n и n+1n+1 също е добър. С индукция всички следващи индекси са добри, а Mk=MnM_k=M_n за k>nk\gt{}n. Тогава mk≤2Mk=2Mnm_k\le2M_k=2M_n, така че и двете редици са ограничени. Остава случаят, в който няма добър индекс, т.е. 2Mn<mn2M_n\lt{}m_n за всички n>Dn\gt{}D. Тогава от (3) следваmn≤mn+1≤mn,m_n\le m_{n+1}\le m_n,следователно mnm_n е константна за n>Dn\gt{}D. Освен това Mn<mn/2M_n\lt{}m_n/2, така че и (Mn)(M_n) е ограничена. И в двата случая числата ana_n са ограничени отгоре чрез MnM_n и отдолу чрез −mn-m_n, а първите краен брой членове не създават проблем. Следователно редицата (an)(a_n) е ограничена.
Отвори задачатаMathNetISL 2017 A4Условие — източник

Задача A5

Пълен запис
Условие
Дадено е цяло число n≥3n\ge3. Ще наричаме nn-торка от реални числа (x1,x2,…,xn)(x_1,x_2,\ldots,x_n) сияйна, ако за всяка пермутация y1,y2,…,yny_1,y_2,\ldots,y_n на тези числа имаме∑i=1n−1yiyi+1=y1y2+y2y3+⋯+yn−1yn≥\sum_{i=1}^{n-1}y_i y_{i+1}=y_1y_2+y_2y_3+\cdots+y_{n-1}y_n\ge−1. -1.Да се намери най-голямата константа K=K(n)K=K(n), за която∑1≤i<j≤nxixj≥K\sum_{1\le i\lt{}j\le n}x_i x_j\ge Kе изпълнено за всяка сияйна nn-торка (x1,x2,…,xn)(x_1,x_2,\ldots,x_n).
РешениеОтговорът еK=−n−12.K=-\frac{n-1}{2}.Първо ще покажем, че не може да се вземе по-голяма константа. Нека t>0t\gt{}0 и некаx1=−12t,x2=x3=⋯=xn=t.x_1=-\frac1{2t},\qquad x_2=x_3=\cdots=x_n=t.Всяко произведение xixjx_i x_j при i≠ji\ne j е равно или на t2t^2, или на −1/2-1/2. В произволна пермутация на тези числа най-много две съседни произведения съдържат x1x_1, затоваy1y2+⋯+yn−1yn≥(n−3)t2−1≥−1.y_1y_2+\cdots+y_{n-1}y_n\ge (n-3)t^2-1\ge -1.Следователно тази nn-торка е сияйна. Но∑i<jxixj=−n−12+(n−1)(n−2)2t2,\sum_{i\lt{}j}x_i x_j=-\frac{n-1}{2}+\frac{(n-1)(n-2)}2t^2,което клони към −(n−1)/2-(n-1)/2, когато t→0+t\to0^+. Значи KK не може да е по-голямо от −(n−1)/2-(n-1)/2. Остава да докажем долната граница. Нека (x1,…,xn)(x_1,\ldots,x_n) е сияйна. Подреждаме числата така, чеx1≤x2≤⋯≤xk≤0≤xk+1≤⋯≤xn,x_1\le x_2\le\cdots\le x_k\le0\le x_{k+1}\le\cdots\le x_n,и полагаме ℓ=n−k\ell=n-k. Ако всички числа са с един и същи знак, твърдението е очевидно. Иначе, като заменим всички xix_i с −xi-x_i, ако е нужно, можем да предполагаме, че k≥ℓk\ge\ell и k<nk\lt{}n. НекаS={1,2,…,k},T={k+1,k+2,…,n}.S=\{1,2,\ldots,k\},\qquad T=\{k+1,k+2,\ldots,n\}.ПишемK1=∑i<ji,j∈Sxixj,\begin{aligned}K_1=\sum_{\substack{i\lt{}j\\ i,j\in S}}x_i x_j,\end{aligned}M=∑i∈Sj∈Txixj,\begin{aligned}\qquad M=\sum_{\substack{i\in S\\ j\in T}}x_i x_j,\end{aligned}L=∑i<ji,j∈Txixj.\begin{aligned}\qquad L=\sum_{\substack{i\lt{}j\\ i,j\in T}}x_i x_j.\end{aligned}Тогава K1,L≥0K_1,L\ge0 и M≤0M\le0, а търсената сума е K1+M+LK_1+M+L. Първо нека k>ℓk\gt{}\ell. Разглеждаме всички пермутации φ\varphi на индексите 1,2,…,n1,2,\ldots,n, за които елементите с индекси от TT стоят точно на позициите 2,4,…,2ℓ2,4,\ldots,2\ell. За всяка такава пермутация сияйността дава∑i=1n−1xφ(i)xφ(i+1)≥−1.\sum_{i=1}^{n-1}x_{\varphi(i)}x_{\varphi(i+1)}\ge -1.Усредняваме тези неравенства по всички такива пермутации. В средната стойност всяко смесено произведение от MM се появява с коефициент 2ℓ/(kℓ)=2/k2\ell/(k\ell)=2/k, а всяко произведение от K1K_1 - с коефициент 2(k−ℓ−1)/(k(k−1))2(k-\ell-1)/(k(k-1)). Следователно−1≤2kM+2(k−ℓ−1)k(k−1)K1.-1\le \frac2k M+\frac{2(k-\ell-1)}{k(k-1)}K_1.Умножаваме по k/2k/2 и получавамеM+k−ℓ−1k−1K1≥−k2.M+\frac{k-\ell-1}{k-1}K_1\ge -\frac k2.ЗатоваK1+M+L≥−k2+ℓk−1K1+L≥−k2≥−n−12,K_1+M+L\ge -\frac k2+\frac{\ell}{k-1}K_1+L\ge -\frac k2\ge -\frac{n-1}{2},понеже k<nk\lt{}n. Остава случаят k=ℓ=n/2k=\ell=n/2. Отново усредняваме по всички пермутации, в които индексите от TT са точно на четните позиции. Тогава в съседните произведения се появяват само смесени произведения, и всяко от тях се появява с коефициент (2ℓ−1)/(kℓ)(2\ell-1)/(k\ell). Получаваме−1≤2ℓ−1kℓM,-1\le \frac{2\ell-1}{k\ell}M,следователноM≥−kℓ2ℓ−1=−n24(n−1).M\ge -\frac{k\ell}{2\ell-1}=-\frac{n^2}{4(n-1)}.Понеже n≥4n\ge4 в този случай и K1,L≥0K_1,L\ge0, имамеK1+M+L≥−n24(n−1)≥−n−12.K_1+M+L\ge -\frac{n^2}{4(n-1)}\ge -\frac{n-1}{2}.Така за всяка сияйна nn-торка е изпълнено∑i<jxixj≥−n−12,\sum_{i\lt{}j}x_i x_j\ge -\frac{n-1}{2},а началната конструкция показва, че това е най-добрата възможна константа.
Отвори задачатаMathNetISL 2017 A5Условие — източник

Задача A6

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, за коитоf(f(x)f(y))+f(x+y)=f(xy)f(f(x)f(y))+f(x+y)=f(xy)за всички x,y∈Rx,y\in\mathbb R.
РешениеОтговорът е: точно функциитеf(x)≡0,f(x)=x−1,f(x)=1−x.f(x)\equiv0,\qquad f(x)=x-1,\qquad f(x)=1-x.Лесно се проверява, че и трите удовлетворяват уравнението. Ако ff е решение, то и −f-f е решение. Затова можем да предполагаме, че f(0)≤0f(0)\le0; накрая ще върнем и противоположното решение. За фиксирано x≠1x\ne1 избираме y=x/(x−1)y=x/(x-1), така че x+y=xyx+y=xy. От уравнението следваf(f(x)f(xx−1))=0.(1)f\left(f(x)f\left(\frac{x}{x-1}\right)\right)=0.\tag{1}В частност при x=0x=0 получаваме, че ff има поне една нула:f(f(0)2)=0.(2)f(f(0)^2)=0.\tag{2}Ако f(0)=0f(0)=0, то при y=0y=0 имамеf(f(x)f(0))+f(x)=f(0),f(f(x)f(0))+f(x)=f(0),откъдето f(x)=0f(x)=0 за всяко xx. Получаваме нулевото решение. Нека вече f(0)<0f(0)\lt{}0. Ще докажем, че единствената нула на ff е 11 и че f(0)=−1f(0)=-1. Наистина, нека aa е нула на ff. Ако a≠1a\ne1, то от (1) при x=ax=a следва f(0)=0f(0)=0, противоречие. Значи a=1a=1. От (2) тогава следва f(0)2=1f(0)^2=1, а понеже f(0)<0f(0)\lt{}0, получаваме f(0)=−1f(0)=-1. При y=1y=1 уравнението даваf(f(x)f(1))+f(x+1)=f(x),f(f(x)f(1))+f(x+1)=f(x),тоестf(x+1)=f(x)+1(x∈R).(3)f(x+1)=f(x)+1\qquad(x\in\mathbb R).\tag{3}Следователноf(x+n)=f(x)+n(x∈R, n∈Z).(4)f(x+n)=f(x)+n\qquad(x\in\mathbb R,\ n\in\mathbb Z).\tag{4}Сега ще докажем, че ff е инективна. Да допуснем, че f(a)=f(b)f(a)=f(b) за a≠ba\ne b. От (4) имамеf(a+N+1)=f(b+N)+1f(a+N+1)=f(b+N)+1за всяко цяло NN. Избираме N<−bN\lt{}-b. Тогава съществуват реални x0,y0x_0,y_0, за коитоx0+y0=a+N+1,x0y0=b+N,x_0+y_0=a+N+1,\qquad x_0y_0=b+N,а понеже a≠ba\ne b, нито x0x_0, нито y0y_0 е равно на 11. Прилагането на функционалното уравнение към x0,y0x_0,y_0 даваf(f(x0)f(y0))+f(a+N+1)=f(b+N),f(f(x_0)f(y_0))+f(a+N+1)=f(b+N),следователно f(f(x0)f(y0))+1=0f(f(x_0)f(y_0))+1=0. По (3) това означаваf(f(x0)f(y0)+1)=0.f(f(x_0)f(y_0)+1)=0.Единствената нула е 11, затова f(x0)f(y0)=0f(x_0)f(y_0)=0, което отново би принудило x0=1x_0=1 или y0=1y_0=1. Противоречие. Значи ff е инективна. За произволно t∈Rt\in\mathbb R прилагаме уравнението за (t,−t)(t,-t):f(f(t)f(−t))+f(0)=f(−t2).f(f(t)f(-t))+f(0)=f(-t^2).Понеже f(0)=−1f(0)=-1 и по (3) имаме f(u)+1=f(u+1)f(u)+1=f(u+1), следваf(f(t)f(−t))=f(1−t2).f(f(t)f(-t))=f(1-t^2).От инективността получавамеf(t)f(−t)=1−t2.(5)f(t)f(-t)=1-t^2.\tag{5}Също, при (t,1−t)(t,1-t) имамеf(f(t)f(1−t))+f(1)=f(t(1−t)),f(f(t)f(1-t))+f(1)=f(t(1-t)),а f(1)=0f(1)=0, така чеf(t)f(1−t)=t(1−t).(6)f(t)f(1-t)=t(1-t).\tag{6}От (3) е f(1−t)=f(−t)+1f(1-t)=f(-t)+1. Комбинирайки (5) и (6), получавамеf(t)(f(−t)+1)=t(1−t),f(t)(f(-t)+1)=t(1-t),тоест(1−t2)+f(t)=t−t2.(1-t^2)+f(t)=t-t^2.Следователно f(t)=t−1f(t)=t-1 за всяко tt. При началната възможност f(0)>0f(0)\gt{}0 прилагаме доказаното към −f-f и получаваме f(x)=1−xf(x)=1-x. Така остават точно трите функции от отговора.
Отвори задачатаMathNetISL 2017 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека a0,a1,a2,…a_0,a_1,a_2,\ldots е редица от цели числа, а b0,b1,b2,…b_0,b_1,b_2,\ldots е редица от положителни цели числа, като a0=0a_0=0, a1=1a_1=1 иan+1={anbn+an−1,ако bn−1=1,anbn−an−1,ако bn−1>1,n=1,2,….a_{n+1}=\begin{cases}a_n b_n+a_{n-1},&\text{ако }b_{n-1}=1,\\ a_n b_n-a_{n-1},&\text{ако }b_{n-1}\gt{}1, \end{cases}\qquad n=1,2,\ldots.Докажете, че поне едно от числата a2017a_{2017} и a2018a_{2018} е не по-малко от 20172017.
РешениеСтойността на b0b_0 не влияе, защото a0=0a_0=0, затова ще приемем b0=1b_0=1. Първо ще докажем лема: an≥1a_n\ge1 за всяко n≥1n\ge1. Да допуснем противното и нека n≥1n\ge1 е най-малкият индекс с an≤0a_n\le0. Тогава n≥2n\ge2, an−1≥1a_{n-1}\ge1 и an−2≥0a_{n-2}\ge0. Формулата за ana_n не може да е от видаan=an−1bn−1+an−2,a_n=a_{n-1}b_{n-1}+a_{n-2},затова е от видаan=an−1bn−1−an−2.a_n=a_{n-1}b_{n-1}-a_{n-2}.От an≤0a_n\le0 следва an−1≤an−2a_{n-1}\le a_{n-2}, т.е.an−2≥an−1≥an.a_{n-2}\ge a_{n-1}\ge a_n.Нека rr е най-малкият индекс, за койтоar≥ar+1≥ar+2.a_r\ge a_{r+1}\ge a_{r+2}.Тогава r≤n−2r\le n-2. Освен това r≥2r\ge2: ако b1=1b_1=1, то a2=1a_2=1 и a3=a2b2+a1>a2a_3=a_2b_2+a_1\gt{}a_2, а ако b1>1b_1\gt{}1, то a2=b1>1=a1a_2=b_1\gt{}1=a_1. От минималността на rr имаме ar−1<ara_{r-1}\lt{}a_r, а от минималността на nn числата ar−1,ar,ar+1a_{r-1},a_r,a_{r+1} са положителни. За да бъде ar+1≥ar+2a_{r+1}\ge a_{r+2}, формулата за ar+2a_{r+2} трябва да е с минус, следователно br>1b_r\gt{}1 и br≥2b_r\ge2. Тогаваar+1=arbr±ar−1≥a_{r+1}=a_r b_r\pm a_{r-1}\ge2ar−ar−1=ar+(ar−ar−1)>ar, 2a_r-a_{r-1}=a_r+(a_r-a_{r-1})\gt{}a_r,което противоречи на ar≥ar+1a_r\ge a_{r+1}. Лемата е доказана. Ще докажем с индукция, чеmax⁡{an,an+1}≥n(n≥0).(1)\max\{a_n,a_{n+1}\}\ge n\qquad(n\ge0).\tag{1}Случаите n=0,1n=0,1 са ясни. Нека n≥2n\ge2 и да предположим, че твърдението е доказано за всички по-малки индекси. Ако bn−1=1b_{n-1}=1, тогаваan+1=anbn+an−1≥an+an−1.a_{n+1}=a_n b_n+a_{n-1}\ge a_n+a_{n-1}.По индукционното предположение едно от an−1,ana_{n-1},a_n е поне n−1n-1, а по лемата другото е поне 11. Следователно an+1≥na_{n+1}\ge n, което доказва (1). Нека сега bn−1>1b_{n-1}\gt{}1. Понеже b0=1b_0=1, съществува индекс rr с 1≤r≤n−11\le r\le n-1, за койтоbn−1,bn−2,…,br≥2,br−1=1.b_{n-1},b_{n-2},\ldots,b_r\ge2,\qquad b_{r-1}=1.Тогаваar+1=arbr+ar−1≥2ar+ar−1,a_{r+1}=a_r b_r+a_{r-1}\ge2a_r+a_{r-1},следователноar+1−ar≥ar+ar−1.a_{r+1}-a_r\ge a_r+a_{r-1}.Ще използваме, че ar+ar−1≥ra_r+a_{r-1}\ge r: за r=1r=1 това е ясно, а за r≥2r\ge2 следва от индукционното предположение и лемата. Значиar+1−ar≥r,a_{r+1}-a_r\ge r,а понеже ar≥1a_r\ge1, получавамеar+1≥r+1иar+1>ar.a_{r+1}\ge r+1\qquad\text{и}\qquad a_{r+1}\gt{}a_r.За m=r+1,r+2,…,n−1m=r+1,r+2,\ldots,n-1 важи импликациятаam>am−1⟹am+1>am,a_m\gt{}a_{m-1}\quad\Longrightarrow\quad a_{m+1}\gt{}a_m,защото в този интервал bm−1≥2b_{m-1}\ge2 и bm≥2b_m\ge2, следователноam+1=ambm−am−1≥2am−am−1>am.a_{m+1}=a_m b_m-a_{m-1}\ge2a_m-a_{m-1}\gt{}a_m.Получавамеan>an−1>⋯>ar+1≥r+1,a_n\gt{}a_{n-1}\gt{}\cdots\gt{}a_{r+1}\ge r+1,откъдето an≥na_n\ge n. Това доказва (1). При n=2017n=2017 от (1) следва, че поне едно от a2017a_{2017} и a2018a_{2018} е не по-малко от 20172017.
Отвори задачатаMathNetISL 2017 A7Условие — източник

Задача A8

Пълен запис
Условие
Да се предположи, че функция f:R→Rf:\mathbb R\to\mathbb R удовлетворява следното условие: за всички x,y∈Rx,y\in\mathbb R, за които(f(x)+y)(f(y)+x)>0,(f(x)+y)(f(y)+x)\gt{}0,е изпълненоf(x)+y=f(y)+x.f(x)+y=f(y)+x.Докажете, чеf(x)+y≤f(y)+xf(x)+y\le f(y)+xвинаги когато x>yx\gt{}y.
РешениеПолагамеg(x)=x−f(x).g(x)=x-f(x).Тогава условието се преформулира така: ако((x+y)−g(x))((x+y)−g(y))>0,((x+y)-g(x))((x+y)-g(y))\gt{}0,то g(x)=g(y)g(x)=g(y). Еквивалентно, в контрапозиция,ако g(x)≠g(y),\text{ако }g(x)\ne g(y), то x+y лежи между g(x) и g(y).(*)\text{ то }x+y\text{ лежи между }g(x)\text{ и }g(y).\tag{*}Трябва да докажем, чеg(x)≤g(y)за x<y.(1)g(x)\le g(y)\qquad\text{за }x\lt{}y.\tag{1}Това е точно желаното неравенство, записано чрез gg. Ще използваме следната лема. Ако X=g(x)<2xX=g(x)\lt{}2x, тоg(a)=Xза всички a∈(X−x,x).(2)g(a)=X\qquad\text{за всички }a\in(X-x,x).\tag{2}Ако X=g(x)>2xX=g(x)\gt{}2x, тоg(a)=Xза всички a∈(x,X−x).(3)g(a)=X\qquad\text{за всички }a\in(x,X-x).\tag{3}Достатъчно е да докажем първото твърдение; второто следва от първото, приложено към функцията g1(t)=−g(−t)g_1(t)=-g(-t), която също удовлетворява (∗)(*). Нека X=g(x)<2xX=g(x)\lt{}2x. Първо ще покажем, че върху интервала (X−x,x](X-x,x] функцията gg приема най-много две стойности: XX и евентуално една стойност Y>XY\gt{}X. Ако a∈(X−x,x)a\in(X-x,x) и g(a)eXg(a) e X, то не може g(a)<Xg(a)\lt{}X, защото по (∗)(*) числото a+xa+x трябва да лежи между g(a)g(a) и XX, откъдето би следвало a+x≤Xa+x\le X, т.е. a≤X−xa\le X-x. Значи g(a)>Xg(a)\gt{}X и по (∗)(*) имамеX≤a+x≤g(a).(4)X\le a+x\le g(a).\tag{4}Ако bb е друг такъв елемент, тогава също b+x≤g(b)b+x\le g(b). Но a+b<a+xa+b\lt{}a+x и a+b<b+xa+b\lt{}b+x, така че a+ba+b не може да лежи между g(a)g(a) и g(b)g(b), освен ако g(a)=g(b)g(a)=g(b). Следователно има най-много една стойност, различна от XX. Сега ще покажем, че на отворения интервал (X−x,x)(X-x,x) функцията е константна. Да допуснем, че там има точки a,ba,b с различни стойности; според предното можем да считаме g(a)=Xg(a)=X и g(b)=Y>Xg(b)=Y\gt{}X. Избирамеu∈(X−x,x)сu<min⁡{X−a,X−b}.u\in(X-x,x)\qquad\text{с}\qquad u\lt{}\min\{X-a,X-b\}.От вече доказаното g(u)g(u) е или XX, или YY. Ако g(u)=Xg(u)=X, то (∗)(*) за двойката u,bu,b дава u+b≥Xu+b\ge X, противоречие с u<X−bu\lt{}X-b. Ако g(u)=Yg(u)=Y, аналогично двойката u,au,a дава противоречие. Значи gg е константна върху (X−x,x)(X-x,x). По симетрия същото твърдение за константност е вярно и върху (x,X−x)(x,X-x), когато X=g(x)>2xX=g(x)\gt{}2x. Остава да видим, че тази константна стойност е именно XX. Ако вместо това g(a)=Y>Xg(a)=Y\gt{}X за всяко a∈(X−x,x)a\in(X-x,x), избираме a<ba\lt{}b в този интервал. От (∗)(*) за двойката b,xb,x следваY≥b+x≥X.(5)Y\ge b+x\ge X.\tag{5}В частност Y>b+x>2aY\gt{}b+x\gt{}2a. По току-що установената симетрична константност, приложена към точката aa и стойността Y=g(a)>2aY=g(a)\gt{}2a, функцията gg е константна върху (a,Y−a)(a,Y-a). От (5) имаме x≤Y−b<Y−ax\le Y-b\lt{}Y-a, а също b∈(a,Y−a)b\in(a,Y-a). Значи и xx, и bb лежат в този интервал, но g(x)=XeY=g(b)g(x)=X e Y=g(b), противоречие. Лемата е доказана. Да допуснем сега, че (1) е невярно, т.е. съществуват x<yx\lt{}y сX=g(x)>g(y)=Y.X=g(x)\gt{}g(y)=Y.По (∗)(*) числото x+yx+y лежи между XX и YY, следователноX≥x+y≥Y.X\ge x+y\ge Y.Оттук X>2xX\gt{}2x и Y<2yY\lt{}2y. По лемата gg е равна на XX върху (x,X−x)(x,X-x) и е равна на YY върху (Y−y,y)(Y-y,y). Но тези два интервала имат общата част (x,y)(x,y), понежеY−y≤x<y≤X−x.Y-y\le x\lt{}y\le X-x.Така на непразен интервал gg трябва да е едновременно равна на XX и на YY, което е невъзможно. Следователно g(x)≤g(y)g(x)\le g(y) за x<yx\lt{}y, а това е еквивалентно наf(x)+y≤f(y)+x(x>y).f(x)+y\le f(y)+x\qquad(x\gt{}y).
Отвори задачатаMathNetISL 2017 A8Условие — източник

Задача C1

Пълен запис
Условие
Правоъгълник RR с нечетни цели дължини на страните е разделен на малки правоъгълници с цели дължини на страните. Докажете, че сред малките правоъгълници има поне един, чиито разстояния до четирите страни на RR са или всички нечетни, или всички четни.
РешениеНека ширината и височината на RR са нечетните числа aa и bb. Разделяме RR на abab единични квадратчета и ги оцветяваме шахматно в зелено и жълто. Понеже aa и bb са нечетни, четирите ъглови квадратчета на RR имат един и същи цвят; нека той е зелен. Ще наричаме правоъгълник зелен, ако четирите му ъглови квадратчета са зелени; жълт, ако четирите му ъглови квадратчета са жълти; и смесен, ако сред тях има и двата цвята. Тогава всеки смесен правоъгълник съдържа равен брой зелени и жълти единични квадратчета; всеки зелен правоъгълник съдържа с едно повече зелени, отколкото жълти квадратчета; а всеки жълт правоъгълник съдържа с едно повече жълти, отколкото зелени квадратчета. Самият RR е зелен, следователно в него зелените единични квадратчета са повече от жълтите. Значи сред малките правоъгълници има поне един зелен; означаваме го със SS. Нека разстоянията от SS до горната, долната, лявата и дясната страна на RR са съответно x,y,u,vx,y,u,v. Горният ляв ъгъл на SS има същия цвят като горния ляв ъгъл на RR точно когато xx и uu имат еднаква четност. Аналогично, от останалите зелени ъгли на SS получаваме, че xx и vv имат еднаква четност, както и че yy и uu имат еднаква четност. Следователно x,y,u,vx,y,u,v имат една и съща четност, т.е. четирите разстояния са или всички четни, или всички нечетни.
Отвори задачатаMathNetISL 2017 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека nn е положително цяло число. Да наречем хамелеон всяка редица от 3n3n букви, в която всяка от буквите a,b,ca,b,c се среща точно nn пъти. Размяна е транспозиция на две съседни букви в хамелеон. Докажете, че за всеки хамелеон XX съществува хамелеон YY, такъв че XX не може да се превърне в YY с по-малко от 3n2/23n^2/2 размени.
РешениеРазмяната на две еднакви букви не променя хамелеона, затова я пренебрегваме. За два хамелеона XX и YY означаваме с d(X,Y)d(X,Y) минималния брой размени, нужни за превръщане на XX в YY. Ясно е, чеd(X,Y)+d(Y,Z)≥d(X,Z)d(X,Y)+d(Y,Z)\ge d(X,Z)за всеки три хамелеона X,Y,ZX,Y,Z. Ще използваме двата специални хамелеонаP=aa…a⏟nbb…b⏟ncc…c⏟n,P=\underbrace{aa\ldots a}_{n}\underbrace{bb\ldots b}_{n}\underbrace{cc\ldots c}_{n},Q=cc…c⏟nbb…b⏟naa…a⏟n.\qquad Q=\underbrace{cc\ldots c}_{n}\underbrace{bb\ldots b}_{n}\underbrace{aa\ldots a}_{n}.Ще докажем, че d(P,Q)≥3n2d(P,Q)\ge3n^2. За хамелеон XX и две различни букви u,v∈{a,b,c}u,v\in\{a,b,c\} нека fu,v(X)f_{u,v}(X) е броят на двойките позиции, в които лявата позиция е заета от uu, а дясната - от vv. Полагамеf(X)=fa,b(X)+fa,c(X)+fb,c(X).f(X)=f_{a,b}(X)+f_{a,c}(X)+f_{b,c}(X).За PP имаме fa,b(P)=fa,c(P)=fb,c(P)=n2f_{a,b}(P)=f_{a,c}(P)=f_{b,c}(P)=n^2, а за QQ и трите броя са 00. Следователно f(P)=3n2f(P)=3n^2 и f(Q)=0f(Q)=0. При една размяна на две различни съседни букви стойността на ff се променя точно с 11. Например, ако се разменят aa и bb, тогава само броят fa,bf_{a,b} се променя с 11, а отношенията на тези две букви към всички букви cc остават същите. Аналогично е за другите двойки букви. Затова за всеки два хамелеона U,VU,V имамеd(U,V)≥∣f(U)−f(V)∣.d(U,V)\ge |f(U)-f(V)|.В частност d(P,Q)≥3n2d(P,Q)\ge3n^2. Сега за даден хамелеон XX получавамеd(X,P)+d(X,Q)≥d(P,Q)≥3n2.d(X,P)+d(X,Q)\ge d(P,Q)\ge3n^2.Следователно поне едно от числата d(X,P)d(X,P) и d(X,Q)d(X,Q) е не по-малко от 3n2/23n^2/2. Избирайки съответно Y=PY=P или Y=QY=Q, получаваме искания хамелеон.
Отвори задачатаMathNetISL 2017 C2Условие — източник

Задача C3

Пълен запис
Условие
Сър Алекс играе следната игра върху редица от 99 клетки. Първоначално всички клетки са празни. На всеки ход сър Алекс трябва да извърши точно една от следните две операции: (1) Да избере число от вида 2j2^j, където jj е неотрицателно цяло число, и да го постави в празна клетка. (2) Да избере две, не непременно съседни, клетки с едно и също число в тях; нека това число е 2j2^j. Той заменя числото в едната клетка с 2j+12^{j+1} и изтрива числото в другата клетка. В края на играта една клетка съдържа числото 2n2^n, където nn е дадено положително цяло число, а останалите клетки са празни. Да се определи в зависимост от nn максималният възможен брой ходове, които сър Алекс може да е направил.
РешениеОтговорът е2∑j=08(nj)−1.2\sum_{j=0}^{8}\binom nj-1.Ще решим по-обща задача, в която редицата има kk клетки. Нека m(n,k)m(n,k) е максималният брой ходове, с които от kk празни клетки може да се стигне до една клетка с 2n2^n и k−1k-1 празни клетки. Ще наричаме ход от тип (1) вмъкване, а ход от тип (2) сливане. Ако k=1k=1, възможен е само един ход, така че m(n,1)=1m(n,1)=1. Нека k≥2k\ge2. Можем да предполагаме, че последният ход е сливане. Точно преди него има две клетки с числото 2n−12^{n-1}, а останалите k−2k-2 клетки са празни. Оцветяваме едното от тези две числа в синьо, а другото в червено. Проследяваме ходовете назад: ако две числа aa и bb са се слели в cc, оцветяваме aa и bb със същия цвят като cc. В обратния процес нови числа се появяват само при обръщане на сливанията, а обръщането на вмъкване просто изтрива число. Следователно всички числа в целия процес получават един от двата цвята. Първият ход на сър Алекс е вмъкване. Без ограничение нека първото вмъкнато число е синьо. От този момент до последния ход винаги има поне една клетка със синьо число. Освен при последния ход няма ход, в който участват едновременно синьо и червено число: сливанията са между числа с един и същи цвят, а вмъкванията засягат само едно число. Редицата от всички сини ходове сама по себе си може да се изпълни в редица от kk клетки и да произведе една клетка с 2n−12^{n-1} и празни останали клетки. Следователно сините ходове са най-много m(n−1,k)m(n-1,k). При всеки червен ход обаче има поне една клетка, заета от синьо число, затова червените ходове могат да се повторят в редица от k−1k-1 клетки и да произведат 2n−12^{n-1}. Те са най-много m(n−1,k−1)m(n-1,k-1). Получавамеm(n,k)≤m(n−1,k)+m(n−1,k−1)+1.m(n,k)\le m(n-1,k)+m(n-1,k-1)+1.Обратното неравенство се получава чрез конструкция. Първо изпълняваме оптимална игра с kk клетки, която дава 2n−12^{n-1}. После върху останалите k−1k-1 празни клетки изпълняваме оптимална игра, която дава второ 2n−12^{n-1}. Накрая сливаме двете числа и получаваме 2n2^n. Следователноm(n,k)=m(n−1,k)+m(n−1,k−1)+1(1)m(n,k)=m(n-1,k)+m(n-1,k-1)+1\tag{1}за n≥1n\ge1 и k≥2k\ge2. Началните стойности са m(0,k)=1m(0,k)=1 и m(n,1)=1m(n,1)=1. Ще докажем с индукция по nn, чеm(n,k)=2∑j=0k−1(nj)−1(2)m(n,k)=2\sum_{j=0}^{k-1}\binom nj-1\tag{2}за всички n≥0n\ge0 и k≥1k\ge1. При n=0n=0 това е ясно. Ако формулата е вярна за nn, то за k=1k=1 тя отново дава 11, а за k≥2k\ge2 от (1) и индукционното предположение получавамеm(n+1,k)=m(n+1,k)=2∑j=0k−1(nj)−1+2∑j=0k−2(nj)−1+1=2\sum_{j=0}^{k-1}\binom nj-1+2\sum_{j=0}^{k-2}\binom nj-1+1=2∑j=0k−1(n+1j)−1.2\sum_{j=0}^{k-1}\binom{n+1}j-1.Това доказва (2). При k=9k=9 получаваме търсения максимален брой ходове.
Отвори задачатаMathNetISL 2017 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека N≥2N\ge2 е цяло число. N(N+1)N(N+1) футболисти, никои двама от които не са с еднакъв ръст, стоят в редица в някакъв ред. Треньорът Ралф иска да премахне N(N−1)N(N-1) души от редицата така, че в останалата редица от 2N2N футболисти никой да не стои между двамата най-високи, никой да не стои между третия и четвъртия най-висок, и така нататък, до двойката на двамата най-ниски. Докажете, че това винаги е възможно.
РешениеРазделяме футболистите според ръста им на NN групи: G1G_1 съдържа N+1N+1 най-високи футболисти, G2G_2 - следващите N+1N+1, и така нататък до GNG_N, която съдържа N+1N+1 най-ниски футболисти. Сканираме първоначалната редица отляво надясно и спираме веднага щом сме срещнали двама футболисти от една и съща група, да кажем GiG_i. Понеже групите са NN, това се случва най-късно при (N+1)(N+1)-вия сканиран футболист. Запазваме тази двойка, а премахваме всички други футболисти от групата GiG_i и всички вече сканирани футболисти, освен двамата избрани. В останалата редица избраната двойка стои съседно: всеки, който е бил между двамата в първоначалната редица, вече е бил сканиран и е премахнат. Освен това никой останал футболист няма ръст между ръстовете на тези двама, защото всички такива футболисти са в същата група GiG_i и са премахнати. Остават N−1N-1 групи. Всяка от тях е загубила най-много един футболист при първото сканиране, следователно във всяка има поне NN несканирани футболисти. Повтаряме същата процедура отляво надясно върху останалата редица: избираме следващите двама футболисти от една и съща оставаща група, премахваме тази група и всички сканирани до този момент футболисти, освен избраната двойка. След tt такива стъпки остават N−tN-t групи, всяка с поне N+1−tN+1-t футболисти, така че процедурата може да продължи. След общо NN стъпки сме запазили точно по двама футболисти от всяка група, т.е. общо 2N2N футболисти. Групите са подредени по ръст, затова запазените двама от G1G_1 са двамата най-високи сред останалите, запазените двама от G2G_2 са третият и четвъртият най-висок, и така нататък. От начина на избиране всяка такава двойка стои съседно в крайната редица. Това е точно исканото.
Отвори задачатаMathNetISL 2017 C4Условие — източник

Задача C5

Пълен запис
Условие
Ловец и невидим заек играят игра в евклидовата равнина. Началната точка H0H_0 на ловеца съвпада с началната точка R0R_0 на заека. В nn-ия рунд на играта, където n≥1n\ge1, се случва следното: (1) Първо невидимият заек се премества тайно от текущата си точка Rn−1R_{n-1} до нова точка RnR_n, като Rn−1Rn=1R_{n-1}R_n=1. (2) Ловецът има проследяващо устройство, което връща приблизителна позиция Rn′R'_n на заека, така че RnRn′≤1R_nR'_n\le1. (3) После ловецът видимо се премества от Hn−1H_{n-1} до нова точка HnH_n, като Hn−1Hn=1H_{n-1}H_n=1. Има ли стратегия за ловеца, която гарантира, че след 10910^9 такива рунда разстоянието между ловеца и заека е по-малко от 100100?
РешениеОтговорът е не. Ще покажем, че при подходящо неблагоприятни отчитания на устройството никоя стратегия на ловеца не може да гарантира успех. Нека dn=HnRnd_n=H_nR_n е разстоянието между ловеца и заека след nn рунда. Ако за някое n<109n\lt{}10^9 имаме dn≥100d_n\ge100, заекът може занапред да се движи право в посока, отдалечаваща го от ловеца, и да запази разстоянието поне 100100. Затова нека dn<100d_n\lt{}100. Ще докажем, че независимо от стратегията на ловеца заекът може, с подходящи допустими отчитания на устройството, да увеличи dn2d_n^2 с повече от 1/21/2 за следващите 200200 рунда. Да поставим Rn=(0,0)R_n=(0,0) и Hn=(−dn,0)H_n=(-d_n,0), така че правата HnRnH_nR_n да е оста xx. НекаZ=(x22002−1,0),Y1=(x22002−1,1),Z=(\sqrt{\vphantom{x^2}200^2-1},0),\qquad Y_1=(\sqrt{\vphantom{x^2}200^2-1},1),Y2=(x22002−1,−1).\qquad Y_2=(\sqrt{\vphantom{x^2}200^2-1},-1).Точките Y1Y_1 и Y2Y_2 са на разстояние 200200 от RnR_n и на разстояние 11 от оста xx. Планът на заека е да избере една от тях и в следващите 200200 рунда да се движи по права линия към нея. През цялото време той остава на разстояние най-много 11 от оста xx, така че е възможно всички отчитания на устройството да лежат върху оста xx. При такива отчитания ловецът не може да знае дали заекът е избрал Y1Y_1 или Y2Y_2. След 200200 хода ловецът не може да е по-надясно от точката H′=(200−dn,0)H'=(200-d_n,0). Ако завърши над оста xx, той е още по-далеч от Y2Y_2; ако завърши под оста xx, е още по-далеч от Y1Y_1. Следователно каквато и стратегия да следва, за една от двете възможни цели разстоянието му до заека е понеy=H′Y1=H′Y2.y=H'Y_1=H'Y_2.Нека ε=200−x22002−1\varepsilon=200-\sqrt{\vphantom{x^2}200^2-1}. Тогаваy2=1+(dn−ε)2=dn2−2εdn+ε2+1.y^2=1+(d_n-\varepsilon)^2=d_n^2-2\varepsilon d_n+\varepsilon^2+1.Понежеε2+1=400εи\varepsilon^2+1=400\varepsilon\qquad\text{и}\qquadε=1200+x22002−1>1400, \varepsilon=\frac1{200+\sqrt{\vphantom{x^2}200^2-1}}\gt{}\frac1{400},получавамеy2=dn2+ε(400−2dn)>dn2+12,y^2=d_n^2+\varepsilon(400-2d_n)\gt{}d_n^2+\frac12,тъй като dn<100d_n\lt{}100. Значи на всеки 200200 рунда, докато разстоянието е под 100100, квадратът му може да бъде увеличен с повече от 1/21/2. Така dn2d_n^2 достига 1002100^2 за по-малко от2⋅104⋅200=4⋅106<1092\cdot10^4\cdot200=4\cdot10^6\lt{}10^9рунда. Следователно ловецът няма стратегия, която да гарантира разстояние под 100100 след 10910^9 рунда.
Отвори задачатаMathNetISL 2017 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека n>1n\gt{}1 е цяло число. Куб n×n×nn\times n\times n е съставен от n3n^3 единични кубчета. Всяко единично кубче е оцветено в един цвят. За всяка кутия n×n×1n\times n\times1, състояща се от n2n^2 единични кубчета, в която и да е от трите възможни ориентации, разглеждаме множеството от цветовете, които се срещат в тази кутия, като всеки цвят се записва само веднъж. Така получаваме 3n3n множества от цветове, разделени в три групи според ориентацията. Оказва се, че за всяко множество от която и да е група същото множество се среща и в двете други групи. Да се определи, в зависимост от nn, максималният възможен брой цветове, които се срещат.
РешениеОтговорът еn(n+1)(2n+1)6.\frac{n(n+1)(2n+1)}6.Първо ще докажем горна граница. Разглеждаме малко по-обща версия: всяко единично кубче може или да има цвят, или да е невидимо. Невидимото не се брои като цвят. Изискваме само всяко непразно множество от цветове, което се появява в една от трите групи кутии n×n×1n\times n\times1, да се появява и в другите две групи. Ще наричаме такова подреждане странно. Нека D(n)D(n) е максималният брой цветове в странен куб n×n×nn\times n\times n. Ще докажем с индукция, чеD(n)≤n(n+1)(2n+1)6.D(n)\le\frac{n(n+1)(2n+1)}6.За n=1n=1 това е ясно. Нека n≥2n\ge2 и да вземем странен куб. Ако всички кубчета са невидими, няма какво да доказваме. Иначе избираме непразно множество от цветове SS, което се среща в някоя кутия XX; по условие същото множество се среща и в кутии YY и ZZ от другите две ориентации. Правим невидими всички кубчета, чиито цветове са в SS. Тогава кутиите X,Y,ZX,Y,Z стават изцяло невидими и можем да ги изхвърлим. Остава куб (n−1)×(n−1)×(n−1)(n-1)\times(n-1)\times(n-1). В него всяко непразно множество от цветове, което се появява в една ориентация, все още се появява и в другите две: от старите множества сме премахнали точно цветовете от SS. Следователно останалият куб пак е странен. По индукционното предположение той съдържа най-много(n−1)n(2n−1)6\frac{(n-1)n(2n-1)}6цвета. А множеството SS има най-много n2n^2 цвята, защото се съдържа в една кутия n×n×1n\times n\times1. Значи първоначалният куб има най-много(n−1)n(2n−1)6+n2=n(n+1)(2n+1)6\frac{(n-1)n(2n-1)}6+n^2=\frac{n(n+1)(2n+1)}6цвета. Остава конструкция с толкова цветове. Номерираме координатите на кубчетата с тройки (i,j,k)(i,j,k), където 1≤i,j,k≤n1\le i,j,k\le n. Ще зададем цветовете чрез множествата от кубчета, които имат един и същи цвят. Първо, за всяко ii даваме отделен цвят на единичното множествоSi={(i,i,i)}.S_i=\{(i,i,i)\}.Второ, за всяко 1≤i<j≤n1\le i\lt{}j\le n даваме по един цвят на всяко от трите двумножества{(i,j,j),(j,i,i)},{(j,i,j),(i,j,i)},\{(i,j,j),(j,i,i)\},\qquad \{(j,i,j),(i,j,i)\},{(j,j,i),(i,i,j)}.\qquad \{(j,j,i),(i,i,j)\}.Трето, за всяко 1≤i<j<k≤n1\le i\lt{}j\lt{}k\le n даваме по един цвят на всяко от двете тримножества{(i,j,k),(j,k,i),(k,i,j)},\{(i,j,k),(j,k,i),(k,i,j)\},{(i,k,j),(k,j,i),(j,i,k)}.\qquad \{(i,k,j),(k,j,i),(j,i,k)\}.Тези множества разбиват всички n3n^3 кубчета. За всяко фиксирано tt кутиите i=ti=t, j=tj=t и k=tk=t съдържат едни и същи цветове: това се вижда директно от цикличния начин, по който са групирани координатите. Следователно условието е изпълнено. Броят на цветовете еn+3(n2)+2(n3)=n(n+1)(2n+1)6,n+3\binom n2+2\binom n3=\frac{n(n+1)(2n+1)}6,което съвпада с горната граница.
Отвори задачатаMathNetISL 2017 C6Условие — източник

Задача C7

Пълен запис
Условие
За всеки крайни множества XX и YY от положителни цели числа означаваме с fX(k)f_X(k) kk-тото най-малко положително цяло число, което не принадлежи на XX, и полагамеX⋆Y=X∪{fX(y):y∈Y}.X\star Y=X\cup\{f_X(y):y\in Y\}.Нека AA е множество от a>0a\gt{}0 положителни цели числа, а BB е множество от b>0b\gt{}0 положителни цели числа. Докажете, че ако A⋆B=B⋆AA\star B=B\star A, тоA⋆(A⋆⋯⋆(A⋆A))⏟A участва b пъти=\underbrace{A\star(A\star\cdots\star(A\star A))}_{A\text{ участва }b\text{ пъти}}=B⋆(B⋆⋯⋆(B⋆B))⏟B участва a пъти.\underbrace{B\star(B\star\cdots\star(B\star B))}_{B\text{ участва }a\text{ пъти}}.
РешениеЗа функция g:Z>0→Z>0g:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0} и множество X⊂Z>0X\subset\mathbb Z_{\gt{}0} ще пишем g(X)={g(x):x∈X}g(X)=\{g(x):x\in X\}. Ще използваме първо следната лема. Лема 1. За всеки крайни множества X,YX,Y от положителни цели числа е изпълненоfX⋆Y=fX∘fY.f_{X\star Y}=f_X\circ f_Y.Доказателство. Образът на fXf_X е Z>0∖X\mathbb Z_{\gt{}0}\setminus X. ЗатоваfX⋆Y(Z>0)=Z>0∖(X⋆Y)=f_{X\star Y}(\mathbb Z_{\gt{}0})=\mathbb Z_{\gt{}0}\setminus(X\star Y)=(Z>0∖X)∖fX(Y)=(\mathbb Z_{\gt{}0}\setminus X)\setminus f_X(Y)=fX(Z>0∖Y)=fX(fY(Z>0)).f_X(\mathbb Z_{\gt{}0}\setminus Y)=f_X(f_Y(\mathbb Z_{\gt{}0})).Функциите fX⋆Yf_{X\star Y} и fX∘fYf_X\circ f_Y са строго растящи и имат един и същ образ, следователно съвпадат. От лема 1 следва, че операцията ⋆\star е асоциативна: за всеки крайни A,B,CA,B,C имаме (A⋆B)⋆C=A⋆(B⋆C)(A\star B)\star C=A\star(B\star C). Затова можем да махаме скобите и да пишем X⋆kX^{\star k} за резултата от kk повторения на XX. Ще ни трябва и втора лема. Лема 2. Нека XX и YY са крайни множества от положителни цели числа, за които X⋆Y=Y⋆XX\star Y=Y\star X и ∣X∣=∣Y∣|X|=|Y|. Тогава X=YX=Y. Доказателство. Да допуснем, че X≠YX\ne Y. Нека ss е най-голямото число, което принадлежи на точно едно от двете множества. Без ограничение s∈X∖Ys\in X\setminus Y. Числото fX(s)f_X(s) е ss-тото положително цяло число, което не е в XX, следователноfX(s)=s+∣X∩{1,2,…,fX(s)}∣.(1)f_X(s)=s+|X\cap\{1,2,\ldots,f_X(s)\}|.\tag{1}Понеже fX(s)≥sf_X(s)\ge s и ss е най-голямото място, на което XX и YY се различават, от ∣X∣=∣Y∣|X|=|Y| получаваме∣X∩{1,2,…,fX(s)}∣=|X\cap\{1,2,\ldots,f_X(s)\}|=∣Y∩{1,2,…,fX(s)}∣.(2)|Y\cap\{1,2,\ldots,f_X(s)\}|.\tag{2}От (1) и (2) следва, че до fX(s)f_X(s) има точно ss положителни цели числа, които не са в YY. Освен това fX(s)∉Xf_X(s)\notin X и fX(s)>sf_X(s)\gt{}s, така че по максималността на ss имаме и fX(s)∉Yf_X(s)\notin Y. Значи fX(s)f_X(s) е точно ss-тото положително цяло число, което не е в YY, т.е.fX(s)=fY(s).f_X(s)=f_Y(s).Но fX(s)f_X(s) не принадлежи на XX и не принадлежи на fX(Y)f_X(Y), понеже s∉Ys\notin Y и fXf_X е инективна. Следователно fX(s)∉X⋆Yf_X(s)\notin X\star Y. От друга страна, s∈Xs\in X, така че fY(s)∈Y⋆Xf_Y(s)\in Y\star X. Това противоречи на X⋆Y=Y⋆XX\star Y=Y\star X, тъй като fX(s)=fY(s)f_X(s)=f_Y(s). Лемата е доказана. Връщаме се към задачата. От A⋆B=B⋆AA\star B=B\star A и асоциативността следва, чеA⋆b⋆B⋆a=B⋆a⋆A⋆b.A^{\star b}\star B^{\star a}=B^{\star a}\star A^{\star b}.Освен това ∣A⋆b∣=ab=∣B⋆a∣|A^{\star b}|=ab=|B^{\star a}|, защото при всяко прилагане на ⋆\star добавената част е извън първото множество и има очакваната големина. По лема 2, приложена към X=A⋆bX=A^{\star b} и Y=B⋆aY=B^{\star a}, получавамеA⋆b=B⋆a,A^{\star b}=B^{\star a},което е точно исканото равенство.
Отвори задачатаMathNetISL 2017 C7Условие — източник

Задача G2

Пълен запис
Условие
Нека RR и SS са различни точки върху окръжност Ω\Omega, а tt е допирателната към Ω\Omega в RR. Точката R′R' е образът на RR при централна симетрия с център SS. Точка II е избрана върху малката дъга RSRS на Ω\Omega така, че описаната окръжност Γ\Gamma на триъгълника ISR′ISR' пресича tt в две различни точки. Нека AA е тази обща точка на Γ\Gamma и tt, която е по-близо до RR. Правата AIAI пресича Ω\Omega втори път в JJ. Докажете, че JR′JR' е допирателна към Γ\Gamma.
РешениеВ окръжностите Ω\Omega и Γ\Gamma имаме∠JRS=∠JIS=∠AR′S.\angle JRS=\angle JIS=\angle AR'S.Първото равенство следва от това, че J,I,R,SJ,I,R,S лежат на Ω\Omega, а второто - от това, че A,I,S,R′A,I,S,R' лежат на Γ\Gamma и точките A,I,JA,I,J са колинеарни. От друга страна, понеже RARA е допирателна към Ω\Omega в RR, теоремата за ъгъла между допирателна и хорда дава∠SJR=∠SRA.\angle SJR=\angle SRA.Следователно триъгълниците ARR′ARR' и SJRSJR са подобни. ОттукR′RRJ=AR′SR.\frac{R'R}{RJ}=\frac{AR'}{SR}.Понеже R′R' е симетрична на RR спрямо SS, имаме SR=SR′SR=SR', така чеR′RRJ=AR′SR′.\frac{R'R}{RJ}=\frac{AR'}{SR'}.Заедно с равенството ∠AR′S=∠JRR′\angle AR'S=\angle JRR' това показва, че△ASR′∼△R′JR.\triangle ASR'\sim\triangle R'JR.Затова∠SAR′=∠RR′J.\angle SAR'=\angle RR'J.Но точките R,S,R′R,S,R' са колинеарни, така че последният ъгъл е ъгълът между правата JR′JR' и хордата SR′SR' на Γ\Gamma. Понеже ∠SAR′\angle SAR' е вписаният ъгъл в Γ\Gamma, който стъпва на същата хорда SR′SR', по обратната теорема за ъгъла между допирателна и хорда получаваме, че JR′JR' е допирателна към Γ\Gamma в R′R'.
Отвори задачатаMathNetISL 2017 G2Условие — източник

Задача N1

Пълен запис
Условие
Редицата a0,a1,a2,…a_0,a_1,a_2,\ldots от положителни цели числа удовлетворяваan+1={x2an,ако x2an е цяло число,an+3,иначеa_{n+1}=\begin{cases}\sqrt{\vphantom{x^2}a_n},&\text{ако }\sqrt{\vphantom{x^2}a_n}\text{ е цяло число},\\a_n+3,&\text{иначе} \end{cases}за всяко n≥0n\ge0. Да се определят всички стойности на a0>1a_0\gt{}1, за които съществува поне едно число aa такова, че an=aa_n=a за безкрайно много стойности на nn.
РешениеОтговорът е: всички кратни на 33 положителни цели числа, по-големи от 11. Тъй като an+1a_{n+1} зависи само от ana_n, ако an=ama_n=a_m за две различни стойности на индексите, редицата е периодична от някой член нататък. Затова ще определим точно кога редицата става периодична. Първо, ако an≡−1(mod3)a_n\equiv -1\pmod3, то за всяко m>nm\gt{}n числото ama_m не е точен квадрат. Наистина, квадрат не може да е сравним с −1-1 по модул 33, така че an+1=an+3>ana_{n+1}=a_n+3\gt{}a_n и отново an+1≡−1(mod3)a_{n+1}\equiv -1\pmod3. Повтаряйки това, получаваме строго растяща опашка на редицата, следователно тя не може да е периодична от някой член нататък. Второ, ако an≢−1(mod3)a_n\not\equiv -1\pmod3 и an>9a_n\gt{}9, тогава съществува m>nm\gt{}n с am<ana_m\lt{}a_n. Нека t2t^2 е най-големият точен квадрат, по-малък от ana_n. Понеже an>9a_n\gt{}9, имаме t≥3t\ge3. Първият точен квадрат сред числата an,an+3,an+6,…a_n,a_n+3,a_n+6,\ldots е едно от (t+1)2,(t+2)2,(t+3)2(t+1)^2,(t+2)^2,(t+3)^2, затова след вземане на корен получаваме някой член, не по-голям от t+3<t2<ant+3\lt{}t^2\lt{}a_n. Трето, ако an≡0(mod3)a_n\equiv0\pmod3, то за някое m>nm\gt{}n имаме am=3a_m=3. Кратно на 33 винаги се последва от кратно на 33. Ако an∈{3,6,9}a_n\in\{3,6,9\}, редицата влиза в цикъла3,6,9,3,6,9,….3,6,9,3,6,9,\ldots.Ако an>9a_n\gt{}9, избираме минимален член сред an+1,an+2,…a_{n+1},a_{n+2},\ldots. Ако той беше по-голям от 99, второто наблюдение би дало още по-малък по-късен член, противоречие. Значи този минимум е едно от 3,6,93,6,9, а оттам редицата стига до 33. Накрая, ако an≡1(mod3)a_n\equiv1\pmod3, то за някое m>nm\gt{}n имаме am≡−1(mod3)a_m\equiv -1\pmod3. За an=4a_n=4 следващият член е 22, а за an=7a_n=7 редицата минава през 10,13,16,4,210,13,16,4,2. Ако an≥10a_n\ge10, избираме минимален член сред по-късните членове. Ако той беше сравним с 11 по модул 33, второто наблюдение би наложило да е 44 или 77, но тогава още по-късно се появява 22, противоречие с минималността. Следователно някой по-късен член е сравним с −1-1 по модул 33. Така, ако a0a_0 е кратно на 33, редицата стига до периодичния цикъл 3,6,93,6,9. Ако a0≡−1(mod3)a_0\equiv -1\pmod3, тя става строго растяща веднага, а ако a0≡1(mod3)a_0\equiv1\pmod3, първо стига до член, сравним с −1-1 по модул 33, и после пак става строго растяща. Следователно търсените начални стойности са точно кратните на 33.
Отвори задачатаMathNetISL 2017 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека p≥2p\ge2 е просто число. Едуардо и Фернандо играят следната игра, като се редуват. На всеки ход текущият играч избира индекс i∈{0,1,…,p−1}i\in\{0,1,\ldots,p-1\}, който не е бил избран преди това от никого, и след това избира елемент ai∈{0,1,2,3,4,5,6,7,8,9}a_i\in\{0,1,2,3,4,5,6,7,8,9\}. Едуардо играе първи. Играта приключва, когато всички индекси i∈{0,1,…,p−1}i\in\{0,1,\ldots,p-1\} са избрани. Тогава се пресмята числотоM=a0+10a1+⋯+10p−1ap−1=∑j=0p−1aj10j.M=a_0+10a_1+\cdots+10^{p-1}a_{p-1}=\sum_{j=0}^{p-1}a_j10^j.Целта на Едуардо е да направи MM делимо на pp, а целта на Фернандо е да предотврати това. Докажете, че Едуардо има печеливша стратегия.
РешениеЩе казваме, че играч прави хода (i,ai)(i,a_i), ако избира индекса ii и цифрата aia_i. Ако p=2p=2 или p=5p=5, Едуардо избира i=0i=0 и a0=0a_0=0 още на първия ход. Тогава независимо от останалите ходове числото MM е кратно на 1010, следователно и на pp. Нека вече p∉{2,5}p\notin\{2,5\}. На първия си ход Едуардо избира i=p−1i=p-1 и ap−1=0a_{p-1}=0. По малката теорема на Ферма(10(p−1)/2)2=10p−1≡1(modp),\left(10^{(p-1)/2}\right)^2=10^{p-1}\equiv1\pmod p,затова или 10(p−1)/2≡−1(modp)10^{(p-1)/2}\equiv -1\pmod p, или 10(p−1)/2≡1(modp)10^{(p-1)/2}\equiv1\pmod p. Първи случай: 10(p−1)/2≡−1(modp)10^{(p-1)/2}\equiv -1\pmod p. След всеки ход (i,ai)(i,a_i) на Фернандо Едуардо избира сдвоения индексj={i+p−12,0≤i≤p−32,i−p−12,p−12≤i≤p−2,j=\begin{cases}i+\frac{p-1}{2},&0\le i\le\frac{p-3}{2},\\i-\frac{p-1}{2},&\frac{p-1}{2}\le i\le p-2, \end{cases}и взема aj=aia_j=a_i. Този ход винаги е възможен, защото преди всеки ход на Фернандо във всяка двойка {r,r+(p−1)/2}\{r,r+(p-1)/2\} или са избрани и двата индекса, или нито един. Освен това 10j≡−10i(modp)10^j\equiv -10^i\pmod p, така че двата нови приноса се унищожават по модул pp:ai10i+aj10j≡0(modp).a_i10^i+a_j10^j\equiv0\pmod p.След всеки свой ход Едуардо е направил сумата на вече избраните приноси кратна на pp, следователно печели. Втори случай: 10(p−1)/2≡1(modp)10^{(p-1)/2}\equiv1\pmod p. Едуардо използва същото сдвояване на индексите, но при ход (i,ai)(i,a_i) на Фернандо избира aj=9−aia_j=9-a_i. Тогава 10j≡10i(modp)10^j\equiv10^i\pmod p иai10i+aj10j≡9⋅10i(modp).a_i10^i+a_j10^j\equiv9\cdot10^i\pmod p.В края на играта получавамеM≡∑i=0(p−3)/29⋅10i=10(p−1)/2−1≡M\equiv\sum_{i=0}^{(p-3)/2}9\cdot10^i=10^{(p-1)/2}-1\equiv0(modp).0\pmod p.И в този случай Едуардо печели.
Отвори задачатаMathNetISL 2017 N2Условие — източник

Задача N3

Пълен запис
Условие
Да се определят всички цели числа n≥2n\ge2 със следното свойство: за всички цели числа a1,a2,…,ana_1,a_2,\ldots,a_n, чиято сума не се дели на nn, съществува индекс 1≤i≤n1\le i\le n такъв, че никое от числатаai, ai+ai+1, …, ai+ai+1+⋯+ai+n−1a_i,\ a_i+a_{i+1},\ \ldots,\ a_i+a_{i+1}+\cdots+a_{i+n-1}не се дели на nn. Тук приемаме ai=ai−na_i=a_{i-n} при i>ni\gt{}n.
РешениеОтговорът е: точно простите числа. Първо нека n=abn=ab, където a,b≥2a,b\ge2. Ще покажем, че свойството не е изпълнено. Вземамеa1=a2=⋯=an−1=a,an=0.a_1=a_2=\cdots=a_{n-1}=a,\qquad a_n=0.Сумата е a(n−1)a(n-1) и не се дели на n=abn=ab. Нека ii е произволен индекс. Ако 1≤i≤n−b1\le i\le n-b, вземаме j=bj=b, а ако n−b<i≤nn-b\lt{}i\le n, вземаме j=b+1j=b+1. В двата случая сред последователните членове от aia_i нататък има точно bb члена, равни на aa, и получаваме сума ab=nab=n, тоест кратна на nn. Следователно съставните nn не работят. Нека сега nn е просто число. Да допуснем противното. Тогава съществуват a1,a2,…,ana_1,a_2,\ldots,a_n със сума, която не се дели на nn, и за всеки начален индекс има непразна последователна сума с дължина най-много nn, която се дели на nn. Тази дължина всъщност е най-много n−1n-1, понеже пълната сума не се дели на nn. Ще построим рекурсивно индекси0=i0<i1<i2<⋯<in0=i_0\lt{}i_1\lt{}i_2\lt{}\cdots\lt{}i_nтака, че is+1−is≤n−1i_{s+1}-i_s\le n-1 иais+1+ais+2+⋯+ais+1≡0(modn)a_{i_s+1}+a_{i_s+2}+\cdots+a_{i_{s+1}}\equiv0\pmod nза всяко s=0,1,…,n−1s=0,1,\ldots,n-1, като индексите на aa се четат циклично по модул nn. Това е възможно по предположението, приложено към началния индекс is+1i_s+1. Сред n+1n+1 индекса i0,i1,…,ini_0,i_1,\ldots,i_n два са сравними по модул nn. Нека 0≤r<s≤n0\le r\lt{}s\le n и is≡ir(modn)i_s\equiv i_r\pmod n. Тогаваair+1+air+2+⋯+ais≡0(modn).a_{i_r+1}+a_{i_r+2}+\cdots+a_{i_s}\equiv0\pmod n.От друга страна is−ir=kni_s-i_r=kn за някое 1≤k≤n−11\le k\le n-1, защото всяка стъпка е най-много n−1n-1. Следователно тази сума е равна наk(a1+a2+⋯+an).k(a_1+a_2+\cdots+a_n).Това не може да се дели на простото число nn, понеже нито kk, нито a1+⋯+ana_1+\cdots+a_n се дели на nn. Получихме противоречие, така че всяко просто nn има исканото свойство.
Отвори задачатаMathNetISL 2017 N3Условие — източник

Задача N4

Пълен запис
Условие
Ще наричаме рационално число кратко, ако десетичният му запис е краен. За положително цяло число mm казваме, че положително цяло число tt е mm-вкусно, ако съществува число c∈{1,2,3,…,2017}c\in\{1,2,3,\ldots,2017\} такова, че10t−1cm\frac{10^t-1}{cm}е кратко, а10k−1cm\frac{10^k-1}{cm}не е кратко за никое 1≤k<t1\le k\lt{}t. Нека S(m)S(m) е множеството от mm-вкусните числа. Когато mm пробягва 1,2,…1,2,\ldots, какъв е максималният възможен брой елементи на S(m)S(m)?
РешениеОтговорът е 807807. Рационално число xx е кратко тогава и само тогава, когато съществуват a,b≥0a,b\ge0 с 2a5bx∈Z2^a5^b x\in\mathbb Z. Затова, ако m=2a5bsm=2^a5^b s и gcd⁡(s,10)=1\gcd(s,10)=1, факторите 22 и 55 в mm не влияят на минималните показатели. Можем да предполагаме, че gcd⁡(m,10)=1\gcd(m,10)=1. НекаC={1≤c≤2017:gcd⁡(c,10)=1}.C=\{1\le c\le2017:\gcd(c,10)=1\}.Тогава mm-вкусните числа са точно редовете на 1010 по модул cmcm за c∈Cc\in C:S(m)={ord⁡cm(10):c∈C}.S(m)=\{\operatorname{ord}_{cm}(10):c\in C\}.Следователно∣S(m)∣≤∣C∣=4⋅201+3=807.|S(m)|\le |C|=4\cdot201+3=807.Остава да построим mm, за което се достига равенство. НекаP={p:1<p≤2017, p е просто, p≠2,5}.P=\{p:1\lt{}p\le2017,\ p\text{ е просто},\ p\ne2,5\}.Избираме положително цяло число α\alpha, за което всяко p∈Pp\in P дели 10α−110^\alpha-1; например можем да вземем α=φ(T)\alpha=\varphi(T), където TT е произведението на всички прости числа от PP. Полагамеm=10α−1.m=10^\alpha-1.Ще докажем, че за всяко c∈Cc\in C е вярноord⁡cm(10)=cα.\operatorname{ord}_{cm}(10)=c\alpha.Нека t=ord⁡cm(10)t=\operatorname{ord}_{cm}(10). От m∣10t−1m\mid10^t-1 следва α∣t\alpha\mid t, така че t=kαt=k\alpha за някое положително цяло число kk. За всяко ℓ≥1\ell\ge1 и всяко p∈Pp\in P лемата за повдигане на показателя даваνp(10ℓα−1)=νp((10α)ℓ−1)=\nu_p(10^{\ell\alpha}-1)=\nu_p((10^\alpha)^\ell-1)=νp(10α−1)+νp(ℓ)=νp(m)+νp(ℓ).\nu_p(10^\alpha-1)+\nu_p(\ell)=\nu_p(m)+\nu_p(\ell).Понеже всеки прост делител на cc принадлежи на PP, получавамеcm∣10kα−1⟺c∣k.cm\mid10^{k\alpha}-1\quad\Longleftrightarrow\quad c\mid k.Най-малкото такова положително kk е k=ck=c, следователно ord⁡cm(10)=cα\operatorname{ord}_{cm}(10)=c\alpha. Така различните c∈Cc\in C дават различни елементи на S(m)S(m) и ∣S(m)∣=807|S(m)|=807.
Отвори задачатаMathNetISL 2017 N4Условие — източник

Задача N5

Пълен запис
Условие
Да се намерят всички двойки (p,q)(p,q) от прости числа с p>qp\gt{}q, за които числото(p+q)p+q(p−q)p−q−1(p+q)p−q(p−q)p+q−1\frac{(p+q)^{p+q}(p-q)^{p-q}-1}{(p+q)^{p-q}(p-q)^{p+q}-1}е цяло.
РешениеОтговорът е единствено (p,q)=(3,2)(p,q)=(3,2). НекаM=(p+q)p−q(p−q)p+q−1.M=(p+q)^{p-q}(p-q)^{p+q}-1.Числото MM е взаимнопросто с p+qp+q и с p−qp-q. Ако дадената дроб е цяло число, то чрез елиминиране на члена −1-1 в числителя получаваме(p+q)2q≡(p−q)2q(modM),(p+q)^{2q}\equiv(p-q)^{2q}\pmod M,тоест((p+q)(p−q)−1)2q≡1(modM).(1)\left((p+q)(p-q)^{-1}\right)^{2q}\equiv1\pmod M.\tag{1}Нека първо q≥5q\ge5. Ако rr е прост делител на MM, то MM е нечетно и r≥3r\ge3. От (1) редът на (p+q)(p−q)−1(p+q)(p-q)^{-1} по модул rr дели 2q2q, следователно е 1,2,q1,2,q или 2q2q. Ако редът е qq или 2q2q, от малката теорема на Ферма следва r≡1(modq)r\equiv1\pmod q. Ако редът е 11 или 22, тогава r∣(p+q)2−(p−q)2=4pqr\mid (p+q)^2-(p-q)^2=4pq, тоест r=pr=p или r=qr=q. Случаят r=pr=p е невъзможен, защотоM≡qp−q(−q)p+q−1=q2p−1≡q2−1≢0(modp).M\equiv q^{p-q}(-q)^{p+q}-1=q^{2p}-1\equiv q^2-1\not\equiv0\pmod p.Значи всеки прост делител на MM е или qq, или е сравним с 11 по модул qq. Следователно всеки положителен делител на MM е сравним с 00 или 11 по модул qq. НоM=M=((p+q)(p−q)/2(p−q)(p+q)/2−1)((p+q)(p−q)/2(p−q)(p+q)/2+1)\left((p+q)^{(p-q)/2}(p-q)^{(p+q)/2}-1\right)\left((p+q)^{(p-q)/2}(p-q)^{(p+q)/2}+1\right)е произведение на две положителни нечетни числа, които се различават с 22. И двете трябва да са сравними с 00 или 11 по модул qq, което е невъзможно при q≥5q\ge5. Нека q=2q=2. От горното сравнение следваM∣(p+2)4−(p−2)4.M\mid(p+2)^4-(p-2)^4.Затова(p+2)p−2(p−2)p+2−1=M≤(p+2)^{p-2}(p-2)^{p+2}-1=M\le(p+2)4−(p−2)4≤(p+2)4−1,(p+2)^4-(p-2)^4\le(p+2)^4-1,и следователно(p+2)p−6(p−2)p+2≤1.(p+2)^{p-6}(p-2)^{p+2}\le1.При p≥7p\ge7 лявата страна е по-голяма от 11, а при p=5p=5 тя е 7−137>17^{-1}3^7\gt{}1. Остава p=3p=3, и тогава55⋅1−151⋅15−1=31244=781,\frac{5^5\cdot1-1}{5^1\cdot1^5-1}=\frac{3124}{4}=781,така че (3,2)(3,2) наистина е решение. Накрая нека q=3q=3. Аналогично MM дели (p+3)6−(p−3)6(p+3)^6-(p-3)^6, а понеже MM е нечетно,M∣(p+32)6−(p−32)6.M\mid\left(\frac{p+3}{2}\right)^6-\left(\frac{p-3}{2}\right)^6.Получаваме64(p+3)p−9(p−3)p+3≤1.64(p+3)^{p-9}(p-3)^{p+3}\le1.При p≥11p\ge11 това е явно невъзможно; за p=7p=7 лявата страна е 64⋅10−2⋅410>164\cdot10^{-2}\cdot4^{10}\gt{}1, а за p=5p=5 е 64⋅8−4⋅28>164\cdot8^{-4}\cdot2^8\gt{}1. Следователно при q=3q=3 решения няма. Единствената двойка е (3,2)(3,2).
Отвори задачатаMathNetISL 2017 N5Условие — източник

Задача N6

Пълен запис
Условие
Да се намери най-малкото положително цяло число nn, или да се докаже, че такова не съществува, със следното свойство: има безкрайно много различни nn-торки от положителни рационални числа (a1,a2,…,an)(a_1,a_2,\ldots,a_n), за които иa1+a2+⋯+an,a_1+a_2+\cdots+a_n,и1a1+1a2+⋯+1an\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_n}са цели числа.
РешениеОтговорът е n=3n=3. За n=1n=1 условията a1∈Z>0a_1\in\mathbb Z_{\gt{}0} и 1/a1∈Z>01/a_1\in\mathbb Z_{\gt{}0} дават само a1=1a_1=1. Ще покажем, че за n=2n=2 има само краен брой възможности. Нека x,y∈Q>0x,y\in\mathbb Q_{\gt{}0}, x+y∈Zx+y\in\mathbb Z и 1/x+1/y∈Z1/x+1/y\in\mathbb Z. Пишем x=a/bx=a/b и y=c/dy=c/d, където a,b,c,d∈Z>0a,b,c,d\in\mathbb Z_{\gt{}0}, gcd⁡(a,b)=gcd⁡(c,d)=1\gcd(a,b)=\gcd(c,d)=1. Условията са еквивалентни наbd∣ad+bcиac∣ad+bc.bd\mid ad+bc\qquad\text{и}\qquad ac\mid ad+bc.От първата делимост следва d∣bd\mid b и b∣db\mid d, следователно b=db=d. Аналогично от втората следва a=ca=c. Значи x=yx=y. Тогава трябва 2x2x и 2/x2/x да са положителни цели числа. Ако N=2xN=2x, то 2/x=4/N2/x=4/N, така че NN дели 44. Получаваме само(x,y)=(12,12),(1,1),(2,2).(x,y)=\left(\frac12,\frac12\right),(1,1),(2,2).Следователно n=2n=2 също не работи. Остава да построим безкрайно много тройки. Ще търсим тройки със сума 11 във вида(aa+b+c,ba+b+c,ca+b+c),a,b,c∈Z>0.\left(\frac{a}{a+b+c},\frac{b}{a+b+c},\frac{c}{a+b+c}\right),\qquad a,b,c\in\mathbb Z_{\gt{}0}.Полагаме a=1a=1. Достатъчно е да намерим безкрайно много двойки (b,c)(b,c), за които1b+1c+cb+bc=3,\frac1b+\frac1c+\frac cb+\frac bc=3,тоестb2+c2−3bc+b+c=0.(1)b^2+c^2-3bc+b+c=0.\tag{1}Една начална двойка е (2,3)(2,3). Нека (b,c)(b,c) е решение на (1) с c≥bc\ge b. Разглеждаме (1) като квадратно уравнение по bb при фиксирано cc:b2−(3c−1)b+(c2+c)=0.b^2-(3c-1)b+(c^2+c)=0.Другият корен b′b' е цяло число и удовлетворяваb+b′=3c−1,bb′=c2+c.b+b'=3c-1,\qquad bb'=c^2+c.Понеже c≥bc\ge b, имамеb′=c2+cb≥c2+cc>c.b'=\frac{c^2+c}{b}\ge\frac{c^2+c}{c}\gt{}c.Следователно от решение (b,c)(b,c) получаваме ново решение (c,b′)(c,b') с по-големи числа. Така от (2,3)(2,3) се получават безкрайно много различни решения, например(2,3),(3,6),(6,14),(14,35),….(2,3),(3,6),(6,14),(14,35),\ldots.Съответните тройки положителни рационални числа имат сума 11 и целочислена сума на реципрочните стойности. Значи най-малкото възможно nn е 33.
Отвори задачатаMathNetISL 2017 N6Условие — източник

Задача N7

Пълен запис
Условие
Ще наричаме наредена двойка (x,y)(x,y) от цели числа неприводима решетъчна точка, ако xx и yy са взаимнопрости. За всяко крайно множество SS от неприводими решетъчни точки докажете, че съществува хомогенен полином f(x,y)f(x,y) с цели коефициенти, от степен поне 11, такъв, че f(x,y)=1f(x,y)=1 за всяко (x,y)∈S(x,y)\in S. Бележка. Хомогенен полином от степен nn е всеки ненулев полином от видаf(x,y)=f(x,y)=a0xn+a1xn−1y+a2xn−2y2a_0x^n+a_1x^{n-1}y+a_2x^{n-2}y^2+⋯+an−1xyn−1+anyn.+\cdots+a_{n-1}xy^{n-1}+a_ny^n.
РешениеПърво е достатъчно да можем да получим стойности ±1\pm1, защото тогава квадратът на полинома дава стойност 11. Нека точките от SS са (x1,y1),…,(xn,yn)(x_1,y_1),\ldots,(x_n,y_n). Ако две от тях лежат на една права през началото, те са противоположни, понеже са неприводими. За хомогенен полином стойностите в такива две точки се различават най-много по знак, затова можем да оставим само една точка от всяка такава права. За всяко ii полагамеℓi(x,y)=yix−xiy,\ell_i(x,y)=y_i x-x_i y,gi(x,y)=∏j≠iℓj(x,y).\qquad g_i(x,y)=\prod_{j\ne i}\ell_j(x,y).Тогава gi(xj,yj)=0g_i(x_j,y_j)=0 при j≠ij\ne i, аai=gi(xi,yi)≠0.a_i=g_i(x_i,y_i)\ne0.Освен това за всяка степен N≥n−1N\ge n-1 можем да заменим gig_i с хомогенен полином от степен NN, който има същите стойности в точките. Наистина, понеже xix_i и yiy_i са взаимнопрости, има линейна форма Ii(x,y)I_i(x,y) с цели коефициенти и Ii(xi,yi)=1I_i(x_i,y_i)=1; тогава Ii(x,y)N−n+1gi(x,y)I_i(x,y)^{N-n+1}g_i(x,y) върши работа. Ще използваме следното твърдение. За всяко положително цяло число aa съществува хомогенен полином Fa(x,y)F_a(x,y) с цели коефициенти и положителна степен, такъв чеFa(x,y)≡1(moda)F_a(x,y)\equiv1\pmod aза всички взаимнопрости цели числа x,yx,y. Доказваме твърдението. Ако a=pka=p^k е степен на просто число, можем да вземемFa(x,y)=(xp−1+yp−1)φ(a)за нечетно p,F_a(x,y)=(x^{p-1}+y^{p-1})^{\varphi(a)}\quad\text{за нечетно }p,а за p=2p=2 можем да вземемFa(x,y)=(x2+xy+y2)φ(a).F_a(x,y)=(x^2+xy+y^2)^{\varphi(a)}.Във всеки от двата случая основата е взаимнопроста с pp за взаимнопрости x,yx,y, така че теоремата на Ойлер дава конгруенцията по модул aa. За общо a=q1q2⋯qsa=q_1q_2\cdots q_s, където qiq_i са две по две взаимнопрости степени на прости числа, вземаме съответните полиноми за qiq_i и ги повдигаме на степени така, че всички да имат една и съща степен. ТогаваaqiFqi(x,y)≡aqi(moda)\frac{a}{q_i}F_{q_i}(x,y)\equiv\frac{a}{q_i}\pmod aза взаимнопрости x,yx,y. По лемата на Безу има целочислена линейна комбинация на числата a/qia/q_i, равна на 11; същата линейна комбинация на полиномите дава желания FaF_a. Сега нека aa е най-малкото общо кратно на числата ∣a1∣,…,∣an∣|a_1|,\ldots,|a_n|. Избираме степен на FaF_a, чиято степен е поне n−1n-1, и нека полученият полином е FF. За всяко ii имамеF(xi,yi)≡1(modai).F(x_i,y_i)\equiv1\pmod{a_i}.Следователно можем да извадим от FF подходяща целочислена кратност на съответния полином gig_i от същата степен, така че стойността в (xi,yi)(x_i,y_i) да стане точно 11, без да променяме стойностите в останалите точки. Правим това за всички ii. Полученият хомогенен полином има цели коефициенти, положителна степен и приема стойност 11 във всяка точка от SS.
Отвори задачатаMathNetISL 2017 N7Условие — източник

Задача N8

Пълен запис
Условие
Нека pp е нечетно просто число и нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Нека функция f:Z>0×Z>0→{0,1}f:\mathbb Z_{\gt{}0}\times\mathbb Z_{\gt{}0}\to\{0,1\} удовлетворява: - f(1,1)=0f(1,1)=0; - f(a,b)+f(b,a)=1f(a,b)+f(b,a)=1 за всяка двойка взаимнопрости положителни цели числа (a,b)(a,b), различна от (1,1)(1,1); - f(a+b,b)=f(a,b)f(a+b,b)=f(a,b) за всяка двойка взаимнопрости положителни цели числа (a,b)(a,b). Докажете, че∑n=1p−1f(n2,p)≥x22p−2.\sum_{n=1}^{p-1} f(n^2,p)\ge\sqrt{\vphantom{x^2}2p}-2.
РешениеНека AA е множеството на двойките взаимнопрости положителни цели числа. За (a,b)∈A(a,b)\in A съществуват цели числа u,vu,v с ua+vb=1ua+vb=1. Сред всички такива двойки има единствена, за която−b2<u≤b2.-\frac b2\lt{}u\le\frac b2.Ще я означаваме с g(a,b)=(u,v)g(a,b)=(u,v). Ще докажем лема: за всяко (a,b)∈A(a,b)\in A и g(a,b)=(u,v)g(a,b)=(u,v) е вярноf(a,b)=1⟺u>0.f(a,b)=1\quad\Longleftrightarrow\quad u\gt{}0.Доказателството е с индукция по a+ba+b. При (a,b)=(1,1)(a,b)=(1,1) имаме g(1,1)=(0,1)g(1,1)=(0,1) и f(1,1)=0f(1,1)=0. Нека a+b>2a+b\gt{}2. Ако a>ba\gt{}b, то g(a−b,b)=(u,v+u)g(a-b,b)=(u,v+u) и от третото условиеf(a,b)=f(a−b,b),f(a,b)=f(a-b,b),така че твърдението следва от индукционното предположение. Остава случаят a<ba\lt{}b. От ua+vb=1ua+vb=1 следва1+\frac{ab}{2}\gt{}vb\ge1- rac{ab}{2},а оттук\frac{1+a}{2}\ge v\gt{}- rac a2.Следователно g(b,a)=(v,u)g(b,a)=(v,u). Освен товаf(a,b)=1⟺f(b,a)=0⟺f(b−a,a)=0.f(a,b)=1\Longleftrightarrow f(b,a)=0\Longleftrightarrow f(b-a,a)=0.Понеже b>ab\gt{}a, за двойката (b−a,a)(b-a,a) сме в предишния случай и g(b−a,a)=(v,u+v)g(b-a,a)=(v,u+v). По индукционното предположение последното е еквивалентно на v≤0v\le0. От ua+vb=1ua+vb=1 и b>ab\gt{}a имаме v≤0v\le0 точно когато u>0u\gt{}0. Лемата е доказана. Лемата означава, че за взаимнопрости a,ba,b стойността f(a,b)f(a,b) е 11 точно когато обратният елемент на aa по модул bb, взет в множеството {1,2,…,b−1}\{1,2,\ldots,b-1\}, е най-много b/2b/2. Прилагаме това за b=pb=p и a=n2a=n^2. Тогава f(n2,p)=1f(n^2,p)=1 точно когато обратният елемент на n2n^2 по модул pp е по-малък от p/2p/2. Но множествата{n2 mod p:1≤n≤p−1}\{n^2\bmod p:1\le n\le p-1\}и{n−2 mod p:1≤n≤p−1}\{n^{-2}\bmod p:1\le n\le p-1\}съвпадат с кратности: всеки квадратичен остатък се среща по два пъти. Следователно∑n=1p−1f(n2,p)=\sum_{n=1}^{p-1}f(n^2,p)=2∣{k:1≤k≤p−12, k2 mod p<p2}∣.2\left|\left\{k:1\le k\le\frac{p-1}{2},\ k^2\bmod p\lt{}\frac p2\right\}\right|.Всички обикновени квадрати 12,22,…,⌊x2p/2⌋21^2,2^2,\ldots,\left\lfloor\sqrt{\vphantom{x^2}p/2}\right\rfloor^2 са различни квадратични остатъци и са по-малки от p/2p/2. Затова∑n=1p−1f(n2,p)≥2⌊x2p2⌋>x22p−2.\sum_{n=1}^{p-1}f(n^2,p)\ge2\left\lfloor\sqrt{\vphantom{x^2}\frac p2}\right\rfloor\gt{}\sqrt{\vphantom{x^2}2p}-2.Исканото неравенство следва.
Отвори задачатаMathNetISL 2017 N8Условие — източник