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

IMO Shortlisted Problems

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

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

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

2011

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

11-12

22 задачи

Задача A1

Пълен запис
Условие
За всяко множество A={a1,a2,a3,a4}A=\{a_1,a_2,a_3,a_4\} от четири различни положителни цели числа със сбор sA=a1+a2+a3+a4s_A=a_1+a_2+a_3+a_4 нека pAp_A е броят на двойките (i,j)(i,j) с 1≤i<j≤41\le i\lt{}j\le4, за които ai+aja_i+a_j дели sAs_A. Сред всички множества от четири различни положителни цели числа намерете тези множества AA, за които pAp_A е максимално.
РешениеОтговорът е: множествата{d,5d,7d,11d}и{d,11d,19d,29d},\{d,5d,7d,11d\}\qquad\text{и}\qquad\{d,11d,19d,29d\},където dd е произволно положително цяло число. За тях pA=4p_A=4. Първо ще докажем, че pA≤4p_A\le4. Без ограничение нека a1<a2<a3<a4a_1\lt{}a_2\lt{}a_3\lt{}a_4. За всяка двойка индекси (i,j)(i,j) сумата ai+aja_i+a_j дели sAs_A точно когато дели сбора на другите два елемента. Ноa2+a4>a1+a3иa3+a4>a1+a2,a_2+a_4\gt{}a_1+a_3\qquad\text{и}\qquad a_3+a_4\gt{}a_1+a_2,следователно двойките (2,4)(2,4) и (3,4)(3,4) не се броят. Значи pA≤4p_A\le4. Нека сега pA=4p_A=4. Тогава останалите четири двойки трябва да се броят. От допълващите се двойки получавамеa1+a4=a2+a3,a_1+a_4=a_2+a_3,а за някои цели числа m>n≥2m\gt{}n\ge2 имамеm(a1+a2)=a3+a4,n(a1+a3)=a2+a4.m(a_1+a_2)=a_3+a_4,\qquad n(a_1+a_3)=a_2+a_4.От първото и третото равенство следваn(a1+a3)=2a2+a3−a1.n(a_1+a_3)=2a_2+a_3-a_1.Ако n≥3n\ge3, то лявата страна е по-голяма от 3a33a_3, а дясната е по-малка от 3a33a_3, противоречие. Следователно n=2n=2. При n=2n=2 от първото и третото равенство получаваме6a1+2a3=4a2,6a_1+2a_3=4a_2,а от първото и второто(m+1)a1+(m−1)a2=2a3.(m+1)a_1+(m-1)a_2=2a_3.Събирането на тези две равенства дава(m+7)a1=(5−m)a2.(m+7)a_1=(5-m)a_2.Понеже лявата страна е положителна, имаме m<5m\lt{}5, а от m>n=2m\gt{}n=2 следва m=3m=3 или m=4m=4. Решаването на системата при (m,n)=(3,2)(m,n)=(3,2) и (m,n)=(4,2)(m,n)=(4,2) дава съответно{a1,a2,a3,a4}={d,5d,7d,11d}\{a_1,a_2,a_3,a_4\}=\{d,5d,7d,11d\}и{a1,a2,a3,a4}={d,11d,19d,29d}.\{a_1,a_2,a_3,a_4\}=\{d,11d,19d,29d\}.Тези множества наистина имат pA=4p_A=4, което завършва доказателството.
Отвори задачатаMathNetISL 2011 A1Условие — източник

Задача A2

Пълен запис
Условие
Да се определят всички редици (x1,x2,…,x2011)(x_1,x_2,\ldots,x_{2011}) от положителни цели числа, за които за всяко положително цяло число nn съществува цяло число aa, такова чеx1n+2x2n+⋯+2011x2011n=an+1+1.x_1^n+2x_2^n+\cdots+2011x_{2011}^n=a^{n+1}+1.
РешениеОтговорът е единствената редица(x1,…,x2011)=(1,k,…,k),(x_1,\ldots,x_{2011})=(1,k,\ldots,k),k=2+3+⋯+2011=2023065.\qquad k=2+3+\cdots+2011=2023065.Тя работи, защото1n+2kn+⋯+2011kn=1+k⋅kn=kn+1+1.1^n+2k^n+\cdots+2011k^n=1+k\cdot k^n=k^{n+1}+1.Нека е дадена произволна редица с исканото свойство. За всяко nn избираме положително цяло число yny_n, за коетоx1n+2x2n+⋯+2011x2011n=ynn+1+1.x_1^n+2x_2^n+\cdots+2011x_{2011}^n=y_n^{n+1}+1.Понеже лявата страна е по-малка от (x1+2x2+⋯+2011x2011)n+1(x_1+2x_2+\cdots+2011x_{2011})^{n+1}, редицата (yn)(y_n) е ограничена. Следователно съществува положително цяло число yy, което се среща като yny_n за безкрайно много nn. Нека m=max⁡{x1,…,x2011}m=\max\{x_1,\ldots,x_{2011}\}. Групираме членовете с еднакви стойности на xix_i и пишемx1n+2x2n+⋯+2011x2011n=x_1^n+2x_2^n+\cdots+2011x_{2011}^n=cmmn+cm−1(m−1)n+⋯+c1,c_m m^n+c_{m-1}(m-1)^n+\cdots+c_1,където ci≥0c_i\ge0 и c1+⋯+cm=1+2+⋯+2011c_1+\cdots+c_m=1+2+\cdots+2011. Ще използваме лемата: ако цели числа b1,…,bNb_1,\ldots,b_N удовлетворяватb1+b22n+⋯+bNNn=0b_1+b_2 2^n+\cdots+b_N N^n=0за произволно големи положителни цели числа nn, то b1=⋯=bN=0b_1=\cdots=b_N=0. Наистина, ако bN≠0b_N\ne0, след деление на NnN^n получаваме∣bN∣≤(∣b1∣+⋯+∣bN−1∣)(N−1N)n,|b_N|\le(|b_1|+\cdots+|b_{N-1}|)\left(\frac{N-1}{N}\right)^n,което е невъзможно за достатъчно голямо nn. За безкрайно много nn имамеcmmn+⋯+c1−1−y⋅yn=0.c_m m^n+\cdots+c_1-1-y\cdot y^n=0.От лемата следва, че y=my=m, cm=mc_m=m, c1=1c_1=1, а всички останали cic_i са нули. Но тогава1+m=c1+⋯+cm=1+2+⋯+2011=1+k,1+m=c_1+\cdots+c_m=1+2+\cdots+2011=1+k,така че m=km=k. Условието c1=1c_1=1 означава x1=1x_1=1, а cm=k=2+3+⋯+2011c_m=k=2+3+\cdots+2011 означава x2=⋯=x2011=kx_2=\cdots=x_{2011}=k. Това е точно намерената редица.
Отвори задачатаMathNetISL 2011 A2Условие — източник

Задача A3

Пълен запис
Условие
Да се определят всички двойки (f,g)(f,g) от функции от множеството на реалните числа в себе си, които удовлетворяватg(f(x+y))=f(x)+(2x+y)g(y)g(f(x+y))=f(x)+(2x+y)g(y)за всички реални числа xx и yy.
РешениеОтговорът е: или ff и gg са тъждествено нулеви, или съществува реална константа CC, такава чеf(x)=x2+C,g(x)=xf(x)=x^2+C,\qquad g(x)=xза всяко реално xx. Лесно се проверява, че тези двойки работят. Заместваме y=−2xy=-2x и получавамеg(f(−x))=f(x).(1)g(f(-x))=f(x).\tag{1}Като приложим това за −x−y-x-y вместо xx, намирамеf(−x−y)=g(f(x+y))=f(x)+(2x+y)g(y).(2)f(-x-y)=g(f(x+y))=f(x)+(2x+y)g(y).\tag{2}Нека a,b,ca,b,c са произволни реални числа. В (2) с x=−bx=-b, y=a+by=a+b имамеf(−a)=f(−b)+(a−b)g(a+b).f(-a)=f(-b)+(a-b)g(a+b).Записваме аналогичните две равенства при циклична смяна на a,b,ca,b,c и ги събираме. След преозначаване получаваме, че за всички реални x,y,zx,y,z е изпълнено(y−x)g(z)+(z−y)g(x)+(x−z)g(y)=0.(y-x)g(z)+(z-y)g(x)+(x-z)g(y)=0.Това означава, че всеки три точки (x,g(x))(x,g(x)), (y,g(y))(y,g(y)), (z,g(z))(z,g(z)) от графиката на gg са колинеарни. Следователно gg е афинна функция: g(x)=Ax+Bg(x)=Ax+B. В (2) с x=0x=0 и y=−ty=-t получаваме, ако C=f(0)C=f(0),f(t)=At2−Bt+C.f(t)=At^2-Bt+C.Сравняваме коефициентите в (1). Коефициентът пред x2x^2 дава A2=AA^2=A, следователно A=0A=0 или A=1A=1. Ако A=0A=0, то g(x)=Bg(x)=B и f(x)=Cf(x)=C. От началното уравнение следва B=C+(2x+y)BB=C+(2x+y)B за всички x,yx,y, откъдето B=C=0B=C=0. Ако A=1A=1, то g(x)=x+Bg(x)=x+B и f(x)=x2−Bx+Cf(x)=x^2-Bx+C. Равенството (1) даваx2+Bx+C+B=x2−Bx+Cx^2+Bx+C+B=x^2-Bx+Cза всяко xx, следователно B=0B=0. Получаваме g(x)=xg(x)=x и f(x)=x2+Cf(x)=x^2+C.
Отвори задачатаMathNetISL 2011 A3Условие — източник

Задача A4

Пълен запис
Условие
Да се определят всички двойки (f,g)(f,g) от функции от множеството на положителните цели числа в себе си, които удовлетворяватfg(n)+1(n)+gf(n)(n)=f(n+1)−g(n+1)+1f^{g(n)+1}(n)+g^{f(n)}(n)=f(n+1)-g(n+1)+1за всяко положително цяло число nn. Тук fk(n)f^k(n) означава f(f(…f(n)…))f(f(\ldots f(n)\ldots)) с kk приложения на ff.
РешениеОтговорът е единствената двойкаf(n)=n,g(n)=1f(n)=n,\qquad g(n)=1за всички положителни цели nn. От даденото равенство следваfg(n)+1(n)<f(n+1)(1)f^{g(n)+1}(n)\lt{}f(n+1)\tag{1}за всяко nn, защото стойностите на gg са положителни цели числа. Нека y1<y2<⋯y_1\lt{}y_2\lt{}\cdots са всички стойности, които приема ff. Ще докажем последователно, че за всяко nn са верни твърдениятаf(x)=yn⟺x=n,yn=n.f(x)=y_n\Longleftrightarrow x=n,\qquad y_n=n.За n=1n=1 вземаме xx с f(x)=y1f(x)=y_1. Ако x>1x\gt{}1, то (1), приложено към x−1x-1, дава стойност на ff, по-малка от y1y_1, противоречие. Значи x=1x=1. Нека вече сме доказали всички твърдения до индекса n−1n-1 и твърдението f(x)=yn⟺x=nf(x)=y_n\Longleftrightarrow x=n. Тогава yn=ny_n=n, щом nn се окаже стойност на ff. Понеже f(n+1)f(n+1) не може да бъде сред y1,…,yny_1,\ldots,y_n, стойността yn+1y_{n+1} съществува. Избираме xx с f(x)=yn+1f(x)=y_{n+1}; тогава x>nx\gt{}n. От (1), приложено към x−1x-1, следва, чеb=fg(x−1)(x−1)∈{1,2,…,n}.b=f^{g(x-1)}(x-1)\in\{1,2,\ldots,n\}.Ако b<nb\lt{}n, то от индукционните твърдения за предходните стойности получаваме x−1=bx-1=b, противоречие с x>nx\gt{}n. Следователно b=nb=n. Понеже bb е стойност на ff, получаваме yn=ny_n=n; а от единствеността на праобраза на nn при ff премахваме итерациите една по една и стигаме до x−1=nx-1=n. Така f(x)=yn+1f(x)=y_{n+1} е възможно само за x=n+1x=n+1. Индукцията дава f(n)=nf(n)=n за всяко положително цяло nn. Тогава началното равенство ставаn+gn(n)=n+2−g(n+1),n+g^n(n)=n+2-g(n+1),тоестgn(n)+g(n+1)=2.g^n(n)+g(n+1)=2.Двата събираеми са положителни цели числа, следователно и двата са равни на 11. Оттук g(n)=1g(n)=1 за всяко nn, и намерената двойка е единствена.
Отвори задачатаMathNetISL 2011 A4Условие — източник

Задача A5

Пълен запис
Условие
Докажете, че за всяко положително цяло число nn множеството {2,3,4,…,3n+1}\{2,3,4,\ldots,3n+1\} може да се разбие на nn тройки така, че числата от всяка тройка да са дължини на страните на някакъв тъпоъгълен триъгълник.
РешениеЩе означаваме с [a,b][a,b] множеството {a,a+1,…,b}\{a,a+1,\ldots,b\}. Казваме, че {a,b,c}\{a,b,c\} е тъпоъгълна тройка, ако числата са страни на тъпоъгълен триъгълник. Първо ни трябва проста лема. Ако a<b<ca\lt{}b\lt{}c образуват тъпоъгълна тройка и x>0x\gt{}0, то {a,b+x,c+x}\{a,b+x,c+x\} също е тъпоъгълна тройка. Наистина, a,b+x,c+xa,b+x,c+x са страни на триъгълник, защото (c+x)−(b+x)=c−b<a(c+x)-(b+x)=c-b\lt{}a. Освен това(c+x)2−(b+x)2=(c−b)(c+b+2x)>(c+x)^2-(b+x)^2=(c-b)(c+b+2x)\gt{}(c−b)(c+b)>a2,(c-b)(c+b)\gt{}a^2,следователно триъгълникът е тъпоъгълен. Ще докажем твърдението по индукция по nn, като по-силно построяваме разбиване на [2,3n+1][2,3n+1] на тройки Ai={i,ai,bi}A_i=\{i,a_i,b_i\} за 2≤i≤n+12\le i\le n+1. При n=1n=1 вземаме A2={2,3,4}A_2=\{2,3,4\}. Нека n>1n\gt{}1 и t=⌊n/2⌋t=\lfloor n/2\rfloor. По индукционното предположение имаме разбиване на [2,3t+1][2,3t+1] на тъпоъгълни тройкиAi′={i,ai′,bi′}(2≤i≤t+1).A'_i=\{i,a'_i,b'_i\}\qquad(2\le i\le t+1).За тези ii полагамеAi={i,ai′+n−t,bi′+n−t}.A_i=\{i,a'_i+n-t,b'_i+n-t\}.По лемата тези тройки са тъпоъгълни и покриват[2,t+1]∪[n+2,n+2t+1].[2,t+1]\cup[n+2,n+2t+1].За t+2≤i≤n+1t+2\le i\le n+1 задавамеAi={i,n+t+i,2n+i}.A_i=\{i,n+t+i,2n+i\}.Тези тройки покриват останалите числа, защото⋃i=t+2n+1Ai=\bigcup_{i=t+2}^{n+1}A_i=[t+2,n+1]∪[n+2t+2,2n+t+1]∪[2n+t+2,3n+1].[t+2,n+1]\cup[n+2t+2,2n+t+1]\cup[2n+t+2,3n+1].Остава да проверим, че новите тройки са тъпоъгълни. За t+2≤i≤n+1t+2\le i\le n+1 имаме(2n+i)−(n+t+i)=n−t<t+2≤i,(2n+i)-(n+t+i)=n-t\lt{}t+2\le i,така че страните образуват триъгълник. Освен това(2n+i)2−(n+t+i)2=(n−t)(3n+t+2i)≥(2n+i)^2-(n+t+i)^2=(n-t)(3n+t+2i)\gen2(3n+3(t+1)+1)>n2⋅9n2≥(n+1)2≥i2.\frac n2(3n+3(t+1)+1)\gt{}\frac n2\cdot\frac{9n}{2}\ge(n+1)^2\ge i^2.Следователно всяка от тези тройки е тъпоъгълна. Индукцията е завършена.
Отвори задачатаMathNetISL 2011 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека ff е функция от множеството на реалните числа в себе си, която удовлетворяваf(x+y)≤yf(x)+f(f(x))f(x+y)\le yf(x)+f(f(x))за всички реални числа xx и yy. Докажете, че f(x)=0f(x)=0 за всяко x≤0x\le0.
РешениеКато положим y=t−xy=t-x, записваме условието във видаf(t)≤tf(x)−xf(x)+f(f(x))(1)f(t)\le tf(x)-xf(x)+f(f(x))\tag{1}за всички реални tt и xx. Нека a,ba,b са реални числа. Прилагаме (1) с t=f(a)t=f(a), x=bx=b, а после с t=f(b)t=f(b), x=ax=a. Получавамеf(f(a))−f(f(b))≤f(a)f(b)−bf(b),f(f(a))-f(f(b))\le f(a)f(b)-bf(b),f(f(b))−f(f(a))≤f(a)f(b)−af(a).f(f(b))-f(f(a))\le f(a)f(b)-af(a).След събиране следва2f(a)f(b)≥af(a)+bf(b).2f(a)f(b)\ge af(a)+bf(b).Сега вземаме b=2f(a)b=2f(a) и получаваме af(a)≤0af(a)\le0 за всяко реално aa. В частностf(a)≥0за всяко a<0.(2)f(a)\ge0\qquad\text{за всяко }a\lt{}0.\tag{2}Да допуснем, че f(x)>0f(x)\gt{}0 за някое реално xx. От (1) следва, че за всякоt<xf(x)−f(f(x))f(x)t\lt{}\frac{xf(x)-f(f(x))}{f(x)}имаме f(t)<0f(t)\lt{}0. Можем да изберем такова t<0t\lt{}0, което противоречи на (2). Следователноf(x)≤0за всяко реално x.(3)f(x)\le0\qquad\text{за всяко реално }x.\tag{3}От (2) и (3) получаваме f(x)=0f(x)=0 за всяко x<0x\lt{}0. Остава x=0x=0. В (1) с t=x<0t=x\lt{}0 получаваме0=f(x)≤f(f(x))=f(0),0=f(x)\le f(f(x))=f(0),а от (3) имаме f(0)≤0f(0)\le0. Следователно f(0)=0f(0)=0.
Отвори задачатаMathNetISL 2011 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа, за които min⁡(a+b,b+c,c+a)>2\min(a+b,b+c,c+a)\gt{}\sqrt2 и a2+b2+c2=3a^2+b^2+c^2=3. Докажете, чеa(b+c−a)2+b(c+a−b)2+c(a+b−c)2≥\frac{a}{(b+c-a)^2}+\frac{b}{(c+a-b)^2}+\frac{c}{(a+b-c)^2}\ge3(abc)2.\frac3{(abc)^2}.
РешениеПърво всички знаменатели са положителни. Например от b+c>2b+c\gt{}\sqrt2 следва b2+c2>1b^2+c^2\gt{}1, следователно a2=3−b2−c2<2a^2=3-b^2-c^2\lt{}2 и a<2<b+ca\lt{}\sqrt2\lt{}b+c. Аналогично b<c+ab\lt{}c+a и c<a+bc\lt{}a+b. Ще използваме неравенството на Хьолдер във вида∑i=1rxip+1yip≥\sum_{i=1}^r\frac{x_i^{p+1}}{y_i^p}\ge(x1+⋯+xr)p+1(y1+⋯+yr)p\frac{(x_1+\cdots+x_r)^{p+1}}{(y_1+\cdots+y_r)^p}за положителни p,xi,yip,x_i,y_i. При p=2p=2 получаваме∑cyca(b+c−a)2=∑cyc(a2)3a5(b+c−a)2≥\sum_{cyc}\frac{a}{(b+c-a)^2}=\sum_{cyc}\frac{(a^2)^3}{a^5(b+c-a)^2}\ge(a2+b2+c2)3(∑cyca5/2(b+c−a))2=\frac{(a^2+b^2+c^2)^3}{\left(\sum_{cyc}a^{5/2}(b+c-a)\right)^2}=27(∑cyca5/2(b+c−a))2.(1)\frac{27}{\left(\sum_{cyc}a^{5/2}(b+c-a)\right)^2}.\tag{1}От неравенството на Шур∑cyca3/2(a−b)(a−c)≥0\sum_{cyc}a^{3/2}(a-b)(a-c)\ge0след пренареждане следва∑cyca5/2(b+c−a)≤abc(a+b+c).(2)\sum_{cyc}a^{5/2}(b+c-a)\le abc(\sqrt a+\sqrt b+\sqrt c).\tag{2}От неравенството между средното аритметично и средното от четвърта степен имаме(a+b+c3)4≤a2+b2+c23=1,\left(\frac{\sqrt a+\sqrt b+\sqrt c}{3}\right)^4\le\frac{a^2+b^2+c^2}{3}=1,тоестa+b+c≤3.(3)\sqrt a+\sqrt b+\sqrt c\le3.\tag{3}От (1), (2) и (3) намираме∑cyca(b+c−a)2≥27(abc(a+b+c))2≥\sum_{cyc}\frac{a}{(b+c-a)^2}\ge\frac{27}{\left(abc(\sqrt a+\sqrt b+\sqrt c)\right)^2}\ge27(3abc)2=3(abc)2,\frac{27}{(3abc)^2}=\frac3{(abc)^2},както трябваше.
Отвори задачатаMathNetISL 2011 A7Условие — източник

Задача C1

Пълен запис
Условие
Нека n>0n\gt{}0 е цяло число. Дадени са везна и nn тежести с тегла 20,21,…,2n−12^0,2^1,\ldots,2^{n-1}. В редица от nn хода поставяме всички тежести върху везната. На първия ход избираме тежест и я поставяме на лявото блюдо. На всеки от следващите ходове избираме една от останалите тежести и я добавяме или към лявото, или към дясното блюдо. Да се намери броят на начините да извършим тези nn хода така, че дясното блюдо никога да не е по-тежко от лявото.
РешениеОтговорът еf(n)=(2n−1)!≠1⋅3⋅5⋯(2n−1).f(n)=(2n-1)!\neq{}1\cdot3\cdot5\cdots(2n-1).Ще докажем рекурсиятаf(n)=(2n−1)f(n−1)(n≥2).(1)f(n)=(2n-1)f(n-1)\qquad(n\ge2).\tag{1}След първия ход лявото блюдо винаги е поне с 11 по-тежко от дясното. Затова, ако в допустимо подреждане на тежестите премахнем тежестта 11, получаваме допустимо подреждане на тежестите 2,22,…,2n−12,2^2,\ldots,2^{n-1}. След деление на всички тегла на 22 броят на допустимите подреждания е f(n−1)f(n-1). Обратно, нека имаме допустимо подреждане на тежестите 2,22,…,2n−12,2^2,\ldots,2^{n-1}. Ако вмъкнем тежестта 11 на първо място, тя трябва да се сложи на лявото блюдо. Ако я вмъкнем след някой вече извършен ход, може да я сложим на което и да е блюдо, защото след първия ход разликата между блюдата е поне 22. Така за всяко подреждане на по-тежките тежести има точно1+2(n−1)=2n−11+2(n-1)=2n-1възможни вмъквания на тежестта 11, и всички те са допустими. Това доказва (1). Понеже f(1)=1f(1)=1, от (1) по индукция следваf(n)=1⋅3⋅5⋯(2n−1),f(n)=1\cdot3\cdot5\cdots(2n-1),както трябваше.
Отвори задачатаMathNetISL 2011 C1Условие — източник

Задача C2

Пълен запис
Условие
Да предположим, че 10001000 ученици са подредени в кръг. Да се докаже, че съществува цяло число kk с 100≤k≤300100\le k\le300, за което в кръга има последователна група от 2k2k ученици, чиято първа половина съдържа същия брой момичета като втората половина.
РешениеНомерираме учениците последователно с 1,2,…,10001,2,\ldots,1000. Полагаме ai=1a_i=1, ако ii-тият ученик е момиче, и ai=0a_i=0 иначе, като продължаваме редицата периодично с период 10001000. За k≥1k\ge1 некаSk(i)=ai+ai+1+⋯+ai+k−1.S_k(i)=a_i+a_{i+1}+\cdots+a_{i+k-1}.Трябва да докажем, че съществуват 100≤k≤300100\le k\le300 и индекс ii, за коитоSk(i)=Sk(i+k).S_k(i)=S_k(i+k).Да допуснем противното. Избираме ii, за което S100(i)S_{100}(i) е максимално. Тогава равенство за k=100k=100 не може да има, затоваS100(i−100)−S100(i)<0,S_{100}(i-100)-S_{100}(i)\lt{}0,S100(i)−S100(i+100)>0.\qquad S_{100}(i)-S_{100}(i+100)\gt{}0.Следователно при преминаване от i−100i-100 до ii величината S100(t)−S100(t+100)S_{100}(t)-S_{100}(t+100) сменя знак и съществува j∈[i−100,i−1]j\in[i-100,i-1], такова чеS100(j)≤S100(j+100)−1,S_{100}(j)\le S_{100}(j+100)-1,ноS100(j+1)≥S100(j+101)+1.(1)S_{100}(j+1)\ge S_{100}(j+101)+1.\tag{1}Изваждайки първото неравенство от второто, получавамеaj+100−aj≥aj+200−aj+100+2,a_{j+100}-a_j\ge a_{j+200}-a_{j+100}+2,откъдетоaj=0,aj+100=1,aj+200=0.a_j=0,\qquad a_{j+100}=1,\qquad a_{j+200}=0.Връщайки това в (1), намирамеS99(j+1)=S99(j+101).(2)S_{99}(j+1)=S_{99}(j+101).\tag{2}Нека pp и qq са най-малките положителни цели числа, за коитоaj−p=1,aj+200+q=1.a_{j-p}=1,\qquad a_{j+200+q}=1.Ако всички ученици са от един и същи пол, твърдението е очевидно, така че тези числа съществуват. По симетрия можем да приемем p≥qp\ge q. Ако p≥200p\ge200, тоaj=aj−1=⋯=aj−199=0,a_j=a_{j-1}=\cdots=a_{j-199}=0,и тогава S100(j−199)=S100(j−99)=0S_{100}(j-199)=S_{100}(j-99)=0, което отново дава забранено равенство за k=100k=100. Значи q≤p≤199q\le p\le199. Сега от (2) получавамеS100+q(j−q+1)=S99(j+1)+1S_{100+q}(j-q+1)=S_{99}(j+1)+1иS100+q(j+101)=S99(j+101)+1.S_{100+q}(j+101)=S_{99}(j+101)+1.СледователноS100+q(j−q+1)=S100+q(j+101),S_{100+q}(j-q+1)=S_{100+q}(j+101),а 100≤100+q≤299100\le100+q\le299. Това противоречи на допускането и доказва задачата.
Отвори задачатаMathNetISL 2011 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека SS е крайно множество от поне две точки в равнината. Да предположим, че няма три колинеарни точки от SS. Вятърна мелница ще наричаме следния процес. Започваме с права ℓ\ell, която минава през точка P∈SP\in S. Завъртаме ℓ\ell по часовниковата стрелка около опорната точка PP, докато правата мине през друга точка Q∈SQ\in S. Тогава QQ става новата опорна точка. Процесът продължава безкрайно, като опорната точка винаги е точка от SS. Да се докаже, че за подходящ избор на P∈SP\in S и подходяща начална права ℓ\ell, минаваща през PP, получената вятърна мелница ще посещава всяка точка от SS като опорна точка безкрайно много пъти.
РешениеОриентираме въртящата се права и наричаме двете нейни страни оранжева и синя. Когато опорната точка се смени от TT на UU, веднага след смяната точката TT е от същата страна, от която UU е била непосредствено преди смяната. Следователно броят на точките от SS от оранжевата страна и броят на точките от синята страна се запазват през целия процес, с изключение на моментите, в които правата съдържа две точки от SS. Първо нека ∣S∣=2n+1|S|=2n+1. През всяка точка T∈ST\in S има права, която оставя по nn точки от двете страни. Наистина, избираме ориентирана права през TT, която не съдържа друга точка от SS, и нека от оранжевата страна има n+rn+r точки. След завъртане на тази права на 180∘180^\circ около TT от оранжевата страна ще има n−rn-r точки, а броят се променя с 11 при всяко преминаване през точка от SS. Значи за някое междинно положение броят е nn. Избираме произволна начална опорна точка PP и начална права през нея, която разделя останалите точки поравно. Ще покажем, че при всяко завъртане на 180∘180^\circ мелницата посещава всички точки. Нека T∈ST\in S и нека ℓ\ell е права през TT, която разделя останалите точки поравно. В дадено направление има единствена такава права: паралелно преместване би нарушило равенството на броевете от двете страни. Понеже мелницата запазва тези броеве, когато нейната права стане успоредна на ℓ\ell, тя трябва да съвпадне с ℓ\ell и следователно да мине през TT. Сега нека ∣S∣=2n|S|=2n. По същия начин през всяка точка T∈ST\in S има ориентирана права с n−1n-1 точки от оранжевата страна и nn точки от синята страна. Избираме такава права през произволна точка PP за начална. Ако T∈ST\in S и ℓ\ell е ориентирана права през TT със същото разделяне, то и тук паралелно преместване би променило броевете от двете страни. Затова, когато мелницата има същото направление като ℓ\ell, тя трябва да мине през TT. Това се случва при всяко завъртане на 360∘360^\circ. И в двата случая процесът продължава безкрайно и същият аргумент се повтаря след всеки съответен полуоборот или пълен оборот. Следователно всяка точка от SS е опорна точка безкрайно много пъти.
Отвори задачатаMathNetISL 2011 C3Условие — източник

Задача C4

Пълен запис
Условие
Да се намери най-голямото положително цяло число kk със следното свойство: множеството на положителните цели числа може да се разбие на kk подмножества A1,A2,…,AkA_1,A_2,\ldots,A_k, така че за всяко цяло число n≥15n\ge15 и всяко i∈{1,2,…,k}i\in\{1,2,\ldots,k\} да съществуват два различни елемента на AiA_i със сбор nn.
РешениеОтговорът еk=3.k=3.Първо даваме пример за k=3k=3:A1={1,2,3}∪{3m:m≥4},A_1=\{1,2,3\}\cup\{3m:m\ge4\},A2={4,5,6}∪{3m−1:m≥4},A_2=\{4,5,6\}\cup\{3m-1:m\ge4\},A3={7,8,9}∪{3m−2:m≥4}.A_3=\{7,8,9\}\cup\{3m-2:m\ge4\}.Сборовете на два различни елемента на A1A_1 дават всички числа n≥13n\ge13, тези на A2A_2 дават всички n≥15n\ge15, а тези на A3A_3 дават всички n≥17n\ge17. За A3A_3 остават само 1515 и 1616, но15=7+8,16=7+9.15=7+8,\qquad 16=7+9.Значи k=3k=3 е възможно. Ще докажем, че k≥4k\ge4 е невъзможно. Ако имаме разбиване на k≥4k\ge4 множества с исканото свойство, то множестватаA1,A2,A3,A4∪A5∪⋯∪AkA_1,A_2,A_3,A_4\cup A_5\cup\cdots\cup A_kсъщо имат същото свойство. Затова е достатъчно да изключим k=4k=4. НекаBi=Ai∩{1,2,…,23}(i=1,2,3,4).B_i=A_i\cap\{1,2,\ldots,23\}\qquad(i=1,2,3,4).За всяко ii всяко от числата 15,16,…,2415,16,\ldots,24 трябва да се представя като сбор на два различни елемента на BiB_i, защото двата положителни събираеми са по-малки от съответния сбор. Следователно всяко BiB_i има поне 55 елемента. Но∣B1∣+∣B2∣+∣B3∣+∣B4∣=23,|B_1|+|B_2|+|B_3|+|B_4|=23,така че за някое jj имаме ∣Bj∣=5|B_j|=5. НекаBj={x1,x2,x3,x4,x5}.B_j=\{x_1,x_2,x_3,x_4,x_5\}.Десетте двойни сборове на тези пет числа трябва да са точно числата 15,16,…,2415,16,\ldots,24. Сумирайки ги по два начина, получаваме4(x1+x2+x3+x4+x5)=15+16+⋯+24=195.4(x_1+x_2+x_3+x_4+x_5)=15+16+\cdots+24=195.Това е невъзможно, понеже 195195 не се дели на 44. Следователно k≤3k\le3, а заедно с примера това дава k=3k=3.
Отвори задачатаMathNetISL 2011 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека mm е положително цяло число и да разгледаме шахматна дъска, съставена от m×mm\times m единични квадрата. В центровете на някои от тези единични квадрати има мравка. В момент 00 всяка мравка започва да се движи със скорост 11 успоредно на някоя страна на дъската. Когато две мравки, движещи се в противоположни посоки, се срещнат, и двете завиват на 90∘90^\circ по часовниковата стрелка и продължават да се движат със скорост 11. Когато се срещнат повече от две мравки или когато две мравки, движещи се в перпендикулярни посоки, се срещнат, мравките продължават да се движат в същата посока като преди срещата. Когато мравка достигне някоя страна на дъската, тя пада от дъската и повече не се връща. Като се разгледат всички възможни начални положения, да се намери най-късният възможен момент, в който последната мравка пада от дъската, или да се докаже, че такъв момент не съществува непременно.
РешениеОтговорът е3m2−1.\frac{3m}{2}-1.При m=1m=1 това е ясно, затова нека m>1m\gt{}1. За достигане на тази стойност поставяме една мравка в центъра на югозападния ъглов квадрат, насочена на изток, и една мравка в центъра на югоизточния ъглов квадрат, насочена на запад. Те се срещат в средата на най-долния ред след време (m−1)/2(m-1)/2. След завоя мравката, която тръгва на север, остава на дъската още m−1/2m-1/2 единици време. Така последната мравка пада в моментm−12+m−12=3m2−1.\frac{m-1}{2}+m-\frac12=\frac{3m}{2}-1.Остава да докажем, че по-късен момент е невъзможен. Среща на точно две мравки, движещи се в противоположни посоки, ще наричаме сблъсък. При даден сблъсък можем вместо завой по часовниковата стрелка да накараме двете мравки да завият обратно на часовниковата стрелка. Тогава последващото движение на всички мравки като множество траектории не се променя; единствено двете мравки разменят местата си. Следователно за оценка на времето можем при всеки сблъсък да избираме в коя от двете посоки да завият двете участващи мравки. Избираме правилата така, че всяка мравка да бъде от един от два типа: СИ-мравки, които се движат само на север или изток, и ЮЗ-мравки, които се движат само на юг или запад. Въвеждаме координати с върхове на дъската (0,0),(m,0),(m,m),(0,m)(0,0),(m,0),(m,m),(0,m). В момент tt няма СИ-мравки в областта x+y<t+1x+y\lt{}t+1 и няма ЮЗ-мравки в областта x+y>2m−t−1x+y\gt{}2m-t-1. Затова, ако в момент tt има сблъсък в точка (x,y)(x,y), тоt+1≤x+y≤2m−t−1.(1)t+1\le x+y\le2m-t-1.\tag{1}Аналогично можем да изберем правилата така, че всяка мравка да се движи редуващо се само на север и запад или само на юг и изток. От това за всеки сблъсък в момент tt следва още∣x−y∣≤m−t−1.(2)|x-y|\le m-t-1.\tag{2}Да разгледаме СИ-мравка, чийто последен сблъсък е в момент tt и в точка (x,y)(x,y). Ако мравката изобщо няма сблъсъци, тя пада от дъската преди момент m−1/2<3m/2−1m-1/2\lt{}3m/2-1, така че този случай не е опасен. От (1) и (2) имамеx+y≥t+1,x−y≥−(m−t−1),x+y\ge t+1,\qquad x-y\ge-(m-t-1),откъдетоx≥t+1−m2.x\ge t+1-\frac m2.По симетрия същоy≥t+1−m2.y\ge t+1-\frac m2.След последния си сблъсък мравката се движи направо към някоя страна на дъската, което отнема най-много m−min⁡(x,y)m-\min(x,y) време. Затова общото време, което тази мравка прекарва на дъската, е най-многоt+m−min⁡(x,y)≤t+m−(t+1−m2)=3m2−1.t+m-\min(x,y)\le t+m-\left(t+1-\frac m2\right)=\frac{3m}{2}-1.Същият аргумент по симетрия важи и за ЮЗ-мравките. Следователно никоя мравка не може да падне по-късно от 3m/2−13m/2-1.
Отвори задачатаMathNetISL 2011 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека nn е положително цяло число и некаW=…x−1x0x1x2…W=\ldots x_{-1}x_0x_1x_2\ldotsе безкрайна периодична дума, съставена от буквите aa и bb. Да предположим, че минималният период NN на WW е по-голям от 2n2^n. Казваме, че крайна непразна дума UU се среща в WW, ако съществуват индекси k≤ℓk\le \ell, за коитоU=xkxk+1⋯xℓ.U=x_kx_{k+1}\cdots x_\ell.Крайна дума UU се нарича вездесъща, ако и четирите думи Ua,Ub,aU,bUUa,Ub,aU,bU се срещат в WW. Да се докаже, че има поне nn вездесъщи крайни непразни думи.
РешениеВ решението всички думи са непразни. За дума RR с дължина mm наричаме кратност на RR броя на индексите i∈{1,2,…,N}i\in\{1,2,\ldots,N\}, за които RR съвпада с поддуматаxi+1xi+2⋯xi+mx_{i+1}x_{i+2}\cdots x_{i+m}на WW; означаваме тази кратност с μ(R)\mu(R). Думата RR се среща в WW точно когато μ(R)>0\mu(R)\gt{}0. Всяко срещане на RR е следвано от една от буквите a,ba,b и е предшествано от една от тях, затоваμ(R)=μ(Ra)+μ(Rb)=μ(aR)+μ(bR).(1)\mu(R)=\mu(Ra)+\mu(Rb)=\mu(aR)+\mu(bR).\tag{1}Понеже NN е минимален период, всяка дума с дължина NN има кратност 00 или 11. Наистина, акоxi+1xi+2⋯xi+N=xj+1xj+2⋯xj+Nx_{i+1}x_{i+2}\cdots x_{i+N}=x_{j+1}x_{j+2}\cdots x_{j+N}за 1≤i<j≤N1\le i\lt{}j\le N, то j−ij-i също би бил период на WW, противоречие. Освен това, тъй като N>2nN\gt{}2^n, поне една от еднобуквените думи a,ba,b има кратност, по-голяма от 2n−12^{n-1}. За всяко k=0,1,…,n−1k=0,1,\ldots,n-1 избираме поддума UkU_k на WW сμ(Uk)>2k,\mu(U_k)\gt{}2^k,която има максимална възможна дължина сред думите с това свойство. Такава дума съществува, а максимална дължина има, защото думите с дължина NN имат кратност най-много 11. Фиксираме kk. Всяка дума, по-дълга от UkU_k и получена от нея чрез добавяне на една буква отляво или отдясно, има кратност най-много 2k2^k. Понеже μ(Uk)>2k\mu(U_k)\gt{}2^k, от (1) следва, че и двете думи UkaU_ka и UkbU_kb се срещат в WW; иначе цялата кратност би била в другото продължение, по-голяма от 2k2^k. Същият аргумент за ляво продължение показва, че aUkaU_k и bUkbU_k също се срещат. Следователно UkU_k е вездесъща. Още, ако μ(Uk)>2k+1\mu(U_k)\gt{}2^{k+1}, то от (1) поне едно от UkaU_ka и UkbU_kb би имало кратност по-голяма от 2k2^k, което противоречи на максималността на дължината на UkU_k. Значи2k<μ(Uk)≤2k+1.2^k\lt{}\mu(U_k)\le2^{k+1}.Тези интервали за k=0,1,…,n−1k=0,1,\ldots,n-1 са последователно разделени, така че думите U0,U1,…,Un−1U_0,U_1,\ldots,U_{n-1} са различни. Всички те са вездесъщи, следователно има поне nn такива думи.
Отвори задачатаMathNetISL 2011 C6Условие — източник

Задача C7

Пълен запис
Условие
Върху квадратна маса от 2011×20112011\times2011 клетки поставяме краен брой салфетки, всяка от които покрива квадрат от 52×5252\times52 клетки. Във всяка клетка записваме броя на салфетките, които я покриват, и отбелязваме максималния брой kk клетки, в които е записано едно и също ненулево число. Като се разгледат всички възможни конфигурации на салфетки, да се намери най-голямата възможна стойност на kk.
РешениеОтговорът е20112−57392=3986729.2011^2-57392=3986729.Ще използваме означението m=39m=39, така че 2011=52m−172011=52m-17. Първо построяваме конфигурация, при която 39867293986729 клетки съдържат едно и също положително число. Номерираме колоните отляво надясно и редовете отдолу нагоре с 1,2,…,20111,2,\ldots,2011. Всяка салфетка означаваме с координатите на долната лява клетка. Поставяме салфетки от следните четири вида:(52i+36,52j+1)(0≤j≤i≤m−2),(52i+36,52j+1)\quad(0\le j\le i\le m-2),(52i+1,52j+36)(0≤i≤j≤m−2),(52i+1,52j+36)\quad(0\le i\le j\le m-2),(52i+36,52i+36)(0≤i≤m−2),(52i+36,52i+36)\quad(0\le i\le m-2),и още салфетката (1,1)(1,1). При това построение всички клетки, освен тези, които попадат в припокриване между различни видове салфетки, са покрити точно веднъж. Директното преброяване по 52×5252\times52 блоковете дава, че броят на изключителните клетки е(522−352)m−172=57392.(52^2-35^2)m-17^2=57392.Значи останалите20112−57392=39867292011^2-57392=3986729клетки съдържат числото 11. Остава да докажем, че повече клетки с еднакво ненулево число не може да има. Разглеждаме произволна конфигурация и фиксираме положително цяло число MM. Нека gg е броят на клетките, в които е записано число, различно от MM. Ще докажем, чеg≥57392.g\ge57392.Това веднага дава горната граница. Нека права означава ред или колона. За една такава права ℓ\ell некаa1,a2,…,a52m−17a_1,a_2,\ldots,a_{52m-17}са числата в последователните нейни клетки. За r=1,2,…,52r=1,2,\ldots,52 полагамеsr=∑t≡r(mod52)at.s_r=\sum_{t\equiv r\pmod{52}} a_t.Сумите s1,…,s35s_1,\ldots,s_{35} имат по mm събираеми, а s36,…,s52s_{36},\ldots,s_{52} имат по m−1m-1 събираеми. Всяка салфетка, която пресича правата ℓ\ell, допринася с 11 към всяко srs_r, следователноs1=s2=⋯=s52.s_1=s_2=\cdots=s_{52}.Наричаме правата богата, ако тази обща стойност е по-голяма от (m−1)M(m-1)M, и бедна иначе. Ако ℓ\ell е богата, то във всяка от сумите s36,…,s52s_{36},\ldots,s_{52} има събираемо, по-голямо от MM; избираме по една такава клетка и я наричаме лоша за тази права. Така всяка богата права има поне 1717 лоши клетки. Ако ℓ\ell е бедна, общата стойност е по-малка от mMmM, затова във всяка от сумите s1,…,s35s_1,\ldots,s_{35} има събираемо, по-малко от MM; избираме по една такава клетка. Така всяка бедна права има поне 3535 лоши клетки. Наричаме индекс малък, ако е конгруентен на едно от числата 1,2,…,351,2,\ldots,35 по модул 5252, и голям иначе. Ред или колона също наричаме малък или голям според индекса му. Лошите клетки на богат ред лежат в големи колони, а лошите клетки на беден ред лежат в малки колони; аналогично за колоните. Слагаме по един маркер върху всяка клетка, която е лоша за своя ред или за своята колона. Освен това, за всяка малка богата права слагаме още един допълнителен маркер върху всяка от нейните лоши клетки. Всяка клетка с маркер има стойност, различна от MM. Ако клетка получи допълнителен маркер, нейната стойност е по-голяма от MM; тя лежи или в малък ред и голяма колона, или обратно. В първия случай тя не може да е лоша за колоната си: ако колоната е богата, лошите нейни клетки са в големи редове, а ако е бедна, лошите нейни клетки имат стойност по-малка от MM. Вторият случай е симетричен. Следователно всяка клетка получава най-много два маркера. Ако NN е общият брой маркери, тоN≤2g.(1)N\le2g.\tag{1}От друга страна, всяка малка права дава поне 3434 маркера: ако е богата, има поне 1717 лоши клетки и за всяка има допълнителен маркер, а ако е бедна, има поне 3535 лоши клетки. Всяка голяма права дава поне 1717 маркера. Има 2⋅35m2\cdot35m малки прави и 2⋅17(m−1)2\cdot17(m-1) големи прави, затоваN≥N\ge2(35m⋅34+17(m−1)⋅17)=2(35m\cdot34+17(m-1)\cdot17)=2(1479m−289)=2⋅57392.(2)2(1479m-289)=2\cdot57392.\tag{2}От (1) и (2) следва g≥57392g\ge57392. Така най-много 20112−57392=39867292011^2-57392=3986729 клетки могат да съдържат едно и също ненулево число, а построението показва, че тази граница се достига.
Отвори задачатаMathNetISL 2011 C7Условие — източник

Задача N1

Пълен запис
Условие
За всяко цяло число d>0d\gt{}0 нека f(d)f(d) е най-малкото положително цяло число, което има точно dd положителни делителя. Например f(1)=1f(1)=1, f(5)=16f(5)=16 и f(6)=12f(6)=12. Докажете, че за всяко цяло число k≥0k\ge0 числото f(2k)f(2^k) дели f(2k+1)f(2^{k+1}).
РешениеНека d(n)d(n) е броят на положителните делители на nn. Акоn=∏ppa(p)n=\prod_p p^{a(p)}е разлагането на nn на прости множители, тоd(n)=∏p(a(p)+1).d(n)=\prod_p(a(p)+1).Следователно d(n)d(n) е степен на 22 точно когато за всяко просто pp имамеa(p)=2b(p)−1=1+2+22+⋯+2b(p)−1a(p)=2^{b(p)}-1=1+2+2^2+\cdots+2^{b(p)-1}с някое неотрицателно цяло число b(p)b(p). Тогаваn=∏p∏i=0b(p)−1p2i,n=\prod_p\prod_{i=0}^{b(p)-1}p^{2^i},d(n)=2k с k=∑pb(p).\qquad d(n)=2^k\text{ с }k=\sum_p b(p).Нека SS е множеството на всички числа от вида p2rp^{2^r}, където pp е просто, а r≥0r\ge0 е цяло. От горното следва, че d(n)d(n) е степен на 22 точно когато nn е произведение на елементите на крайно подмножество T⊂ST\subset S със следното свойство: ако t∈Tt\in T, s∈Ss\in S и s∣ts\mid t, то s∈Ts\in T. Освен това, ако d(n)=2kd(n)=2^k, то TT има kk елемента. Нека TkT_k е множеството от най-малките kk елемента на SS. То очевидно има описаното свойство. Произведението на елементите на всяко друго kk-елементно подмножество на SS е поне произведението на елементите на TkT_k, следователноf(2k)=∏t∈Tkt.f(2^k)=\prod_{t\in T_k}t.Понеже Tk⊂Tk+1T_k\subset T_{k+1}, веднага получавамеf(2k)∣f(2k+1),f(2^k)\mid f(2^{k+1}),което трябваше да се докаже.
Отвори задачатаMathNetISL 2011 N1Условие — източник

Задача N2

Пълен запис
Условие
Разглеждаме многочлена P(x)=(x+d1)(x+d2)⋯(x+d9)P(x)=(x+d_1)(x+d_2)\cdots(x+d_9), където d1,d2,…,d9d_1,d_2,\ldots,d_9 са девет различни цели числа. Докажете, че съществува цяло число NN, такова че за всички цели числа x≥Nx\ge N числото P(x)P(x) се дели на просто число, по-голямо от 2020.
РешениеТвърдението не се променя при транслация на променливата, затова можем да приемем, че числата d1,d2,…,d9d_1,d_2,\ldots,d_9 са положителни. Некаd=max⁡{d1,d2,…,d9}.d=\max\{d_1,d_2,\ldots,d_9\}.Ще докажем, че N=d8N=d^8 върши работа. Да допуснем противното: за някое цяло x≥d8x\ge d^8 всички прости делители на P(x)P(x) са по-малки от 2020. Тогава всяко от числата x+dix+d_i е произведение на степени на първите осем прости числа. Понеже x+di>d8x+d_i\gt{}d^8, в разлагането на x+dix+d_i съществува степен на просто число qiq_i, по-голяма от dd. Имаме девет числа qiq_i, но само осем възможни прости основи. По принципа на Дирихле съществуват различни индекси i,ji,j, за които qiq_i и qjq_j са степени на едно и също просто число. Без ограничение нека qi≤qjq_i\le q_j. Тогава qiq_i дели и x+dix+d_i, и x+djx+d_j, следователно дели разликата di−djd_i-d_j. Но0<∣di−dj∣≤d<qi,0\lt{}|d_i-d_j|\le d\lt{}q_i,което е невъзможно. Противоречието доказва твърдението.
Отвори задачатаMathNetISL 2011 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека n≥1n\ge1 е нечетно цяло число. Да се определят всички функции ff от множеството на целите числа в себе си, такива че за всички цели числа xx и yy разликата f(x)−f(y)f(x)-f(y) дели xn−ynx^n-y^n.
РешениеОтговорът еf(x)=εxd+c,f(x)=\varepsilon x^d+c,където ε∈{1,−1}\varepsilon\in\{1,-1\}, числото dd е положителен делител на nn, а cc е цяло число. Тези функции работят, защото xd−ydx^d-y^d дели xn−ynx^n-y^n при d∣nd\mid n. Нека ff е решение. Добавянето на константа към ff не променя условието, затова можем да приемем f(0)=0f(0)=0. За всяко просто число pp от условието с (x,y)=(p,0)(x,y)=(p,0) следва, че f(p)f(p) дели pnp^n. Следователно за безкрайно много прости pp имамеf(p)=εpdf(p)=\varepsilon p^dс фиксирани 0≤d≤n0\le d\le n и ε∈{1,−1}\varepsilon\in\{1,-1\}. Ако е нужно, заменяме ff с −f-f и приемаме ε=1\varepsilon=1. Нека P\mathcal P е безкрайното множество от такива прости числа. Случаят d=0d=0 е невъзможен: тогава за две различни прости числа p,q∈Pp,q\in\mathcal P ще имаме f(p)−f(q)=0f(p)-f(q)=0, което не може да дели ненулевото число pn−qnp^n-q^n. Значи d≥1d\ge1. Пишем n=md+rn=md+r, където m≥1m\ge1 и 0≤r<d0\le r\lt{}d. Нека xx е произволно цяло число. За всяко p∈Pp\in\mathcal P числото pd−f(x)p^d-f(x) дели pn−xnp^n-x^n. По модул pd−f(x)p^d-f(x) имамеpn−xn=pr(pd)m−xn≡prf(x)m−xn.p^n-x^n=p^r(p^d)^m-x^n\equiv p^r f(x)^m-x^n.За достатъчно големи p∈Pp\in\mathcal P абсолютната стойност на последния израз е по-малка от ∣pd−f(x)∣|p^d-f(x)|, следователно той е равен на нула. Избираме фиксирано q∈Pq\in\mathcal P и прилагаме последното за x=qx=q и безкрайно много p∈Pp\in\mathcal P. Тъй като f(q)=qdf(q)=q^d, получаваме prqdm=qnp^r q^{dm}=q^n. Това е възможно за безкрайно много pp само ако r=0r=0. Следователно d∣nd\mid n, а за произволно xx горното равенство даваxn=f(x)m.x^n=f(x)^m.Понеже m=n/dm=n/d е нечетно, следва f(x)=xdf(x)=x^d за всяко xx. Връщайки възможността за знак и добавена константа, получаваме точно описаните функции.
Отвори задачатаMathNetISL 2011 N3Условие — източник

Задача N4

Пълен запис
Условие
За всяко положително цяло число kk нека t(k)t(k) е най-големият нечетен делител на kk. Да се определят всички положителни цели числа aa, за които съществува положително цяло число nn, такова че всички разликиt(n+a)−t(n), t(n+a+1)−t(n+1),t(n+a)-t(n),\ t(n+a+1)-t(n+1),…, t(n+2a−1)−t(n+a−1)\ldots,\ t(n+2a-1)-t(n+a-1)се делят на 44.
РешениеОтговорът еa=1,3,5.a=1,3,5.Лесно се проверява, че двойките (a,n)=(1,1),(3,1),(5,4)(a,n)=(1,1),(3,1),(5,4) удовлетворяват условието. Ще наричаме двойка (a,n)(a,n) добра, ако удовлетворява условието. Нека aa е положително цяло число, различно от 1,3,51,3,5. Ще докажем, че няма добра двойка (a,n)(a,n). Първи случай: aa е четно. Пишем a=2αda=2^\alpha d, където α≥1\alpha\ge1 и dd е нечетно. За всяко nn можем да изберем i∈{0,1,…,a−1}i\in\{0,1,\ldots,a-1\} така, че n+i=2α−1en+i=2^{\alpha-1}e с нечетно ee. Тогаваt(n+i)=e,t(n+i)=e,аt(n+a+i)=t(2αd+2α−1e)=2d+e≡e+2(mod4).t(n+a+i)=t(2^\alpha d+2^{\alpha-1}e)=2d+e\equiv e+2\pmod4.Следователно съответната разлика не се дели на 44. Втори случай: aa е нечетно и a>8a\gt{}8. За всяко nn има i∈{0,1,…,a−5}i\in\{0,1,\ldots,a-5\}, за което n+i=2dn+i=2d с нечетно dd. Тогаваt(n+i)=d≢d+2=t(n+i+4)(mod4),t(n+i)=d\not\equiv d+2=t(n+i+4)\pmod4,докато, понеже aa е нечетно,t(n+a+i)=n+a+i≡n+a+i+4=t(n+a+i+4)(mod4).t(n+a+i)=n+a+i\equiv n+a+i+4=t(n+a+i+4)\pmod4.Значи двете разлики с индекси ii и i+4i+4 не могат едновременно да се делят на 44. Трети случай: a=7a=7. За всяко nn сред числата n,n+1,…,n+6n,n+1,\ldots,n+6 има число от вида 8k+38k+3 или 8k+68k+6. Ако n+i=8k+3n+i=8k+3, тоt(n+i)≡3(mod4),t(n+i)\equiv3\pmod4,t(n+i+7)=t(8k+10)=4k+5≡1(mod4).\qquad t(n+i+7)=t(8k+10)=4k+5\equiv1\pmod4.Ако n+i=8k+6n+i=8k+6, тоt(n+i)=4k+3≡3(mod4),t(n+i)=4k+3\equiv3\pmod4,t(n+i+7)=8k+13≡1(mod4).\qquad t(n+i+7)=8k+13\equiv1\pmod4.И в двата подслучая съответната разлика не се дели на 44. Следователно единствените възможни стойности са 1,3,51,3,5.
Отвори задачатаMathNetISL 2011 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека ff е функция от множеството на целите числа към множеството на положителните цели числа. Да се предположи, че за всеки две цели числа mm и nn разликата f(m)−f(n)f(m)-f(n) се дели на f(m−n)f(m-n). Докажете, че за всички цели числа m,nm,n с f(m)≤f(n)f(m)\le f(n) числото f(n)f(n) се дели на f(m)f(m).
РешениеДостатъчно е да разгледаме случая f(x)<f(y)f(x)\lt{}f(y); при равенство твърдението е очевидно. От условието с m=xm=x, n=yn=y получавамеf(x−y)∣f(x)−f(y),f(x-y)\mid f(x)-f(y),затоваf(x−y)≤f(y)−f(x)<f(y).(1)f(x-y)\le f(y)-f(x)\lt{}f(y).\tag{1}Некаd=f(x)−f(x−y).d=f(x)-f(x-y).От (1) следва−f(y)<d<f(y).-f(y)\lt{}d\lt{}f(y).От друга страна, с m=xm=x и n=x−yn=x-y условието даваf(y)∣d.f(y)\mid d.Следователно d=0d=0, тоест f(x)=f(x−y)f(x)=f(x-y). Връщаме се към делимостта при m=xm=x, n=yn=y:f(x−y)∣f(x)−f(y).f(x-y)\mid f(x)-f(y).Понеже f(x−y)=f(x)f(x-y)=f(x), получаваме f(x)∣f(y)f(x)\mid f(y). Това доказва исканото.
Отвори задачатаMathNetISL 2011 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека P(x)P(x) и Q(x)Q(x) са два многочлена с цели коефициенти, такива че няма неконстантен многочлен с рационални коефициенти, който да дели едновременно P(x)P(x) и Q(x)Q(x). Да се предположи, че за всяко положително цяло число nn числата P(n)P(n) и Q(n)Q(n) са положителни и 2Q(n)−12^{Q(n)}-1 дели 3P(n)−13^{P(n)}-1. Докажете, че Q(x)Q(x) е константен многочлен.
РешениеПърво ще докажем, че съществува цяло число dd, такова чеgcd⁡(P(n),Q(n))≤d\gcd(P(n),Q(n))\le dза всяко положително цяло число nn. Понеже PP и QQ са взаимно прости над Q[x]\mathbb Q[x], съществуват многочлени R0,S0∈Q[x]R_0,S_0\in\mathbb Q[x] сP(x)R0(x)−Q(x)S0(x)=1.P(x)R_0(x)-Q(x)S_0(x)=1.След умножение с подходящо положително цяло число dd получаваме R,S∈Z[x]R,S\in\mathbb Z[x], за коитоP(x)R(x)−Q(x)S(x)=d.P(x)R(x)-Q(x)S(x)=d.Следователно gcd⁡(P(n),Q(n))\gcd(P(n),Q(n)) дели dd за всяко nn. Да допуснем, че QQ не е константен. Тогава редицата Q(n)Q(n) е неограничена, така че можем да изберем положително цяло mm, за коетоM=2Q(m)−1≥3max⁡{P(1),P(2),…,P(d)}.(1)M=2^{Q(m)}-1\ge3^{\max\{P(1),P(2),\ldots,P(d)\}}.\tag{1}От условието MM дели 3P(m)−13^{P(m)}-1, следователно 2∤M2\nmid M и 3∤M3\nmid M. Нека aa и bb са съответно мултипликативните порядъци на 22 и 33 по модул MM. Ясно е, че a=Q(m)a=Q(m), а от M∣3P(m)−1M\mid3^{P(m)}-1 следва b∣P(m)b\mid P(m). Затоваgcd⁡(a,b)≤gcd⁡(Q(m),P(m))≤d.\gcd(a,b)\le\gcd(Q(m),P(m))\le d.Избираме неотрицателни цели числа u,vu,v, такива че1≤m+au−bv≤d.1\le m+au-bv\le d.Това е възможно, защото линейните комбинации au−bvau-bv дават всички кратни на gcd⁡(a,b)\gcd(a,b), а интервалът [1,d][1,d] съдържа число, сравнимо с mm по модул gcd⁡(a,b)\gcd(a,b). Понеже QQ има цели коефициенти и a∣aua\mid au, имамеQ(m+au)≡Q(m)(moda).Q(m+au)\equiv Q(m)\pmod a.Следователно2Q(m+au)≡2Q(m)≡1(modM),2^{Q(m+au)}\equiv2^{Q(m)}\equiv1\pmod M,така че M∣2Q(m+au)−1M\mid2^{Q(m+au)}-1. По условие 2Q(m+au)−12^{Q(m+au)}-1 дели 3P(m+au)−13^{P(m+au)}-1, следователно3P(m+au)≡1(modM).3^{P(m+au)}\equiv1\pmod M.Понеже P(m+au−bv)≡P(m+au)(modb)P(m+au-bv)\equiv P(m+au)\pmod b, получаваме3P(m+au−bv)≡1(modM).3^{P(m+au-bv)}\equiv1\pmod M.Но P(m+au−bv)>0P(m+au-bv)\gt{}0, затоваM<3P(m+au−bv)≤3max⁡{P(1),P(2),…,P(d)},M\lt{}3^{P(m+au-bv)}\le3^{\max\{P(1),P(2),\ldots,P(d)\}},което противоречи на (1). Следователно QQ е константен многочлен.
Отвори задачатаMathNetISL 2011 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека pp е нечетно просто число. За всяко цяло число aa дефинирамеSa=a1+a22+⋯+ap−1p−1.S_a=\frac a1+\frac{a^2}2+\cdots+\frac{a^{p-1}}{p-1}.Нека mm и nn са цели числа, такива чеS3+S4−3S2=mn.S_3+S_4-3S_2=\frac mn.Докажете, че pp дели mm.
РешениеЩе работим с рационални числа по модул pp, чиито знаменатели не се делят на pp. За 1≤k≤p−11\le k\le p-1 имаме1p(pk)=(p−1)(p−2)⋯(p−k+1)k!≡\frac1p\binom pk=\frac{(p-1)(p-2)\cdots(p-k+1)}{k!}\equiv(−1)k−1k(modp).\frac{(-1)^{k-1}}k\pmod p.СледователноSa=−∑k=1p−1(−a)k(−1)k−1k≡S_a=-\sum_{k=1}^{p-1}(-a)^k\frac{(-1)^{k-1}}k\equiv−∑k=1p−1(−a)k1p(pk)(modp).-\sum_{k=1}^{p-1}(-a)^k\frac1p\binom pk\pmod p.По бинома на Нютон дясната страна е−1p((1−a)p−1−(−a)p)=(a−1)p−ap+1p,-\frac1p\left((1-a)^p-1-(-a)^p\right)=\frac{(a-1)^p-a^p+1}{p},тъй като pp е нечетно. ЗначиSa≡(a−1)p−ap+1p(modp).(1)S_a\equiv\frac{(a-1)^p-a^p+1}{p}\pmod p.\tag{1}Прилагаме (1) за a=3,4,2a=3,4,2:S3+S4−3S2≡S_3+S_4-3S_2\equiv(2p−3p+1)+(3p−4p+1)−3(1p−2p+1)p\frac{(2^p-3^p+1)+(3^p-4^p+1)-3(1^p-2^p+1)}p=4⋅2p−4p−4p=−(2p−2)2p(modp).=\frac{4\cdot2^p-4^p-4}{p}=-\frac{(2^p-2)^2}{p}\pmod p.По малката теорема на Ферма p∣2p−2p\mid2^p-2, следователно p2∣(2p−2)2p^2\mid(2^p-2)^2 и последният израз е 00 по модул pp. Така рационалното число S3+S4−3S2S_3+S_4-3S_2 е сравнимо с 00 по модул pp. Понеже знаменателите в SaS_a не се делят на pp, това означава, че в несъкратимия вид числителят се дели на pp; следователно pp дели и всеки числител mm в представяне m/nm/n на това число.
Отвори задачатаMathNetISL 2011 N7Условие — източник

Задача N8

Пълен запис
Условие
Нека kk е положително цяло число и n=2k+1n=2^k+1. Докажете, че nn е просто число тогава и само тогава, когато е изпълнено следното: съществуват пермутация a1,a2,…,an−1a_1,a_2,\ldots,a_{n-1} на числата 1,2,…,n−11,2,\ldots,n-1 и редица от цели числа g1,g2,…,gn−1g_1,g_2,\ldots,g_{n-1}, такива че nn дели giai−ai+1g_i^{a_i}-a_{i+1} за всяко i∈{1,2,…,n−1}i\in\{1,2,\ldots,n-1\}, където полагаме an=a1a_n=a_1.
РешениеНека N={1,2,…,n−1}N=\{1,2,\ldots,n-1\}. За a,b∈Na,b\in N ще казваме, че bb следва aa, и ще пишем a→ba\to b, ако съществува цяло число gg сb≡ga(modn).b\equiv g^a\pmod n.Така получаваме ориентиран граф с върхове NN. Условието на задачата е точно съществуването на хамилтонов цикъл в този граф. Първо нека nn е съставно. Пишем n=p1α1⋯psαsn=p_1^{\alpha_1}\cdots p_s^{\alpha_s}. Ако някое αi>1\alpha_i\gt{}1, то за всяко a≥2a\ge2 и всяко цяло gg числото gag^a не може да е сравнимо с pip_i по модул pi2p_i^2: или се дели на pi2p_i^2, или не се дели на pip_i. Следователно в хамилтонов цикъл върхът pip_i трябва да следва непосредствено след 11. Същото важи и за 2pi2p_i, което е невъзможно. Остава nn да е свободно от квадрати. Тогава n=p1p2⋯ps>9n=p_1p_2\cdots p_s\gt{}9 и s≥2s\ge2. Ако има хамилтонов цикъл, всеки от (n−1)/2(n-1)/2-те четни върха трябва да има наследник, който е квадратичен остатък по модул nn. Значи трябва да има поне (n−1)/2(n-1)/2 ненулеви квадратични остатъка. От китайската теорема за остатъците броят на всички квадратични остатъци по модул nn, включително 00, еp1+12⋅p2+12⋯ps+12≤\frac{p_1+1}{2}\cdot\frac{p_2+1}{2}\cdots\frac{p_s+1}{2}\le(23)sn≤4n9<n−12,\left(\frac23\right)^s n\le\frac{4n}{9}\lt{}\frac{n-1}{2},противоречие. Следователно при съставно nn такъв цикъл не съществува. Нека вече n=2k+1n=2^k+1 е просто. За a∈Na\in N нека ν2(a)\nu_2(a) е показателят на 22 в разлагането на aa, аμ(a)=max⁡{t∈{0,1,…,k}:2t→a}.\mu(a)=\max\{t\in\{0,1,\ldots,k\}:2^t\to a\}.Ще използваме лемата: за a,b∈Na,b\in N имаме a→ba\to b тогава и само тогава, когато ν2(a)≤μ(b)\nu_2(a)\le\mu(b). Доказателство на лемата. Нека ℓ=ν2(a)\ell=\nu_2(a) и m=μ(b)m=\mu(b). Ако ℓ≤m\ell\le m, то от 2m→b2^m\to b следва, че b≡g02m(modn)b\equiv g_0^{2^m}\pmod n за някое g0g_0. Понеже gcd⁡(a,n−1)=2ℓ\gcd(a,n-1)=2^\ell, съществуват цели u,vu,v с ua−v(n−1)=2ℓua-v(n-1)=2^\ell. При g=g02m−ℓug=g_0^{2^{m-\ell}u} от малката теорема на Ферма получавамеga≡g02m≡b(modn),g^a\equiv g_0^{2^m}\equiv b\pmod n,тоест a→ba\to b. Обратно, ако b≡ga(modn)b\equiv g^a\pmod n, тоb≡(ga/2ℓ)2ℓ(modn),b\equiv\left(g^{a/2^\ell}\right)^{2^\ell}\pmod n,значи 2ℓ→b2^\ell\to b и μ(b)≥ℓ\mu(b)\ge\ell. Лемата е доказана. За 0≤i≤k0\le i\le k дефинирамеAi={a∈N:ν2(a)=i},A_i=\{a\in N:\nu_2(a)=i\},Bi={a∈N:μ(a)=i},\qquad B_i=\{a\in N:\mu(a)=i\},Ci={a∈N:μ(a)≥i}.\qquad C_i=\{a\in N:\mu(a)\ge i\}.Ще докажем, че ∣Ai∣=∣Bi∣|A_i|=|B_i| за всички ii. Ясно е, че ∣Ai∣=2k−i−1|A_i|=2^{k-i-1} за 0≤i<k0\le i\lt{}k, а ∣Ak∣=1|A_k|=1. Имаме C0=NC_0=N и, по малката теорема на Ферма, Ck={1}C_k=\{1\}. Освен товаCi+1={x2 mod n:x∈Ci}.C_{i+1}=\{x^2\bmod n:x\in C_i\}.Тъй като nn е просто, всяко сравнение x2≡y(modn)x^2\equiv y\pmod n има най-много две решения. Следователно 2∣Ci+1∣≤∣Ci∣2|C_{i+1}|\le |C_i|. Но ∣C0∣=2k∣Ck∣|C_0|=2^k|C_k|, затова във всяка стъпка имаме равенство и∣Ci∣=2k−i.|C_i|=2^{k-i}.Оттук ∣Bi∣=∣Ci∣−∣Ci+1∣=2k−i−1|B_i|=|C_i|-|C_{i+1}|=2^{k-i-1} за 0≤i<k0\le i\lt{}k и ∣Bk∣=1|B_k|=1, тоест ∣Ai∣=∣Bi∣|A_i|=|B_i|. Нещо повече, равенството в предходното броене показва, че ако z∈Ciz\in C_i и i<ki\lt{}k, то n−z∈Cin-z\in C_i. Затова точно половината елементи на CiC_i са нечетни; същото важи за Bi=Ci∖Ci+1B_i=C_i\setminus C_{i+1} при 0≤i≤k−20\le i\le k-2. Следователно всяко такова BiB_i съдържа нечетно число. Освен това Bk={1}B_k=\{1\}, а Bk−1={2k}B_{k-1}=\{2^k\}. Сега построяваме цикъла. За всяко ii свързваме елементите на AiA_i с елементите на BiB_i чрез произволна биекция. По лемата всички тези ребра са допустими, а полученият подграф има входяща и изходяща степен 11 във всеки връх. Значи той е обединение на дизюнктни цикли. Ако цикълът е един, сме готови. Ако циклите са повече, ще намалим броя им. За цикъл CC полагамеλ(C)=min⁡c∈Cν2(c)\lambda(C)=\min_{c\in C}\nu_2(c)и избираме цикъл CC с максимална стойност на λ(C)\lambda(C). Ако λ(C)=0\lambda(C)=0, то всеки друг цикъл също има връх с ν2=0\nu_2=0. Вземаме такива върхове a∈Ca\in C и a′∈C′a'\in C' и нека наследниците им са bb и b′b'. Заменяме ребрата a→ba\to b, a′→b′a'\to b' с a→b′a\to b' и a′→ba'\to b. Новите ребра пак са допустими по лемата и двата цикъла се сливат. Нека λ(C)=λ≥1\lambda(C)=\lambda\ge1 и вземем a∈C∩Aλa\in C\cap A_\lambda. Ако съществува a′∈Aλ∖Ca'\in A_\lambda\setminus C, правим същата размяна на наследници и сливаме два цикъла. Остава да е вярно Aλ⊂CA_\lambda\subset C. Тогава, понеже ребрата от AλA_\lambda отиват в BλB_\lambda и ∣Aλ∣=∣Bλ∣|A_\lambda|=|B_\lambda|, имаме Bλ⊂CB_\lambda\subset C. Ако λ≠k−1\lambda\ne k-1, множеството BλB_\lambda съдържа нечетен елемент, което противоречи на λ(C)>0\lambda(C)\gt{}0. Ако λ=k−1\lambda=k-1, цикълът съдържа 2k−12^{k-1}, после 2k2^k, а после 11, отново противоречие. Значи винаги можем да сливаме цикли, докато остане един хамилтонов цикъл. Това доказва съществуването на исканата пермутация и редица gig_i при просто nn.
Отвори задачатаMathNetISL 2011 N8Условие — източник