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

IMO Shortlisted Problems

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

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

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

2010

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

11-12

21 задачи

Задача A1

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, за коитоf(⌊x⌋y)=f(x)⌊f(y)⌋f(\lfloor x\rfloor y)=f(x)\lfloor f(y)\rfloorза всички x,y∈Rx,y\in\mathbb R. Тук ⌊x⌋\lfloor x\rfloor означава най-голямото цяло число, ненадминаващо xx.
РешениеОтговорът е: f(x)≡Cf(x)\equiv C, където C=0C=0 или 1≤C<21\le C\lt{}2. Поставяме x=0x=0. Получавамеf(0)=f(0)⌊f(y)⌋(1)f(0)=f(0)\lfloor f(y)\rfloor\tag{1}за всяко реално yy. Ако f(0)≠0f(0)\ne0, от (1) следва ⌊f(y)⌋=1\lfloor f(y)\rfloor=1 за всяко yy. Тогава началното уравнение става f(⌊x⌋y)=f(x)f(\lfloor x\rfloor y)=f(x). С y=0y=0 получаваме f(x)=f(0)f(x)=f(0) за всяко xx, а от ⌊f(y)⌋=1\lfloor f(y)\rfloor=1 следва 1≤f(0)<21\le f(0)\lt{}2. Нека сега f(0)=0f(0)=0. Ако съществува α\alpha с 0≤α<10\le\alpha\lt{}1 и f(α)≠0f(\alpha)\ne0, поставяме x=αx=\alpha и получаваме 0=f(0)=f(α)⌊f(y)⌋0=f(0)=f(\alpha)\lfloor f(y)\rfloor за всяко yy, тоест ⌊f(y)⌋=0\lfloor f(y)\rfloor=0. Тогава с x=1x=1 следва f(y)=0f(y)=0 за всяко yy, противоречие. Следователно f(α)=0f(\alpha)=0 за всяко α∈[0,1)\alpha\in[0,1). За произволно реално zz избираме цяло N≠0N\ne0, за което z/N∈[0,1)z/N\in[0,1). Тогаваf(z)=f(⌊N⌋⋅z/N)=f(N)⌊f(z/N)⌋=0.f(z)=f(\lfloor N\rfloor\cdot z/N)=f(N)\lfloor f(z/N)\rfloor=0.Значи в този случай ff е нулевата функция. Пряка проверка показва, че точно намерените функции удовлетворяват условието.
Отвори задачатаMathNetISL 2010 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека реалните числа a,b,c,da,b,c,d удовлетворяватa+b+c+d=6,a2+b2+c2+d2=12.a+b+c+d=6,\qquad a^2+b^2+c^2+d^2=12.Докажете, че36≤4(a3+b3+c3+d3)−(a4+b4+c4+d4)≤48.36\le 4(a^3+b^3+c^3+d^3)-(a^4+b^4+c^4+d^4)\le48.
РешениеПолагамеx=a−1,y=b−1,z=c−1,t=d−1.x=a-1,\quad y=b-1,\quad z=c-1,\quad t=d-1.От условията следваx2+y2+z2+t2=4.x^2+y^2+z^2+t^2=4.Освен това, след разкриване на скобите и използване на дадените две равенства, получаваме4(a3+b3+c3+d3)−(a4+b4+c4+d4)=4(a^3+b^3+c^3+d^3)-(a^4+b^4+c^4+d^4)=52−(x4+y4+z4+t4).52-(x^4+y^4+z^4+t^4).Затова е достатъчно да докажем4≤x4+y4+z4+t4≤16.4\le x^4+y^4+z^4+t^4\le16.Първото неравенство следва от(x2+y2+z2+t2)2≤4(x4+y4+z4+t4),(x^2+y^2+z^2+t^2)^2\le4(x^4+y^4+z^4+t^4),а второто - отx4+y4+z4+t4≤(x2+y2+z2+t2)2.x^4+y^4+z^4+t^4\le(x^2+y^2+z^2+t^2)^2.Така 4≤x4+y4+z4+t4≤164\le x^4+y^4+z^4+t^4\le16, което е еквивалентно на исканото двойно неравенство.
Отвори задачатаMathNetISL 2010 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека x1,x2,…,x100x_1,x_2,\ldots,x_{100} са неотрицателни реални числа, за коитоxi+xi+1+xi+2≤1x_i+x_{i+1}+x_{i+2}\le1за всяко i=1,2,…,100i=1,2,\ldots,100, където x101=x1x_{101}=x_1 и x102=x2x_{102}=x_2. Да се намери най-голямата възможна стойност наS=∑i=1100xixi+2.S=\sum_{i=1}^{100}x_i x_{i+2}.
РешениеОтговорът е252.\frac{25}{2}.Стойността се достига, ако x2i−1=12x_{2i-1}=\frac12 и x2i=0x_{2i}=0 за i=1,2,…,50i=1,2,\ldots,50. Остава да докажем горната оценка. За всяко i=1,2,…,50i=1,2,\ldots,50 от условията имамеx2i−1≤1−x2i−x2i+1,x_{2i-1}\le1-x_{2i}-x_{2i+1},x2i+2≤1−x2i−x2i+1.\qquad x_{2i+2}\le1-x_{2i}-x_{2i+1}.Следователноx2i−1x2i+1+x2ix2i+2≤(1−x2i−x2i+1)x2i+1+x2i(1−x2i−x2i+1)=(x2i+x2i+1)(1−x2i−x2i+1)≤14.\begin{aligned}x_{2i-1}x_{2i+1}+x_{2i}x_{2i+2}&\le (1-x_{2i}-x_{2i+1})x_{2i+1}+x_{2i}(1-x_{2i}-x_{2i+1})\\&=(x_{2i}+x_{2i+1})(1-x_{2i}-x_{2i+1})\le\frac14. \end{aligned}Сумирайки тези 50 неравенства, получавамеS≤50⋅14=252.S\le50\cdot\frac14=\frac{25}{2}.Така намерената стойност е максимална.
Отвори задачатаMathNetISL 2010 A3Условие — източник

Задача A4

Пълен запис
Условие
Редицата x1,x2,…x_1,x_2,\ldots е дефинирана чрез x1=1x_1=1 иx2k=−xk,x2k−1=(−1)k+1xkx_{2k}=-x_k,\qquad x_{2k-1}=(-1)^{k+1}x_kза всяко k≥1k\ge1. Докажете, чеx1+x2+⋯+xn≥0x_1+x_2+\cdots+x_n\ge0за всяко n≥1n\ge1.
РешениеНекаSn=x1+x2+⋯+xn.S_n=x_1+x_2+\cdots+x_n.От дефиницията следва, че за всяко k≥1k\ge1x4k−3=x2k−1=−x4k−2,x_{4k-3}=x_{2k-1}=-x_{4k-2},x4k−1=x4k=−x2k=xk.(1)\qquad x_{4k-1}=x_{4k}=-x_{2k}=x_k.\tag{1}ЗатоваS4k=2Sk,S4k+2=S4k.(2)S_{4k}=2S_k,\qquad S_{4k+2}=S_{4k}.\tag{2}Също така всички xix_i са равни на 11 или −1-1, така че Sn≡n(mod2)S_n\equiv n\pmod2. Ще докажем по индукция по kk, че Si≥0S_i\ge0 за всички i≤4ki\le4k. За k=1k=1 имаме x1=1,x2=−1,x3=1,x4=1x_1=1,x_2=-1,x_3=1,x_4=1, така че твърдението е вярно. Да предположим, че е вярно до 4k4k. От (2) получавамеS4k+4=2Sk+1≥0,S4k+2=S4k≥0.S_{4k+4}=2S_{k+1}\ge0,\qquad S_{4k+2}=S_{4k}\ge0.Освен товаS4k+3=S4k+2+S4k+42≥0,S_{4k+3}=\frac{S_{4k+2}+S_{4k+4}}2\ge0,защото последните два члена в блока са равни. Остава S4k+1S_{4k+1}. Ако kk е нечетно, тогава SkS_k е нечетно и неотрицателно, следователно Sk≥1S_k\ge1 и S4k=2Sk≥2S_{4k}=2S_k\ge2; понеже x4k+1=±1x_{4k+1}=\pm1, имаме S4k+1≥1S_{4k+1}\ge1. Ако kk е четно, тогава x4k+1=xk+1x_{4k+1}=x_{k+1} иS4k+1=S4k+x4k+1=2Sk+xk+1=Sk+Sk+1≥0.S_{4k+1}=S_{4k}+x_{4k+1}=2S_k+x_{k+1}=S_k+S_{k+1}\ge0.Индукцията е завършена, а с нея и доказателството.
Отвори задачатаMathNetISL 2010 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека Q>0\mathbb Q_{\gt{}0} е множеството на положителните рационални числа. Да се намерят всички функции f:Q>0→Q>0f:\mathbb Q_{\gt{}0}\to\mathbb Q_{\gt{}0}, които удовлетворяватf(f(x)2y)=x3f(xy)f(f(x)^2y)=x^3f(xy)за всички x,y∈Q>0x,y\in\mathbb Q_{\gt{}0}.
РешениеОтговорът е единствената функцияf(x)=1x.f(x)=\frac1x.При y=1y=1 получавамеf(f(x)2)=x3f(x).(1)f(f(x)^2)=x^3f(x).\tag{1}Ако f(x)=f(y)f(x)=f(y), то от (1) следва x3f(x)=y3f(y)x^3f(x)=y^3f(y), откъдето x=yx=y. Значи ff е инективна. Заместваме xx с xyxy в (1) и използваме даденото уравнение два пъти:f(f(xy)2)=(xy)3f(xy)=f(f(xy)^2)=(xy)^3f(xy)=y3f(f(x)2y)=f(f(x)2f(y)2).y^3f(f(x)^2y)=f(f(x)^2f(y)^2).От инективността следваf(xy)2=f(x)2f(y)2,f(xy)^2=f(x)^2f(y)^2,а понеже стойностите са положителни,f(xy)=f(x)f(y).(2)f(xy)=f(x)f(y).\tag{2}Така ff е мултипликативна и f(1)=1f(1)=1. От (1) и (2) имамеf(f(x))2=f(f(x)2)=x3f(x).(3)f(f(x))^2=f(f(x)^2)=x^3f(x).\tag{3}Нека g(x)=xf(x)g(x)=xf(x). Тогава, използвайки мултипликативността и (3), получавамеg(g(x))=xf(x)2f(f(x))=g(x)5/2.g(g(x))=xf(x)^2f(f(x))=g(x)^{5/2}.Следователно по индукцияg∘(n+1)(x)=g(x)(5/2)ng^{\circ(n+1)}(x)=g(x)^{(5/2)^n}за всяко n≥0n\ge0. Фиксираме xx. Лявата страна винаги е положително рационално число. Ако g(x)≠1g(x)\ne1 иg(x)=p1α1⋯prαrg(x)=p_1^{\alpha_1}\cdots p_r^{\alpha_r}е разлагането му на прости множители с някой ненулев цял показател αi\alpha_i, то в g(x)(5/2)ng(x)^{(5/2)^n} показателят на pip_i е αi5n/2n\alpha_i5^n/2^n, което не е цяло число за достатъчно голямо nn. Противоречие. Значи g(x)=1g(x)=1 за всяко xx, тоест f(x)=1/xf(x)=1/x. Накрая пряко се проверява, че f(x)=1/xf(x)=1/x удовлетворява уравнението.
Отвори задачатаMathNetISL 2010 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека ff и gg са функции, дефинирани върху положителните цели числа и приемащи положителни цели стойности. Нека за всяко положително цяло nn е изпълненоf(g(n))=f(n)+1,g(f(n))=g(n)+1.f(g(n))=f(n)+1,\qquad g(f(n))=g(n)+1.Докажете, че f(n)=g(n)f(n)=g(n) за всяко положително цяло nn.
РешениеНека aa и bb са най-малките стойности, които приемат съответно ff и gg. От равенствата следваf(gk(x))=f(x)+k,g(fk(x))=g(x)+k,f(g^k(x))=f(x)+k,\qquad g(f^k(x))=g(x)+k,така че ff приема точно всички стойности a,a+1,a+2,…a,a+1,a+2,\ldots, а gg приема точно всички стойности b,b+1,b+2,…b,b+1,b+2,\ldots. Ще казваме, че x∼yx\sim y, ако f(x)=f(y)f(x)=f(y). Това е еквивалентно на g(x)=g(y)g(x)=g(y), понежеg(f(x))=g(x)+1.g(f(x))=g(x)+1.Ако f(x)∼f(y)f(x)\sim f(y), тогаваg(x)=g(f(x))−1=g(f(y))−1=g(y),g(x)=g(f(x))-1=g(f(y))-1=g(y),следователно x∼yx\sim y. Затова във всеки клас по ∼\sim има най-много един елемент от множеството {a,a+1,a+2,…}\{a,a+1,a+2,\ldots\} и най-много един елемент от множеството {b,b+1,b+2,…}\{b,b+1,b+2,\ldots\}. Ще докажем, че a=ba=b. Можем да предположим a≤ba\le b. Понеже f(a)≥af(a)\ge a и равенството f(a)=af(a)=a би дало g(a)=g(f(a))=g(a)+1g(a)=g(f(a))=g(a)+1, имаме f(a)≥a+1f(a)\ge a+1. Избираме xx с f(x)=f(a)−1f(x)=f(a)-1. Тогава f(g(x))=f(a)f(g(x))=f(a), т.е. a∼g(x)a\sim g(x). Но g(x)≥b≥ag(x)\ge b\ge a, така че и aa, и g(x)g(x) са стойности на ff; от предното наблюдение следва a=g(x)≥ba=g(x)\ge b. Значи a=ba=b. Сега ще покажем, че f(a)=g(a)=a+1f(a)=g(a)=a+1. Ако например f(a)≥a+2f(a)\ge a+2, избираме xx с f(x)=f(a)−2f(x)=f(a)-2 и после yy с f(y)=g(x)f(y)=g(x), което е възможно, защото g(x)≥ag(x)\ge a. Тогаваf(g2(x))=f(x)+2=f(a),f(g^2(x))=f(x)+2=f(a),следователно a∼g2(x)a\sim g^2(x). Но g2(x)=g(f(y))=g(y)+1≥a+1g^2(x)=g(f(y))=g(y)+1\ge a+1, а и g2(x)g^2(x) е стойност на ff; това противоречи на единствеността в класа на aa. Значи f(a)=a+1f(a)=a+1. По същия начин g(a)=a+1g(a)=a+1. По индукция доказваме, че за всяко x≥ax\ge af(x)=g(x)=x+1.f(x)=g(x)=x+1.Базата x=ax=a вече е доказана. Ако твърдението е вярно за xx, тогаваf(x+1)=f(g(x))=f(x)+1=x+2,f(x+1)=f(g(x))=f(x)+1=x+2,и аналогично g(x+1)=x+2g(x+1)=x+2. Накрая за произволно положително цяло nn имаме g(n)≥ag(n)\ge a, затоваf(n)+1=f(g(n))=g(n)+1,f(n)+1=f(g(n))=g(n)+1,откъдето f(n)=g(n)f(n)=g(n).
Отвори задачатаMathNetISL 2010 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека a1,a2,…,ara_1,a_2,\ldots,a_r са положителни реални числа. За n>rn\gt{}r дефинираме индуктивноan=max⁡1≤k≤n−1(ak+an−k).a_n=\max_{1\le k\le n-1}(a_k+a_{n-k}).Докажете, че съществуват положителни цели числа ℓ≤r\ell\le r и NN, за коитоan=an−ℓ+aℓa_n=a_{n-\ell}+a_\ellза всяко n≥Nn\ge N.
РешениеИзбираме индекс ℓ≤r\ell\le r, за койтоs=max⁡1≤i≤raii=aℓℓ.s=\max_{1\le i\le r}\frac{a_i}{i}=\frac{a_\ell}{\ell}.Полагаме bn=an−snb_n=a_n-sn. Тогава bℓ=0b_\ell=0 и за 1≤i≤r1\le i\le r имаме bi≤0b_i\le0. Ще докажем по индукция, че bn≤0b_n\le0 за всяко nn и че за n>rn\gt{}rbn=max⁡1≤k≤n−1(bk+bn−k).(1)b_n=\max_{1\le k\le n-1}(b_k+b_{n-k}).\tag{1}За n≤rn\le r това вече е ясно. Ако n>rn\gt{}r, използваме дефиницията на ana_n:bn=max⁡1≤k≤n−1(ak+an−k)−sn=b_n=\max_{1\le k\le n-1}(a_k+a_{n-k})-sn=max⁡1≤k≤n−1(bk+bn−k)≤\max_{1\le k\le n-1}(b_k+b_{n-k})\le0.0.Така (1) също е доказано. Ако bi=0b_i=0 за всички 1≤i≤r1\le i\le r, то от (1) следва bn=0b_n=0 за всяко nn и задачата е решена. Иначе некаM=max⁡1≤i≤r∣bi∣,M=\max_{1\le i\le r}|b_i|,ε=min⁡{∣bi∣:1≤i≤r, bi≠0}.\qquad \varepsilon=\min\{|b_i|:1\le i\le r,\ b_i\ne0\}.От (1) имаме0≥bn≥bn−ℓ≥bn−2ℓ≥⋯≥−M.0\ge b_n\ge b_{n-\ell}\ge b_{n-2\ell}\ge\cdots\ge -M.Освен това, като разлагаме bnb_n чрез (1) до началните индекси, всяка стойност bnb_n е сума от някои числа измежду b1,…,brb_1,\ldots,b_r. В такава сума, ако стойността е в интервала [−M,0][-M,0], броят на ненулевите събираеми е най-много M/εM/\varepsilon. Следователно множеството от всички възможни стойности на bnb_n е крайно. За всеки остатък t=1,2,…,ℓt=1,2,\ldots,\ell редицатаbt,bt+ℓ,bt+2ℓ,…b_t,b_{t+\ell},b_{t+2\ell},\ldotsе ненамаляваща и приема стойности в крайно множество. Значи от някое място нататък тя е константна. Следователно съществува NN, за което bn=bn−ℓ=bn−ℓ+bℓb_n=b_{n-\ell}=b_{n-\ell}+b_\ell за всички n≥Nn\ge N. Тогаваan−sn=an−ℓ−s(n−ℓ)+aℓ−sℓ,a_n-sn=a_{n-\ell}-s(n-\ell)+a_\ell-s\ell,тоест an=an−ℓ+aℓa_n=a_{n-\ell}+a_\ell за всички достатъчно големи nn.
Отвори задачатаMathNetISL 2010 A7Условие — източник

Задача A8

Пълен запис
Условие
Дадени са шест положителни числа a,b,c,d,e,fa,b,c,d,e,f, за коитоa<b<c<d<e<f.a\lt{}b\lt{}c\lt{}d\lt{}e\lt{}f.Нека a+c+e=Sa+c+e=S и b+d+f=Tb+d+f=T. Докажете, че2ST>2ST\gt{}x23(S+T)(S(bd+bf+df)+T(ac+ae+ce)).\sqrt{\vphantom{x^2}3(S+T)\bigl(S(bd+bf+df)+T(ac+ae+ce)\bigr)}.
РешениеПолагамеσ=ac+ae+ce,τ=bd+bf+df.\sigma=ac+ae+ce,\qquad \tau=bd+bf+df.Ще докажем еквивалентното неравенство4S2T2>3(S+T)(Sτ+Tσ).(1)4S^2T^2\gt{}3(S+T)(S\tau+T\sigma).\tag{1}Разглеждаме полиномаP(x)=P(x)=T(x−a)(x−c)(x−e)+S(x−b)(x−d)(x−f).T(x-a)(x-c)(x-e)+S(x-b)(x-d)(x-f).Той е кубичен с водещ коефициент S+T>0S+T\gt{}0. Освен товаP(a)<0,P(c)>0,P(e)<0,P(f)>0.P(a)\lt{}0,\qquad P(c)\gt{}0,\qquad P(e)\lt{}0,\qquad P(f)\gt{}0.Затова в интервалите (a,c)(a,c), (c,e)(c,e) и (e,f)(e,f) има по един корен. Нека те са α,β,γ\alpha,\beta,\gamma. ТогаваP(x)=(S+T)(x−α)(x−β)(x−γ).P(x)=(S+T)(x-\alpha)(x-\beta)(x-\gamma).От друга страна, след разкриване на скобите,P(x)=P(x)=(S+T)x3−2STx2+(Sτ+Tσ)x−(Tace+Sbdf).(S+T)x^3-2STx^2+(S\tau+T\sigma)x-(Tace+Sbdf).Сравнявайки коефициентите, получаваме\alpha+eta+\gamma=\frac{2ST}{S+T},\qquad \alpha\beta+\alpha\gamma+eta\gamma=\frac{S\tau+T\sigma}{S+T}.Корените са различни, следователно0<0\lt{}(\alpha-eta)^2+(\alpha-\gamma)^2+(eta-\gamma)^2=2(\alpha+eta+\gamma)^2-6(\alphaeta+\alpha\gamma+eta\gamma).Значи(2STS+T)2>3Sτ+TσS+T,\left(\frac{2ST}{S+T}\right)^2\gt{}3\frac{S\tau+T\sigma}{S+T},което е точно (1). Следователно исканото неравенство е доказано.
Отвори задачатаMathNetISL 2010 A8Условие — източник

Задача C1

Пълен запис
Условие
В концерт ще участват 2020 певци. За всеки певец е дадено, възможно празно, множество от други певци, след които той иска да пее. Възможно ли е да има точно 20102010 нареждания на певците, при които всички желания са изпълнени?
РешениеДа, възможно е. Ще казваме, че числото NN е реализируемо с kk певци, ако за подходящи желания между тези kk певци има точно NN допустими нареждания. Ако N1N_1 и N2N_2 са реализируеми съответно с k1k_1 и k2k_2 певци, то N1N2N_1N_2 е реализируемо с k1+k2k_1+k_2 певци: вземаме двете групи независимо и добавяме желание всеки певец от втората група да пее след всички певци от първата. Тогава допустимите нареждания се получават независимо в двата блока. Остава да реализираме 55, 66 и 6767, защото 2010=5⋅6⋅672010=5\cdot6\cdot67 и 4+3+13=204+3+13=20. Числото 55 се реализира с четирима певци a,b,c,da,b,c,d, ако cc иска да пее след aa и bb, а dd иска да пее след bb. Допустимите нареждания са точно(a,b,c,d), (a,b,d,c), (b,a,c,d),(a,b,c,d),\ (a,b,d,c),\ (b,a,c,d), (b,a,d,c), (b,d,a,c).\ (b,a,d,c),\ (b,d,a,c).Числото 66 се реализира с трима певци без никакви желания. За 6767 вземаме певци u1,u2,…,u11,x,yu_1,u_2,\ldots,u_{11},x,y. Поставяме желанията ui+1u_{i+1} да пее след uiu_i за i=1,2,…,10i=1,2,\ldots,10, още u9u_9 да пее след xx, и yy да пее след u5u_5. Така редът на u1,…,u11u_1,\ldots,u_{11} е фиксиран. Певецът xx може да бъде поставен в една от 99 позиции преди u9u_9, а yy - в една от 77 позиции след u5u_5. Това дава 9⋅79\cdot7 избора на позиции. Ако двамата попаднат в една и съща междина между uiu_i и ui+1u_{i+1} за i=5,6,7,8i=5,6,7,8, има два възможни реда на xx и yy вместо един. Следователно общият брой е 9⋅7+4=679\cdot7+4=67. По лемата за произведение тези три конструкции дават точно 20102010 допустими нареждания на 2020 певци.
Отвори задачатаMathNetISL 2010 C1Условие — източник

Задача C2

Пълен запис
Условие
На някаква планета има 2N2^N държави, където N≥4N\ge4. Всяка държава има знаме с ширина NN единици и височина 11 единица, съставено от NN полета 1×11\times1, всяко от които е жълто или синьо. Няма две държави с еднакви знамена. Множество от NN знамена се нарича разнообразно, ако тези знамена могат да бъдат подредени като квадрат N×NN\times N така, че всички NN полета по главния диагонал да са в един и същ цвят. Да се намери най-малкото положително цяло число MM, за което измежду всеки MM различни знамена съществуват NN знамена, образуващи разнообразно множество.
РешениеОтговорът еM=2N−2+1.M=2^{N-2}+1.Най-напред M>2N−2M\gt{}2^{N-2}. Вземаме всички 2N−22^{N-2} знамена, при които първото поле е жълто, а второто е синьо. Във всеки квадрат N×NN\times N, образуван от такива знамена, диагоналът минава през една клетка от първата колона и една клетка от втората колона, следователно на диагонала се срещат и двата цвята. Остава да докажем, че всяко множество от 2N−2+12^{N-2}+1 знамена съдържа разнообразно подмножество. Да построим два двуделни графа. Отляво са колоните 1,2,…,N1,2,\ldots,N, а отдясно са избраните знамена. В графа GYG_Y свързваме колона cc със знаме ff, ако в колона cc на ff стои жълто поле; аналогично дефинираме GBG_B за сините полета. Ако в някой от двата графа има съчетание, което покрива всички колони, тогава подреждаме съответните NN знамена като редове, така че знамето, съчетано с колона cc, да бъде на cc-тия ред. Диагоналът е едноцветен, значи имаме разнообразно множество. Да допуснем, че такова съчетание няма нито в GYG_Y, нито в GBG_B. По лемата на Хол съществуват множества от колони SY,SBS_Y,S_B с∣NY(SY)∣≤∣SY∣−1,∣NB(SB)∣≤∣SB∣−1,|N_Y(S_Y)|\le |S_Y|-1,\qquad |N_B(S_B)|\le |S_B|-1,където NYN_Y и NBN_B са съответните множества от съседни знамена. Тези множества колони не могат да бъдат всички колони, защото тогава, освен евентуално едно изцяло противоположно едноцветно знаме, всички знамена биха били съседи, а общият им брой е по-голям от NN. Ако SY∩SB≠∅S_Y\cap S_B\ne\varnothing, всяко знаме е съседно или на SYS_Y в жълтия граф, или на SBS_B в синия граф. Тогава2N−2+1≤∣NY(SY)∣+∣NB(SB)∣≤2^{N-2}+1\le |N_Y(S_Y)|+|N_B(S_B)|\le∣SY∣+∣SB∣−2≤2N−4, |S_Y|+|S_B|-2\le2N-4,което е невъзможно за N≥4N\ge4. Значи SYS_Y и SBS_B са непресичащи се. Нека c=∣SY∣+∣SB∣c=|S_Y|+|S_B|. Знаме, което не е в NY(SY)∪NB(SB)N_Y(S_Y)\cup N_B(S_B), трябва да е синьо във всички колони от SYS_Y и жълто във всички колони от SBS_B; останалите N−cN-c позиции се избират най-много по 2N−c2^{N-c} начина. Следователно2N−c≥2^{N-c}\ge2N−2+1−(∣SY∣−1)−(∣SB∣−1)=2N−2+3−c. 2^{N-2}+1-(|S_Y|-1)-(|S_B|-1)=2^{N-2}+3-c.Това е невъзможно за всяко 2≤c≤N2\le c\le N: при c=2c=2 дясната страна е с 11 по-голяма от лявата, а при c≥3c\ge3 неравенството е още по-силно невярно. Полученото противоречие доказва горната граница.
Отвори задачатаMathNetISL 2010 C2Условие — източник

Задача C3

Пълен запис
Условие
Трябва да се поставят 25002500 шахматни царя върху дъска 100×100100\times100 така, че: (i) никой цар да не може да вземе друг цар, т.е. никои два царя да не са в две клетки с общ връх; (ii) всеки ред и всеки стълб да съдържа точно 2525 царя. Да се намери броят на такива разположения. Две разположения, които се получават едно от друго чрез завъртане или симетрия, се считат за различни.
РешениеОтговорът е: точно две разположения. Разделяме дъската на 50×5050\times50 блока 2×22\times2. Във всеки блок има най-много един цар, а блоковете са точно 25002500, колкото са царете. Следователно във всеки блок има точно един цар. За всеки блок записваме дали царят е в горната или долната половина, съответно с TT или BB, и дали е в лявата или дясната половина, съответно с LL или RR. Блоковете номерираме с (i,j)(i,j), 1≤i,j≤501\le i,j\le50. Ако (i,j)(i,j) е BB-блок, то (i+1,j)(i+1,j), ако съществува, също е BB-блок; иначе царете в тези два съседни блока биха се нападали. Аналогично TT се разпространява нагоре, LL наляво, а RR надясно. Освен това всеки ред от блокове съдържа 2525 TT-блока и 2525 BB-блока, а всеки стълб от блокове съдържа 2525 LL-блока и 2525 RR-блока. Ако в първия ред на блоковете даден стълб е BB, то целият този стълб е BB-стълб. В първия ред има точно 2525 такива стълба, значи всички останали 2525 стълба са TT-стълбове. По същия начин има точно 2525 LL-реда и 2525 RR-реда. Да разгледаме две съседни колони от блокове с различен тип. Ако първата е TT-стълб, а втората е BB-стълб, тогава всеки LL-ред принуждава следващия ред също да бъде LL-ред; иначе в двата блока около границата между колоните биха се получили нападнати царе. Следователно LL-редовете са последните 2525 реда, а RR-редовете са първите 2525 реда. Прилагайки същия аргумент към съседните редове 2525 и 2626, получаваме, че TT-стълбовете са първите 2525 стълба, а BB-стълбовете - последните 2525. Това определя едно разположение: в блоковете от горната лява четвърт царете са в позиция TRTR, в горната дясна - в BRBR, в долната лява - в TLTL, а в долната дясна - в BLBL. Ако при съседната двойка първата колона е BB-стълб, а втората е TT-стълб, симетрично получаваме второто разположение: първите 2525 реда са LL-редове, последните 2525 са RR-редове, първите 2525 стълба са BB-стълбове, а последните 2525 са TT-стълбове. Двете описани разположения очевидно удовлетворяват условията, а други случаи няма.
Отвори задачатаMathNetISL 2010 C3Условие — източник

Задача C4

Пълен запис
Условие
Шест купчини S1,S2,…,S6S_1,S_2,\ldots,S_6 от монети са наредени в редица. В началото всяка купчина съдържа по една монета. Позволени са два вида ходове: Ход 1: ако купчината SkS_k, където 1≤k≤51\le k\le5, съдържа поне една монета, може да премахнем една монета от SkS_k и да добавим две монети към Sk+1S_{k+1}. Ход 2: ако купчината SkS_k, където 1≤k≤41\le k\le4, съдържа поне една монета, може да премахнем една монета от SkS_k и да разменим купчините Sk+1S_{k+1} и Sk+2S_{k+2}. Възможно ли е чрез редица от такива ходове първите пет купчини да станат празни, а шестата купчина S6S_6 да съдържа точно 2010201020102010^{2010^{2010}} монети?
РешениеДа. Нека A=201020102010A=2010^{2010^{2010}}. Ще пишем(a1,a2,…,am)⇒(b1,b2,…,bm),(a_1,a_2,\ldots,a_m)\Rightarrow(b_1,b_2,\ldots,b_m),ако за няколко последователни купчини с първоначални размери a1,…,ama_1,\ldots,a_m можем чрез позволени ходове да получим размери b1,…,bmb_1,\ldots,b_m, без да променяме останалите купчини. Първо, за всяко a≥1a\ge1 имаме(a,0,0)⇒(0,2a,0).(1)(a,0,0)\Rightarrow(0,2^a,0).\tag{1}Наистина, с индукция по kk получаваме(a,0,0)⇒(a−k,2k,0)(1≤k≤a).(a,0,0)\Rightarrow(a-k,2^k,0)\qquad(1\le k\le a).Преходът от kk към k+1k+1 става, като с ход 1 прехвърлим средната купчина надясно до (a−k,0,2k+1)(a-k,0,2^{k+1}), а после приложим ход 2 към първата купчина, което разменя двете празни/непразни следващи позиции и дава (a−k−1,2k+1,0)(a-k-1,2^{k+1},0). Дефинираме P1=2P_1=2 и Pm+1=2PmP_{m+1}=2^{P_m}. Ще докажем, че(a,0,0,0)⇒(0,Pa,0,0)(2)(a,0,0,0)\Rightarrow(0,P_a,0,0)\tag{2}за всяко a≥1a\ge1. Отново използваме индукция: ако вече имаме (a−k,Pk,0,0)(a-k,P_k,0,0), прилагаме (1) към последните три купчини и получаваме (a−k,0,Pk+1,0)(a-k,0,P_{k+1},0); после ход 1 от първата купчина и ход 2 връщат голямата купчина във втора позиция, т.е. (a−k−1,Pk+1,0,0)(a-k-1,P_{k+1},0,0). Сега започваме от шестте купчини:(1,1,1,1,1,1)⇒(1,1,1,1,0,3)⇒(1,1,1,0,3,0)⇒(1,1,0,3,0,0)⇒(1,0,3,0,0,0)⇒(0,3,0,0,0,0).\begin{aligned} (1,1,1,1,1,1)&\Rightarrow(1,1,1,1,0,3)\Rightarrow(1,1,1,0,3,0)\\ &\Rightarrow(1,1,0,3,0,0)\Rightarrow(1,0,3,0,0,0)\Rightarrow(0,3,0,0,0,0). \end{aligned}Прилагаме (2) два пъти:(0,3,0,0,0,0)⇒(0,0,P3,0,0,0)=(0,3,0,0,0,0)\Rightarrow(0,0,P_3,0,0,0)=(0,0,16,0,0,0)⇒(0,0,0,P16,0,0).(0,0,16,0,0,0)\Rightarrow(0,0,0,P_{16},0,0).Имаме 2010<2112010\lt{}2^{11} и20102010<211⋅2010<265536=P5,2010^{2010}\lt{}2^{11\cdot2010}\lt{}2^{65536}=P_5,откъдетоA=201020102010<A=2010^{2010^{2010}}\lt{}(211)P5=211P5<2P6=P7<P16.(2^{11})^{P_5}=2^{11P_5}\lt{}2^{P_6}=P_7\lt{}P_{16}.Освен това AA се дели на 44. Чрез многократно прилагане на ход 2 към четвъртата купчина намаляваме броя монети в нея от P16P_{16} до A/4A/4, като петата и шестата купчина остават празни. Накрая прилагаме ход 1 A/4A/4 пъти от S4S_4 към S5S_5 и после A/2A/2 пъти от S5S_5 към S6S_6. Получаваме(0,0,0,A/4,0,0)⇒(0,0,0,0,A/2,0)⇒(0,0,0,0,0,A),(0,0,0,A/4,0,0)\Rightarrow(0,0,0,0,A/2,0)\Rightarrow(0,0,0,0,0,A),както се иска.
Отвори задачатаMathNetISL 2010 C4Условие — източник

Задача C5

Пълен запис
Условие
В тенис турнир участвали n≥4n\ge4 играчи. Всеки двама играчи играли точно една игра и не е имало равен резултат. Компания от четирима играчи се нарича лоша, ако един от играчите е победен от другите трима, а всеки от тези трима е спечелил една игра и е загубил една игра помежду им. Да предположим, че в турнира няма лоша компания. Нека wiw_i и ℓi\ell_i са съответно броят победи и броят загуби на ii-тия играч. Докажете, че∑i=1n(wi−ℓi)3≥0.\sum_{i=1}^n (w_i-\ell_i)^3\ge0.
РешениеВ произволно множество от играчи ще наричаме даден играч локален шампион, ако е победил всички останали в това множество, и локален губещ, ако е загубил от всички останали. Броят на локалните шампиони във всички kk-елементни множества е∑i=1n(wik−1),\sum_{i=1}^n \binom{w_i}{k-1},а броят на локалните губещи е∑i=1n(ℓik−1).\sum_{i=1}^n \binom{\ell_i}{k-1}.За k=2k=2 тези два броя са равни, защото всяка игра има един победител и един загубил:∑i=1n(wi−ℓi)=0.(1)\sum_{i=1}^n(w_i-\ell_i)=0.\tag{1}За k=3k=3 всяка тройка или е цикъл без локален шампион и без локален губещ, или има по един от двата вида. Затова∑i=1n((wi2)−(ℓi2))=0.(2)\sum_{i=1}^n\left(\binom{w_i}{2}-\binom{\ell_i}{2}\right)=0.\tag{2}За k=4k=4 условието на задачата означава, че всяка четворка с локален губещ има и локален шампион; следователно∑i=1n((wi3)−(ℓi3))≥0.(3)\sum_{i=1}^n\left(\binom{w_i}{3}-\binom{\ell_i}{3}\right)\ge0.\tag{3}Използваме тъждеството(x−y)3=(x-y)^3=24((x3)−(y3))+24((x2)−(y2))24\left(\binom{x}{3}-\binom{y}{3}\right)+24\left(\binom{x}{2}-\binom{y}{2}\right)−(3(x+y)2−4)(x−y).-\bigl(3(x+y)^2-4\bigr)(x-y).Прилагаме го за x=wix=w_i, y=ℓiy=\ell_i. Понеже всеки играч е изиграл n−1n-1 игри, имаме wi+ℓi=n−1w_i+\ell_i=n-1. Сумирайки по ii и използвайки (1), (2) и (3), получаваме∑i=1n(wi−ℓi)3≥0,\sum_{i=1}^n(w_i-\ell_i)^3\ge0,което трябваше да се докаже.
Отвори задачатаMathNetISL 2010 C5Условие — източник

Задача C6

Пълен запис
Условие
Дадени са положително цяло число kk и две цели числа b>w>1b\gt{}w\gt{}1. Има два низа от перли: низ от bb черни перли и низ от ww бели перли. Дължината на низ е броят перли в него. Низовете се режат на стъпки по следните правила. На всяка стъпка: (i) Низовете се подреждат по дължина в ненарастващ ред. Ако има низове с равни дължини, белите се поставят преди черните. Избират се първите kk низа, ако съдържат повече от една перла; ако низовете с дължина по-голяма от 11 са по-малко от kk, се избират всички такива низове. (ii) Всеки избран низ се разрязва на две части, чиито дължини се различават с най-много 11. Например, ако има черни низове с дължини 5,4,4,25,4,4,2, бели низове с дължини 8,4,38,4,3 и k=4k=4, тогава се режат белият низ с дължина 88, черният с дължина 55, белият с дължина 44 и черният с дължина 44, като се получават части с дължини съответно (4,4)(4,4), (3,2)(3,2), (2,2)(2,2) и (2,2)(2,2). Процесът спира веднага след стъпката, при която за първи път се появи отделна бяла перла. Докажете, че в този момент все още съществува черен низ с поне две перли.
РешениеПродължаваме процеса мислено и след първата отделна бяла перла, докато всички перли станат отделни. Нека AiA_i е състоянието след ii-тата стъпка. Нека ss е първият момент, в който се появява отделна перла от който и да е цвят, tt - първият момент, в който общият брой низове става по-голям от kk (ако това не се случи, полагаме t=∞t=\infty), а ff - първият момент, в който всички черни перли са отделни. Достатъчно е да докажем, че не по-късно от Af−1A_{f-1} вече има отделна бяла перла. За i≤min⁡(s,t)i\le \min(s,t) в състоянието AiA_i има точно 2i2^i черни и 2i2^i бели низа. Нека Bi,biB_i,b_i са най-голямата и най-малката дължина на черен низ в AiA_i, а Wi,wiW_i,w_i - съответните величини за белите низове. С индукция получавамеBi≥Wi,bi≥wi(i≤min⁡(s,t)).(1)B_i\ge W_i,\qquad b_i\ge w_i\qquad(i\le \min(s,t)).\tag{1}Наистина, до тези моменти всички низове с дължина по-голяма от 11 се режат, а разрязването запазва тези сравнения след закръгляне нагоре и надолу. Първи случай: s≤ts\le t или f≤t+1f\le t+1. В състоянието As−1A_{s-1} няма отделни перли и по (1) най-късите черни низове са не по-къси от най-късите бели. Ако s=fs=f, тогава непосредствено преди това всички черни низове трябва да са с дължина 22, а бели единични низове още няма; от (1) следва, че всички бели низове също са с дължина 22. Тогава броят на черните и белите перли би бил един и същ, противоречие с b>wb\gt{}w. Значи s≤f−1s\le f-1. При стъпка ss се появява отделна перла; ако тя е черна, от (1) се появява и бяла, а ако е бяла - сме готови. Следователно преди всички черни перли да станат отделни вече се е появила отделна бяла перла. Втори случай: t+1≤st+1\le s и t+2≤ft+2\le f. Тогава в AtA_t има точно 2t2^t черни и 2t2^t бели низа, всички с дължина по-голяма от 11, и2t+1>k≥2t.2^{t+1}\gt{}k\ge2^t.На следващата стъпка се режат точно kk низа, от които най-много 2t2^t са черни. Затова броят на белите низове в At+1A_{t+1} е поне kk, а по-нататък той не намалява. Следователно в Af−1A_{f-1} има поне kk бели низа. В стъпката ff поне един черен низ с дължина 22 се реже, а всички черни низове в Af−1A_{f-1} са с дължина най-много 22. Понеже се режат най-много kk низа, поне един от белите низове в Af−1A_{f-1} не се реже. Но всеки бял низ с дължина поне 22 би стоял в реда преди черен низ с дължина 22 или не по-късно от него, следователно би бил избран за рязане. Значи неизбраният бял низ е отделна перла. Това отново показва, че отделна бяла перла се появява преди всички черни перли да са отделни. И в двата случая, когато първата отделна бяла перла се появи, все още има черен низ с дължина поне 22.
Отвори задачатаMathNetISL 2010 C6Условие — източник

Задача C7

Пълен запис
Условие
Нека P1,P2,…,PsP_1,P_2,\ldots,P_s са аритметични прогресии от цели числа, за които са изпълнени следните условия: (i) всяко цяло число принадлежи на поне една от тях; (ii) всяка прогресия съдържа число, което не принадлежи на никоя от другите прогресии. Нека nn е най-малкото общо кратно на разликите на тези прогресии и некаn=p1α1⋯pkαkn=p_1^{\alpha_1}\cdots p_k^{\alpha_k}е разлагането му на прости множители. Докажете, чеs≥1+∑i=1kαi(pi−1).s\ge1+\sum_{i=1}^k \alpha_i(p_i-1).
РешениеЩе използваме следната лема. НекаN={(a1,…,ak):0≤ai≤ni−1}\mathcal N=\{(a_1,\ldots,a_k):0\le a_i\le n_i-1\}е решетка n1×⋯×nkn_1\times\cdots\times n_k. Подрешетка ще наричаме множество от точки, в което е фиксирано непразно множество от координати. Да предположим, че подрешетки L1,…,LsL_1,\ldots,L_s покриват N\mathcal N, всяка от тях има точка, която не лежи в никоя друга, и за всяка координатна ос има подрешетка, която фиксира тази координата. Тогаваs≥1+∑i=1k(ni−1).(1)s\ge1+\sum_{i=1}^k(n_i-1).\tag{1}Доказателство на лемата. Да допуснем противното, т.е. s≤∑(ni−1)s\le\sum(n_i-1). Построяваме двуделен граф. Отляво са подрешетките LjL_j, а отдясно има ni−1n_i-1 копия на всяка координата ii. Свързваме LjL_j с копията на координата ii, ако LjL_j фиксира координата ii. Нека WW е максимално по включване множество от леви върхове, за което броят на съседите е по-малък от ∣W∣|W|; ако няма такова множество, вземаме W=∅W=\varnothing. Понеже всяка координата е фиксирана от някоя подрешетка, всички десни върхове имат съсед, а от s≤∑(ni−1)s\le\sum(n_i-1) следва W≠{L1,…,Ls}W\ne\{L_1,\ldots,L_s\}. Нека UU са останалите леви върхове, а U′U' - десните върхове, които не са съседи на WW. От максималността на WW следва, че за всяко X⊆UX\subseteq U множеството XX има поне ∣X∣|X| съседи в U′U'. По лемата на Хол можем да съчетаем всяка подрешетка от UU с различен десен връх от U′U'. Избираме точка bb, която не е покрита от подрешетките в WW; такава има, защото някоя подрешетка от UU има собствена точка. За всяка координата, която се появява в U′U', има най-много ni−1n_i-1 подрешетки от UU, съчетани с копия на тази координата, затова можем да изберем стойност aia_i, различна от всички фиксирани стойности на тези подрешетки. За останалите координати полагаме ai=bia_i=b_i. Получената точка aa не лежи в никоя подрешетка от UU поради съчетаната координата. Ако лежеше в подрешетка от WW, понеже bb не лежи там, тази подрешетка би фиксирала координата, в която aa и bb се различават; но тогава би имала съсед в U′U', противоречие. Значи aa не е покрита, което доказва лемата. Сега прилагаме лемата към прогресиите. Достатъчно е да разглеждаме остатъците по модул nn. За число mm и за всеки ii записваме остатъка на mm по модул piαip_i^{\alpha_i} в основа pip_i с точно αi\alpha_i цифри. Така на mm съответства точка в решетка, чиито координатни размери саp1,…,p1⏟α1 пъти,…,pk,…,pk⏟αk пъти.\underbrace{p_1,\ldots,p_1}_{\alpha_1\text{ пъти}},\ldots,\underbrace{p_k,\ldots,p_k}_{\alpha_k\text{ пъти}}.Китайската теорема за остатъците показва, че това е биекция между остатъците по модул nn и точките на решетката. Нека разликата на PjP_j еdj=p1γ1⋯pkγk.d_j=p_1^{\gamma_1}\cdots p_k^{\gamma_k}.Принадлежността към PjP_j означава, че числото има фиксиран остатък по модул djd_j. В описаните координати това точно фиксира първите γi\gamma_i цифри за всяко просто pip_i, следователно образът на PjP_j е подрешетка. Условията (i) и (ii) дават покритие на решетката и собствена точка за всяка подрешетка. Остава условието за координатните оси. Тъй като nn е най-малкото общо кратно на всички djd_j, за всяко ii и всяко ниво 1≤r≤αi1\le r\le\alpha_i има прогресия, чиято разлика се дели на pirp_i^r; съответната подрешетка фиксира координатата на тази rr-та цифра. Лемата даваs≥1+∑i=1kαi(pi−1),s\ge1+\sum_{i=1}^k\alpha_i(p_i-1),както трябваше да се докаже.
Отвори задачатаMathNetISL 2010 C7Условие — източник

Задача N1

Пълен запис
Условие
Да се намери най-малкото положително цяло число nn, за което съществува множество {s1,s2,…,sn}\{s_1,s_2,\ldots,s_n\} от nn различни положителни цели числа, такова че(1−1s1)(1−1s2)⋯(1−1sn)=512010.\left(1-\frac1{s_1}\right)\left(1-\frac1{s_2}\right)\cdots\left(1-\frac1{s_n}\right)=\frac{51}{2010}.
РешениеОтговорът еn=39.n=39.Нека такова множество съществува и подредим елементите му катоs1<s2<⋯<sn.s_1\lt{}s_2\lt{}\cdots\lt{}s_n.Не може s1=1s_1=1, защото тогава произведението би било 00. Следователно si≥i+1s_i\ge i+1 за всяко ii, и затова512010=∏i=1n(1−1si)≥\frac{51}{2010}=\prod_{i=1}^n\left(1-\frac1{s_i}\right)\ge∏i=1n(1−1i+1)=1n+1.\prod_{i=1}^n\left(1-\frac1{i+1}\right)=\frac1{n+1}.Понеже 51/2010=17/67051/2010=17/670, получаваме n+1≥670/17>39n+1\ge670/17\gt{}39, тоест n≥39n\ge39. Остава да дадем пример с 39 числа. Вземаме{2,3,…,33,35,36,…,40,67}.\{2,3,\ldots,33,35,36,\ldots,40,67\}.Това множество има 39 елемента и∏(1−1s)=\prod\left(1-\frac1s\right)=12⋅23⋯3233⋅3435⋯3940⋅6667=\frac12\cdot\frac23\cdots\frac{32}{33}\cdot\frac{34}{35}\cdots\frac{39}{40}\cdot\frac{66}{67}=133⋅3440⋅6667=17670=512010.\frac1{33}\cdot\frac{34}{40}\cdot\frac{66}{67}=\frac{17}{670}=\frac{51}{2010}.Следователно най-малката стойност е 3939.
Отвори задачатаMathNetISL 2010 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се намерят всички двойки (m,n)(m,n) от неотрицателни цели числа, за коитоm2+2⋅3n=m(2n+1−1).m^2+2\cdot3^n=m(2^{n+1}-1).
РешениеОтговорът е(6,3), (9,3), (9,5), (54,5).(6,3),\ (9,3),\ (9,5),\ (54,5).За n=0,1,2,3,4,5n=0,1,2,3,4,5 разглеждаме уравнението като квадратно по mm. Пряка проверка дава решения само при n=3n=3, където m=6,9m=6,9, и при n=5n=5, където m=9,54m=9,54. Ще докажем, че при n≥6n\ge6 решения няма. От уравнението следва, че mm дели 2⋅3n2\cdot3^n, а m>0m\gt{}0. Значи или m=3pm=3^p, или m=2⋅3qm=2\cdot3^q, където показателите са неотрицателни и не надминават nn. И в двата случая получаваме уравнение3p+2⋅3q=2n+1−1,p+q=n.(1)3^p+2\cdot3^q=2^{n+1}-1,\qquad p+q=n.\tag{1}От (1) следват оценкитеn−23<p,q<2(n+1)3.(2)\frac{n-2}{3}\lt{}p,q\lt{}\frac{2(n+1)}3.\tag{2}Нека h=min⁡(p,q)h=\min(p,q). Тогава h>1h\gt{}1, а лявата страна на (1) се дели на 3h3^h, следователно9∣2n+1−1.9\mid 2^{n+1}-1.Понеже редът на 22 по модул 99 е 66, имаме n+1=6rn+1=6r за някое положително цяло rr. Разлагаме2n+1−1=26r−1=(42r+4r+1)(2r−1)(2r+1).2^{n+1}-1=2^{6r}-1=(4^{2r}+4^r+1)(2^r-1)(2^r+1).Първият множител се дели на 33, но не и на 99, а последните два множителя са взаимнопрости. Затова един от тях се дели на 3h−13^{h-1}, откъдето3h−1≤2r+1≤3r=3(n+1)/6.3^{h-1}\le2^r+1\le3^r=3^{(n+1)/6}.Оттук h−1≤(n+1)/6h-1\le(n+1)/6, което противоречи на h>(n−2)/3h\gt{}(n-2)/3 и n+1≡0(mod6)n+1\equiv0\pmod6 при n≥6n\ge6. Значи други решения няма.
Отвори задачатаMathNetISL 2010 N2Условие — източник

Задача N3

Пълен запис
Условие
Да се намери най-малкото число nn, за което съществуват полиноми f1,f2,…,fnf_1,f_2,\ldots,f_n с рационални коефициенти, удовлетворяващиx2+7=f1(x)2+f2(x)2+⋯+fn(x)2.x^2+7=f_1(x)^2+f_2(x)^2+\cdots+f_n(x)^2.
РешениеОтговорът еn=5.n=5.Примерътx2+7=x2+22+12+12+12x^2+7=x^2+2^2+1^2+1^2+1^2показва, че n≤5n\le5. Ще докажем, че четири квадрата не стигат. Ако имаме представяне с най-много четири квадрата, добавяме нулеви полиноми и пишемx2+7=f1(x)2+f2(x)2+f3(x)2+f4(x)2.x^2+7=f_1(x)^2+f_2(x)^2+f_3(x)^2+f_4(x)^2.Всеки fif_i е от степен най-много 11, така че fi(x)=aix+bif_i(x)=a_ix+b_i с рационални ai,bia_i,b_i. От сравнение на коефициентите получаваме∑i=14ai2=1,∑i=14aibi=0,\sum_{i=1}^4a_i^2=1,\qquad \sum_{i=1}^4a_ib_i=0,∑i=14bi2=7.(1)\qquad \sum_{i=1}^4b_i^2=7.\tag{1}Нека pi=ai+bip_i=a_i+b_i и qi=ai−biq_i=a_i-b_i. Тогава от (1)∑pi2=8,∑qi2=8,∑piqi=−6.\sum p_i^2=8,\qquad \sum q_i^2=8,\qquad \sum p_iq_i=-6.След умножаване с общ знаменател получаваме цели числа xi,yix_i,y_i и положително цяло mm, за които∑xi2=8m2,∑yi2=8m2,\sum x_i^2=8m^2,\qquad \sum y_i^2=8m^2,∑xiyi=−6m2.(2)\qquad \sum x_iy_i=-6m^2.\tag{2}Избираме решение на (2) с минимално mm. От първото равенство по модул 88 следва, че всички xix_i са четни; от второто - че всички yiy_i са четни. Тогава лявата страна на третото равенство в (2) се дели на 44, следователно mm е четно. Делим всички xi,yi,mx_i,y_i,m на 22 и получаваме ново решение на (2) с по-малко положително mm, противоречие. Значи представяне с четири или по-малко квадрата не съществува, и минималното nn е 55.
Отвори задачатаMathNetISL 2010 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека a,ba,b са цели числа и P(x)=ax3+bxP(x)=ax^3+bx. За положително цяло число nn ще казваме, че двойката (a,b)(a,b) е nn-добра, ако отn∣P(m)−P(k)n\mid P(m)-P(k)следваn∣m−kn\mid m-kза всички цели числа m,km,k. Ще казваме, че (a,b)(a,b) е много добра, ако е nn-добра за безкрайно много положителни цели числа nn. (a) Намерете двойка (a,b)(a,b), която е 5151-добра, но не е много добра. (b) Докажете, че всички 20102010-добри двойки са много добри.
Решение(a) Ще покажем, че (1,−512)(1,-51^2) работи. Тогава P(x)=x3−512xP(x)=x^3-51^2x. Понеже P(51)=P(0)P(51)=P(0), двойката не е nn-добра за никое nn, което не дели 5151; следователно не е много добра. Ако P(m)≡P(k)(mod51)P(m)\equiv P(k)\pmod{51}, то m3≡k3(mod51)m^3\equiv k^3\pmod{51}. По модул 33 имаме m3≡mm^3\equiv m и k3≡kk^3\equiv k. По модул 1717 от m3≡k3m^3\equiv k^3 следва m33≡k33m^{33}\equiv k^{33}, а x33≡x(mod17)x^{33}\equiv x\pmod{17} за всяко цяло xx. Значи m≡k(mod3)m\equiv k\pmod3 и m≡k(mod17)m\equiv k\pmod{17}, откъдето m≡k(mod51)m\equiv k\pmod{51}. Така двойката е 5151-добра. (b) Нека (a,b)(a,b) е 20102010-добра и P(x)=ax3+bxP(x)=ax^3+bx. Първо ще докажем, че тя е 6767-добра. Ако P(m)≡P(k)(mod67)P(m)\equiv P(k)\pmod{67}, по китайската теорема за остатъците избираме m′,k′m',k' така, чеm′≡m,k′≡k(mod67),m′≡k′≡0(mod30).m'\equiv m,\quad k'\equiv k\pmod{67},\qquad m'\equiv k'\equiv0\pmod{30}.Тогава P(m′)≡P(k′)(mod67)P(m')\equiv P(k')\pmod{67} и P(m′)≡P(k′)(mod30)P(m')\equiv P(k')\pmod{30}, следователно P(m′)≡P(k′)(mod2010)P(m')\equiv P(k')\pmod{2010}. От 20102010-доброта получаваме m′≡k′(mod2010)m'\equiv k'\pmod{2010}, а значи m≡k(mod67)m\equiv k\pmod{67}. Следващата стъпка е да докажем 67∣a67\mid a. Да допуснем обратното. Множествата{at2(mod67):0≤t≤33}\{at^2\pmod{67}:0\le t\le33\}и{−3as2−b(mod67):0≤s≤33}\{-3as^2-b\pmod{67}:0\le s\le33\}имат по 34 елемента, затова се пресичат. Значи съществуват s,ts,t, за коитоat2≡−3as2−b(mod67).at^2\equiv-3as^2-b\pmod{67}.За двойките (m,k)=(t+s,−2s)(m,k)=(t+s,-2s) и (m,k)=(t−s,2s)(m,k)=(t-s,2s) имамеP(m)−P(k)=(m−k)(a(m2+mk+k2)+b)≡0(mod67).P(m)-P(k)=(m-k)(a(m^2+mk+k^2)+b)\equiv0\pmod{67}.Понеже двойката е 6767-добра, получаваме едновременно t+3s≡0t+3s\equiv0 и t−3s≡0(mod67)t-3s\equiv0\pmod{67}. Следователно s≡t≡0(mod67)s\equiv t\equiv0\pmod{67}, а от избраното сравнение следва b≡0(mod67)b\equiv0\pmod{67}. Но тогаваP(7)−P(2)=67⋅5a+5bP(7)-P(2)=67\cdot5a+5bсе дели на 6767, докато 7−27-2 не се дели на 6767, противоречие. Значи 67∣a67\mid a. Ако и 67∣b67\mid b, то P(x)≡0(mod67)P(x)\equiv0\pmod{67} за всяко xx, което противоречи на 6767-доброта. Значи 67∤b67\nmid b. Нека i≥1i\ge1 и67i∣P(m)−P(k)=(m−k)(a(m2+mk+k2)+b).67^i\mid P(m)-P(k)=(m-k)(a(m^2+mk+k^2)+b).Вторият множител е взаимнопрост с 6767, понеже 67∣a67\mid a и 67∤b67\nmid b. Следователно 67i∣m−k67^i\mid m-k. Значи двойката е 67i67^i-добра за всяко i≥1i\ge1, тоест е много добра.
Отвори задачатаMathNetISL 2010 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека N\mathbb N е множеството на положителните цели числа. Да се намерят всички функции f:N→Nf:\mathbb N\to\mathbb N, за които числото(f(m)+n)(m+f(n))(f(m)+n)(m+f(n))е точен квадрат за всички m,n∈Nm,n\in\mathbb N.
РешениеОтговорът еf(n)=n+c,f(n)=n+c,където cc е неотрицателно цяло число. Тези функции наистина работят, защото(f(m)+n)(m+f(n))=(m+n+c)2.(f(m)+n)(m+f(n))=(m+n+c)^2.Ще докажем, че други няма. Нужна ни е лема: ако pp е просто число и p∣f(k)−f(ℓ)p\mid f(k)-f(\ell), то p∣k−ℓp\mid k-\ell. Първо нека p2∣f(k)−f(ℓ)p^2\mid f(k)-f(\ell). Избираме положително цяло D>max⁡(f(k),f(ℓ))D\gt{}\max(f(k),f(\ell)), което не се дели на pp, и полагаме n=pD−f(k)n=pD-f(k). Тогава n+f(k)n+f(k) и n+f(ℓ)n+f(\ell) се делят на pp, но не и на p2p^2. Понеже(f(k)+n)(k+f(n))(f(k)+n)(k+f(n))и(f(ℓ)+n)(ℓ+f(n))(f(\ell)+n)(\ell+f(n))са квадрати, числата k+f(n)k+f(n) и ℓ+f(n)\ell+f(n) също се делят на pp. Значи p∣k−ℓp\mid k-\ell. Ако f(k)−f(ℓ)f(k)-f(\ell) се дели на pp, но не и на p2p^2, използваме същия аргумент с n=p3D−f(k)n=p^3D-f(k). Тогава едното от числата n+f(k)n+f(k), n+f(ℓ)n+f(\ell) има pp-адичен показател 33, а другото - показател 11, и отново получаваме p∣k−ℓp\mid k-\ell. Лемата е доказана. Ако f(k)=f(ℓ)f(k)=f(\ell), лемата показва, че всяко просто число дели k−ℓk-\ell; следователно k=ℓk=\ell. Значи ff е инективна. За съседни аргументи kk и k+1k+1 числото f(k+1)−f(k)f(k+1)-f(k) няма прост делител, иначе лемата би дала делимост на 11 от това просто число. Понеже разликата не е нула, получаваме∣f(k+1)−f(k)∣=1|f(k+1)-f(k)|=1за всяко kk. Знаците на тези разлики не могат да се сменят, защото тогава за някое kk бихме имали f(k)=f(k+2)f(k)=f(k+2), противоречие с инективността. Всички разлики не могат да са −1-1, понеже стойностите на ff са положителни за безкрайно много аргументи. Значи всички разлики са +1+1, иf(n)=f(1)+n−1=n+cf(n)=f(1)+n-1=n+cс c=f(1)−1≥0c=f(1)-1\ge0.
Отвори задачатаMathNetISL 2010 N5Условие — източник

Задача N6

Пълен запис
Условие
Редовете и колоните на таблица 2n×2n2^n\times2^n са номерирани от 00 до 2n−12^n-1. Клетките са оцветени така, че за всяка двойка 0≤i,j≤2n−10\le i,j\le2^n-1 jj-тата клетка в ii-тия ред и (i+j)(i+j)-тата клетка в jj-тия ред имат един и същи цвят. Индексите в един ред се разглеждат по модул 2n2^n. Докажете, че най-големият възможен брой цветове е 2n2^n.
РешениеЩе означаваме клетката в ред ii и колона jj с (i,j)(i,j), като координатите се разглеждат по модул 2n2^n. Построяваме ориентиран граф с върхове клетките и ребра(i,j)→(j,i+j).(i,j)\to(j,i+j).От всеки връх излиза точно едно ребро и във всеки връх влиза точно едно ребро, следователно графът се разпада на цикли. Условието казва, че всички клетки в един цикъл имат един и същи цвят. Обратно, ако оцветим различните цикли с различни цветове, условието е изпълнено. Значи трябва да преброим циклите на преобразуването (i,j)↦(j,i+j)(i,j)\mapsto(j,i+j). Нека F0=0,F1=1F_0=0,F_1=1 и Fr+2=Fr+1+FrF_{r+2}=F_{r+1}+F_r са числата на Фибоначи, като поставяме и F−1=1F_{-1}=1. Ако последователност (ur)(u_r) удовлетворява ur+1=ur+ur−1u_{r+1}=u_r+u_{r-1}, то лесна индукция даваur=Fr−1u0+Fru1.(1)u_r=F_{r-1}u_0+F_ru_1.\tag{1}Орбитата на клетка (u0,u1)(u_0,u_1) е точно последователността от двойки (ur,ur+1)(u_r,u_{r+1}) по модул 2n2^n. Ще използваме следния стандартен факт за периодите на Фибоначи по модул степени на 22: за q≥1q\ge1 най-малкият период на (Fr)(F_r) по модул 2q2^q е3⋅2q−1.(2)3\cdot2^{q-1}.\tag{2}За пълнота припомняме доказателството. С директна проверка (2) е вярно за q=1,2q=1,2. За q≥3q\ge3 с индукция се доказва, че ако dq=3⋅2q−2d_q=3\cdot2^{q-2}, тоν2(Fdq)=q,Fdq+1≡1+2q−1(mod2q),\nu_2(F_{d_q})=q,\qquad F_{d_q+1}\equiv1+2^{q-1}\pmod{2^q},и dqd_q е най-малкият положителен индекс, за който 2q∣Fdq2^q\mid F_{d_q}. Индукционната стъпка следва от формулитеF2k=2FkFk+1−Fk2,F2k+1=Fk2+Fk+12.F_{2k}=2F_kF_{k+1}-F_k^2,\qquad F_{2k+1}=F_k^2+F_{k+1}^2.Оттук 2dq=3⋅2q−12d_q=3\cdot2^{q-1} е период, а по-малък период не е възможен. Нека двойката (u0,u1)(u_0,u_1) не е (0,0)(0,0) по модул 2n2^n, и нека kk е най-голямото цяло с 0≤k<n0\le k\lt{}n, за което 2k2^k дели и u0u_0, и u1u_1. След деление на 2k2^k получаваме двойка, в която поне една координата е нечетна, и периодът по модул 2n2^n се свежда до периода на тази нова двойка по модул 2n−k2^{n-k}. Ще покажем, че всяка такава примитивна двойка има същите периоди като редицата на Фибоначи по същия модул. Наистина, нека поне едно от u0,u1u_0,u_1 е нечетно. Ако pp е период на двойката, то по (1)up≡u0,up+1≡u1(mod2q).u_p\equiv u_0,\qquad u_{p+1}\equiv u_1\pmod{2^q}.Комбинирайки тези две сравнения, получавамеFp(u12−u0u1−u02)≡0(mod2q),F_p(u_1^2-u_0u_1-u_0^2)\equiv0\pmod{2^q},и(Fp+1−1)(u12−u0u1−u02)≡0(mod2q).(F_{p+1}-1)(u_1^2-u_0u_1-u_0^2)\equiv0\pmod{2^q}.Множителят u12−u0u1−u02u_1^2-u_0u_1-u_0^2 е нечетен, затова Fp≡0F_p\equiv0 и Fp+1≡1(mod2q)F_{p+1}\equiv1\pmod{2^q}, тоест pp е период на Фибоначи. Обратната посока следва веднага от (1). Значи дължината на всеки цикъл с общ точен делител 2k2^k е3⋅2n−k−1.3\cdot2^{n-k-1}.За фиксирано k=0,1,…,n−1k=0,1,\ldots,n-1 броят на двойките (i,j)(i,j), при които 2k2^k дели и двете координати, но 2k+12^{k+1} не дели и двете, е22(n−k)−22(n−k−1)=3⋅22n−2k−2.2^{2(n-k)}-2^{2(n-k-1)}=3\cdot2^{2n-2k-2}.Те се разбиват на цикли с дължина 3⋅2n−k−13\cdot2^{n-k-1}, следователно дават2n−k−12^{n-k-1}цикъла. Двойката (0,0)(0,0) образува отделен цикъл. Общият брой цикли е1+∑k=0n−12n−k−1=1+(1+2+⋯+2n−1)=2n.1+\sum_{k=0}^{n-1}2^{n-k-1}=1+(1+2+\cdots+2^{n-1})=2^n.Следователно най-големият възможен брой цветове е 2n2^n.
Отвори задачатаMathNetISL 2010 N6Условие — източник