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

IMO Shortlisted Problems

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

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

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

2005

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

11-12

20 задачи

Задача A1

Пълен запис
Условие
Да се намерят всички монични полиноми p(x)p(x) с цели коефициенти и степен 22, за които съществува полином q(x)q(x) с цели коефициенти, такъв че всички коефициенти на p(x)q(x)p(x)q(x) са равни на 11 или −1-1.
РешениеОтговорът еx2±x±1,x2±1,x2±2x+1.x^2\pm x\pm1,\qquad x^2\pm1,\qquad x^2\pm2x+1.Понеже свободният член на произведението p(x)q(x)p(x)q(x) е ±1\pm1, свободният член на pp също е ±1\pm1. Значиp(x)=x2+ax±1p(x)=x^2+ax\pm1за някое цяло число aa. При a=±1a=\pm1 полиномът pp вече има всички коефициенти ±1\pm1, така че можем да вземем q=1q=1. При a=0a=0 полиномите x2+1x^2+1 и x2−1x^2-1 също работят, например с q=x+1q=x+1. Нека сега ∣a∣≥2|a|\ge2. Ако pp има исканото свойство, то двата му корена x1,x2x_1,x_2 са корени и на някакъв полиномF(x)=xn+an−1xn−1+⋯+a0,F(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0,където всеки aia_i е равен на 11 или −1-1. Ако ∣xi∣>1|x_i|\gt{}1, от F(xi)=0F(x_i)=0 получаваме1=∣an−1xi+⋯+a0xin∣≤1=\left|\frac{a_{n-1}}{x_i}+\cdots+\frac{a_0}{x_i^n}\right|\le1∣xi∣+⋯+1∣xi∣n<1∣xi∣−1.\frac1{|x_i|}+\cdots+\frac1{|x_i|^n}\lt{}\frac1{|x_i|-1}.Следователно ∣xi∣<2|x_i|\lt{}2 за всеки корен извън единичната окръжност. При ∣a∣≥3|a|\ge3 сумата на корените е −a-a, което е невъзможно, ако и двата корена са по абсолютна стойност по-малки от 22 или ако единият е с абсолютна стойност най-много 11. Остават за проверка само полиномите x2±2x−1x^2\pm2x-1 и x2±2x+1x^2\pm2x+1. Първите два имат корен с абсолютна стойност поне 22, затова отпадат. Последните два работят:(x+1)2(x−1)=x3+x2−x−1,(x+1)^2(x-1)=x^3+x^2-x-1,(x−1)2(x+1)=x3−x2−x+1.(x-1)^2(x+1)=x^3-x^2-x+1.Така списъкът е пълен.
Отвори задачатаMathNetISL 2005 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека R>0\mathbb R_{\gt{}0} означава множеството на положителните реални числа. Да се определят всички функции f:R>0→R>0f:\mathbb R_{\gt{}0}\to\mathbb R_{\gt{}0}, за коитоf(x)f(y)=2f(x+yf(x))f(x)f(y)=2f(x+yf(x))за всички положителни реални числа xx и yy.
РешениеЕдинственото решение еf(x)=2(x>0).f(x)=2\qquad(x\gt{}0).Фиксираме y>0y\gt{}0 и разглеждаме функциятаφ(x)=x+yf(x),x>0.\varphi(x)=x+yf(x),\qquad x\gt{}0.Тя е инективна. Наистина, ако φ(x1)=φ(x2)\varphi(x_1)=\varphi(x_2), то от даденото уравнение следваf(x1)f(y)=2f(φ(x1))=f(x_1)f(y)=2f(\varphi(x_1))=2f(φ(x2))=f(x2)f(y),2f(\varphi(x_2))=f(x_2)f(y),а понеже f(y)>0f(y)\gt{}0, имаме f(x1)=f(x2)f(x_1)=f(x_2) и после x1=x2x_1=x_2. Ако x1>x2x_1\gt{}x_2, но f(x1)<f(x2)f(x_1)\lt{}f(x_2), избирамеy=x1−x2f(x2)−f(x1)>0.y=\frac{x_1-x_2}{f(x_2)-f(x_1)}\gt{}0.Тогава φ(x1)=φ(x2)\varphi(x_1)=\varphi(x_2), противоречие. Следователно ff е ненамаляваща. От уравнението получавамеf(x)f(y)=2f(x+yf(x))≥2f(x),f(x)f(y)=2f(x+yf(x))\ge2f(x),затова f(y)≥2f(y)\ge2 за всяко y>0y\gt{}0. Освен товаf(x+yf(x))=f(xy)=f(y+xf(y))≥f(2x),f(x+yf(x))=f(xy)=f(y+xf(y))\ge f(2x),като в последното неравенство използвахме f(y)≥2f(y)\ge2. Понеже y>0y\gt{}0 може да бъде произволно малко, а ff е ненамаляваща, следва, че ff е константна върху всеки интервал (x,2x](x,2x]. Тези интервали се застъпват по вериги и покриват R>0\mathbb R_{\gt{}0}, така че ff е константна върху цялото множество на положителните реални числа. Ако f≡cf\equiv c, уравнението дава c2=2cc^2=2c, а понеже c>0c\gt{}0, получаваме c=2c=2. Пряката проверка е очевидна.
Отвори задачатаMathNetISL 2005 A2Условие — източник

Задача A3

Пълен запис
Условие
Четири реални числа p,q,r,sp,q,r,s удовлетворяватp+q+r+s=9иp2+q2+r2+s2=21.p+q+r+s=9\qquad\text{и}\qquad p^2+q^2+r^2+s^2=21.Докажете, че за някоя пермутация (a,b,c,d)(a,b,c,d) на (p,q,r,s)(p,q,r,s) е изпълненоab−cd≥2.ab-cd\ge2.
РешениеБез ограничение некаp≥q≥r≥s.p\ge q\ge r\ge s.Ще докажем, че pq−rs≥2pq-rs\ge2, което е исканото твърдение за пермутацията (p,q,r,s)(p,q,r,s). Имаме(pq+rs)+(pr+qs)+(ps+qr)=(pq+rs)+(pr+qs)+(ps+qr)=(p+q+r+s)2−(p2+q2+r2+s2)2=30.\frac{(p+q+r+s)^2-(p^2+q^2+r^2+s^2)}2=30.От подредбата следваpq+rs≥pr+qs≥ps+qr,pq+rs\ge pr+qs\ge ps+qr,затова pq+rs≥10pq+rs\ge10. Нека x=p+qx=p+q. Тогаваx2+(9−x)2=(p+q)2+(r+s)2=21+2(pq+rs)≥x^2+(9-x)^2=(p+q)^2+(r+s)^2=21+2(pq+rs)\ge41.41.Това е еквивалентно на(x−4)(x−5)≥0.(x-4)(x-5)\ge0.Понеже x=p+q≥r+s=9−xx=p+q\ge r+s=9-x, имаме x≥9/2x\ge9/2, следователно x≥5x\ge5. Сега25≤(p+q)2=p2+q2+2pq=21−(r2+s2)+2pq≤25\le(p+q)^2=p^2+q^2+2pq=21-(r^2+s^2)+2pq\le21+2(pq−rs),21+2(pq-rs),понеже r2+s2+2rs=(r+s)2≥0r^2+s^2+2rs=(r+s)^2\ge0. Следователно pq−rs≥2pq-rs\ge2, както трябваше.
Отвори задачатаMathNetISL 2005 A3Условие — източник

Задача A4

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, които удовлетворяватf(x+y)+f(x)f(y)=f(xy)+2xy+1f(x+y)+f(x)f(y)=f(xy)+2xy+1за всички реални числа xx и yy.
РешениеОтговорът еf(x)=2x−1,f(x)=−x−1,f(x)=x2−1.f(x)=2x-1,\qquad f(x)=-x-1,\qquad f(x)=x^2-1.При y=0y=0 получаваме(f(0)+1)(f(x)−1)=0.(f(0)+1)(f(x)-1)=0.Функцията f(x)≡1f(x)\equiv1 не удовлетворява уравнението, следователноf(0)=−1.f(0)=-1.Замествайки (x,y)=(1,−1)(x,y)=(1,-1), получаваме f(1)=1f(1)=1 или f(−1)=0f(-1)=0. Ако f(1)=1f(1)=1, то при x=1x=1 уравнението даваf(y+1)=2y+1,f(y+1)=2y+1,тоест f(x)=2x−1f(x)=2x-1, което наистина работи. Нека занапред f(1)=a≠1f(1)=a\ne1 и f(−1)=0f(-1)=0. Замяната съответно с (x,y)=(z,1)(x,y)=(z,1) и (x,y)=(−z,−1)(x,y)=(-z,-1) даваf(z+1)=(1−a)f(z)+2z+1,(1)f(z+1)=(1-a)f(z)+2z+1,\tag{1}f(−z−1)=f(z)+2z+1.(2)f(-z-1)=f(z)+2z+1.\tag{2}Оттукf(z+1)=(1−a)f(−z−1)+a(2z+1),f(z+1)=(1-a)f(-z-1)+a(2z+1),или, с x=z+1x=z+1,f(x)=(1−a)f(−x)+a(2x−1).(3)f(x)=(1-a)f(-x)+a(2x-1).\tag{3}Аналогичноf(−x)=(1−a)f(x)+a(−2x−1).(4)f(-x)=(1-a)f(x)+a(-2x-1).\tag{4}Сравнявайки (3) и (4), получаваме(a2−2a)f(x)=−2a2x−(a2−2a).(5)(a^2-2a)f(x)=-2a^2x-(a^2-2a).\tag{5}Стойността a=2a=2 е невъзможна в (5). Ако a∉{0,2}a\notin\{0,2\}, от (5) следваf(x)=−2aa−2x−1.f(x)=-\frac{2a}{a-2}x-1.Директното заместване показва, че такава линейна функция удовлетворява уравнението само при a=−2a=-2, което дава f(x)=−x−1f(x)=-x-1. Остава случаят a=0a=0. Тогава от (3) следва f(x)=f(−x)f(x)=f(-x) за всяко xx. Прилагаме началното уравнение за двойките (z,z)(z,z) и (z,−z)(z,-z) и изваждаме. Като използваме четността и f(0)=−1f(0)=-1, получавамеf(2z)=4z2−1.f(2z)=4z^2-1.Следователно f(x)=x2−1f(x)=x^2-1 за всяко реално xx. И тази функция се проверява пряко.
Отвори задачатаMathNetISL 2005 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека x,y,zx,y,z са положителни реални числа, за които xyz≥1xyz\ge1. Докажете, чеx5−x2x5+y2+z2+y5−y2y5+z2+x2\frac{x^5-x^2}{x^5+y^2+z^2}+\frac{y^5-y^2}{y^5+z^2+x^2}+z5−z2z5+x2+y2≥+\frac{z^5-z^2}{z^5+x^2+y^2}\ge0.0.
РешениеНеравенството е еквивалентно наx2+y2+z2x5+y2+z2+x2+y2+z2y5+z2+x2\frac{x^2+y^2+z^2}{x^5+y^2+z^2}+\frac{x^2+y^2+z^2}{y^5+z^2+x^2}+x2+y2+z2z5+x2+y2≤+\frac{x^2+y^2+z^2}{z^5+x^2+y^2}\le3.(1)3.\tag{1}По неравенството на Коши-Шварц имаме(x5+y2+z2)(yz+y2+z2)≥(x^5+y^2+z^2)(yz+y^2+z^2)\ge(x5/2x2yz+y2+z2)2.\left(x^{5/2}\sqrt{\vphantom{x^2}yz}+y^2+z^2\right)^2.Понеже xyz≥1xyz\ge1, следва x5/2x2yz=x2x2xyz≥x2x^{5/2}\sqrt{\vphantom{x^2}yz}=x^2\sqrt{\vphantom{x^2}xyz}\ge x^2, и затова(x5+y2+z2)(yz+y2+z2)≥(x2+y2+z2)2.(x^5+y^2+z^2)(yz+y^2+z^2)\ge(x^2+y^2+z^2)^2.Следователноx2+y2+z2x5+y2+z2≤yz+y2+z2x2+y2+z2.\frac{x^2+y^2+z^2}{x^5+y^2+z^2}\le\frac{yz+y^2+z^2}{x^2+y^2+z^2}.Аналогично получаваме двете циклични оценки. След събиране намирамеx2+y2+z2x5+y2+z2+x2+y2+z2y5+z2+x2+x2+y2+z2z5+x2+y2≤yz+y2+z2+zx+z2+x2+xy+x2+y2x2+y2+z2=2+xy+yz+zxx2+y2+z2≤3,\begin{aligned} &\frac{x^2+y^2+z^2}{x^5+y^2+z^2}+\frac{x^2+y^2+z^2}{y^5+z^2+x^2}+\frac{x^2+y^2+z^2}{z^5+x^2+y^2}\\ &\le\frac{yz+y^2+z^2+zx+z^2+x^2+xy+x^2+y^2}{x^2+y^2+z^2}\\ &=2+\frac{xy+yz+zx}{x^2+y^2+z^2}\le3, \end{aligned}защото x2+y2+z2≥xy+yz+zxx^2+y^2+z^2\ge xy+yz+zx. Това доказва (1), а с него и задачата.
Отвори задачатаMathNetISL 2005 A5Условие — източник

Задача C1

Пълен запис
Условие
В една къща има четен брой лампи, разпределени по стаите така, че във всяка стая има поне три лампи. Всяка лампа има общ ключ с точно една друга лампа, която не е задължително да е в същата стая; натискането на този ключ сменя едновременно състоянието на двете лампи. Докажете, че от всяко начално състояние на лампите може да се натисне подходяща редица от ключове така, че накрая във всяка стая да има както светеща, така и несветеща лампа.
РешениеЩе наричаме една стая добра, ако в нея има и светеща, и несветеща лампа, и лоша в противен случай. Избираме състояние, достижимо от началното, в което броят на лошите стаи е възможно най-малък. Ще докажем, че този минимум е 00. Да допуснем, че има лоша стая R0R_0. Избираме лампа l0l_0 в нея и натискаме нейния ключ. Ако другата лампа със същия ключ също беше в R0R_0, то понеже в стаята има поне три лампи, след натискането R0R_0 би станала добра и никоя друга стая не би се променила; това противоречи на минималността. Значи другата лампа е в някаква стая R1R_1. След натискането R0R_0 става добра, затова по минималност R1R_1 трябва да стане лоша. Сега избираме в R1R_1 лампа l1l_1, различна от току-що променената лампа, и натискаме нейния ключ. Същият аргумент показва, че R1R_1 става добра, а стаята R2R_2, съдържаща другата лампа на този ключ, става лоша. Продължаваме така и получаваме редица от стаи R0,R1,R2,…R_0,R_1,R_2,\ldots и лампи li∈Ril_i\in R_i, като след натискане на ключа на lil_i стаята RiR_i става добра, а Ri+1R_{i+1} става лоша. Стаите са краен брой, затова нека Rm=RkR_m=R_k е първото повторение в редицата. Спираме след натискането на ключовете на l0,l1,…,lm−1l_0,l_1,\ldots,l_{m-1}. Всички стаи R0,R1,…,Rm−1R_0,R_1,\ldots,R_{m-1}, с изключение евентуално на повторената RkR_k, са добри. Стаята RkR_k е била лоша непосредствено преди натискането на ключа на lkl_k, а след това в нея са сменени две различни лампи: lkl_k и другата лампа от ключа на lm−1l_{m-1}. Понеже в стаята има поне три лампи, след тези две смени тя също е добра. Така получихме достижимо състояние с по-малко лоши стаи, противоречие. Следователно минималният брой лоши стаи е 00, което доказва твърдението.
Отвори задачатаMathNetISL 2005 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека kk е фиксирано положително цяло число. Една фирма продава сомбрера по специален начин. След като си купи сомбреро, всеки клиент може да убеди още двама души да си купят сомбрера; ако някой вече е бил убеден, ново убеждаване на същия човек не се брои. Всеки от тези нови клиенти може на свой ред да убеди още двама души и т.н. Ако всеки от двамата клиенти, убедени от даден човек, доведе поне kk нови купувачи, пряко или косвено, тогава този човек получава безплатен обучителен видеозапис. Докажете, че ако общо nn души са си купили сомбрера, то най-много nk+2\frac{n}{k+2} от тях са получили видеозаписи.
РешениеНека vv е броят на хората, получили видеозапис. Ще докажем по-силното твърдение: ако v>0v\gt{}0, то общият брой купувачи е поне (k+2)(v+1)−1(k+2)(v+1)-1. Оттук веднага следва n≥(k+2)vn\ge (k+2)v. Доказателството е с индукция по vv. За v=1v=1 човекът с видеозапис е убедил двама клиенти, всеки от които е довел поне kk нови купувачи; заедно с него това дава поне 2k+3=(k+2)⋅2−12k+3=(k+2)\cdot2-1 души. Случаят v=2v=2 се получава по същата идея, но общият индукционен аргумент обхваща и него. Да разгледаме подредба с даден брой v>0v\gt{}0 видеозаписа и с възможно най-малък брой купувачи. Вземаме човек PP, който не е бил убеден от никого. Ако PP не беше получил видеозапис, можехме да го премахнем, без да намалим броя на видеозаписите, противоречие с минималността. Следователно PP е получил видеозапис. Нека QQ и RR са двамата клиенти, които той е убедил. Нека CC е множеството от хората, които са дошли през клона на QQ, включително QQ, а DD - всички останали купувачи, освен PP. Нека в CC има xx видеозаписа. Ако x>0x\gt{}0, от индукционното предположение получаваме ∣C∣≥(k+2)(x+1)−1|C|\ge (k+2)(x+1)-1; ако x=0x=0, пак имаме ∣C∣≥k+1|C|\ge k+1, защото PP е получил видеозапис и клонът на QQ съдържа поне kk човека, убедени от QQ, плюс самия QQ. И в двата случая∣C∣≥(k+2)(x+1)−1.|C|\ge (k+2)(x+1)-1.Аналогично в DD има v−x−1v-x-1 видеозаписа и, понеже клонът на RR също има размер поне k+1k+1, получаваме∣D∣≥(k+2)(v−x)−1.|D|\ge (k+2)(v-x)-1.Следователноn=1+∣C∣+∣D∣≥n=1+|C|+|D|\ge1+(k+2)(x+1)−1+(k+2)(v−x)−1= 1+(k+2)(x+1)-1+(k+2)(v-x)-1=(k+2)(v+1)−1.(k+2)(v+1)-1.Индукцията е завършена, а оттук броят на хората с видеозапис е най-много n/(k+2)n/(k+2).
Отвори задачатаMathNetISL 2005 C2Условие — източник

Задача C3

Пълен запис
Условие
Дадена е правоъгълна дъска m×nm\times n, разделена на mnmn единични квадратчета. Две квадратчета са съседни, ако имат обща страна, а път е редица от квадратчета, в която всеки две последователни квадратчета са съседни. Всяко квадратче може да бъде оцветено в черно или бяло. Нека NN е броят на оцветяванията, при които съществува поне един черен път от левия край на дъската до десния край, а MM - броят на оцветяванията, при които съществуват поне два непресичащи се черни пътя от левия край до десния край. Докажете, чеN2≥2mnM.N^2\ge 2^{mn}M.
РешениеЩе докажем малко по-общо твърдение. Разглеждаме двустранна дъска m×nm\times n, в която точно kk квадратчета са прозрачни. Прозрачно квадратче има един цвят и се вижда еднакво от двете страни, а непрозрачно квадратче може да има независимо зададен цвят от горната и от долната страна. Нека CkC_k е броят на оцветяванията, при които има черен път от левия до десния край от горната страна и черен път от левия до десния край от долната страна, като двата пътя не минават през едно и също прозрачно квадратче. Ще докажем с индукция по kk, че2kCk≤N2.(1)2^k C_k\le N^2.\tag{1}При k=0k=0 двете страни са напълно независими, а условието е просто всяка от тях да има черен път отляво надясно. Следователно C0=N2C_0=N^2, така че (1) е вярно. Нека сега k≥1k\ge1 и изберем едно прозрачно квадратче qq. Превръщаме го в непрозрачно квадратче и получаваме дъска с k−1k-1 прозрачни квадратчета. Всяко оцветяване, броено в CkC_k, съдържа два пътя, които не използват едновременно qq. След като qq стане непрозрачно, цветът на новата му страна, която не е нужна на евентуалния път през qq, може да се избере по два начина и условието пак остава изпълнено. Значи от всяко оцветяване, броено в CkC_k, получаваме поне две оцветявания, броени в Ck−1C_{k-1}, тоестCk−1≥2Ck.C_{k-1}\ge2C_k.По индукционното предположение2kCk≤2k−1Ck−1≤N2,2^kC_k\le2^{k-1}C_{k-1}\le N^2,което доказва (1). Накрая вземаме k=mnk=mn, т.е. всички квадратчета са прозрачни. Тогава оцветяване на двустранната дъска е просто обикновено оцветяване на първоначалната дъска, а условието за двата пътя точно означава да има два непресичащи се черни пътя от левия до десния край. Следователно Cmn=MC_{mn}=M. От (1) получаваме2mnM≤N2,2^{mn}M\le N^2,както трябваше да се докаже.
Отвори задачатаMathNetISL 2005 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека n≥3n\ge3 е дадено положително цяло число. Искаме да означим всяка страна и всеки диагонал на правилен nn-ъгълник P1…PnP_1\ldots P_n с положително цяло число, не по-голямо от rr, така че: (i) всяко число от 11 до rr да се среща като етикет; (ii) във всеки триъгълник PiPjPkP_iP_jP_k два от трите етикета да са равни и по-големи от третия. При тези условия: (a) определете най-голямото възможно rr; (b) за тази най-голяма стойност на rr намерете броя на всички такива означавания.
РешениеОтговорът еrmax⁡=n−1r_{\max}=n-1и за тази стойност броят на означаванията еn!(n−1)!2n−1.\frac{n!(n-1)!}{2^{n-1}}.Първо описваме структурата. Нека MNMN е отсечка с максимален етикет rr. За всеки друг връх XX в триъгълника MXNMXN точно една от отсечките XMXM и XNXN има етикет rr, защото двете най-големи стойности в триъгълника трябва да са равни. Така върховете се разделят на две непразни групи AA и BB, като M∈AM\in A, N∈BN\in B, и отсечка има етикет rr точно когато свързва връх от AA с връх от BB. Вътре във всяка от групите остават същите условия, но с етикети, по-малки от rr. Оттук с индукция по броя на върховете получаваме горна граница за броя на различните етикети. Ако групите имат размери aa и bb, то вътре в тях могат да се използват най-много a−1a-1 и b−1b-1 етикета, а всички отсечки между групите имат общия етикет rr. Значиr≤(a−1)+(b−1)+1=n−1.r\le (a-1)+(b-1)+1=n-1.Тази граница се достига, например като разделяме рекурсивно множеството от върхове на две непразни части и даваме на всички отсечки между двете части най-големия оставащ етикет. Следователно най-голямото rr е n−1n-1. Нека ana_n е броят на означаванията с максимална стойност n−1n-1 върху дадени nn върха. Имаме a1=1a_1=1. За n≥2n\ge2 избираме размера kk на едната група, самата група по (nk)\binom nk начина и множеството от k−1k-1 етикета, които ще се използват вътре в нея, по (n−2k−1)\binom{n-2}{k-1} начина. Двете групи могат да се означат съответно по aka_k и an−ka_{n-k} начина. Така всяко разделяне е преброено два пъти, понеже групите могат да се разменят, и затоваan=12∑k=1n−1(nk)(n−2k−1)akan−k.(1)a_n=\frac12\sum_{k=1}^{n-1}\binom nk\binom{n-2}{k-1}a_ka_{n-k}.\tag{1}Ще докажем с индукция, чеan=n!(n−1)!2n−1.a_n=\frac{n!(n-1)!}{2^{n-1}}.За n=1n=1 е вярно. Замествайки индукционната хипотеза в (1), получавамеan=12∑k=1n−1(nk)(n−2k−1)k!(k−1)!2k−1(n−k)!(n−k−1)!2n−k−1=n!(n−2)!2n−2⋅12∑k=1n−11=n!(n−1)!2n−1.\begin{aligned} a_n&=\frac12\sum_{k=1}^{n-1}\binom nk\binom{n-2}{k-1}\frac{k!(k-1)!}{2^{k-1}}\frac{(n-k)!(n-k-1)!}{2^{n-k-1}}\\ &=\frac{n!(n-2)!}{2^{n-2}}\cdot\frac12\sum_{k=1}^{n-1}1 =\frac{n!(n-1)!}{2^{n-1}}. \end{aligned}Това завършва броенето.
Отвори задачатаMathNetISL 2005 C4Условие — източник

Задача C5

Пълен запис
Условие
Има nn жетона, всеки с една бяла и една черна страна, подредени в редица така, че първоначално белите им страни са нагоре. На всяка стъпка, ако това е възможно, избираме жетон с бялата страна нагоре, който не е един от двата крайни жетона, премахваме го и обръщаме най-близкия останал жетон отляво и най-близкия останал жетон отдясно. Докажете, че може да се стигне до състояние само с два останали жетона тогава и само тогава, когато n−1n-1 не се дели на 33.
РешениеПърво ще докажем необходимостта чрез инвариант. На всеки бял жетон приписваме числото (−1)b(-1)^b, където bb е броят на черните жетони вляво от него, и нека SS е сумата на тези числа. При един ход лесна проверка по цветовете на двата съседни жетона показва, че SS се променя с кратно на 33. Следователно остатъкът на SS по модул 33 е инвариант. В началото всички жетони са бели, така че S=nS=n. Освен това четността на броя на черните жетони също се запазва: премахва се бял жетон и се обръщат два други жетона. В крайно състояние с два жетона двата трябва да са с еднакъв цвят. Ако са бели, тогава S=2S=2; ако са черни, тогава S=0S=0. Значи непременно n≡0n\equiv0 или n≡2(mod3)n\equiv2\pmod3, тоест n−1n-1 не се дели на 33. Остава да покажем, че това условие е достатъчно. Ще докажем по индукция по nn, че ако n≡0n\equiv0 или 2(mod3)2\pmod3, играта може да завърши с два жетона. За n=2n=2 вече сме готови, а за n=3n=3 премахваме средния жетон. За n≥5n\ge5 можем да сведем играта до същата игра с n−3n-3 жетона. Номерираме първоначалните жетони отляво надясно. Първо премахваме втория жетон; тогава първият и третият се обръщат. След това премахваме четвъртия първоначален жетон; обръщат се третият и петият. Накрая премахваме третия първоначален жетон; обръщат се първият и петият. След тези три хода първият, петият, шестият и всички следващи жетони са отново с бялата страна нагоре и образуват редица от n−3n-3 жетона в начално състояние. Понеже nn и n−3n-3 имат един и същ остатък по модул 33, индукционното предположение завършва доказателството.
Отвори задачатаMathNetISL 2005 C5Условие — източник

Задача C6

Пълен запис
Условие
В математическо състезание са дадени 66 задачи. Всяка двойка задачи е решена от повече от 25\frac25 от състезателите. Никой не е решил всичките 66 задачи. Докажете, че има поне двама състезатели, всеки от които е решил точно 55 задачи.
РешениеНека състезателите са nn на брой, а aia_i е броят на състезателите, решили точно ii задачи. Преброяваме двойките (C,P)(C,P), където CC е състезател, а PP е двойка задачи, решени от CC. От условието всяка от 1515-те двойки задачи е решена от повече от 2n/52n/5 състезатели, следователно броят NN на тези двойки удовлетворяваN≥15⋅2n+15=6n+3.N\ge 15\cdot\frac{2n+1}{5}=6n+3.От друга страна, понеже никой не е решил 66 задачи,N=a2+3a3+6a4+10a5≤N=a_2+3a_3+6a_4+10a_5\le6n+4a5−(3a3+5a2+6a1+6a0). 6n+4a_5-(3a_3+5a_2+6a_1+6a_0).Оттук a5≥1a_5\ge1. Да допуснем, че a5=1a_5=1. Тогава последното неравенство и долната граница налагат всички останали състезатели да са решили точно 44 задачи, а общият брой решавания на двойки да е N=6n+4N=6n+4. Освен това непременно n≡2(mod5)n\equiv2\pmod5 и акоk=2n+15,k=\frac{2n+1}{5},то точно една двойка задачи е решена от k+1k+1 състезатели, а всяка от останалите 1414 двойки е решена от kk състезатели. Ще наричаме тази единствена двойка специална. Нека tt е задачата, която не е решена от единствения състезател с 55 решени задачи; ще я наричаме трудната задача. За фиксирана задача pp нека bpb_p е броят на състезателите, които са я решили, а MpM_p - броят на двойките (C,P)(C,P), в които двойката задачи PP съдържа pp и е решена от CC. Ако p=tp=t, всеки състезател, решил tt, е решил общо 44 задачи и допринася точно 33 двойки, съдържащи tt. Значи Mt=3btM_t=3b_t. От друга страна, петте двойки задачи, съдържащи tt, имат общо Mt=5kM_t=5k или 5k+15k+1, тоест Mt=2n+1M_t=2n+1 или 2n+22n+2. Следователно2n+1≡0 или 2(mod3).2n+1\equiv0\text{ или }2\pmod3.Избираме задача p≠tp\ne t, която не участва в специалната двойка; такава има, защото специалната двойка съдържа само две задачи. Тогава Mp=5k=2n+1M_p=5k=2n+1. Но единственият състезател с 55 решени задачи е решил pp и допринася 44 двойки, съдържащи pp, докато всеки друг състезател, решил pp, допринася 33. Следователно Mp=3bp+1M_p=3b_p+1, откъдето2n+1≡1(mod3),2n+1\equiv1\pmod3,противоречие. Значи предположението a5=1a_5=1 е невъзможно. Понеже вече знаем a5≥1a_5\ge1, получаваме a5≥2a_5\ge2, както трябваше да се докаже.
Отвори задачатаMathNetISL 2005 C6Условие — източник

Задача C7

Пълен запис
Условие
Нека n≥1n\ge1 е дадено цяло число и нека a1,…,ana_1,\ldots,a_n е редица от цели числа, такава че nn дели сумата a1+⋯+ana_1+\cdots+a_n. Докажете, че съществуват пермутации σ\sigma и τ\tau на числата 1,2,…,n1,2,\ldots,n, за коитоσ(i)+τ(i)≡ai(modn)\sigma(i)+\tau(i)\equiv a_i\pmod nза всяко i=1,2,…,ni=1,2,\ldots,n.
РешениеЩе докажем, че ако твърдението е вярно за една редица, то остава вярно след промяна само на два нейни члена, стига сумата да остане същата по модул nn. След това ще можем да стигнем до всяка редица от очевидно решима такава. Нека за редицата a1,…,ana_1,\ldots,a_n вече имаме пермутации σ\sigma и τ\tau. Нека редицата b1,…,bnb_1,\ldots,b_n се различава от нея само на позиции i1i_1 и i2i_2 и има същата сума по модул nn. Ще построим нови пермутации. Дефинираме редица от индекси i1,i2,i3,…i_1,i_2,i_3,\ldots така: за k≥2k\ge2 индексът ik+1i_{k+1} е единственият индекс, за койтоσ(ik−1)+τ(ik+1)≡bik(modn).(1)\sigma(i_{k-1})+\tau(i_{k+1})\equiv b_{i_k}\pmod n.\tag{1}Такъв индекс съществува и е единствен, защото τ\tau е пермутация. Нека iq=ipi_q=i_p е първото повторение в тази редица. Ще покажем, че p=1p=1 или p=2p=2. Ако p>2p\gt{}2, сумираме (1) за k=p,p+1,…,q−1k=p,p+1,\ldots,q-1. За всички междинни индекси редиците aa и bb съвпадат, затова bik≡σ(ik)+τ(ik)b_{i_k}\equiv\sigma(i_k)+\tau(i_k). След съкращаване получавамеσ(ip−1)+τ(iq−1)≡biq−1(modn).\sigma(i_{p-1})+\tau(i_{q-1})\equiv b_{i_{q-1}}\pmod n.По единствеността в дефиницията на iqi_q следва ip−1=iq−1i_{p-1}=i_{q-1}, което противоречи на избора на първото повторение. Следователно действително p=1p=1 или p=2p=2. Сега променяме пермутациите само върху индексите i1,…,iq−1i_1,\ldots,i_{q-1}. Полагамеσ′(ik)=σ(ik−1)(k=2,3,…,q−1),\sigma'(i_k)=\sigma(i_{k-1})\quad(k=2,3,\ldots,q-1),σ′(i1)=σ(iq−1).\qquad \sigma'(i_1)=\sigma(i_{q-1}).За τ′\tau' полагамеτ′(ik)=τ(ik+1)(k=2,3,…,q−1),\tau'(i_k)=\tau(i_{k+1})\quad(k=2,3,\ldots,q-1),а за i1i_1 вземаме τ′(i1)=τ(i2)\tau'(i_1)=\tau(i_2), ако p=1p=1, и τ′(i1)=τ(i1)\tau'(i_1)=\tau(i_1), ако p=2p=2. Извън тези индекси оставяме σ′\sigma' и τ′\tau' равни на σ\sigma и τ\tau. Получените σ′\sigma' и τ′\tau' са пермутации. От (1) веднага следва, чеσ′(ik)+τ′(ik)≡bik(modn)\sigma'(i_k)+\tau'(i_k)\equiv b_{i_k}\pmod n\qquad(k=2,3,…,q−1).(k=2,3,\ldots,q-1).За всички останали индекси, различни от i1i_1, равенството е очевидно. Накрая сумите на двете страни по всички индекси са равни по модул nn, понеже bb има същата обща сума като aa и σ′,τ′\sigma',\tau' са пермутации; следователно равенството важи и за i1i_1. Остава началото. Редицата ci≡2i(modn)c_i\equiv2i\pmod n е решима чрез σ(i)=i\sigma(i)=i и τ(i)=i\tau(i)=i, а сумата на cic_i е делима на nn. Всяка друга редица със сума, делима на nn, се получава от нея чрез краен брой промени на две позиции, запазващи сумата по модул nn. По доказаната стъпка тя също е решима.
Отвори задачатаMathNetISL 2005 C7Условие — източник

Задача C8

Пълен запис
Условие
Нека MM е изпъкнал nn-ъгълник, n≥4n\ge4. Някои n−3n-3 от диагоналите му са оцветени в зелено, а други n−3n-3 диагонала са оцветени в червено, така че никои два диагонала от един и същ цвят не се пресичат във вътрешността на MM. Да се намери най-големият възможен брой пресечни точки на зелен и червен диагонал във вътрешността на MM.
РешениеОтговорът е⌈34(n−3)2⌉.\left\lceil\frac34(n-3)^2\right\rceil.За зелен диагонал dd нека CdC_d е броят на червените диагонали, които го пресичат. Ще оценим сумата ∑dCd\sum_d C_d по всички зелени диагонали. Нека dd и ee са два зелени диагонала и нека едната част на многоъгълника между тях има mm върха. Понеже червените диагонали не се пресичат помежду си, най-много n−m−1n-m-1 от тях могат да пресичат едновременно dd и ee. Всеки от останалите червени диагонали пресича най-много един от dd и ee, а в частта с mm върха има най-много m−2m-2 такива диагонала. СледователноCd+Ce≤2(n−m−1)+(m−2)=2n−m−4.(1)C_d+C_e\le 2(n-m-1)+(m-2)=2n-m-4.\tag{1}Зелените диагонали образуват триангулация на MM. Можем да ги подредим в редица d1,d2,…,dn−3d_1,d_2,\ldots,d_{n-3} по следния начин. Първо избираме две зелени диагонала, които отрязват две триъгълни уши и оставят (n−2)(n-2)-ъгълник; после в останалия многоъгълник правим същото и продължаваме. Ако n−3=2r+en-3=2r+e, където e∈{0,1}e\in\{0,1\}, то за всяко k=1,2,…,rk=1,2,\ldots,r частта между d2k−1d_{2k-1} и d2kd_{2k} има поне n−2kn-2k върха. От (1) получавамеCd2k−1+Cd2k≤n+2k−4.C_{d_{2k-1}}+C_{d_{2k}}\le n+2k-4.Ако остане един непарен зелен диагонал, за него очевидно Cd≤n−3C_d\le n-3. Сумирайки, намираме∑dCd≤\sum_d C_d\le∑k=1r(n+2k−4)+e(n−3)=\sum_{k=1}^r(n+2k-4)+e(n-3)=3r2+e(3r+1)=⌈34(n−3)2⌉.3r^2+e(3r+1)=\left\lceil\frac34(n-3)^2\right\rceil.Това дава горната граница. Остава конструкция. Нека върховете са A1,A2,…,AnA_1,A_2,\ldots,A_n в този ред и нека ℓ=⌊n+12⌋\ell=\left\lfloor\frac{n+1}{2}\right\rfloor. Оцветяваме в зелено диагоналитеAiAn(2≤i≤ℓ),A_iA_n\quad(2\le i\le \ell),AℓAj(ℓ+2≤j≤n−1),\qquad A_\ell A_j\quad(\ell+2\le j\le n-1),а в червено диагоналитеA1Aj(ℓ+1≤j≤n−1),A_1A_j\quad(\ell+1\le j\le n-1),AjAℓ+1(2≤j≤ℓ−1).\qquad A_jA_{\ell+1}\quad(2\le j\le \ell-1).Във всеки цвят получаваме точно n−3n-3 диагонала и те не се пресичат помежду си. Ако положим a=ℓ−1a=\ell-1 и b=n−ℓ−1b=n-\ell-1, където aa и bb се различават най-много с 11, броят на зеленочервените пресичания в тази конструкция еab+a(a−1)2+b(b−1)2+(a−1)(b−1).ab+\frac{a(a-1)}2+\frac{b(b-1)}2+(a-1)(b-1).При n−3=2rn-3=2r това е 3r23r^2, а при n−3=2r+1n-3=2r+1 е 3r2+3r+13r^2+3r+1. И в двата случая получаваме точно⌈34(n−3)2⌉,\left\lceil\frac34(n-3)^2\right\rceil,така че горната граница е достижима.
Отвори задачатаMathNetISL 2005 C8Условие — източник

Задача N1

Пълен запис
Условие
Редицата a1,a2,…a_1,a_2,\ldots е зададена сan=2n+3n+6n−1(n=1,2,…).a_n=2^n+3^n+6^n-1\qquad(n=1,2,\ldots).Да се определят всички положителни цели числа, които са взаимно прости с всеки член на редицата.
РешениеЩе докажем, че единственото такова число е 11. Достатъчно е да покажем, че за всяко просто число pp съществува член ama_m, който се дели на pp. За p=2p=2 и p=3p=3 имамеa2=22+32+62−1=48,a_2=2^2+3^2+6^2-1=48,така че p∣a2p\mid a_2. Нека p>3p\gt{}3. По малката теорема на Ферма6ap−2=3⋅2p−1+2⋅3p−1+6p−1−6≡6a_{p-2}=3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1}-6\equiv3+2+1−6≡0(modp).3+2+1-6\equiv0\pmod p.Понеже pp не дели 66, получаваме p∣ap−2p\mid a_{p-2}. Следователно всяко просто число дели някой член на редицата, и положително цяло число, взаимно просто с всички членове, не може да има прост делител. Значи то е 11.
Отвори задачатаMathNetISL 2005 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека a1,a2,…a_1,a_2,\ldots е редица от цели числа с безкрайно много положителни и безкрайно много отрицателни членове. Да предположим, че за всяко положително цяло число nn числата a1,a2,…,ana_1,a_2,\ldots,a_n дават nn различни остатъка при деление на nn. Докажете, че всяко цяло число се среща точно веднъж в редицата.
РешениеОт условието веднага следва, че всички членове на редицата са различни: ако ai=aja_i=a_j за i<ji\lt{}j, то първите jj члена не биха давали различни остатъци по модул jj. Ще докажем, че за всяко nn множествотоAn={a1,a2,…,an}A_n=\{a_1,a_2,\ldots,a_n\}се състои от nn последователни цели числа. Нека i<ni\lt{}n. Ако d=∣ai−an∣≥nd=|a_i-a_n|\ge n, тогава сред първите dd члена се намират и aia_i, и ana_n, а те са сравними по модул dd; противоречие с условието за dd. Значи∣ai−an∣≤n−1|a_i-a_n|\le n-1за всички i<ni\lt{}n. По индукция всички разлики между два елемента на AnA_n са най-много n−1n-1, а понеже елементите са nn различни цели числа, AnA_n е точно интервал от nn последователни цели числа. Да допуснем, че някое цяло число kk не се среща в редицата. Тогава нито едно от последователните множества AnA_n не съдържа kk. Понеже An⊂An+1A_n\subset A_{n+1}, всички тези интервали остават от една и съща страна на kk: или всички членове са <k\lt{}k, или всички са >k\gt{}k. Това противоречи на условието, че редицата има безкрайно много положителни и безкрайно много отрицателни членове. Следователно всяко цяло число се среща в редицата. Понеже вече знаем, че членовете са различни, всяко цяло число се среща точно веднъж.
Отвори задачатаMathNetISL 2005 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека a,b,c,d,e,fa,b,c,d,e,f са положителни цели числа. Да предположим, че суматаS=a+b+c+d+e+fS=a+b+c+d+e+fдели и двете числаabc+defиab+bc+ca−de−ef−fd.abc+def\qquad\text{и}\qquad ab+bc+ca-de-ef-fd.Докажете, че SS е съставно число.
РешениеРазглеждаме полиномаP(x)=(x+a)(x+b)(x+c)−(x−d)(x−e)(x−f).P(x)=(x+a)(x+b)(x+c)-(x-d)(x-e)(x-f).След разкриване получавамеP(x)=Sx2+Qx+R,P(x)=Sx^2+Qx+R,къдетоQ=ab+bc+ca−de−ef−fd,R=abc+def.Q=ab+bc+ca-de-ef-fd,\qquad R=abc+def.По условие SS дели QQ и RR, следователно S∣P(x)S\mid P(x) за всяко цяло число xx. В частностS∣P(d)=(d+a)(d+b)(d+c).S\mid P(d)=(d+a)(d+b)(d+c).НоS>d+a,S>d+b,S>d+c,S\gt{}d+a,\qquad S\gt{}d+b,\qquad S\gt{}d+c,защото b+c+e+fb+c+e+f, съответно a+c+e+fa+c+e+f и a+b+e+fa+b+e+f, са положителни. Значи SS не може да дели нито един от трите множителя поотделно. Ако SS беше просто число, от делимостта на произведението щеше да дели един от множителите, невъзможно. Следователно SS е съставно.
Отвори задачатаMathNetISL 2005 N3Условие — източник

Задача N4

Пълен запис
Условие
Да се намерят всички положителни цели числа n>1n\gt{}1, за които съществува единствено цяло число aa с 0<a≤n!0\lt{}a\le n!, такова че n!n! дели an+1a^n+1.
РешениеЩе докажем, че исканите nn са точно простите числа. При n=2n=2 единствената възможност е a=1a=1, така че n=2n=2 работи. Ако n>2n\gt{}2 е четно, то 4∣n!4\mid n!, но an+1a^n+1 е сравнимо с 11 или 22 по модул 44; следователно решение няма. Нека сега nn е нечетно. Винаги имаме(n!−1)n+1≡(−1)n+1≡0(modn!),(n!-1)^n+1\equiv(-1)^n+1\equiv0\pmod{n!},така че a=n!−1a=n!-1 е решение. Ако nn е съставно и dd е негов прост делител, тогава d2∣n!d^2\mid n!. По бинома(n!d−1)n+1=∑k=1n(nk)(n!d)k(−1)n−k,\left(\frac{n!}{d}-1\right)^n+1=\sum_{k=1}^n {n\choose k}\left(\frac{n!}{d}\right)^k(-1)^{n-k},и всеки член в сумата се дели на n!n!: при k=1k=1 използваме d∣nd\mid n, а при k≥2k\ge2 използваме d2∣n!d^2\mid n!. Следователноa=n!d−1a=\frac{n!}{d}-1също е решение. То е различно от n!−1n!-1, затова съставните нечетни nn отпадат. Остава да разгледаме нечетно просто nn. Нека n!∣an+1n!\mid a^n+1 и 0<a≤n!0\lt{}a\le n!. Ще докажем, че n!∣a+1n!\mid a+1. За всяко просто p<np\lt{}n ако pp делиan+1a+1=an−1−an−2+⋯−a+1,\frac{a^n+1}{a+1}=a^{n-1}-a^{n-2}+\cdots-a+1,то p∣(−a)n−1p\mid(-a)^n-1. По малката теорема на Ферма имаме и p∣(−a)p−1−1p\mid(-a)^{p-1}-1, а понеже gcd⁡(n,p−1)=1\gcd(n,p-1)=1, следва p∣−a−1p\mid-a-1. Но тогава горното частно е сравнимо с nn по модул pp, което е невъзможно, тъй като p<np\lt{}n и nn е просто. Значи частното е взаимно просто с (n−1)!(n-1)!, откъдето (n−1)!∣a+1(n-1)!\mid a+1. Освен това от малката теорема на Ферма по модул nn получаваме an+1≡a+1(modn)a^n+1\equiv a+1\pmod n, така че n∣a+1n\mid a+1. Следователно n!∣a+1n!\mid a+1. Понеже 0<a≤n!0\lt{}a\le n!, единствената възможност е a=n!−1a=n!-1. Значи всяко просто nn работи и отговорът е: всички прости числа nn.
Отвори задачатаMathNetISL 2005 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека d(n)d(n) означава броя на положителните делители на положителното цяло число nn. Ще наричаме nn силно делимо, ако d(n)>d(m)d(n)\gt{}d(m) за всяко положително цяло число m<nm\lt{}n. Две силно делими числа m<nm\lt{}n се наричат последователни, ако няма силно делимо число ss с m<s<nm\lt{}s\lt{}n. а) Докажете, че има само крайно много двойки последователни силно делими числа (a,b)(a,b), за които a∣ba\mid b. б) Докажете, че за всяко просто число pp съществуват безкрайно много положителни силно делими числа rr, за които prpr също е силно делимо.
РешениеСъкратено ще наричаме силно делимите числа СД. Акоn=2α2(n)3α3(n)⋯qαq(n)n=2^{\alpha_2(n)}3^{\alpha_3(n)}\cdots q^{\alpha_q(n)}е разлагането на nn на прости множители, тоd(n)=∏q(αq(n)+1).d(n)=\prod_q(\alpha_q(n)+1).Ще използваме две леми. Лема 1. Ако nn е СД и p,qp,q са прости числа, като pk<qℓp^k\lt{}q^\ell, тоkαq(n)≤ℓαp(n)+(k+1)(ℓ−1).k\alpha_q(n)\le \ell\alpha_p(n)+(k+1)(\ell-1).Доказателство. Ако αq(n)<ℓ\alpha_q(n)\lt{}\ell, твърдението е ясно. Иначе числото npk/qℓnp^k/q^\ell е цяло и е по-малко от nn. Понеже nn е СД,d(npk/qℓ)<d(n).d(np^k/q^\ell)\lt{}d(n).След съкращаване на непроменените множители това е еквивалентно на(αq(n)+1)(αp(n)+1)>(\alpha_q(n)+1)(\alpha_p(n)+1)\gt{}(αq(n)−ℓ+1)(αp(n)+k+1),(\alpha_q(n)-\ell+1)(\alpha_p(n)+k+1),което се преобразува точно до желаното неравенство. Лема 2. За всяко просто pp и всяко цяло k≥0k\ge0 има само крайно много СД числа nn, за които αp(n)≤k\alpha_p(n)\le k. Доказателство. От лема 1 следва, че ако nn е СД и αp(n)≤k\alpha_p(n)\le k, то за всяко просто qq показателят αq(n)\alpha_q(n) е ограничен, а при q>pk+1q\gt{}p^{k+1} непременно αq(n)=0\alpha_q(n)=0. Следователно са възможни само крайно много такива nn. а) Да допуснем, че има безкрайно много двойки последователни СД числа (a,b)(a,b) с a∣ba\mid b. Понеже d(2a)>d(a)d(2a)\gt{}d(a), трябва да е b=2ab=2a; иначе между aa и bb би имало СД число. В частност d(s)≤d(a)d(s)\le d(a) за всяко s<2as\lt{}2a. По лема 2 за всички освен крайно много такива aa числото aa се дели на 22 и на 373^7. За тях от 8a/9<a8a/9\lt{}a имамеd(8a/9)<d(a),d(8a/9)\lt{}d(a),а от a<3a/2<2aa\lt{}3a/2\lt{}2a имамеd(3a/2)≤d(a).d(3a/2)\le d(a).Ако означим u=α2(a)u=\alpha_2(a) и v=α3(a)v=\alpha_3(a), тези две неравенства дават(u+4)(v−1)<(u+1)(v+1),(u+4)(v-1)\lt{}(u+1)(v+1),u(v+2)≤(u+1)(v+1).u(v+2)\le(u+1)(v+1).Оттук3v−5<2u,u≤v+1.3v-5\lt{}2u,\qquad u\le v+1.Следователно3v−5<2v+2,3v-5\lt{}2v+2,тоест v<7v\lt{}7, противоречие с 37∣a3^7\mid a. Значи такива двойки са само крайно много. б) Фиксираме просто число pp и положително цяло число kk. Нека nn е най-малкото СД число, за което αp(n)≥k\alpha_p(n)\ge k. Ще докажем, че npnp също е СД. Да допуснем противното. Тогава съществува СД число m<npm\lt{}np, за което d(m)≥d(np)d(m)\ge d(np). От избора на nn следва, че mm трябва да удовлетворяваαp(m)+1≤αp(n).\alpha_p(m)+1\le\alpha_p(n).Тогаваd(mp)=d(m)αp(m)+2αp(m)+1≥d(mp)=d(m)\frac{\alpha_p(m)+2}{\alpha_p(m)+1}\ged(n/p)αp(n)+1αp(n)=d(n), d(n/p)\frac{\alpha_p(n)+1}{\alpha_p(n)}=d(n),което противоречи на това, че nn е СД, защото mp<nmp\lt{}n. Следователно npnp е СД. Като приложим това за произволно големи kk, получаваме безкрайно много СД числа r=nr=n, за които prpr също е СД.
Отвори задачатаMathNetISL 2005 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека aa и bb са положителни цели числа, такива че an+na^n+n дели bn+nb^n+n за всяко положително цяло число nn. Докажете, че a=ba=b.
РешениеДа допуснем, че a≠ba\ne b. Тогава очевидно b>ab\gt{}a, защото условието при големи nn не може да е изпълнено, ако b<ab\lt{}a. Избираме просто число p>bp\gt{}b и полагамеn=(a+1)(p−1)+1.n=(a+1)(p-1)+1.Тогаваn≡1(modp−1)иn≡−a(modp).n\equiv1\pmod{p-1}\qquad\text{и}\qquad n\equiv-a\pmod p.За всяко цяло число rr по малката теорема на Ферма имамеrn=r⋅(rp−1)a+1≡r(modp).r^n=r\cdot(r^{p-1})^{a+1}\equiv r\pmod p.В частностan+n≡a−a≡0(modp).a^n+n\equiv a-a\equiv0\pmod p.Следователно pp дели an+na^n+n, а по условие тогава pp дели и bn+nb^n+n. Ноbn+n≡b−a(modp),b^n+n\equiv b-a\pmod p,затова p∣b−ap\mid b-a, което е невъзможно, понеже 0<b−a<p0\lt{}b-a\lt{}p. Полученото противоречие доказва a=ba=b. Обратно, при a=ba=b условието е изпълнено тривиално.
Отвори задачатаMathNetISL 2005 N6Условие — източник

Задача N7

Пълен запис
Условие
НекаP(x)=anxn+an−1xn−1+⋯+a0,P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0,където a0,…,ana_0,\ldots,a_n са цели числа, an>0a_n\gt{}0 и n≥2n\ge2. Докажете, че съществува положително цяло число mm, за което P(m!)P(m!) е съставно число.
РешениеНека pp е просто число и нека k<pk\lt{}p е четно положително число. По теоремата на Уилсън(p−k)!(k−1)!≡(p-k)!(k-1)!\equiv(−1)k−1(p−k)!(p−k+1)⋯(p−1)≡(-1)^{k-1}(p-k)!(p-k+1)\cdots(p-1)\equiv(−1)k−1(p−1)!≡1(modp).(-1)^{k-1}(p-1)!\equiv1\pmod p.Следователно(k−1)!nP((p−k)!)=∑i=0nai(k−1)! n−i((p−k)!(k−1)!)i≡∑i=0nai(k−1)! n−i=S((k−1)!)(modp),\begin{aligned} (k-1)!^nP((p-k)!)&=\sum_{i=0}^n a_i (k-1)!^{\,n-i}\bigl((p-k)!(k-1)!\bigr)^i\\ &\equiv\sum_{i=0}^n a_i (k-1)!^{\,n-i}=S((k-1)!)\pmod p, \end{aligned}къдетоS(x)=an+an−1x+⋯+a0xn.S(x)=a_n+a_{n-1}x+\cdots+a_0x^n.Понеже p∤(k−1)!p\nmid(k-1)!, получавамеp∣P((p−k)!)⟺p∣S((k−1)!).(1)p\mid P((p-k)!)\quad\Longleftrightarrow\quad p\mid S((k-1)!).\tag{1}Избираме четно k>2an+1k\gt{}2a_n+1. Тогаваs=(k−1)!ans=\frac{(k-1)!}{a_n}е цяло число, което се дели на всички прости числа, по-малки от kk. Освен товаS((k−1)!)=anbkS((k-1)!)=a_n b_kза някое цяло число bkb_k, удовлетворяващоbk≡1(mods).b_k\equiv1\pmod s.Значи всеки прост делител на bkb_k е по-голям от kk. За достатъчно голямо kk имаме ∣bk∣>1|b_k|\gt{}1; вземаме прост делител pp на bkb_k. Тогава p>kp\gt{}k и по (1)p∣P((p−k)!).p\mid P((p-k)!).Остава да изберем kk така, че P((p−k)!)>pP((p-k)!)\gt{}p. Некаk=(q−1)!,k=(q-1)!,където qq е достатъчно голямо просто число. Всички числа k+ik+i за i=1,2,…,q−1i=1,2,\ldots,q-1 са съставни: за i=1i=1 това следва от теоремата на Уилсън, а за 2≤i≤q−12\le i\le q-1 числото ii дели (q−1)!+i(q-1)!+i и е по-малко от него. Следователно простият делител pp на bkb_k има видp=k+q+rp=k+q+rза някое r≥0r\ge0. Тогава m=p−k=q+rm=p-k=q+r. Понеже deg⁡P=n≥2\deg P=n\ge2 и старшият коефициент е положителен, за достатъчно голямо qq имамеP(m!)=P((q+r)!)>(q+r)!>(q−1)!+q+r=p.P(m!)=P((q+r)!)\gt{}(q+r)!\gt{}(q-1)!+q+r=p.От друга страна вече знаем, че p∣P(m!)p\mid P(m!). Значи P(m!)P(m!) има нетривиален прост делител и е по-голямо от него; следователно е съставно число.
Отвори задачатаMathNetISL 2005 N7Условие — източник