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

IMO Shortlisted Problems

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

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

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

2014

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

11-12

22 задачи

Задача A1

Пълен запис
Условие
Нека z0<z1<z2<⋯z_0\lt{}z_1\lt{}z_2\lt{}\cdots е безкрайна редица от положителни цели числа. Докажете, че съществува единствено цяло число n≥1n\ge1, за коетоzn<z0+z1+⋯+znn≤zn+1.z_n\lt{}\frac{z_0+z_1+\cdots+z_n}{n}\le z_{n+1}.
РешениеЗа n=1,2,…n=1,2,\ldots полагамеdn=(z0+z1+⋯+zn)−nzn.d_n=(z_0+z_1+\cdots+z_n)-nz_n.Първото неравенство от условието е изпълнено точно когато dn>0d_n\gt{}0. Освен товаnzn+1−(z0+z1+⋯+zn)=−dn+1,nz_{n+1}-(z_0+z_1+\cdots+z_n)=-d_{n+1},така че второто неравенство е еквивалентно на dn+1≤0d_{n+1}\le0. Следователно трябва да докажем, че има единствен индекс n≥1n\ge1 сdn>0≥dn+1.d_n\gt{}0\ge d_{n+1}.Имаме d1=z0>0d_1=z_0\gt{}0, аdn+1−dn=n(zn−zn+1)<0.d_{n+1}-d_n=n(z_n-z_{n+1})\lt{}0.Следователно d1,d2,…d_1,d_2,\ldots е строго намаляваща редица от цели числа. Понеже при всяка стъпка намалява поне с 11, тя непременно става неположителна. Значи съществува последен положителен член dnd_n, и този индекс е единствен. Точно той дава търсеното nn.
Отвори задачатаMathNetISL 2014 A1Условие — източник

Задача A2

Пълен запис
Условие
Дефинираме функцията f:(0,1)→(0,1)f:(0,1)\to(0,1) чрезf(x)={x+12,ако x<12,x2,ако x≥12.f(x)=\begin{cases}x+\frac12,&\text{ако }x\lt{}\frac12,\\x^2,&\text{ако }x\ge\frac12.\end{cases}Нека aa и bb са реални числа с 0<a<b<10\lt{}a\lt{}b\lt{}1. Дефинираме редиците ana_n и bnb_n чрез a0=aa_0=a, b0=bb_0=b и an=f(an−1)a_n=f(a_{n-1}), bn=f(bn−1)b_n=f(b_{n-1}) за n>0n\gt{}0. Докажете, че съществува положително цяло число nn, за което(an−an−1)(bn−bn−1)<0.(a_n-a_{n-1})(b_n-b_{n-1})\lt{}0.
РешениеРазделяме интервала (0,1)(0,1) наI1=(0,12),I2=[12,1).I_1=\left(0,\frac12\right),\qquad I_2=\left[\frac12,1\right).За x∈I1x\in I_1 имаме f(x)−x=12>0f(x)-x=\frac12\gt{}0, а за x∈I2x\in I_2 имаме f(x)−x=x2−x<0f(x)-x=x^2-x\lt{}0. Следователно търсеното неравенство е вярно точно когато an−1a_{n-1} и bn−1b_{n-1} лежат в различни от тези два интервала. Да допуснем противното: за всяко k≥0k\ge0 числата aka_k и bkb_k лежат в един и същи интервал. Некаdk=∣ak−bk∣.d_k=|a_k-b_k|.Ако и двете числа са в I1I_1, тогава dk+1=dkd_{k+1}=d_k. Ако и двете са в I2I_2, тогаваdk+1=∣ak2−bk2∣=dk(ak+bk).d_{k+1}=|a_k^2-b_k^2|=d_k(a_k+b_k).Понеже по-малкото от ak,bka_k,b_k е поне 12\frac12, а по-голямото е с dkd_k повече, имаме ak+bk≥1+dka_k+b_k\ge1+d_k, откъдетоdk+1≥dk(1+dk)≥dk.d_{k+1}\ge d_k(1+d_k)\ge d_k.Значи редицата (dk)(d_k) е ненамаляваща и dk≥d0>0d_k\ge d_0\gt{}0 за всяко kk. Нещо повече, за всяко kk получавамеdk+2≥dk(1+d0).d_{k+2}\ge d_k(1+d_0).Наистина, ако ak,bk∈I2a_k,b_k\in I_2, това следва от предното неравенство и ненамаляването на (dk)(d_k); ако ak,bk∈I1a_k,b_k\in I_1, то след една стъпка и двете числа попадат в I2I_2, а dk+1=dkd_{k+1}=d_k. Следователно по индукцияd2m≥d0(1+d0)m.d_{2m}\ge d_0(1+d_0)^m.За достатъчно голямо mm дясната страна е по-голяма от 11, което е невъзможно, тъй като a2m,b2m∈(0,1)a_{2m},b_{2m}\in(0,1). Противоречието доказва твърдението.
Отвори задачатаMathNetISL 2014 A2Условие — източник

Задача A3

Пълен запис
Условие
За редица x1,x2,…,xnx_1,x_2,\ldots,x_n от реални числа дефинираме нейната цена катоmax⁡1≤i≤n∣x1+x2+⋯+xi∣.\max_{1\le i\le n}|x_1+x_2+\cdots+x_i|.Дадени са nn реални числа. Дейв и Джордж искат да ги подредят в редица с малка цена. Старателният Дейв проверява всички възможни подредби и намира най-малката възможна цена DD. Алчният Джордж избира x1x_1 така, че ∣x1∣|x_1| да е възможно най-малко; измежду останалите числа избира x2x_2 така, че ∣x1+x2∣|x_1+x_2| да е възможно най-малко, и така нататък. На ii-тата стъпка той избира xix_i измежду останалите числа така, че да минимизира ∣x1+x2+⋯+xi∣|x_1+x_2+\cdots+x_i|. Ако на някоя стъпка няколко числа дават една и съща стойност, Джордж избира произволно едно от тях. Накрая той получава редица с цена GG. Намерете най-малката възможна константа cc, такава че за всяко положително цяло число nn, за всяка колекция от nn реални числа и за всяка възможна редица, която Джордж може да получи, да е изпълнено G≤cDG\le cD.
РешениеОтговорът еc=2.c=2.Първо ще покажем, че по-малка константа не стига. За числата 1,−1,2,−21,-1,2,-2 Дейв може да ги подреди като1,−2,2,−1,1,-2,2,-1,което дава цена D=1D=1. Джордж обаче може да получи редицата1,−1,2,−2,1,-1,2,-2,за която цената е G=2G=2. Следователно c≥2c\ge2. Остава да докажем, че винаги G≤2DG\le2D. Нека дадените числа са x1,x2,…,xnx_1,x_2,\ldots,x_n. Нека Дейв ги подреди като d1,d2,…,dnd_1,d_2,\ldots,d_n, а Джордж - като g1,g2,…,gng_1,g_2,\ldots,g_n. ПолагамеM=max⁡1≤i≤n∣xi∣,M=\max_{1\le i\le n}|x_i|,S=∣x1+x2+⋯+xn∣,N=max⁡{M,S}.\qquad S=|x_1+x_2+\cdots+x_n|,\qquad N=\max\{M,S\}.Ще използваме трите оценкиD≥S,D≥M2,G≤N.D\ge S,\qquad D\ge\frac M2,\qquad G\le N.Първата е очевидна, защото последната частична сума във всяка подредба е общата сума. За втората избираме индекс ii с ∣di∣=M|d_i|=M; тогаваM=∣di∣≤∣d1+⋯+di∣+∣d1+⋯+di−1∣≤2D,M=|d_i|\le |d_1+\cdots+d_i|+|d_1+\cdots+d_{i-1}|\le2D,като при i=1i=1 втората частична сума се разбира като 00. Остава да докажем G≤NG\le N. Некаhi=g1+g2+⋯+gi.h_i=g_1+g_2+\cdots+g_i.Ще докажем по индукция, че ∣hi∣≤N|h_i|\le N за всяко ii. За i=1i=1 това следва от ∣g1∣≤M≤N|g_1|\le M\le N, а за i=ni=n имаме ∣hn∣=S≤N|h_n|=S\le N. Нека ∣hi−1∣≤N|h_{i-1}|\le N. Ако всички оставащи числа gi,gi+1,…,gng_i,g_{i+1},\ldots,g_n са с един и същи знак, то частичните суми от hi−1h_{i-1} до hnh_n се движат монотонно, следователно∣hi∣≤max⁡{∣hi−1∣,∣hn∣}≤N.|h_i|\le\max\{|h_{i-1}|,|h_n|\}\le N.Ако сред оставащите числа има и положително, и отрицателно, избираме j≥ij\ge i така, че hi−1gj≤0h_{i-1}g_j\le0. Понеже Джордж избира gig_i алчно,∣hi∣=∣hi−1+gi∣≤∣hi−1+gj∣≤|h_i|=|h_{i-1}+g_i|\le |h_{i-1}+g_j|\lemax⁡{∣hi−1∣,∣gj∣}≤N.\max\{|h_{i-1}|,|g_j|\}\le N.Индукцията е доказана. НакраяG≤N=max⁡{M,S}≤max⁡{2D,D}=2D,G\le N=\max\{M,S\}\le\max\{2D,D\}=2D,така че най-малката възможна константа е 22.
Отвори задачатаMathNetISL 2014 A3Условие — източник

Задача A4

Пълен запис
Условие
Да се определят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за коитоf(f(m)+n)+f(m)=f(n)+f(3m)+2014f(f(m)+n)+f(m)=f(n)+f(3m)+2014за всички цели числа mm и nn.
РешениеОтговорът е единствената функцияf(n)=2n+1007.f(n)=2n+1007.Лесно се проверява, че тя наистина удовлетворява уравнението. Нека C=1007C=1007 и нека ff е произволно решение. Дефинирамеg(m)=f(3m)−f(m)+2C.g(m)=f(3m)-f(m)+2C.Тогава уравнението ставаf(f(m)+n)=g(m)+f(n)(1)f(f(m)+n)=g(m)+f(n)\tag{1}за всички цели m,nm,n. Чрез индукция в двете посоки по tt получавамеf(tf(m)+n)=tg(m)+f(n)(2)f(tf(m)+n)=tg(m)+f(n)\tag{2}за всички m,n,t∈Zm,n,t\in\mathbb Z. Прилагаме (2) за тройките (r,0,f(0))(r,0,f(0)) и (0,0,f(r))(0,0,f(r)). Получавамеf(0)g(r)=f(f(r)f(0))−f(0)=f(r)g(0).f(0)g(r)=f(f(r)f(0))-f(0)=f(r)g(0).Ако f(0)=0f(0)=0, понеже g(0)=2C≠0g(0)=2C\ne0, следва f(r)=0f(r)=0 за всяко rr, което противоречи на първоначалното уравнение. Значи f(0)≠0f(0)\ne0 и съществува ненулева константаα=g(0)f(0)\alpha=\frac{g(0)}{f(0)}такава, чеg(r)=αf(r)(3)g(r)=\alpha f(r)\tag{3}за всяко rr. От дефиницията на gg и (3) следваf(3m)−β=(1+α)(f(m)−β),β=2Cα.f(3m)-\beta=(1+\alpha)(f(m)-\beta),\qquad \beta=\frac{2C}{\alpha}.Следователно за всяко k≥0k\ge0 имамеf(3km)−β=(1+α)k(f(m)−β).(4)f(3^k m)-\beta=(1+\alpha)^k(f(m)-\beta).\tag{4}Понеже 3∤20143\nmid2014, не е възможно всички стойности на ff да се делят на 33: иначе първоначалното уравнение би дало противоречие по модул 33. Избираме стойност d=f(a)d=f(a), която не се дели на 33. От (2) и (3) получавамеf(n+td)=f(n)+αtd(5)f(n+td)=f(n)+\alpha td\tag{5}за всички n,t∈Zn,t\in\mathbb Z. Избираме положително цяло число kk, за което d∣3k−1d\mid 3^k-1. Тогава от (5) с n=mn=m и t=(3k−1)m/dt=(3^k-1)m/d имамеf(3km)=f(m)+α(3k−1)m.f(3^k m)=f(m)+\alpha(3^k-1)m.Сравнявайки това с (4), получаваме((1+α)k−1)(f(m)−β)=α(3k−1)m.\big((1+\alpha)^k-1\big)(f(m)-\beta)=\alpha(3^k-1)m.Коефициентът ((1+α)k−1)((1+\alpha)^k-1) не може да е нула, защото дясната страна не е нула при m≠0m\ne0. Следователно ff е линейна функция:f(m)=Am+βf(m)=Am+\betaза някое рационално число AA. Замяната в началното уравнение дава за всяко mm(A2−2A)m+(Aβ−2C)=0.(A^2-2A)m+(A\beta-2C)=0.ЗначиA2=2A,Aβ=2C.A^2=2A,\qquad A\beta=2C.Понеже C≠0C\ne0, имаме A≠0A\ne0, следователно A=2A=2 и β=C=1007\beta=C=1007. Така f(n)=2n+1007f(n)=2n+1007, както трябваше да се докаже.
Отвори задачатаMathNetISL 2014 A4Условие — източник

Задача A5

Пълен запис
Условие
Разглеждаме всички полиноми P(x)P(x) с реални коефициенти, които имат следното свойство: за всеки две реални числа xx и yy е изпълнено∣y2−P(x)∣≤2∣x∣|y^2-P(x)|\le2|x|\qquadтогава и само тогава, когато\text{тогава и само тогава, когато}\qquad∣x2−P(y)∣≤2∣y∣. |x^2-P(y)|\le2|y|.Да се определят всички възможни стойности на P(0)P(0).
РешениеОтговорът еP(0)∈(−∞,0)∪{1}.P(0)\in(-\infty,0)\cup\{1\}.Първо ще покажем, че всички тези стойности се достигат. Ако C>0C\gt{}0, полиномътP(x)=−(2x2C+C)P(x)=-\left(\frac{2x^2}{C}+C\right)има P(0)=−CP(0)=-C и за всички реални x,yx,y е изпълнено∣y2−P(x)∣=y2+x2C+(∣x∣−C)2C+2∣x∣>2∣x∣.|y^2-P(x)|=y^2+\frac{x^2}{C}+\frac{(|x|-C)^2}{C}+2|x|\gt{}2|x|.Следователно и двете твърдения в условието са винаги неверни, така че еквивалентността е изпълнена. Стойността P(0)=1P(0)=1 се получава от P(x)=x2+1P(x)=x^2+1. Наистина,∣y2−P(x)∣≤2∣x∣  ⟺  (y2−x2−1)2≤4x2  ⟺  0≤((x+y)2−1)(1−(x−y)2),\begin{aligned} |y^2-P(x)|\le2|x| &\iff (y^2-x^2-1)^2\le4x^2\\ &\iff 0\le\big((x+y)^2-1\big)\big(1-(x-y)^2\big), \end{aligned}а последното условие е симетрично относно xx и yy. Остава да докажем, че ако P(0)≥0P(0)\ge0, тогава непременно P(x)=x2+1P(x)=x^2+1. От дадената еквивалентност имаме∣y2−P(x)∣≤2∣x∣  ⟺  ∣y2−P(−x)∣≤2∣x∣|y^2-P(x)|\le2|x|\iff |y^2-P(-x)|\le2|x|за всички реални x,yx,y. Понеже y2y^2 пробягва всички неотрицателни реални числа, получаваме[P(x)−2∣x∣,P(x)+2∣x∣]∩R≥0=[P(x)-2|x|,P(x)+2|x|]\cap\mathbb R_{\ge0}=[P(−x)−2∣x∣,P(−x)+2∣x∣]∩R≥0.[P(-x)-2|x|,P(-x)+2|x|]\cap\mathbb R_{\ge0}.Има безкрайно много xx, за които P(x)+2∣x∣≥0P(x)+2|x|\ge0; например това е вярно за безкрайно много достатъчно малки xx от едната страна на нулата. За тези xx горните две отсечки имат еднакъв десен край, следователно P(x)=P(−x)P(x)=P(-x). Значи полиномът P(x)−P(−x)P(x)-P(-x) има безкрайно много корени и PP е четен. Ще покажем, че P(t)>0P(t)\gt{}0 за всяко реално tt. Ако t≠0t\ne0 и P(t)=0P(t)=0, то по непрекъснатост за всички yy в малък интервал около tt ще имаме ∣P(y)∣≤2∣y∣|P(y)|\le2|y|. При x=0x=0 условието би дало y2=P(0)y^2=P(0) за всички тези yy, което е невъзможно. Значи P(t)≠0P(t)\ne0 за t≠0t\ne0. Ако оставаше P(0)=0P(0)=0, от четността щяхме да имаме P(x)=x2Q(x)P(x)=x^2Q(x); при x=0x=0 и произволно y≠0y\ne0 условието би налагало ∣yQ(y)∣>2|yQ(y)|\gt{}2, което е невъзможно за достатъчно малко yy. Следователно P(t)>0P(t)\gt{}0 за всяко tt. Полиномът PP не може да е константа: ако P(x)=P(0)P(x)=P(0), при x=x2P(0)x=\sqrt{\vphantom{x^2}P(0)} и достатъчно голямо yy двете страни на еквивалентността имат различни стойности. Значи степента на PP е четно число поне 22, а водещият коефициент е положителен. Ако степента е n≥4n\ge4, вземаме y=x2P(x)y=\sqrt{\vphantom{x^2}P(x)}. Тогава лявото неравенство е вярно и следователноP(x2P(x))≤x2+2x2P(x).P(\sqrt{\vphantom{x^2}P(x)})\le x^2+2\sqrt{\vphantom{x^2}P(x)}.Но при x→+∞x\to+\infty лявата страна расте като положителна константа по xn2/2x^{n^2/2}, а дясната е O(xn/2)O(x^{n/2}), противоречие. Следователно PP е квадратичен. Пишем P(x)=ax2+bP(x)=ax^2+b, където a>0a\gt{}0. За достатъчно голямо положително xx и y=a xy=\sqrt a\,x лявото неравенство е изпълнено, затова∣(1−a2)x2−b∣≤2a x.|(1-a^2)x^2-b|\le2\sqrt a\,x.Това е възможно за безкрайно много големи xx само ако a=1a=1. Значи P(x)=x2+bP(x)=x^2+b. Сега заместваме y=x+1y=x+1, x>0x\gt{}0. Получаваме∣2x+1−b∣≤2x  ⟺  ∣2x+1+b∣≤2x+2.|2x+1-b|\le2x\iff |2x+1+b|\le2x+2.За достатъчно голямо xx лявото условие е еквивалентно на b≥1b\ge1, а дясното - на b≤1b\le1. Следователно b=1b=1. Значи при P(0)≥0P(0)\ge0 единствената възможност е P(0)=1P(0)=1, и отговорът е доказан.
Отвори задачатаMathNetISL 2014 A5Условие — източник

Задача A6

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb Z\to\mathbb Z, за коитоn2+4f(n)=f(f(n))2n^2+4f(n)=f(f(n))^2за всяко n∈Zn\in\mathbb Z.
РешениеОтговорът е следният. Работят точно функциитеf(n)=n+1(n∈Z),f(n)=n+1\qquad(n\in\mathbb Z),както и, за всяко цяло a≥1a\ge1,f(n)={n+1,n>−a,1−n,n≤−a,f(n)=\begin{cases}n+1,&n\gt{}-a,\\1-n,&n\le -a, \end{cases}и още функциятаf(n)={n+1,n>0,0,n=0,1−n,n<0.f(n)=\begin{cases}n+1,&n\gt{}0,\\0,&n=0,\\1-n,&n\lt{}0. \end{cases}Проверката е пряка. В клон f(n)=n+1f(n)=n+1 имамеn2+4f(n)=n2+4n+4=(n+2)2=f(n+1)2.n^2+4f(n)=n^2+4n+4=(n+2)^2=f(n+1)^2.В клон f(n)=1−nf(n)=1-n стойността 1−n1-n попада в линейния клон, така чеn2+4f(n)=n2+4−4n=(2−n)2=f(1−n)2.n^2+4f(n)=n^2+4-4n=(2-n)^2=f(1-n)^2.В третата функция случаят n=0n=0 също дава 0=00=0. Остава да докажем, че други решения няма. Първо ще докажем, чеf(n)=n+1за всяко n>0.(1)f(n)=n+1\qquad\text{за всяко }n\gt{}0.\tag{1}Нека ak=fk(1)a_k=f^k(1) за k≥0k\ge0. От уравнението, приложено за n=akn=a_k, следваak+22=ak2+4ak+1.(2)a_{k+2}^2=a_k^2+4a_{k+1}.\tag{2}Понеже a0=1a_0=1 и a22=1+4a1a_2^2=1+4a_1 е нечетен квадрат, пишем a2=2r+1a_2=2r+1. Тогава a1=r2+ra_1=r^2+r, аa32=(r2+r)2+8r+4.a_3^2=(r^2+r)^2+8r+4.Сравнение с най-близките четни квадрати дава ∣r∣<4|r|\lt{}4, а пряка проверка на тези крайно много стойности оставя самоr=−3,r=0,r=1.r=-3,\quad r=0,\quad r=1.Ако r=−3r=-3, тогава a1=6a_1=6, a2=−5a_2=-5 и последователното използване на (2) даваa3=−4,a4=−3,a5=−2,a_3=-4, a_4=-3, a_5=-2,a6=−1,a7=0,a8=1,a9=2, a_6=-1, a_7=0, a_8=1, a_9=2,което противоречи на f(1)=a1=6f(1)=a_1=6 и f(1)=f(a8)=a9=2f(1)=f(a_8)=a_9=2. Ако r=0r=0, тогава a1=0a_1=0, a2=1a_2=1 и a3=±2a_3=\pm2, което отново противоречи на еднозначността на f(1)f(1). Остава r=1r=1, т.е. a1=2a_1=2 и a2=3a_2=3. Ще докажем с индукция, че ak=k+1a_k=k+1 за всички k≥0k\ge0. Ако ak−1=ka_{k-1}=k и ak=k+1a_k=k+1, то от (2) имаме ak+1=±(k+2)a_{k+1}=\pm(k+2). Ако ak+1=−(k+2)a_{k+1}=-(k+2), тогаваak+22=(k+1)2−4k−8=(k−1)2−8.a_{k+2}^2=(k+1)^2-4k-8=(k-1)^2-8.Две квадратни числа могат да се различават с 88 само като 11 и 99, откъдето би следвало k=4k=4; но тогава следващата стъпка дава a72=32a_7^2=32 или a72=40a_7^2=40, невъзможно. Значи ak+1=k+2a_{k+1}=k+2, и индукцията е завършена. От an−1=na_{n-1}=n и an=n+1a_n=n+1 следва (1). Сега разглеждаме f(0)f(0). От уравнението при n=0n=0 получаваме4f(0)=f(f(0))2,4f(0)=f(f(0))^2,така че f(0)≥0f(0)\ge0. Ако f(0)=0f(0)=0, то никое ненулево цяло число не може да има образ 00, защото иначе от уравнението би следвало n2=0n^2=0. Ако f(0)>0f(0)\gt{}0, то по (1) имаме f(f(0))=f(0)+1f(f(0))=f(0)+1, следователно4f(0)=(f(0)+1)2,4f(0)=(f(0)+1)^2,и f(0)=1f(0)=1. Значи или f(0)=1f(0)=1, или f(0)=0f(0)=0 и 00 няма ненулев прообраз.\tag{3} Ще докажем лема. За всяко n≥1n\ge1 е вярноf(−n)=1−nилиf(−n)=n+1.f(-n)=1-n\qquad\text{или}\qquad f(-n)=n+1.Освен това, ако f(−n)=1−nf(-n)=1-n за някое n≥2n\ge2, то f(−n+1)=2−nf(-n+1)=2-n. Доказваме лемата с пълна индукция по nn. При n=1n=1 от1+4f(−1)=f(f(−1))21+4f(-1)=f(f(-1))^2следва f(−1)≥0f(-1)\ge0. Ако f(−1)=0f(-1)=0, това е първата възможност. Ако f(−1)>0f(-1)\gt{}0, по (1) имаме f(f(−1))=f(−1)+1f(f(-1))=f(-1)+1, откъдето 1+4f(−1)=(f(−1)+1)21+4f(-1)=(f(-1)+1)^2 и f(−1)=2f(-1)=2. Нека n≥2n\ge2 и лемата е доказана за по-малки положителни числа. Пишем b=f(−n)b=f(-n). Ако b≤−nb\le -n, тогаваf(b)2=n2+4b≤n2−4n<(n−2)2,f(b)^2=n^2+4b\le n^2-4n\lt{}(n-2)^2,така че ∣f(b)∣≤n−3|f(b)|\le n-3. Ако f(b)f(b) е неотрицателно, от (1) и (3) следва f(f(b))=f(b)+1f(f(b))=f(b)+1; ако е отрицателно, прилагаме индукционното предположение към f(b)f(b) и пак получавамеf(f(b))=±f(b)+1.f(f(b))=\pm f(b)+1.Прилагайки уравнението за bb, намирамеb2+4f(b)=f(f(b))2=(±f(b)+1)2.b^2+4f(b)=f(f(b))^2=(\pm f(b)+1)^2.Понеже ∣b∣≥n|b|\ge n и ∣f(b)∣≤n−3|f(b)|\le n-3, това даваn2≤b2≤f(b)2+6∣f(b)∣+1≤n^2\le b^2\le f(b)^2+6|f(b)|+1\le(n−3)2+6(n−3)+1=n2−8,(n-3)^2+6(n-3)+1=n^2-8,противоречие. Следователно b>−nb\gt{}-n. При b>−nb\gt{}-n от (1), (3) и индукционното предположение отново имаме f(b)=±b+1f(b)=\pm b+1. Затоваn2+4b=(±b+1)2.n^2+4b=(\pm b+1)^2.Ако знакът е плюс, получаваме n2=(b−1)2n^2=(b-1)^2, т.е. b=1−nb=1-n или b=n+1b=n+1. Ако знакът е минус, получавамеn2=(b−3)2−8,n^2=(b-3)^2-8,което е възможно само при вече разгледания случай n=1n=1. Така първата част на лемата е доказана. Ако сега f(−n)=1−nf(-n)=1-n за n≥2n\ge2, тоf(−n+1)2=f(f(−n))2=n2+4(1−n)=(n−2)2.f(-n+1)^2=f(f(-n))^2=n^2+4(1-n)=(n-2)^2.Първата част на лемата, приложена към n−1n-1, казва, че f(−n+1)f(-n+1) е или 2−n2-n, или nn; от последното равенство остава само 2−n2-n. Лемата е доказана. От (1) и лемата описанието вече е принудително. Ако f(n)=n+1f(n)=n+1 за всички цели nn, получаваме първата функция. Иначе има най-голямо цяло число m≤0m\le0, за което f(m)≠m+1f(m)\ne m+1. Лемата показва, че за всички n<mn\lt{}m трябва да е f(n)=1−nf(n)=1-n. Ако m=−a<0m=-a\lt{}0, получаваме второто семейство с a≥1a\ge1. Ако m=0m=0, то по (3) трябва да е f(0)=0f(0)=0, а лемата дава f(n)=1−nf(n)=1-n за n<0n\lt{}0 и f(n)=n+1f(n)=n+1 за n>0n\gt{}0, което е третата функция. Това изчерпва всички решения.
Отвори задачатаMathNetISL 2014 A6Условие — източник

Задача C1

Пълен запис
Условие
Дадени са nn точки във вътрешността на правоъгълник RR, като никои две от тях не лежат на права, успоредна на страна на RR. Правоъгълникът RR трябва да се разреже на по-малки правоъгълници със страни, успоредни на страните на RR, така че нито един от тези правоъгълници да не съдържа някоя от дадените точки във вътрешността си. Докажете, че са нужни поне n+1n+1 малки правоъгълника.
РешениеНека kk е броят на малките правоъгълници. Разглеждаме всички точки, които са върхове на някой от малките правоъгълници, и ги разделяме на три групи: - AA са четирите върха на първоначалния правоъгълник RR; всеки от тях е връх на точно един малък правоъгълник; - BB са точките, в които точно два малки правоъгълника имат общ връх; - CC са точките, в които точно четири малки правоъгълника имат общ връх. Нека ∣B∣=b|B|=b и ∣C∣=c|C|=c. Понеже всеки от kk-те малки правоъгълника има четири върха, броенето на върховете с кратности дава4k=4+2b+4c.4k=4+2b+4c.Следователно b≤2k−2b\le2k-2. Всяка от дадените nn точки лежи върху страна на някой малък правоъгълник, но не върху страна на RR. Продължаваме тази страна по границите между малките правоъгълници колкото е възможно в двете посоки. Получаваме отсечка, чиито два края са точки от BB. Освен това една точка от BB може да бъде край на най-много една такава отсечка, съдържаща дадена точка; иначе две от дадените точки биха лежали на една права, успоредна на страна на RR. Значи b≥2nb\ge2n. Комбинирайки двете оценки, получаваме2k−2≥b≥2n,2k-2\ge b\ge2n,откъдето k≥n+1k\ge n+1. Това доказва твърдението.
Отвори задачатаMathNetISL 2014 C1Условие — източник

Задача C2

Пълен запис
Условие
Имаме 2m2^m листа хартия, като на всеки е записано числото 11. Извършваме следната операция. На всяка стъпка избираме два различни листа; ако числата върху тях са aa и bb, изтриваме тези числа и записваме числото a+ba+b върху двата листа. Докажете, че след m2m−1m2^{m-1} стъпки сумата на числата върху всички листа е поне 4m4^m.
РешениеНека PkP_k е произведението на числата върху листовете след kk стъпки. Да предположим, че на следващата стъпка числата aa и bb се заменят с a+ba+b. В произведението множителят abab се заменя с (a+b)2(a+b)^2, а останалите множители не се променят. Понеже(a+b)2≥4ab,(a+b)^2\ge4ab,получаваме Pk+1≥4PkP_{k+1}\ge4P_k. Първоначално P0=1P_0=1, следователно по индукцияPk≥4kP_k\ge4^kза всяко k≥0k\ge0. В частност след m2m−1m2^{m-1} стъпки имамеPm2m−1≥4m2m−1=(2m)2m.P_{m2^{m-1}}\ge4^{m2^{m-1}}=(2^m)^{2^m}.Върху листовете има общо 2m2^m положителни числа. По неравенството между средно аритметично и средно геометрично тяхната сума е поне2mx2Pm2m−12m≥2m⋅2m=4m.2^m\sqrt[2^m]{\vphantom{x^2}P_{m2^{m-1}}}\ge2^m\cdot2^m=4^m.Това е исканото.
Отвори задачатаMathNetISL 2014 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. Разглеждаме шахматна дъска n×nn\times n, разделена на n2n^2 единични квадратчета. Ще наричаме една конфигурация от nn топа върху тази дъска щастлива, ако във всеки ред и във всяка колона има точно един топ. Да се намери най-голямото положително цяло число kk, такова че за всяка щастлива конфигурация на топовете може да се намери квадрат k×kk\times k, в чиито k2k^2 единични квадратчета няма топ.
РешениеОтговорът е⌊x2n−1⌋.\left\lfloor\sqrt{\vphantom{x^2}n-1}\right\rfloor.Нека ℓ\ell е положително цяло число. Ще докажем две твърдения: (i) ако n>ℓ2n\gt{}\ell^2, всяка щастлива конфигурация съдържа празен квадрат ℓ×ℓ\ell\times\ell; (ii) ако n≤ℓ2n\le\ell^2, съществува щастлива конфигурация без празен квадрат ℓ×ℓ\ell\times\ell. Тези две твърдения дават точно посочения отговор. Първо нека n>ℓ2n\gt{}\ell^2. Вземаме ред RR, в който топът е в най-лявото поле измежду всички топове. Избираме ℓ\ell последователни реда, един от които е RR; тяхното обединение UU съдържа точно ℓ\ell топа. Премахваме от UU най-левите n−ℓ2n-\ell^2 колони. Понеже n−ℓ2≥1n-\ell^2\ge1, така премахваме и топа от реда RR. Останалата част е правоъгълник с размери ℓ×ℓ2\ell\times\ell^2, който се разделя на ℓ\ell квадрата ℓ×ℓ\ell\times\ell, а в него има най-много ℓ−1\ell-1 топа. Следователно един от тези квадрати е празен. Сега нека n≤ℓ2n\le\ell^2. Първо построяваме щастлива конфигурация без празен квадрат ℓ×ℓ\ell\times\ell за случая n=ℓ2n=\ell^2. Номерираме редовете отдолу нагоре и колоните отляво надясно с 0,1,…,ℓ2−10,1,\ldots,\ell^2-1. Поставяме топове в квадратчетата(iℓ+j, jℓ+i),0≤i,j≤ℓ−1.(i\ell+j,\ j\ell+i),\qquad 0\le i,j\le\ell-1.Всяко число от 00 до ℓ2−1\ell^2-1 има единствен вид iℓ+ji\ell+j, затова във всеки ред и във всяка колона има точно един топ. Ще покажем, че всеки квадрат ℓ×ℓ\ell\times\ell съдържа топ. Вземаме произволни ℓ\ell последователни реда, започващи с ред номер pℓ+qp\ell+q, където 0≤p,q≤ℓ−10\le p,q\le\ell-1. Колоните на топовете в тези редове, подредени нарастващо, саp+1, ℓ+p+1, …, (q−1)ℓ+p+1,p+1,\ \ell+p+1,\ \ldots,\ (q-1)\ell+p+1, qℓ+p, (q+1)ℓ+p, …, (ℓ−1)ℓ+p,\ q\ell+p,\ (q+1)\ell+p,\ \ldots,\ (\ell-1)\ell+p,като празните части от списъка се пропускат. Първото число в този списък е най-много ℓ−1\ell-1, последното е поне (ℓ−1)ℓ(\ell-1)\ell, а разликата между две съседни числа е най-много ℓ\ell. Затова всеки блок от ℓ\ell последователни колони пресича този списък, т.е. съответният квадрат ℓ×ℓ\ell\times\ell съдържа топ. Ако n<ℓ2n\lt{}\ell^2, започваме от построената конфигурация върху дъската ℓ2×ℓ2\ell^2\times\ell^2 и премахваме ℓ2−n\ell^2-n най-долни реда заедно с ℓ2−n\ell^2-n най-десни колони. Остава разположение без празен квадрат ℓ×ℓ\ell\times\ell, макар някои редове и колони да може да са празни. Броят на празните редове е равен на броя на празните колони, така че слагаме по един топ в пресечните им квадратчета според произволна биекция между тях. Получаваме щастлива конфигурация и добавянето на топове не може да създаде празен квадрат ℓ×ℓ\ell\times\ell. Това доказва и (ii).
Отвори задачатаMathNetISL 2014 C3Условие — източник

Задача C5

Пълен запис
Условие
Дадени са n≥3n\ge3 прави в равнината, като никои две не са успоредни и никои три не минават през една точка. Тези прави разделят равнината на многоъгълни области; нека F\mathcal F е множеството от областите с крайно лице. Докажете, че е възможно да се оцветят ⌈x2n/2⌉\left\lceil\sqrt{\vphantom{x^2}n/2}\right\rceil от правите в синьо така, че никоя област от F\mathcal F да няма изцяло синя граница. Тук ⌈x⌉\lceil x\rceil означава най-малкото цяло число, което не е по-малко от xx.
РешениеНека LL е множеството от дадените прави. Избираме по включване максимално множество B⊆LB\subseteq L със свойството, че ако правите от BB се оцветят в синьо, никоя област от F\mathcal F няма изцяло синя граница. Нека ∣B∣=k|B|=k. Ще докажем, чеk≥⌈x2n/2⌉.k\ge\left\lceil\sqrt{\vphantom{x^2}n/2}\right\rceil.Оцветяваме всички прави от L∖BL\setminus B в червено. Ще наричаме една пресечна точка синя, ако е пресечна точка на две сини прави. Такива точки има (k2)\binom k2. Да разгледаме произволна червена права ℓ\ell. Поради максималността на BB, ако добавим ℓ\ell към сините прави, ще се появи област A∈FA\in\mathcal F с изцяло синя граница. Преди добавянето единствената червена страна на тази област е лежала върху ℓ\ell. Понеже AA има поне три страни, тя има поне един син връх. Избираме един такъв син връх и го съпоставяме на правата ℓ\ell. Всяка синя пресечна точка е връх на четири области, някои от които може да са неограничени, следователно може да бъде съпоставена на най-много четири червени прави. Затова броят на червените прави е най-много4(k2)=2k(k−1).4\binom k2=2k(k-1).От друга страна, този брой е n−kn-k. Значиn−k≤2k(k−1),n-k\le2k(k-1),откъдетоn≤2k2−k≤2k2.n\le2k^2-k\le2k^2.Следователно k≥x2n/2k\ge\sqrt{\vphantom{x^2}n/2}, а понеже kk е цяло число, получаваме k≥⌈x2n/2⌉k\ge\left\lceil\sqrt{\vphantom{x^2}n/2}\right\rceil. Избраните kk сини прави съдържат поне толкова прави, така че можем да оставим сини само ⌈x2n/2⌉\left\lceil\sqrt{\vphantom{x^2}n/2}\right\rceil от тях; това не може да създаде изцяло синя граница.
Отвори задачатаMathNetISL 2014 C5Условие — източник

Задача C6

Пълен запис
Условие
Дадено е безкрайно тесте карти, като върху всяка карта е записано реално число. За всяко реално число xx в тестето има точно една карта с написано xx. Двама играчи теглят непресичащи се множества AA и BB от по 100100 карти. Искаме да дефинираме правило, което обявява един от тях за победител. Правилото трябва да удовлетворява следните условия: 1. Победителят зависи само от относителния ред на 200200-те карти: ако картите се подредят във възходящ ред с лице надолу и знаем коя карта на кой играч принадлежи, но не знаем записаните числа, пак можем да определим победителя. 2. Ако запишем елементите на двете множества във възходящ ред като A={a1,a2,…,a100}A=\{a_1,a_2,\ldots,a_{100}\} и B={b1,b2,…,b100}B=\{b_1,b_2,\ldots,b_{100}\} и ai>bia_i\gt{}b_i за всяко ii, то AA побеждава BB. 3. Ако трима играчи изтеглят три непресичащи се множества A,B,CA,B,C от тестето, AA побеждава BB и BB побеждава CC, то AA побеждава CC. По колко начина може да се дефинира такова правило? Две правила се считат за различни, ако съществуват две множества AA и BB, такива че според едното правило AA побеждава BB, а според другото BB побеждава AA.
РешениеОтговорът е 100100. Ще докажем по-общо твърдение за множества с по nn елемента; задачата е случаят n=100n=100. Ще пишем A>BA\gt{}B, ако AA побеждава BB. Първо описваме nn правила, които работят. Фиксираме индекс k∈{1,2,…,n}k\in\{1,2,\ldots,n\}. АкоA={a1<a2<⋯<an},B={b1<b2<⋯<bn},A=\{a_1\lt{}a_2\lt{}\cdots\lt{}a_n\},\qquad B=\{b_1\lt{}b_2\lt{}\cdots\lt{}b_n\},казваме, че AA побеждава BB точно когато ak>bka_k\gt{}b_k. Ясно е, че всяко от тези правила удовлетворява трите условия, а различните стойности на kk дават различни правила. Значи правилата са поне nn. Остава да докажем, че други няма. Нека е дадено правило, удовлетворяващо условията. За k=1,2,…,nk=1,2,\ldots,n дефинирамеAk={1,2,…,k,n+k+1,n+k+2,…,2n},A_k=\{1,2,\ldots,k,n+k+1,n+k+2,\ldots,2n\},Bk={k+1,k+2,…,n+k}.B_k=\{k+1,k+2,\ldots,n+k\}.Съществува kk, за което Bk>AkB_k\gt{}A_k: например за k=nk=n всеки елемент на BnB_n е по-голям от съответния елемент на AnA_n. Избираме най-малкото такова kk. Ще докажем, че за всеки две непресичащи се множестваX={x1<x2<⋯<xn},Y={y1<y2<⋯<yn}X=\{x_1\lt{}x_2\lt{}\cdots\lt{}x_n\},\qquad Y=\{y_1\lt{}y_2\lt{}\cdots\lt{}y_n\}от условието xk<ykx_k\lt{}y_k следва Y>XY\gt{}X. Избираме реални числа ui,vi,wiu_i,v_i,w_i, които не принадлежат на X∪YX\cup Y, така чеu1<u2<⋯<uk−1<min⁡(x1,y1),u_1\lt{}u_2\lt{}\cdots\lt{}u_{k-1}\lt{}\min(x_1,y_1),max⁡(xn,yn)<vk+1<vk+2<⋯<vn,\max(x_n,y_n)\lt{}v_{k+1}\lt{}v_{k+2}\lt{}\cdots\lt{}v_n,иxk<v1<⋯<vk<w1<⋯<wn<uk<⋯<un<yk.x_k\lt{}v_1\lt{}\cdots\lt{}v_k\lt{}w_1\lt{}\cdots\lt{}w_n\lt{}u_k\lt{}\cdots\lt{}u_n\lt{}y_k.ПолагамеU={u1,u2,…,un},V={v1,v2,…,vn},U=\{u_1,u_2,\ldots,u_n\},\quad V=\{v_1,v_2,\ldots,v_n\},W={w1,w2,…,wn}.\quad W=\{w_1,w_2,\ldots,w_n\}.От второто условие за правилото имаме Y>UY\gt{}U и V>XV\gt{}X, защото ui<yiu_i\lt{}y_i и xi<vix_i\lt{}v_i за всички ii. По минималността на kk множествата Ak−1A_{k-1} и Bk−1B_{k-1} са в обратния ред; същият относителен ред имат UU и WW, така че U>WU\gt{}W (при k=1k=1 това следва директно от второто условие). От избора на kk и от относителния ред на VV и WW получаваме W>VW\gt{}V. СледователноY>U>W>V>X.Y\gt{}U\gt{}W\gt{}V\gt{}X.По транзитивността от третото условие следва Y>XY\gt{}X. Ако xk>ykx_k\gt{}y_k, със същия аргумент при разменени XX и YY получаваме X>YX\gt{}Y. Значи победителят между произволни две множества се определя само от сравнението на техните kk-ти най-малки елементи. Това е точно едно от вече описаните nn правила. При n=100n=100 получаваме 100100 възможни правила.
Отвори задачатаMathNetISL 2014 C6Условие — източник

Задача C7

Пълен запис
Условие
Нека MM е множество от n≥4n\ge4 точки в равнината, никои три от които не са колинеарни. Първоначално тези точки са свързани с nn отсечки така, че всяка точка от MM е край на точно две отсечки. След това на всяка стъпка можем да изберем две отсечки ABAB и CDCD, които имат обща вътрешна точка, и да ги заменим с отсечките ACAC и BDBD, ако нито една от тях не присъства в този момент. Докажете, че е невъзможно да се направят n3/4n^3/4 или повече такива хода.
РешениеЩе наричаме една права червена, ако съдържа две точки от MM. Понеже никои три точки от MM не са колинеарни, всяка червена права се определя от единствена двойка точки от MM, а броят на червените прави е(n2)<n22.\binom n2\lt{}\frac{n^2}2.Стойност на една отсечка ще наричаме броя на червените прави, които я пресичат във вътрешна точка. Стойността на множество от отсечки е сумата от стойностите им. Ще докажем две неща: (i) началната стойност е по-малка от n3/2n^3/2; (ii) всеки ход намалява стойността поне с 22. От тях твърдението следва веднага, защото стойността никога не е отрицателна. За (i) е достатъчно да отбележим, че стойността на всяка отсечка е по-малка от n2/2n^2/2, а начално има nn отсечки. Остава да докажем (ii). Нека отсечките ABAB и CDCD се пресичат във вътрешна точка SS и ги заменяме с ACAC и BDBD. За отсечка UVUV означаваме с XUVX_{UV} множеството от червените прави, които пресичат UVUV във вътрешна точка. Ще докажем∣XAC∣+∣XBD∣+2≤∣XAB∣+∣XCD∣.(1)|X_{AC}|+|X_{BD}|+2\le |X_{AB}|+|X_{CD}|.\tag{1}Първо имаме∣XAC∪XBD∣+2≤∣XAB∪XCD∣.(2)|X_{AC}\cup X_{BD}|+2\le |X_{AB}\cup X_{CD}|.\tag{2}Наистина, ако червена права пресича например ACAC във вътрешна точка, то при влизане и излизане от триъгълника ACSACS тя трябва да пресече още една от страните ASAS, CSCS или да мине през SS; във всички случаи тя принадлежи на XAB∪XCDX_{AB}\cup X_{CD}. Същото важи за права, която пресича BDBD. Освен това правите ABAB и CDCD самите принадлежат на XAB∪XCDX_{AB}\cup X_{CD}, но не принадлежат на XAC∪XBDX_{AC}\cup X_{BD}, което дава допълнителните 22. Второ,∣XAC∩XBD∣≤∣XAB∩XCD∣.(3)|X_{AC}\cap X_{BD}|\le |X_{AB}\cap X_{CD}|.\tag{3}Ако червена права пресича и ACAC, и BDBD, тогава по същото разглеждане на четирите малки триъгълника около SS тя пресича и ABAB, и CDCD; случаят, когато правата минава през SS, също е непосредствен. Като съберем (2) и (3) и използваме тъждеството ∣P∣+∣Q∣=∣P∪Q∣+∣P∩Q∣|P|+|Q|=|P\cup Q|+|P\cap Q|, получаваме (1). Следователно стойността намалява поне с 22 при всяка стъпка. Началната стойност е под n3/2n^3/2, така че броят на стъпките е по-малък от n3/4n^3/4.
Отвори задачатаMathNetISL 2014 C7Условие — източник

Задача C8

Пълен запис
Условие
Тесте съдържа 10241024 карти. Върху всяка карта е записано множество от различни десетични цифри, като никои две от тези множества не съвпадат; следователно една от картите е празна. Двама играчи се редуват да вземат карти от тестето, по една карта на ход. След като тестето се изчерпи, всеки играч проверява дали може да изхвърли една от своите карти така, че всяка от десетте цифри да се среща върху четен брой от останалите му карти. Ако един играч може да направи това, а другият не може, победител е този, който може; иначе се обявява равенство. Определете всички възможни първи ходове на първия играч, след които той има печеливша стратегия.
РешениеОтговорът е: всички ходове освен вземането на празната карта. Ще отъждествяваме всяка карта с множеството от цифрите, записани върху нея. За карти C1,C2,…,CkC_1,C_2,\ldots,C_k ще наричаме тяхна сума симетричната разликаC1△C2△⋯△Ck,C_1\triangle C_2\triangle\cdots\triangle C_k,тоест множеството от цифрите, които се срещат в нечетен брой от тези карти. Нека първият и вторият играч са съответно F\mathcal F и S\mathcal S. Всяка цифра се среща върху точно 512512 карти, така че сумата на всички карти е ∅\varnothing. Следователно в края на играта сумата на картите на F\mathcal F е същата като сумата на картите на S\mathcal S; нека тази обща сума е CC. Играчът, който притежава картата CC, може да я изхвърли и да получи четни бройки за всички цифри. Другият играч не може да направи това, защото би трябвало да изхвърли точно картата CC, а тя е у първия. Значи печели играчът, който е взел картата CC, и равенство не може да има. Ще използваме следната лема. Нека B≠∅B\ne\varnothing е карта. Разделяме всички карти на двойки (X,X△B)(X,X\triangle B). Ако изберем точно по една карта от всяка двойка, сумата на избраните карти е или ∅\varnothing, или BB. Доказателство на лемата. Избираме цифра b∈Bb\in B. Във всяка двойка означаваме с XiX_i картата, която не съдържа bb, а с YiY_i другата карта. Картите XiX_i са точно всички множества от цифри, които не съдържат bb. В тях всяка друга цифра се среща точно 256256 пъти, а bb не се среща нито веднъж. Следователно сумата на всички XiX_i е ∅\varnothing. Ако заменим някои от XiX_i със съответните Yi=Xi△BY_i=X_i\triangle B, към сумата добавяме BB толкова пъти, колкото замени сме направили. Затова крайната сума е ∅\varnothing или BB. Лемата е доказана. Първи случай: F\mathcal F взема празната карта на първия си ход. Ще дадем печеливша стратегия за S\mathcal S. Нека S\mathcal S вземе произволна карта AA. Ако след това F\mathcal F вземе карта BB, то S\mathcal S взема A△BA\triangle B. Разделяме картите на двойки (X,X△B)(X,X\triangle B). Дотук F\mathcal F е взел двойката (∅,B)(\varnothing,B), а S\mathcal S - двойката (A,A△B)(A,A\triangle B). Оттук нататък, когато F\mathcal F вземе карта, S\mathcal S взема нейния партньор от същата двойка. В края мислено заменяме картата AA на S\mathcal S с ∅\varnothing. Тогава S\mathcal S има точно по една карта от всяка двойка, следователно по лемата сумата е ∅\varnothing или BB. Като върнем AA, действителната сума на картите на S\mathcal S е AA или A△BA\triangle B, а и двете карти са у него. Значи S\mathcal S печели. Втори случай: F\mathcal F първо взема непразна карта AA. Ще дадем печеливша стратегия за F\mathcal F. Ако S\mathcal S първо вземе непразна карта BB, то F\mathcal F взема A△BA\triangle B. Разделяме картите на двойки (X,X△B)(X,X\triangle B). Останалите невзети карти се състоят от няколко цели двойки и един допълнителен елемент, първоначално ∅\varnothing. Оттук нататък, ако S\mathcal S вземе карта от цяла двойка, F\mathcal F взема партньора и. Ако S\mathcal S вземе допълнителния елемент, F\mathcal F взема произволна карта YY, а партньорът на YY става новият допълнителен елемент. На последния си ход S\mathcal S е принуден да вземе допълнителния елемент. Тогава F\mathcal F има картите AA и A△BA\triangle B, играчът S\mathcal S има BB и ∅\varnothing, а F\mathcal F има точно по една карта от всяка друга двойка. Както в първия случай, сумата на картите на F\mathcal F е AA или A△BA\triangle B, и двете са у него. Значи F\mathcal F печели. Ако първият отговор на S\mathcal S е празната карта, тогава F\mathcal F избира произволна още невзета карта BB и взема A△BA\triangle B. Същата стратегия работи с допълнителен елемент BB. Следователно точно непразните карти са печеливши първи ходове за първия играч.
Отвори задачатаMathNetISL 2014 C8Условие — източник

Задача C9

Пълен запис
Условие
Върху лист хартия са начертани nn окръжности така, че всеки две от тях се пресичат в две точки и никои три не минават през една точка. Охлювът Турбо се плъзга по окръжностите по следния начин. Първоначално той се движи по една от окръжностите по часовниковата стрелка. Турбо винаги продължава по текущата окръжност, докато стигне до пресечна точка с друга окръжност. Тогава продължава пътя си по новата окръжност и сменя посоката си на движение, т.е. от по часовниковата стрелка към обратно на часовниковата стрелка или обратно. Да предположим, че пътят на Турбо покрива изцяло всички окръжности. Докажете, че nn е нечетно.
РешениеЩе докажем по-общо твърдение: във всяка конфигурация от nn окръжности без допирания броят на възможните орбити на охлюва има същата четност като nn. В задачата пътят на Турбо покрива всички окръжности, следователно има само една орбита; тогава nn трябва да е нечетно. Във всяка пресечна точка правилото на движение свързва четирите излизащи малки дъги по двойки: охлювът преминава на другата окръжност и сменя ориентацията си. Така всички дъги на окръжностите се разпадат на прости затворени криви, които ще наричаме орбити. Ще използваме операцията обръщане на пресечна точка. Нека около такава точка четирите малки дъги са a,b,c,da,b,c,d, като aa и bb лежат на едната окръжност, а cc и dd - на другата. При обръщане заменяме локалното свързване aa с cc и bb с dd със свързването aa с dd и bb с cc. Да видим как това променя броя на орбитите. Извън малка околност на пресечната точка дъгите a,b,c,da,b,c,d са свързани по двойки от останалите части на орбитите. Случаят, в който извън околността aa е свързана с bb, а cc с dd, е невъзможен: ако затворим така двете криви през пресечната точка, те се пресичат там, следователно по теоремата на Жордан едната трябва да пресече другата още веднъж, което е невъзможно за орбити. Остават два случая. Ако извън околността aa е свързана с cc, а bb с dd, обръщането слива две орбити в една. Ако aa е свързана с dd, а bb с cc, обръщането разделя една орбита на две. Значи всяко обръщане променя четността на броя орбити. Сега обръщаме всички пресечни точки една по една. Всяка двойка окръжности има 00 или 22 пресечни точки, така че общият брой обръщания е четен. Следователно четността на броя орбити след всички обръщания е същата като първоначалната. Остава да намерим четността след всички обръщания. Ориентираме всяка получена орбита така, че по всяка дъга от окръжност охлювът да се движи обратно на часовниковата стрелка по тази окръжност. Ако една орбита се обходи веднъж, общото изменение на посоката на движение е 2π2\pi или −2π-2\pi според ориентацията и като равнинна крива. Нека PP е броят на орбитите с положителна ориентация, а NN - броят на орбитите с отрицателна ориентация. Тогава общото изменение за всички орбити е(P−N)2π.(P-N)2\pi.От друга страна, можем да го преброим по окръжности. По всяка окръжност дъгите заедно дават принос 2π2\pi. Във всяка пресечна точка двата малки завоя имат равни по абсолютна стойност и противоположни знаци, така че приносите им се унищожават. Следователно общият принос е n⋅2πn\cdot2\pi. Получаваме(P−N)2π=n⋅2π,(P-N)2\pi=n\cdot2\pi,тоест P−N=nP-N=n. Броят на орбитите е P+NP+N, а P+NP+N има същата четност като P−N=nP-N=n. Това доказва общото твърдение и завършва решението.
Отвори задачатаMathNetISL 2014 C9Условие — източник

Задача N1

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число и некаAn={2n−2k∣k∈Z, 0≤k<n}.A_n=\{2^n-2^k\mid k\in\mathbb Z,\ 0\le k\lt{}n\}.Да се определи най-голямото положително цяло число, което не може да се представи като сума на един или повече, не непременно различни, елементи на AnA_n.
РешениеОтговорът е(n−2)2n+1.(n-2)2^n+1.Първо ще докажем, че всяко цяло число, по-голямо от (n−2)2n+1(n-2)2^n+1, има исканото представяне. Доказателството е с индукция по nn. При n=2n=2 имаме A2={2,3}A_2=\{2,3\} и всяко положително цяло число, различно от 11, се представя като сума от двойки и евентуално една тройка. Нека n>2n\gt{}2 и нека m>(n−2)2n+1m\gt{}(n-2)2^n+1. Ако mm е четно, тоm2≥(n−2)2n−1+1>(n−3)2n−1+1.\frac m2\ge (n-2)2^{n-1}+1\gt{}(n-3)2^{n-1}+1.По индукционното предположение m/2m/2 е сума от числа 2n−1−2k2^{n-1}-2^k с 0≤k<n−10\le k\lt{}n-1. Умножавайки тази сума по 22, получаваме представяне на mm чрез числа 2n−2k+12^n-2^{k+1} от AnA_n. Ако mm е нечетно, тогаваm−(2n−1)2>(n−3)2n−1+1.\frac{m-(2^n-1)}2\gt{}(n-3)2^{n-1}+1.Отново по индукция това число е сума от елементи на An−1A_{n-1}, а след умножаване по 22 и добавяне на 2n−12^n-1 получаваме представяне на mm чрез елементи на AnA_n. Остава да докажем, че (n−2)2n+1(n-2)2^n+1 не се представя. Нека NN е най-малкото положително цяло число, за коетоN≡1(mod2n)N\equiv1\pmod{2^n}и което се представя като сума от елементи на AnA_n. НекаN=(2n−2k1)+(2n−2k2)+⋯+(2n−2kr),N=(2^n-2^{k_1})+(2^n-2^{k_2})+\cdots+(2^n-2^{k_r}),0≤ki<n.\qquad 0\le k_i\lt{}n.Ако две от числата kik_i са равни, да кажем на kk, то можем да заменим съответните два члена. При k=n−1k=n-1 просто ги махаме, а при k<n−1k\lt{}n-1 ги заменяме с един член 2n−2k+12^n-2^{k+1}. И в двата случая получаваме представяне на N−2nN-2^n, което противоречи на минималността на NN. Следователно всички kik_i са различни. Тогава2k1+2k2+⋯+2kr≤1+2+⋯+2n−1=2n−1.2^{k_1}+2^{k_2}+\cdots+2^{k_r}\le 1+2+\cdots+2^{n-1}=2^n-1.От друга страна, сравнявайки представянето по модул 2n2^n, получаваме2k1+2k2+⋯+2kr≡−N≡−1(mod2n).2^{k_1}+2^{k_2}+\cdots+2^{k_r}\equiv -N\equiv -1\pmod{2^n}.Значи сумата е точно 2n−12^n-1, което е възможно само когато участват всички степени 20,21,…,2n−12^0,2^1,\ldots,2^{n-1}. СледователноN=n2n−(2n−1)=(n−1)2n+1.N=n2^n-(2^n-1)=(n-1)2^n+1.В частност всяко представимо число, сравнимо с 11 по модул 2n2^n, е поне (n−1)2n+1(n-1)2^n+1. Затова (n−2)2n+1(n-2)2^n+1 не е представимо, а от първата част то е най-голямото такова число.
Отвори задачатаMathNetISL 2014 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се определят всички двойки (x,y)(x,y) от положителни цели числа, за коитоx27x2−13xy+7y23=∣x−y∣+1.\sqrt[3]{\vphantom{x^2}7x^2-13xy+7y^2}=|x-y|+1.
РешениеОтговорът е(x,y)=(1,1)(x,y)=(1,1)или{x,y}={m3+m2−2m−1, m3+2m2−m−1}\{x,y\}=\{m^3+m^2-2m-1,\ m^3+2m^2-m-1\}за някое цяло число m≥2m\ge2. Ако x=yx=y, уравнението става x2x23=1\sqrt[3]{\vphantom{x^2}x^2}=1, откъдето x=y=1x=y=1. Нека вече x≠yx\ne y. Поради симетрия можем да приемем, че x>yx\gt{}y, и полагаме n=x−y>0n=x-y\gt{}0. Тогава след повдигане на трета степен получаваме7(y+n)2−13(y+n)y+7y2=(n+1)3,7(y+n)^2-13(y+n)y+7y^2=(n+1)^3,тоестy2+ny=n3−4n2+3n+1.y^2+ny=n^3-4n^2+3n+1.Умножаваме по 44 и допълваме до квадрат:(2y+n)2=4n3−15n2+12n+4=(n−2)2(4n+1).(2y+n)^2=4n^3-15n^2+12n+4=(n-2)^2(4n+1).Случаите n=1n=1 и n=2n=2 са невъзможни, затова n>2n\gt{}2. Следователно 4n+14n+1 е квадрат на рационално число, а значи е точен квадрат. Понеже е нечетно, съществува цяло m≥0m\ge0, за което4n+1=(2m+1)2,4n+1=(2m+1)^2,т.е. n=m2+mn=m^2+m. От n>2n\gt{}2 следва m≥2m\ge2. Замествайки n=m2+mn=m^2+m в горното равенство, намираме(2y+m2+m)2=(m2+m−2)2(2m+1)2=(2y+m^2+m)^2=(m^2+m-2)^2(2m+1)^2=(2m3+3m2−3m−2)2.(2m^3+3m^2-3m-2)^2.Тъй като 2m3+3m2−3m−2=(m−1)(2m2+5m+2)>02m^3+3m^2-3m-2=(m-1)(2m^2+5m+2)\gt{}0, получаваме2y+m2+m=2m3+3m2−3m−2,2y+m^2+m=2m^3+3m^2-3m-2,откъдетоy=m3+m2−2m−1.y=m^3+m^2-2m-1.Тогаваx=y+n=m3+2m2−m−1.x=y+n=m^3+2m^2-m-1.За m≥2m\ge2 тези числа са положителни. Обратната проверка се получава чрез същите равенства в обратен ред, така че всички посочени двойки наистина са решения.
Отвори задачатаMathNetISL 2014 N2Условие — източник

Задача N3

Пълен запис
Условие
Ще наричаме една монета монета от Кейптаун, ако стойността и е 1/n1/n за някое положително цяло число nn. Дадена е колекция от монети от Кейптаун с обща стойност най-много 99+1299+\frac12. Докажете, че тази колекция може да се раздели на най-много 100100 групи, всяка с обща стойност най-много 11.
РешениеЩе докажем по-общото твърдение: за всяко положително цяло число NN всяка колекция от такива монети с обща стойност най-много N−12N-\frac12 може да се раздели на NN групи, всяка със стойност най-много 11. Задачата е случаят N=100N=100. Първо извършваме следното опростяване. Ако няколко монети имат обща стойност от вида 1/k1/k, можем да ги слеем в една монета със стойност 1/k1/k. Ако след това новата колекция може да се раздели както трябва, то може и старата. Понеже броят монети намалява, след краен брой такива сливания стигаме до колекция, в която повече сливане не е възможно. В такава колекция за всяко четно kk има най-много една монета със стойност 1/k1/k, защото две такива монети биха дали стойност 1/(k/2)1/(k/2). За всяко нечетно k>1k\gt{}1 има най-много k−1k-1 монети със стойност 1/k1/k, защото kk такива монети биха дали стойност 11. Монетите със стойност 11 могат да се поставят всяка в отделна група; ако са dd, ги махаме и заменяме NN с N−dN-d. Затова можем да приемем, че няма монети със стойност 11. За k=1,2,…,Nk=1,2,\ldots,N поставяме в групата GkG_k всички монети със стойности 1/(2k−1)1/(2k-1) и 1/(2k)1/(2k). Общата стойност в GkG_k е най-много(2k−2)⋅12k−1+12k<1.(2k-2)\cdot\frac1{2k-1}+\frac1{2k}\lt{}1.Остават само монети със стойност по-малка от 1/(2N)1/(2N). Добавяме ги една по една. Във всеки момент общата стойност на вече поставените монети е най-много N−12N-\frac12, следователно някоя от NN-те групи има стойност най-много1N(N−12)=1−12N.\frac1N\left(N-\frac12\right)=1-\frac1{2N}.В тази група можем да поставим следващата останала монета, понеже стойността и е по-малка от 1/(2N)1/(2N). Така всички монети се разпределят в най-много NN групи със стойност най-много 11.
Отвори задачатаMathNetISL 2014 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека n>1n\gt{}1 е дадено цяло число. Докажете, че безкрайно много членове на редицата (ak)k≥1(a_k)_{k\ge1}, зададена сak=⌊nkk⌋,a_k=\left\lfloor\frac{n^k}{k}\right\rfloor,са нечетни. Тук ⌊x⌋\lfloor x\rfloor означава най-голямото цяло число, което не надминава xx.
РешениеАко nn е нечетно, вземаме k=nmk=n^m за m=1,2,…m=1,2,\ldots. Тогаваak=nnmnm=nnm−m,a_k=\frac{n^{n^m}}{n^m}=n^{n^m-m},което е нечетно. Нека занапред nn е четно, n=2tn=2t. За всяко m≥2m\ge2 числотоn2m−2m=2m(22m−mt2m−1)n^{2^m}-2^m=2^m(2^{2^m-m}t^{2^m}-1)има нечетен прост делител pp, защото 2m−m>12^m-m\gt{}1. Полагамеk=p⋅2m.k=p\cdot2^m.От избора на pp имаме n2m≡2m(modp)n^{2^m}\equiv2^m\pmod p, а по малката теорема на Ферма(2m)p≡2m(modp).(2^m)^p\equiv2^m\pmod p.Следователноnk=(n2m)p≡2m(modp).n^k=(n^{2^m})^p\equiv2^m\pmod p.Понеже 2m∣nk2^m\mid n^k и 0<2m<k0\lt{}2^m\lt{}k, остатъкът на nkn^k при деление на k=p2mk=p2^m е точно 2m2^m. Затоваak=⌊nkk⌋=nk−2mp2m=nk/2m−1p.a_k=\left\lfloor\frac{n^k}{k}\right\rfloor=\frac{n^k-2^m}{p2^m}=\frac{n^k/2^m-1}{p}.Числото nk/2mn^k/2^m е четно, понеже k>mk\gt{}m, така че nk/2m−1n^k/2^m-1 е нечетно; делението на нечетното просто pp оставя нечетно частно. Значи aka_k е нечетно. За различни mm получаваме различни kk, тъй като точната степен на 22, която дели kk, е 2m2^m. Следователно има безкрайно много нечетни членове.
Отвори задачатаMathNetISL 2014 N4Условие — източник

Задача N5

Пълен запис
Условие
Да се намерят всички тройки (p,x,y)(p,x,y), съставени от просто число pp и две положителни цели числа xx и yy, за които xp−1+yx^{p-1}+y и x+yp−1x+y^{p-1} са степени на pp.
РешениеОтговорът е(p,x,y)=(3,2,5),(3,5,2),(p,x,y)=(3,2,5),\quad (3,5,2),както и всички тройки(2,n,2k−n),k≥1,0<n<2k.(2,n,2^k-n),\qquad k\ge1,\quad 0\lt{}n\lt{}2^k.При p=2p=2 условието означава само, че x+yx+y е степен на 22, което дава точно посоченото семейство. Нека вече pp е нечетно. Пишемxp−1+y=pa,x+yp−1=pbx^{p-1}+y=p^a,\qquad x+y^{p-1}=p^bс положителни цели a,ba,b. Поради симетрия можем да приемем, че x≤yx\le y, откъдето a≤ba\le b. Ще използваме стандартния факт за повдигане на показателя: ако pp е нечетно просто, p∣u+vp\mid u+v, p∤uvp\nmid uv и rr е нечетно положително цяло число, тоvp(ur+vr)=vp(u+v)+vp(r).v_p(u^r+v^r)=v_p(u+v)+v_p(r).Отpb=yp−1+x=(pa−xp−1)p−1+xp^b=y^{p-1}+x=(p^a-x^{p-1})^{p-1}+xи от четността на p−1p-1 получаваме по модул pap^a0≡x(p−1)2+x=x(xp(p−2)+1).0\equiv x^{(p-1)^2}+x=x(x^{p(p-2)}+1).Ако p∣xp\mid x, вторият множител не се дели на pp, следователно pa∣xp^a\mid x, което е невъзможно, понеже x<pax\lt{}p^a. Значи p∤xp\nmid x иpa∣xp(p−2)+1.p^a\mid x^{p(p-2)}+1.По малката теорема на Ферма от последното сравнение следва x≡−1(modp)x\equiv-1\pmod p. Нека prp^r е точната степен на pp, която дели x+1x+1. От горния факт, приложен към xp(p−2)+1x^{p(p-2)}+1, получавамеvp(xp(p−2)+1)=r+1,v_p(x^{p(p-2)}+1)=r+1,така че a≤r+1a\le r+1. От друга странаpr≤x+1≤xp−1+y=pa,p^r\le x+1\le x^{p-1}+y=p^a,следователно r≤ar\le a. Значи a=ra=r или a=r+1a=r+1. Ако a=ra=r, тогава x+1=pa=xp−1+yx+1=p^a=x^{p-1}+y. Това налага x=y=1x=y=1, което не е възможно за нечетно pp. Следователно a=r+1a=r+1. Тогаваx=x2+xx+1≤xp−1+yx+1=pax+1≤papr=p.x=\frac{x^2+x}{x+1}\le\frac{x^{p-1}+y}{x+1}=\frac{p^a}{x+1}\le\frac{p^a}{p^r}=p.Понеже p∣x+1p\mid x+1, от 1≤x≤p1\le x\le p следва x=p−1x=p-1. Тогава r=1r=1 и a=2a=2. Ако p≥5p\ge5, получаваме противоречие:p2=pa=xp−1+y>(p−1)4>p2.p^2=p^a=x^{p-1}+y\gt{}(p-1)^4\gt{}p^2.Значи p=3p=3, x=2x=2 иy=pa−xp−1=9−4=5.y=p^a-x^{p-1}=9-4=5.По симетрия получаваме и (3,5,2)(3,5,2). Пряката проверка показва, че тези две тройки наистина работят.
Отвори задачатаMathNetISL 2014 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека a1<a2<⋯<ana_1\lt{}a_2\lt{}\cdots\lt{}a_n са две по две взаимнопрости положителни цели числа, като a1a_1 е просто число и a1≥n+2a_1\ge n+2. Върху отсечката I=[0,a1a2⋯an]I=[0,a_1a_2\cdots a_n] от реалната права са отбелязани всички цели числа, които се делят поне на едно от числата a1,…,ana_1,\ldots,a_n. Тези точки разделят II на по-малки отсечки. Докажете, че сумата от квадратите на дължините на тези отсечки се дели на a1a_1.
РешениеНекаA=a1a2⋯an.A=a_1a_2\cdots a_n.Всички отсечки по-долу имат цели краища и положителна дължина. Нека SS е семейството от отсечки [x,y][x,y], чиито краища са две съседни отбелязани точки. Нека TT е семейството от отсечки [x,y][x,y], за които x<yx\lt{}y са цели числа, 0≤x≤A−10\le x\le A-1, и в отворения интервал (x,y)(x,y) няма отбелязана точка. На отсечка Y∈TY\in T даваме тегло w(∣Y∣)w(|Y|), къдетоw(1)=1,w(k)=2(k≥2).w(1)=1,\qquad w(k)=2\quad(k\ge2).Ако X∈SX\in S има дължина LL, то подотсечките на XX, които принадлежат на TT, са: една с дължина LL, две с дължина L−1L-1, и така нататък. Следователно сумата на теглата им еL+2((L−1)+(L−2)+⋯+1)=L2.L+2((L-1)+(L-2)+\cdots+1)=L^2.Понеже всяка отсечка от TT лежи в точно една отсечка от SS, получаваме∑X∈S∣X∣2=∑Y∈Tw(∣Y∣).(1)\sum_{X\in S}|X|^2=\sum_{Y\in T}w(|Y|).\tag{1}Ще преброим отсечките от TT с дадена дължина dd. Достатъчно е да разглеждаме 1≤d≤a11\le d\le a_1, защото всички кратни на a1a_1 са отбелязани. За фиксирано xx с 0≤x≤A−10\le x\le A-1 нека rir_i е остатъкът на xx по модул aia_i. По китайската теорема за остатъците числото xx се определя еднозначно от (r1,…,rn)(r_1,\ldots,r_n). Условието (x,x+d)(x,x+d) да не съдържа кратно на aia_i е еквивалентно наri+d≤ai,r_i+d\le a_i,т.е. има ai−d+1a_i-d+1 възможности за rir_i. Затова броят на отсечките от TT с дължина dd еf(d)=(a1+1−d)(a2+1−d)⋯(an+1−d).f(d)=(a_1+1-d)(a_2+1-d)\cdots(a_n+1-d).От (1) следва∑X∈S∣X∣2=2∑d=1a1f(d)−f(1).(2)\sum_{X\in S}|X|^2=2\sum_{d=1}^{a_1}f(d)-f(1).\tag{2}Ще използваме лемата: ако pp е просто число, F(x)F(x) е полином с цели коефициенти и deg⁡F≤p−2\deg F\le p-2, то∑x=1pF(x)≡0(modp).\sum_{x=1}^{p}F(x)\equiv0\pmod p.Достатъчно е тя да се докаже за F(x)=xkF(x)=x^k, 0≤k≤p−20\le k\le p-2. За k=0k=0 е ясно. За 1≤k≤p−21\le k\le p-2 телескопичната сума∑x=1p(xk+1−(x−1)k+1)=pk+1\sum_{x=1}^{p}(x^{k+1}-(x-1)^{k+1})=p^{k+1}след разкриване по бинома и използване на вече доказаните по-ниски степени дава(k+1)∑x=1pxk≡0(modp),(k+1)\sum_{x=1}^{p}x^k\equiv0\pmod p,а p∤k+1p\nmid k+1. Прилагаме лемата за простото число a1a_1 и полинома ff. Имаме deg⁡f=n≤a1−2\deg f=n\le a_1-2, така че∑d=1a1f(d)≡0(moda1).\sum_{d=1}^{a_1}f(d)\equiv0\pmod{a_1}.Освен това f(1)=a1a2⋯anf(1)=a_1a_2\cdots a_n също се дели на a1a_1. От (2) следва, че∑X∈S∣X∣2\sum_{X\in S}|X|^2се дели на a1a_1, както трябваше.
Отвори задачатаMathNetISL 2014 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека c≥1c\ge1 е цяло число. Редицата от положителни цели числа е зададена с a1=ca_1=c иan+1=an3−4c⋅an2+5c2⋅an+ca_{n+1}=a_n^3-4c\cdot a_n^2+5c^2\cdot a_n+cза всяко n≥1n\ge1. Докажете, че за всяко цяло число n≥2n\ge2 съществува просто число pp, което дели ana_n, но не дели никое от числата a1,…,an−1a_1,\ldots,a_{n-1}.
РешениеПолагаме x0=0x_0=0 и xn=an/cx_n=a_n/c за n≥1n\ge1. Тогава x1=1x_1=1 иxn+1=c2(xn3−4xn2+5xn)+1(1)x_{n+1}=c^2(x_n^3-4x_n^2+5x_n)+1\tag{1}за всички n≥0n\ge0. Всички xnx_n са положителни цели числа за n≥1n\ge1, аxn+1=c2xn(xn−2)2+c2xn+1>xn,x_{n+1}=c^2x_n(x_n-2)^2+c^2x_n+1\gt{}x_n,така че редицата е строго растяща. Освен това всяко xn+1x_{n+1} е взаимнопросто с cc. Затова е достатъчно да докажем, че за всяко n≥2n\ge2 числото xnx_n има прост делител, който не дели нито едно от x1,…,xn−1x_1,\ldots,x_{n-1}. Ще използваме три твърдения. 1. Ако i≡j(modm)i\equiv j\pmod m, където i,j≥0i,j\ge0 и m≥1m\ge1, тоxi≡xj(modxm).x_i\equiv x_j\pmod{x_m}.Достатъчно е да се докаже xi+m≡xi(modxm)x_{i+m}\equiv x_i\pmod{x_m} с индукция по ii. За i=0i=0 е ясно, а индукционната стъпка следва направо от рекурентната формула (1). 2. Ако i≡j(modm)i\equiv j\pmod m, където i,j≥2i,j\ge2 и m≥1m\ge1, тоxi≡xj(modxm2).x_i\equiv x_j\pmod{x_m^2}.Отново е достатъчно да се докаже xi+m≡xi(modxm2)x_{i+m}\equiv x_i\pmod{x_m^2} с индукция по ii. Стъпката следва от (1). За началото i=2i=2 полагаме L=5c2L=5c^2. От (1) имаме xm+1≡Lxm+1(modxm2)x_{m+1}\equiv Lx_m+1\pmod{x_m^2}, откъдетоxm+13−4xm+12+5xm+1≡2(modxm2).x_{m+1}^3-4x_{m+1}^2+5x_{m+1}\equiv2\pmod{x_m^2}.Следователно xm+2≡2c2+1=x2(modxm2)x_{m+2}\equiv2c^2+1=x_2\pmod{x_m^2}. 3. За всяко n≥2n\ge2 е вярноxn>x1x2⋯xn−2.x_n\gt{}x_1x_2\cdots x_{n-2}.За n=2,3n=2,3 това е ясно. Ако твърдението е вярно за някое n≥3n\ge3, то x2=2c2+1≥3x_2=2c^2+1\ge3 и по монотонност xn≥x3≥7x_n\ge x_3\ge7. Затоваxn+1>xn3−4xn2+5xn>x_{n+1}\gt{}x_n^3-4x_n^2+5x_n\gt{}7xn2−4xn2>xn2>xnxn−1,7x_n^2-4x_n^2\gt{}x_n^2\gt{}x_nx_{n-1},а заедно с индукционното предположение това дава твърдението за n+1n+1. Фиксираме n≥2n\ge2. По твърдение 3 съществува просто число pp, което участва в разлагането на xnx_n с по-голям показател, отколкото в произведението x1x2⋯xn−2x_1x_2\cdots x_{n-2}. Ще докажем, че pp не дели никое от предишните xix_i. Да допуснем противното и нека kk е най-малкият индекс с 1≤k<n1\le k\lt{}n, за който p∣xkp\mid x_k. Понеже x1=1x_1=1 и xn−1x_{n-1} е взаимнопросто с xnx_n по (1), имаме 2≤k≤n−22\le k\le n-2. Некаn=qk+r,0≤r<k.n=qk+r,\qquad 0\le r\lt{}k.От твърдение 1 следва xn≡xr(modxk)x_n\equiv x_r\pmod{x_k}, следователно p∣xrp\mid x_r. Минималността на kk налага r=0r=0, т.е. k∣nk\mid n. Тогава от твърдение 2 получавамеxn≡xk(modxk2).x_n\equiv x_k\pmod{x_k^2}.Нека α≥1\alpha\ge1 е точният показател, за който pα∣xkp^\alpha\mid x_k. По избора на pp числото xnx_n се дели на pα+1p^{\alpha+1}, а xk2x_k^2 също се дели на pα+1p^{\alpha+1}. Последното сравнение тогава показва, че xkx_k се дели на pα+1p^{\alpha+1}, противоречие. Следователно избраното pp е нов прост делител на xnx_n, а понеже всички xix_i са взаимнопрости с cc, същото pp е нов прост делител и на ana_n.
Отвори задачатаMathNetISL 2014 N7Условие — източник

Задача N8

Пълен запис
Условие
За всяко реално число xx нека ∥x∥\lVert x\rVert означава разстоянието от xx до най-близкото цяло число. Докажете, че за всяка двойка (a,b)(a,b) от положителни цели числа съществуват нечетно просто число pp и положително цяло число kk, за които∥apk∥+∥bpk∥+∥a+bpk∥=1.\left\lVert\frac a{p^k}\right\rVert+\left\lVert\frac b{p^k}\right\rVert+\left\lVert\frac{a+b}{p^k}\right\rVert=1.
РешениеЗа всяко реално xx числото ⌊x+12⌋\left\lfloor x+\frac12\right\rfloor е най-близко цяло до xx, така че⌊x+12⌋=x±∥x∥.(1)\left\lfloor x+\frac12\right\rfloor=x\pm\lVert x\rVert.\tag{1}За рационално число rr и просто число pp означаваме с vp(r)v_p(r) показателя на pp в разлагането на rr. Нека(2n−1)!≠1⋅3⋅5⋯(2n−1).(2n-1)!\neq{}1\cdot3\cdot5\cdots(2n-1).Ще използваме лематаvp((2n−1)!!)=∑j≥1⌊npj+12⌋(2)v_p((2n-1)!!)=\sum_{j\ge1}\left\lfloor\frac n{p^j}+\frac12\right\rfloor\tag{2}за всяко положително цяло nn и всяко нечетно просто pp. Наистина, за фиксирано jj кратните на pjp^j измежду 1,3,…,2n−11,3,\ldots,2n-1 са числата (2ℓ−1)pj(2\ell-1)p^j. Условието0<(2ℓ−1)pj≤2n0\lt{}(2\ell-1)p^j\le2nе еквивалентно на1≤ℓ≤npj+12,1\le \ell\le \frac n{p^j}+\frac12,така че броят им е точно членът в сумата (2). Сумирането по всички jj дава лемата. Разглеждаме рационалното числоN=(2a+2b−1)!!(2a−1)!!(2b−1)!!=N=\frac{(2a+2b-1)!!}{(2a-1)!!(2b-1)!!}=(2a+1)(2a+3)⋯(2a+2b−1)1⋅3⋯(2b−1).\frac{(2a+1)(2a+3)\cdots(2a+2b-1)}{1\cdot3\cdots(2b-1)}.То е по-голямо от 11, следователно съществува прост делител pp с vp(N)>0v_p(N)\gt{}0. Тъй като NN е частно на нечетни числа, pp е нечетно. От лемата получаваме0<0\lt{}vp(N)=v_p(N)=∑j≥1(⌊a+bpj+12⌋−⌊apj+12⌋−⌊bpj+12⌋).\sum_{j\ge1}\left(\left\lfloor\frac{a+b}{p^j}+\frac12\right\rfloor-\left\lfloor\frac a{p^j}+\frac12\right\rfloor-\left\lfloor\frac b{p^j}+\frac12\right\rfloor\right).Затова за някое положително цяло kk числотоd=d=⌊a+bpk+12⌋\left\lfloor\frac{a+b}{p^k}+\frac12\right\rfloor−⌊apk+12⌋−⌊bpk+12⌋-\left\lfloor\frac a{p^k}+\frac12\right\rfloor-\left\lfloor\frac b{p^k}+\frac12\right\rfloorе положително. Прилагаме (1) към трите дроби. Обикновените дробни части се съкращават и получаваме1≤d=±∥a+bpk∥±∥apk∥±∥bpk∥.1\le d=\pm\left\lVert\frac{a+b}{p^k}\right\rVert\pm\left\lVert\frac a{p^k}\right\rVert\pm\left\lVert\frac b{p^k}\right\rVert.Понеже знаменателят pkp^k е нечетен, всяко от трите разстояния е строго по-малко от 1/21/2. Ако поне един знак е минус, дясната страна е по-малка от 11; следователно всички знаци са плюс. Тогава дясната страна е по-малка от 3/23/2, а е положително цяло число, така че d=1d=1. Следователно∥apk∥+∥bpk∥+∥a+bpk∥=1,\left\lVert\frac a{p^k}\right\rVert+\left\lVert\frac b{p^k}\right\rVert+\left\lVert\frac{a+b}{p^k}\right\rVert=1,както трябваше.
Отвори задачатаMathNetISL 2014 N8Условие — източник