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

IMO Shortlisted Problems

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

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

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

2013

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

11-12

19 задачи

Задача A1

Пълен запис
Условие
Нека nn е положително цяло число и нека a1,…,an−1a_1,\ldots,a_{n-1} са произволни реални числа. Дефинираме редиците u0,…,unu_0,\ldots,u_n и v0,…,vnv_0,\ldots,v_n рекурентно чрез u0=u1=v0=v1=1u_0=u_1=v_0=v_1=1 иuk+1=uk+akuk−1,u_{k+1}=u_k+a_ku_{k-1},vk+1=vk+an−kvk−1(k=1,…,n−1).\qquad v_{k+1}=v_k+a_{n-k}v_{k-1}\qquad(k=1,\ldots,n-1).Докажете, че un=vnu_n=v_n.
РешениеЩе докажем по индукция, че за всяко kk е вярна формулатаuk=u_k=∑0<i1<⋯<it<kij+1−ij≥2ai1⋯ait.(1)\begin{aligned}\sum_{\substack{0\lt{}i_1\lt{}\cdots\lt{}i_t\lt{}k\\ i_{j+1}-i_j\ge2}}a_{i_1}\cdots a_{i_t}.\tag{1}\end{aligned}В сумата участва и празното произведение, равно на 11, което съответства на t=0t=0. За k=0,1k=0,1 дясната страна съдържа само празното произведение, така че (1) следва от u0=u1=1u_0=u_1=1. Нека сега k≥1k\ge1 и формулата е доказана до kk. От рекурентната връзка получавамеuk+1=∑0<i1<⋯<it<kij+1−ij≥2ai1⋯ait+ak∑0<i1<⋯<it<k−1ij+1−ij≥2ai1⋯ait=∑0<i1<⋯<it<k+1ij+1−ij≥2ai1⋯ait.\begin{aligned} u_{k+1}&=\sum_{\substack{0\lt{}i_1\lt{}\cdots\lt{}i_t\lt{}k\\ i_{j+1}-i_j\ge2}}a_{i_1}\cdots a_{i_t}+a_k\sum_{\substack{0\lt{}i_1\lt{}\cdots\lt{}i_t\lt{}k-1\\ i_{j+1}-i_j\ge2}}a_{i_1}\cdots a_{i_t}\\ &=\sum_{\substack{0\lt{}i_1\lt{}\cdots\lt{}i_t\lt{}k+1\\ i_{j+1}-i_j\ge2}}a_{i_1}\cdots a_{i_t}. \end{aligned}Това завършва индукцията. Прилагаме (1) към обратната редица bi=an−ib_i=a_{n-i}, 1≤i≤n−11\le i\le n-1. Получавамеvk=v_k=∑0<i1<⋯<it<kij+1−ij≥2bi1⋯bit=\begin{aligned}\sum_{\substack{0\lt{}i_1\lt{}\cdots\lt{}i_t\lt{}k\\ i_{j+1}-i_j\ge2}}b_{i_1}\cdots b_{i_t}=\end{aligned}∑n>j1>⋯>jt>n−kjs−js+1≥2aj1⋯ajt.(2)\begin{aligned}\sum_{\substack{n\gt{}j_1\gt{}\cdots\gt{}j_t\gt{}n-k\\ j_s-j_{s+1}\ge2}}a_{j_1}\cdots a_{j_t}.\tag{2}\end{aligned}За k=nk=n сумите в (1) и (2) обхождат едни и същи подмножества на {1,2,…,n−1}\{1,2,\ldots,n-1\} без съседни елементи. Следователно un=vnu_n=v_n.
Отвори задачатаMathNetISL 2013 A1Условие — източник

Задача A2

Пълен запис
Условие
Докажете, че във всяко множество от 20002000 различни реални числа съществуват две двойки a>ba\gt{}b и c>dc\gt{}d, като a≠ca\ne c или b≠db\ne d, за които∣a−bc−d−1∣<1100000.\left|\frac{a-b}{c-d}-1\right|\lt{}\frac1{100000}.
РешениеНека SS е множество от n=2000n=2000 различни реални числа. НекаD1≤D2≤⋯≤DmD_1\le D_2\le\cdots\le D_mса всички разстояния между две числа от SS, записани с кратности; тук m=n(n−1)/2m=n(n-1)/2. Чрез умножаване на всички числа с един и същи положителен коефициент можем да предполагаме, че най-малкото разстояние е D1=1D_1=1. Нека D1=y−x=1D_1=y-x=1 за x,y∈Sx,y\in S. Ясно е, че Dm=v−uD_m=v-u, където vv е най-голямото, а uu е най-малкото число в SS. Ако за някое ii имаме Di+1/Di<1+10−5D_{i+1}/D_i\lt{}1+10^{-5}, то съответните две разстояния дават търсените две двойки, защото0≤Di+1Di−1<10−5.0\le\frac{D_{i+1}}{D_i}-1\lt{}10^{-5}.Остава да разгледаме случая, когатоDi+1Di≥1+1105(i=1,2,…,m−1).\frac{D_{i+1}}{D_i}\ge1+\frac1{10^5}\qquad(i=1,2,\ldots,m-1).Тогаваv−u=Dm=DmDm−1⋯D2D1≥(1+1105)m−1.v-u=D_m=\frac{D_m}{D_{m-1}}\cdots\frac{D_2}{D_1}\ge\left(1+\frac1{10^5}\right)^{m-1}.Понежеm−1=2000⋅19992−1>19⋅105m-1=\frac{2000\cdot1999}{2}-1\gt{}19\cdot10^5и (1+1N)N≥2\left(1+\frac1N\right)^N\ge2 за всяко положително цяло число NN, получаваме(1+1105)19⋅105≥219>2⋅105.\left(1+\frac1{10^5}\right)^{19\cdot10^5}\ge2^{19}\gt{}2\cdot10^5.Следователно v−u>2⋅105v-u\gt{}2\cdot10^5. Поне едно от разстоянията от xx до uu и vv е по-голямо от 10510^5. Избираме z∈{u,v}z\in\{u,v\} така, че ∣x−z∣>105|x-z|\gt{}10^5. Тъй като y−x=1y-x=1, имаме или z>y>xz\gt{}y\gt{}x, или y>x>zy\gt{}x\gt{}z. Ако z>y>xz\gt{}y\gt{}x, вземаме a=za=z, b=yb=y, c=zc=z, d=xd=x. Тогава b≠db\ne d и∣a−bc−d−1∣=∣z−yz−x−1∣=1z−x<10−5.\left|\frac{a-b}{c-d}-1\right|=\left|\frac{z-y}{z-x}-1\right|=\frac1{z-x}\lt{}10^{-5}.Ако y>x>zy\gt{}x\gt{}z, вземаме a=ya=y, b=zb=z, c=xc=x, d=zd=z. Тогава a≠ca\ne c и∣a−bc−d−1∣=∣y−zx−z−1∣=1x−z<10−5.\left|\frac{a-b}{c-d}-1\right|=\left|\frac{y-z}{x-z}-1\right|=\frac1{x-z}\lt{}10^{-5}.И в двата случая получаваме исканото.
Отвори задачатаMathNetISL 2013 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека Q>0\mathbb Q_{\gt{}0} е множеството на положителните рационални числа. Нека f:Q>0→Rf:\mathbb Q_{\gt{}0}\to\mathbb R е функция, за коятоf(x)f(y)≥f(xy)иf(x+y)≥f(x)+f(y)f(x)f(y)\ge f(xy)\qquad\text{и}\qquad f(x+y)\ge f(x)+f(y)за всички x,y∈Q>0x,y\in\mathbb Q_{\gt{}0}. Дадено е, че f(a)=af(a)=a за някое рационално число a>1a\gt{}1. Докажете, че f(x)=xf(x)=x за всяко x∈Q>0x\in\mathbb Q_{\gt{}0}.
РешениеПоставяйки x=1x=1 и y=ay=a в първото неравенство, получаваме f(1)≥1f(1)\ge1. От второто неравенство чрез лесна индукция следва, чеf(nx)≥nf(x)(n∈Z>0, x∈Q>0).(1)f(nx)\ge n f(x)\qquad(n\in\mathbb Z_{\gt{}0},\ x\in\mathbb Q_{\gt{}0}).\tag{1}В частностf(n)≥nf(1)≥n(n∈Z>0).(2)f(n)\ge n f(1)\ge n\qquad(n\in\mathbb Z_{\gt{}0}).\tag{2}От първото неравенство, приложено към m/nm/n и nn, имамеf(mn)f(n)≥f(m),f\left(\frac mn\right)f(n)\ge f(m),така че f(q)>0f(q)\gt{}0 за всяко q∈Q>0q\in\mathbb Q_{\gt{}0}. Следователно второто неравенство показва, че ff е строго растяща: ако x>y>0x\gt{}y\gt{}0, тоf(x)=f(y+(x−y))≥f(y)+f(x−y)>f(y).f(x)=f(y+(x-y))\ge f(y)+f(x-y)\gt{}f(y).За всяко рационално x≥1x\ge1 оттук и от (2) получавамеf(x)≥f(⌊x⌋)≥⌊x⌋>x−1.(3)f(x)\ge f(\lfloor x\rfloor)\ge\lfloor x\rfloor\gt{}x-1.\tag{3}От първото неравенство чрез индукция имаме f(x)n≥f(xn)f(x)^n\ge f(x^n). Ако x>1x\gt{}1, то заради (3)f(x)n≥f(xn)>xn−1.f(x)^n\ge f(x^n)\gt{}x^n-1.Затова f(x)≥xf(x)\ge x за всяко x>1x\gt{}1: наистина, ако 1<y<x1\lt{}y\lt{}x, то за достатъчно голямо nn имаме xn−1>ynx^n-1\gt{}y^n, откъдето f(x)>yf(x)\gt{}y. От f(a)=af(a)=a и първото неравенство следваan=f(a)n≥f(an)≥an,a^n=f(a)^n\ge f(a^n)\ge a^n,тоест f(an)=anf(a^n)=a^n за всяко положително цяло число nn. Нека сега x>1x\gt{}1. Избираме nn така, че an−x>1a^n-x\gt{}1. Тогава от второто неравенство и вече доказаната оценка f(t)≥tf(t)\ge t за t>1t\gt{}1 получавамеan=f(an)≥f(x)+f(an−x)≥x+(an−x)=an.a^n=f(a^n)\ge f(x)+f(a^n-x)\ge x+(a^n-x)=a^n.Следователно навсякъде има равенство и f(x)=xf(x)=x за всяко x>1x\gt{}1. Остава 0<x≤10\lt{}x\le1. Избираме положително цяло число NN, за което Nx>1Nx\gt{}1. От първото неравенство и (1) имамеNf(x)=f(N)f(x)≥f(Nx)≥Nf(x),Nf(x)=f(N)f(x)\ge f(Nx)\ge Nf(x),следователно f(Nx)=Nf(x)f(Nx)=Nf(x). Но Nx>1Nx\gt{}1, така че f(Nx)=Nxf(Nx)=Nx, и получаваме f(x)=xf(x)=x. Доказателството е завършено.
Отвори задачатаMathNetISL 2013 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека nn е положително цяло число и нека a1,a2,…,ana_1,a_2,\ldots,a_n е редица от положителни цели числа. Продължаваме я периодично до безкрайна редица чрез an+i=aia_{n+i}=a_i за всяко i≥1i\ge1. Акоa1≤a2≤⋯≤an≤a1+na_1\le a_2\le\cdots\le a_n\le a_1+nиaai≤n+i−1(i=1,2,…,n),a_{a_i}\le n+i-1\qquad(i=1,2,\ldots,n),докажете, чеa1+a2+⋯+an≤n2.a_1+a_2+\cdots+a_n\le n^2.
РешениеПърво ще докажем, чеai≤n+i−1(i=1,2,…,n).(1)a_i\le n+i-1\qquad(i=1,2,\ldots,n).\tag{1}Да допуснем противното и нека ii е най-малкият контрапример. Отan≥an−1≥⋯≥ai≥n+ia_n\ge a_{n-1}\ge\cdots\ge a_i\ge n+iи от aai≤n+i−1a_{a_i}\le n+i-1, като използваме периодичността на редицата, следва, че aia_i не може да е сравнимо с никое от числата i,i+1,…,ni,i+1,\ldots,n по модул nn. Наистина, ако ai≡r(modn)a_i\equiv r\pmod n за някое r∈{i,i+1,…,n}r\in\{i,i+1,\ldots,n\}, тогава aai=ar≥ai≥n+ia_{a_i}=a_r\ge a_i\ge n+i, противоречие. Следователно от ai≥n+ia_i\ge n+i всъщност следва ai≥2n+1a_i\ge2n+1. Понеже ai≤an≤a1+na_i\le a_n\le a_1+n, получаваме a1≥n+1a_1\ge n+1. Тогава i=1i=1 по минималността на ii, но при i=1i=1 забранените остатъци са всички остатъци по модул nn, невъзможно. Така (1) е доказано. В частност a1≤na_1\le n. Ако an≤na_n\le n, то веднага a1+⋯+an≤n2a_1+\cdots+a_n\le n^2. Остава случаят an>na_n\gt{}n. Нека tt е числото, за коетоa1≤a2≤⋯≤at≤n<at+1≤⋯≤an,a_1\le a_2\le\cdots\le a_t\le n\lt{}a_{t+1}\le\cdots\le a_n,където 1≤t≤n−11\le t\le n-1. Понеже 1≤a1≤n1\le a_1\le n и aa1≤na_{a_1}\le n, трябва a1≤ta_1\le t; иначе aa1>na_{a_1}\gt{}n. Следователноan≤a1+n≤n+t.(2)a_n\le a_1+n\le n+t.\tag{2}За всяко положително цяло число ii нека bib_i е броят на индексите j∈{t+1,t+2,…,n}j\in\{t+1,t+2,\ldots,n\}, за които aj≥n+ia_j\ge n+i. От (2) имамеb1≥b2≥⋯≥bt≥bt+1=0.b_1\ge b_2\ge\cdots\ge b_t\ge b_{t+1}=0.Ще докажем, чеai+bi≤n(1≤i≤t).(3)a_i+b_i\le n\qquad(1\le i\le t).\tag{3}Наистина, от ai≤na_i\le n и aai≤n+i−1a_{a_i}\le n+i-1 следва, че ако aj≥n+ia_j\ge n+i, то aj>aaia_j\gt{}a_{a_i}, а понеже редицата е ненамаляваща в първия период, това налага j>aij\gt{}a_i. Значи такива индекси jj могат да лежат само сред ai+1,ai+2,…,na_i+1,a_i+2,\ldots,n, и затова bi≤n−aib_i\le n-a_i. От дефиницията на числата bib_i получавамеat+1+at+2+⋯+an≤n(n−t)+b1+b2+⋯+bt.a_{t+1}+a_{t+2}+\cdots+a_n\le n(n-t)+b_1+b_2+\cdots+b_t.Като прибавим a1+⋯+ata_1+\cdots+a_t и използваме (3), намирамеa1+a2+⋯+an≤n(n−t)+nt=n2,a_1+a_2+\cdots+a_n\le n(n-t)+nt=n^2,което трябваше да се докаже.
Отвори задачатаMathNetISL 2013 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека Z≥0\mathbb Z_{\ge0} е множеството на неотрицателните цели числа. Да се намерят всички функции f:Z≥0→Z≥0f:\mathbb Z_{\ge0}\to\mathbb Z_{\ge0}, за коитоf(f(f(n)))=f(n+1)+1f(f(f(n)))=f(n+1)+1за всяко n∈Z≥0n\in\mathbb Z_{\ge0}.
РешениеОтговорът е: точно следните две функции. Първата еf(n)=n+1(n∈Z≥0),f(n)=n+1\qquad(n\in\mathbb Z_{\ge0}),а втората еf(n)={n+1,n≡0,2(mod4),n+5,n≡1(mod4),n−3,n≡3(mod4).f(n)=\begin{cases} n+1, & n\equiv0,2\pmod4,\\ n+5, & n\equiv1\pmod4,\\ n-3, & n\equiv3\pmod4. \end{cases}Ще пишем hkh^k за kk-тата итерация на функцията hh. Поставямеg(n)=f(n)+1.g(n)=f(n)+1.Замествайки f(n)f(n) вместо nn в условието, получавамеf4(n)=f(f(n)+1)+1=g2(n).(1)f^4(n)=f(f(n)+1)+1=g^2(n).\tag{1}От друга страна, ако приложим ff към двете страни на условието и използваме (1) за n+1n+1, следваf4(n)+1=f4(n+1).(2)f^4(n)+1=f^4(n+1).\tag{2}Ако c=f4(0)=g2(0)c=f^4(0)=g^2(0), от (1) и (2) по индукция получавамеf4(n)=g2(n)=n+c(n∈Z≥0).(3)f^4(n)=g^2(n)=n+c\qquad(n\in\mathbb Z_{\ge0}).\tag{3}Тук c≥1c\ge1. От (3) веднага следва, че ff и gg са инективни: например f(m)=f(n)f(m)=f(n) влече m+c=f4(m)=f4(n)=n+cm+c=f^4(m)=f^4(n)=n+c. Също така f(n)≠nf(n)\ne n и g(n)≠ng(n)\ne n за всяко nn. Прилагайки ff и gg към (3), намирамеf(n+c)=f5(n)=f4(f(n))=f(n)+c,f(n+c)=f^5(n)=f^4(f(n))=f(n)+c,g(n+c)=g3(n)=g(n)+c.(4)g(n+c)=g^3(n)=g(n)+c.\tag{4}Следователно ff и gg запазват остатъците по модул cc, а обратната посока следва от (3):m≡n(modc)⟺f(m)≡m\equiv n\pmod c\Longleftrightarrow f(m)\equivf(n)(modc)⟺g(m)≡g(n)(modc).(5) f(n)\pmod c\Longleftrightarrow g(m)\equiv g(n)\pmod c.\tag{5}Некаδ(n)=f(n)−n=g(n)−n−1,\delta(n)=f(n)-n=g(n)-n-1,S=∑n=0c−1δ(n).\qquad S=\sum_{n=0}^{c-1}\delta(n).От (4) функцията δ\delta зависи само от остатъка по модул cc. Поради (5), множествата {fk(0),…,fk(c−1)}\{f^k(0),\ldots,f^k(c-1)\} и {gk(0),…,gk(c−1)}\{g^k(0),\ldots,g^k(c-1)\} са пълни системи от остатъци по модул cc за всяко kk. Затова телескопичноc2=∑n=0c−1(f4(n)−n)=c^2=\sum_{n=0}^{c-1}(f^4(n)-n)=∑k=03∑n=0c−1(fk+1(n)−fk(n))=4S,\sum_{k=0}^3\sum_{n=0}^{c-1}(f^{k+1}(n)-f^k(n))=4S,а същоc2=∑n=0c−1(g2(n)−n)=c^2=\sum_{n=0}^{c-1}(g^2(n)-n)=∑k=01∑n=0c−1(gk+1(n)−gk(n))=2S+2c.\sum_{k=0}^1\sum_{n=0}^{c-1}(g^{k+1}(n)-g^k(n))=2S+2c.Следователно c2=4S=2(c2−2c)c^2=4S=2(c^2-2c), откъдето c2=4cc^2=4c и понеже c≠0c\ne0, получавамеc=4.(6)c=4.\tag{6}Остава да определим стойностите на ff върху 0,1,2,30,1,2,3, защото от (4) вече знаем f(n+4)=f(n)+4f(n+4)=f(n)+4. Нека d=g(0)d=g(0). Тогава g(d)=g2(0)=4g(d)=g^2(0)=4. Ако d≥4d\ge4, то от g(n+4)=g(n)+4g(n+4)=g(n)+4 следва g(d−4)=0g(d-4)=0, невъзможно. Значи d∈{1,2,3}d\in\{1,2,3\}. При d=1d=1 имаме f(0)=0f(0)=0, а при d=3d=3 имаме g(3)=4g(3)=4, т.е. f(3)=3f(3)=3; и двете противоречат на липсата на неподвижни точки. Следователно d=2d=2, така чеf(0)=1,f(2)=3.f(0)=1,\qquad f(2)=3.Понеже g(0),g(1),g(2),g(3)g(0),g(1),g(2),g(3) дават пълна система от остатъци по модул 44, числото g(1)g(1) не може да бъде 1(mod4)1\pmod4: ако g(1)=1+4kg(1)=1+4k, то5=g2(1)=g(1+4k)=g(1)+4k=1+8k,5=g^2(1)=g(1+4k)=g(1)+4k=1+8k,което е невъзможно. Значи g(1)=3+4kg(1)=3+4k. Тогава5=g2(1)=g(3+4k)=g(3)+4k,5=g^2(1)=g(3+4k)=g(3)+4k,така че g(3)=5−4kg(3)=5-4k, откъдето k=0k=0 или k=1k=1. Получаваме съответноf(0)=1,f(1)=2,f(2)=3,f(3)=4f(0)=1, f(1)=2, f(2)=3, f(3)=4илиf(0)=1,f(1)=6,f(2)=3,f(3)=0.f(0)=1, f(1)=6, f(2)=3, f(3)=0.С f(n+4)=f(n)+4f(n+4)=f(n)+4 това дава точно двете функции, посочени в отговора. Накрая директна проверка по остатъците на nn по модул 44 показва, че и двете удовлетворяват условието.
Отвори задачатаMathNetISL 2013 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека m≠0m\ne0 е цяло число. Да се намерят всички полиноми P(x)P(x) с реални коефициенти, за които(x3−mx2+1)P(x+1)+(x3+mx2+1)P(x−1)=\left(x^3-mx^2+1\right)P(x+1)+\left(x^3+mx^2+1\right)P(x-1)=2(x3−mx+1)P(x)2\left(x^3-mx+1\right)P(x)за всяко реално число xx.
РешениеОтговорът еP(x)=tx(t∈R).P(x)=tx\qquad(t\in\mathbb R).Тези полиноми очевидно работят, затова остава да докажем, че други няма. Нулевият полином е включен при t=0t=0. Нека PP е ненулев иP(x)=anxn+⋯+a0,an≠0.P(x)=a_nx^n+\cdots+a_0,\qquad a_n\ne0.Сравнявайки коефициентите пред xn+1x^{n+1} в даденото тъждество, получавамеan(n−2m)(n−1)=0.a_n(n-2m)(n-1)=0.Следователно n=1n=1 или n=2mn=2m. Ако n=1n=1, то поради линейността на условието е достатъчно да проверим базисните полиноми xx и 11. Полиномът P(x)=xP(x)=x работи, а P(x)=1P(x)=1 не работи. Значи всички линейни решения са точно P(x)=txP(x)=tx. Да допуснем сега, че n=2mn=2m. Тогава понеже n>0n\gt{}0, имаме m>0m\gt{}0. ПолиномътxP(x+1)−(x+1)P(x)=(n−1)anxn+⋯xP(x+1)-(x+1)P(x)=(n-1)a_nx^n+\cdotsима степен nn, следователно има поне един комплексен корен rr. Ако r∉{0,−1}r\notin\{0,-1\}, полагамеk=P(r)r=P(r+1)r+1;k=\frac{P(r)}r=\frac{P(r+1)}{r+1};ако r=0r=0, полагаме k=P(1)k=P(1), а ако r=−1r=-1, полагаме k=−P(−1)k=-P(-1). НекаS(x)=P(x)−kx.S(x)=P(x)-kx.Тъй като и P(x)P(x), и kxkx удовлетворяват тъждеството, същото важи за S(x)S(x). Освен това rr и r+1r+1 са корени на SS. ЗаписвамеA(x)=x3−mx2+1,B(x)=x3+mx2+1.A(x)=x^3-mx^2+1,\qquad B(x)=x^3+mx^2+1.От тъждеството за SS следват две правила. Ако s−1s-1 и ss са корени на SS, а A(s)≠0A(s)\ne0, то s+1s+1 също е корен на SS. Ако ss и s+1s+1 са корени на SS, а B(s)≠0B(s)\ne0, то s−1s-1 също е корен на SS. Избираме максимална верига от последователни корениr−a,r−a+1,…,r,r+1,…,r+b,r-a, r-a+1,\ldots,r, r+1,\ldots,r+b,където a≥0a\ge0 и b≥1b\ge1. Максималността и двете правила показват, че r−ar-a е корен на BB, а r+br+b е корен на AA. Ако c=a+b≥1c=a+b\ge1, то r−ar-a е общ корен на B(x)B(x) и A(x+c)A(x+c). Понеже това са монични полиноми с цели коефициенти, техният най-голям общ делител над Q[x]\mathbb Q[x] е нетривиален делител на BB. Ако той беше собствен делител, кубичният полином BB щеше да има рационален корен. По теоремата за рационалните корени това може да бъде само 11 или −1-1, ноB(−1)=m>0,B(1)=m+2>0.B(-1)=m\gt{}0,\qquad B(1)=m+2\gt{}0.Следователно общият делител не е собствен и трябва да имамеB(x)=A(x+c).B(x)=A(x+c).Но тогава0=A(x+c)−B(x)=0=A(x+c)-B(x)=(3c−2m)x2+c(3c−2m)x+c2(c−m).(3c-2m)x^2+c(3c-2m)x+c^2(c-m).Следователно 3c−2m=03c-2m=0 и c−m=0c-m=0, което дава m=0m=0 - противоречие. Значи случаят n=2mn=2m е невъзможен. Остават само линейните решения P(x)=txP(x)=tx, както твърдяхме.
Отвори задачатаMathNetISL 2013 A6Условие — източник

Задача C1

Пълен запис
Условие
Нека nn е положително цяло число. Да се намери най-малкото цяло число kk със следното свойство: за всякакви реални числа a1,…,ada_1,\ldots,a_d, за коитоa1+a2+⋯+ad=nиa_1+a_2+\cdots+a_d=n\qquad\text{и}\qquad0≤ai≤1(i=1,2,…,d), 0\le a_i\le1\quad(i=1,2,\ldots,d),можем да разделим тези числа на kk групи, някои от които може да са празни, така че сумата на числата във всяка група да е най-много 11.
РешениеОтговорът е k=2n−1k=2n-1. Първо ще покажем, че по-малко групи не стигат. Ако d=2n−1d=2n-1 иa1=a2=⋯=a2n−1=n2n−1,a_1=a_2=\cdots=a_{2n-1}=\frac{n}{2n-1},то всяка група може да съдържа най-много едно число, понеже2n2n−1>1.\frac{2n}{2n-1}\gt{}1.Следователно са нужни поне 2n−12n-1 групи. Остава да докажем, че 2n−12n-1 групи винаги стигат. Ще направим индукция по dd. Ако d≤2n−1d\le2n-1, твърдението е очевидно: поставяме всяко число в отделна група, а останалите групи оставяме празни. Нека d≥2nd\ge2n. От(a1+a2)+(a3+a4)+⋯+(a2n−1+a2n)≤(a_1+a_2)+(a_3+a_4)+\cdots+(a_{2n-1}+a_{2n})\lea1+a2+⋯+ad=n a_1+a_2+\cdots+a_d=nследва, че поне една от двойките (a2j−1,a2j)(a_{2j-1},a_{2j}) има сума най-много 11. Обединяваме тази двойка, например aia_i и ai+1a_{i+1}, в едно ново число ai+ai+1a_i+a_{i+1}. Получаваме d−1d-1 числа със същата обща сума nn и с всяко число в интервала [0,1][0,1]. По индукционното предположение те могат да се разделят на 2n−12n-1 групи със сума във всяка група най-много 11. Ако в тази подредба заменим обединеното число обратно с aia_i и ai+1a_{i+1} в същата група, получаваме търсеното разделяне на първоначалните числа. Следователно минималната стойност е 2n−12n-1.
Отвори задачатаMathNetISL 2013 C1Условие — източник

Задача C2

Пълен запис
Условие
В равнината са отбелязани 20132013 червени и 20142014 сини точки, като никои три от отбелязаните точки не са колинеарни. Трябва да се начертаят kk прави, които не минават през отбелязана точка и разделят равнината на области. Целта е никоя област да не съдържа точки и от двата цвята. Да се намери минималната стойност на kk, за която целта може да се постигне при всяка възможна конфигурация на 40274027 точки.
РешениеОтговорът е k=2013k=2013. Първо ще дадем пример, който показва, че k≥2013k\ge2013. Поставяме 20132013 червени и 20132013 сини точки върху една окръжност, редувайки цветовете им, и добавяме още една синя точка някъде в равнината. Окръжността се разделя на 40264026 дъги, всяка с краища от различни цветове. Ако целта е постигната, всяка такава дъга трябва да се пресича с някоя от начертаните прави. Понеже една права пресича окръжността в най-много две точки, са нужни поне40262=2013\frac{4026}{2}=2013прави. Остава да докажем, че 20132013 прави винаги стигат. Първо отбелязваме, че за всякакви две точки AA и BB от един и същи цвят можем да ги отделим от всички останали точки с две прави. Достатъчно е да вземем две прави, успоредни на ABAB, лежащи от двете страни на ABAB и достатъчно близо до нея; тогава между тези две прави ще останат само AA и BB. Нека PP е изпъкналата обвивка на всички отбелязани точки. Има два случая. Ако PP има червен връх AA, начертаваме една права, която отделя AA от всички останали точки. Останалите 20122012 червени точки сдвояваме в 10061006 двойки, като всяка двойка отделяме от останалите точки с две прави, както беше описано по-горе. Общият брой прави е1+2⋅1006=2013.1+2\cdot1006=2013.Ако всички върхове на PP са сини, вземаме два съседни върха AA и BB на PP. Една права, успоредна на ABAB и достатъчно близо до него, отделя тези две точки от всички останали. Останалите 20122012 сини точки отново сдвояваме в 10061006 двойки и отделяме всяка двойка с две прави. Пак използваме 20132013 прави. Следователно минималната стойност е 20132013.
Отвори задачатаMathNetISL 2013 C2Условие — източник

Задача C3

Пълен запис
Условие
Един странен физик открил нов вид частици, които нарекъл имони, след като няколко от тях загадъчно се появили в лабораторията му. Някои двойки имони в лабораторията може да са заплетени и всеки имон може да участва в много отношения на заплитане. Физикът открил начин да извършва следните два вида операции с тези частици, по една операция наведнъж. (i) Ако някой имон е заплетен с нечетен брой други имони в лабораторията, физикът може да го унищожи. (ii) Във всеки момент той може да удвои цялото семейство имони в лабораторията, като създаде копие I′I' на всеки имон II. При тази процедура копията I′I' и J′J' стават заплетени тогава и само тогава, когато първоначалните имони II и JJ са били заплетени, и всяко копие I′I' става заплетено със своя първоначален имон II; никакви други заплитания не възникват или изчезват в този момент. Докажете, че физикът може да приложи редица от такива операции, след която да остане семейство имони, сред които никои два не са заплетени.
РешениеЩе преведем задачата на езика на графите: имоните са върхове, а две частици са свързани с ребро точно когато са заплетени. Да припомним, че правилно оцветяване на граф е оцветяване на върховете му с няколко цвята така, че всеки два съседни върха да имат различни цветове. Ще докажем следната лема. Ако граф GG има правилно оцветяване с nn цвята, където n>1n\gt{}1, то чрез разрешените операции можем да получим граф, който има правилно оцветяване с n−1n-1 цвята. Доказателство на лемата. Първо прилагаме операция (i) многократно към всеки подходящ връх, докато това е възможно. Понеже броят на върховете намалява, процесът завършва. Полученият граф има само върхове с четни степени и все още допуска правилно оцветяване с цветовете 1,2,…,n1,2,\ldots,n. Сега прилагаме операция (ii). Полученият граф отново може да се оцвети правилно с nn цвята: запазваме цветовете на старите върхове, а ако старият връх II е имал цвят kk, оцветяваме копието I′I' с цвят k+1(modn)k+1\pmod n. Така старите съседни върхове остават с различни цветове, копията на съседни върхове също са с различни цветове, а II и I′I' имат различни цветове, понеже n>1n\gt{}1. След удвояването всички степени са нечетни: старият връх получава точно едно ново ребро към копието си, а всяко копие има степента на първообраза си плюс това едно ново ребро. Затова можем с операция (i) последователно да унищожим всички върхове с цвят nn. Никои два от тях не са съседни, така че степените им не се променят от унищожаването на друг връх със същия цвят. След като ги премахнем, останалият граф е правилно оцветен с цветовете 1,2,…,n−11,2,\ldots,n-1. Лемата е доказана. Сега, ако началният граф има NN върха, той очевидно допуска правилно оцветяване с NN цвята. Прилагаме лемата последователно, докато получим граф, който се оцветява правилно с един цвят. Такъв граф няма ребра, тоест сред останалите имони никои два не са заплетени.
Отвори задачатаMathNetISL 2013 C3Условие — източник

Задача C5

Пълен запис
Условие
Нека rr е положително цяло число и нека a0,a1,…a_0,a_1,\ldots е безкрайна редица от реални числа. Да предположим, че за всички неотрицателни цели числа mm и ss съществува цяло число n∈[m+1,m+r]n\in[m+1,m+r], за коетоam+am+1+⋯+am+s=an+an+1+⋯+an+s.a_m+a_{m+1}+\cdots+a_{m+s}=a_n+a_{n+1}+\cdots+a_{n+s}.Докажете, че редицата е периодична, т.е. съществува p≥1p\ge1, такова, че an+p=ana_{n+p}=a_n за всяко n≥0n\ge0.
РешениеЗа индекси m≤nm\le n ще означавамеS(m,n)=am+am+1+⋯+an−1,S(m,n)=a_m+a_{m+1}+\cdots+a_{n-1},като S(n,n)=0S(n,n)=0. Започваме със следната лема. Лема. Нека b0,b1,…b_0,b_1,\ldots е безкрайна редица. Да предположим, че за всяко неотрицателно цяло число mm съществува цяло число n∈[m+1,m+r]n\in[m+1,m+r], за което bm=bnb_m=b_n. Тогава за всеки два индекса k≤ℓk\le \ell съществува индекс t∈[ℓ,ℓ+r−1]t\in[\ell,\ell+r-1], за който bt=bkb_t=b_k. Освен това сред членовете на редицата (bi)(b_i) има най-много rr различни стойности. Доказателство на лемата. За първото твърдение забелязваме, че съществува безкрайна редица от индексиk1=k,k2,k3,…k_1=k,k_2,k_3,\ldotsтакава, чеbk1=bk2=⋯=bkиki<ki+1≤ki+rb_{k_1}=b_{k_2}=\cdots=b_k\qquad\text{и}\qquad k_i\lt{}k_{i+1}\le k_i+rза всяко i≥1i\ge1. Тази редица от индекси е неограничена отгоре, а стъпките й са най-много rr, следователно пресича всеки интервал от вида [ℓ,ℓ+r−1][\ell,\ell+r-1] с ℓ≥k\ell\ge k. За второто твърдение допускаме противното: нека има r+1r+1 различни стойности bi1,…,bir+1b_{i_1},\ldots,b_{i_{r+1}}. Прилагаме първото твърдение за k=i1,…,ir+1k=i_1,\ldots,i_{r+1} и заℓ=max⁡{i1,…,ir+1}.\ell=\max\{i_1,\ldots,i_{r+1}\}.Тогава за всяко j=1,2,…,r+1j=1,2,\ldots,r+1 намираме tj∈[ℓ,ℓ+r−1]t_j\in[\ell,\ell+r-1] с btj=bijb_{t_j}=b_{i_j}. Така интервалът [ℓ,ℓ+r−1][\ell,\ell+r-1] съдържа r+1r+1 различни стойности на редицата, което е невъзможно, защото в него има само rr индекса. Лемата е доказана. Ако в условието на задачата положим s=0s=0, виждаме, че редицата (ai)(a_i) удовлетворява условието на лемата. Следователно тя приема най-много rr различни стойности. НекаAi=(ai,ai+1,…,ai+r−1)A_i=(a_i,a_{i+1},\ldots,a_{i+r-1})е наредената rr-орка от rr последователни члена. Между всички AiA_i има най-много rrr^r различни rr-орки, така че за всяко k≥0k\ge0 две от rr+1r^r+1-те rr-оркиAk,Ak+1,…,Ak+rrA_k,A_{k+1},\ldots,A_{k+r^r}са равни. Понеже възможните разлики между индексите са само 1,2,…,rr1,2,\ldots,r^r, съществува положително цяло число p≤rrp\le r^r, за което равенството Ad=Ad+pA_d=A_{d+p} е изпълнено за безкрайно много индекси dd. Нека DD е множеството от всички такива индекси dd. Ще докажем, че DD всъщност е множеството на всички неотрицателни цели числа. Тъй като DD е неограничено, достатъчно е да покажем, че от d+1∈Dd+1\in D следва d∈Dd\in D. Да приемем, че d+1∈Dd+1\in D, т.е. Ad+1=Ad+p+1A_{d+1}=A_{d+p+1}. Полагамеbk=S(k,p+k).b_k=S(k,p+k).Редицата (bk)(b_k) също удовлетворява условието на лемата: това е точно условието на задачата, приложено към суми с pp последователни члена. Затова съществува индекс t∈[d+1,d+r]t\in[d+1,d+r], за койтоS(t,t+p)=S(d,d+p).S(t,t+p)=S(d,d+p).Последното равенство е еквивалентно наS(d,t)=S(d+p,t+p).S(d,t)=S(d+p,t+p).От Ad+1=Ad+p+1A_{d+1}=A_{d+p+1} имаме ощеS(d+1,t)=S(d+p+1,t+p).S(d+1,t)=S(d+p+1,t+p).Като извадим тези две равенства, получавамеad=S(d,t)−S(d+1,t)=a_d=S(d,t)-S(d+1,t)=S(d+p,t+p)−S(d+p+1,t+p)=ad+p.S(d+p,t+p)-S(d+p+1,t+p)=a_{d+p}.Заедно с Ad+1=Ad+p+1A_{d+1}=A_{d+p+1} това дава Ad=Ad+pA_d=A_{d+p}, тоест d∈Dd\in D. Следователно Ad=Ad+pA_d=A_{d+p} за всяко d≥0d\ge0. В частност ad+p=ada_{d+p}=a_d за всяко d≥0d\ge0, което доказва, че редицата е периодична.
Отвори задачатаMathNetISL 2013 C5Условие — източник

Задача C7

Пълен запис
Условие
Играчите AA и BB играят игра с боядисване върху реалната права. Играчът AA има кутия с 44 единици черна боя. Количество pp от тази боя е достатъчно, за да се боядиса в черно затворен реален интервал с дължина pp. Във всеки ход играчът AA избира положително цяло число mm и предоставя 1/2m1/2^m единици боя от кутията. След това играчът BB избира цяло число kk и боядисва интервала от k/2mk/2^m до (k+1)/2m(k+1)/2^m; някои части от този интервал може вече да са били боядисани. Целта на играча AA е да се стигне до положение, в което кутията е празна, но интервалът [0,1][0,1] не е напълно боядисан в черно. Да се реши дали съществува стратегия, с която играчът AA печели за краен брой ходове.
РешениеОтговорът е не: такава стратегия за играча AA не съществува. Ще опишем стратегия за играча BB, която гарантира, че интервалът [0,1][0,1] е напълно боядисан, щом кутията с боя се изпразни. В началото на ход rr нека xrx_r е най-голямото реално число, за което интервалът от 00 до xrx_r вече е боядисан в черно; за пълнота поставяме x1=0x_1=0. Нека mm е числото, избрано от AA в този ход. Определяме цяло число yry_r чрезyr2m≤xr<yr+12m.\frac{y_r}{2^m}\le x_r\lt{}\frac{y_r+1}{2^m}.ИнтервалътI0r=[yr2m,yr+12m]I_0^r=\left[\frac{y_r}{2^m},\frac{y_r+1}{2^m}\right]е най-левият интервал, който може да бъде боядисан в ход rr и все още съдържа небоядисана точка. Играчът BB разглежда следващия интервалI1r=[yr+12m,yr+22m].I_1^r=\left[\frac{y_r+1}{2^m},\frac{y_r+2}{2^m}\right].Ако I1rI_1^r все още съдържа небоядисана точка, BB боядисва I1rI_1^r; в противен случай боядисва I0rI_0^r. Договаряме се, че в началото на играта интервалът [1,2][1,2] вече е боядисан; така, ако yr+1=2my_r+1=2^m, играчът BB боядисва I0rI_0^r. Ще докажем с индукция следното. Ако преди ход rr отсечката [0,1][0,1] не е напълно боядисана, то преди този ход: (i) количеството боя, използвано върху отсечката [0,xr][0,x_r], е най-много 3xr3x_r; (ii) за всяко mm играчът BB е боядисал най-много един интервал с дължина 1/2m1/2^m вдясно от xrx_r. За началото това е очевидно. Да предположим, че условията са изпълнени преди ход rr, и нека mm е числото, избрано от AA. Ако в този ход BB боядиса I1rI_1^r, то xr+1=xrx_{r+1}=x_r и (i) остава вярно. Освен това, ако преди този ход BB вече беше боядисал интервал с дължина 1/2m1/2^m вдясно от xrx_r, той непременно щеше да съвпада с I1rI_1^r. Но според стратегията BB не би боядисал вече напълно боядисан интервал I1rI_1^r. Следователно (ii) също остава вярно. Нека сега BB боядиса I0rI_0^r, но [0,1][0,1] все още съдържа небоядисани точки; тогава I1r⊂[0,1]I_1^r\subset[0,1]. Условието (ii) ясно остава вярно, а трябва да проверим (i). В този случай интервалите I0rI_0^r и I1rI_1^r са напълно боядисани след хода, така че xr+1x_{r+1} достига десния край на I1rI_1^r или минава още по-надясно. Следователно xr+1=xr+αx_{r+1}=x_r+\alpha за някое α>1/2m\alpha\gt{}1/2^m. Всеки интервал, боядисан от BB преди ход rr и пресичащ (xr,xr+1)(x_r,x_{r+1}), се съдържа в [xr,xr+1][x_r,x_{r+1}]. По (ii) всички такива интервали имат различни дължини, не по-големи от 1/2m1/2^m, затова общото количество боя, използвано за тях, е по-малко от 2/2m2/2^m. Значи количеството боя, използвано върху [0,xr+1][0,x_{r+1}], е най-много3xr+22m+12m=3(xr+12m)<3x_r+\frac{2}{2^m}+\frac{1}{2^m}=3\left(x_r+\frac1{2^m}\right)\lt{}3(xr+α)=3xr+1.3(x_r+\alpha)=3x_{r+1}.Така (i) също е доказано, и индукцията е завършена. Накрая разглеждаме произволно положение, например след ход r−1r-1, и допускаме, че [0,1][0,1] не е напълно боядисан в черно. По (ii), в интервала [xr,1][x_r,1] играчът BB е боядисал няколко интервала с различни дължини; всички тези дължини са отрицателни степени на 22 и не надвишават 1−xr1-x_r. Следователно общото количество боя, използвано за тази част, е най-много 2(1−xr)2(1-x_r). От (i) получаваме, че общо използваната боя е най-много3xr+2(1−xr)<3.3x_r+2(1-x_r)\lt{}3.Кутията още не е празна, следователно AA никога не печели.
Отвори задачатаMathNetISL 2013 C7Условие — източник

Задача G1

Пълен запис
Условие
Нека ω\omega е описаната окръжност на триъгълника ABCABC. Нека MM и NN са средите съответно на страните ABAB и ACAC, а TT е средата на дъгата BCBC на ω\omega, която не съдържа AA. Описаните окръжности на триъгълниците AMTAMT и ANTANT пресичат симетралите на ACAC и ABAB съответно в точки XX и YY; да предположим, че XX и YY лежат във вътрешността на триъгълника ABCABC. Правите MNMN и XYXY се пресичат в KK. Докажете, че KA=KTKA=KT.
РешениеНека OO е центърът на ω\omega. Тогава O=MY∩NXO=MY\cap NX. Нека ℓ\ell е симетралата на отсечката ATAT; тя минава и през OO. Нека rr е отражението спрямо ℓ\ell. Понеже ATAT е ъглополовяща на ∠BAC\angle BAC, правата r(AB)r(AB) е успоредна на ACAC. От OM⊥ABOM\perp AB и ON⊥ACON\perp AC следва, че r(OM)r(OM) е успоредна на ONON и минава през OO, следователно r(OM)=ONr(OM)=ON. Нека γ\gamma е описаната окръжност на триъгълника AMTAMT. Тя е симетрична спрямо ℓ\ell, защото ℓ\ell е симетралата на ATAT, така че r(γ)=γr(\gamma)=\gamma. Затова образът на MM е общата точка на ONON с окръжността γ\gamma в съответното положение, т.е. точно точката XX. Следователно r(M)=Xr(M)=X. Аналогично r(N)=Yr(N)=Y. Значи r(MN)=XYr(MN)=XY. Тъй като KK е пресечната точка на правата MNMN с нейния образ XYXY при отражение спрямо ℓ\ell, точката KK лежи върху оста на отражението ℓ\ell. Но ℓ\ell е симетралата на ATAT, следователно KA=KTKA=KT, както трябваше да се докаже.
Отвори задачатаMathNetISL 2013 G1Условие — източник

Задача N1

Пълен запис
Условие
Нека Z>0\mathbb Z_{\gt{}0} е множеството на положителните цели числа. Да се намерят всички функции f:Z>0→Z>0f:\mathbb Z_{\gt{}0}\to\mathbb Z_{\gt{}0}, за коитоm2+f(n)∣mf(m)+nm^2+f(n)\mid mf(m)+nза всички положителни цели числа mm и nn.
РешениеОтговорът е f(n)=nf(n)=n за всяко n∈Z>0n\in\mathbb Z_{\gt{}0}. Полагаме m=n=2m=n=2. Тогава4+f(2)∣2f(2)+2,4+f(2)\mid 2f(2)+2,а 0<2f(2)+2<2(4+f(2))0\lt{}2f(2)+2\lt{}2(4+f(2)). Следователно 2f(2)+2=4+f(2)2f(2)+2=4+f(2) и f(2)=2f(2)=2. Сега при m=2m=2 получаваме4+f(n)∣4+n,4+f(n)\mid 4+n,откъдето f(n)≤nf(n)\le n за всяко nn. От друга страна, при m=nm=n имамеn2+f(n)∣nf(n)+n.n^2+f(n)\mid nf(n)+n.За n≥2n\ge2 това дава nf(n)+n≥n2+f(n)nf(n)+n\ge n^2+f(n), т.е.(n−1)(f(n)−n)≥0,(n-1)(f(n)-n)\ge0,следователно f(n)≥nf(n)\ge n. Значи f(n)=nf(n)=n за n≥2n\ge2, а от вече доказаното f(1)≤1f(1)\le1 и положителността дават f(1)=1f(1)=1. Функцията f(n)=nf(n)=n очевидно удовлетворява условието.
Отвори задачатаMathNetISL 2013 N1Условие — източник

Задача N2

Пълен запис
Условие
Докажете, че за всяка двойка положителни цели числа kk и nn съществуват kk положителни цели числа m1,m2,…,mkm_1,m_2,\ldots,m_k, такива че1+2k−1n=(1+1m1)(1+1m2)⋯(1+1mk).1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\left(1+\frac1{m_2}\right)\cdots\left(1+\frac1{m_k}\right).
РешениеДоказваме твърдението с индукция по kk. При k=1k=1 е достатъчно да вземем m1=nm_1=n. Нека твърдението е доказано за k=j−1k=j-1 и да го докажем за k=jk=j. Ако n=2t−1n=2t-1, то1+2j−12t−1=(1+2j−1−1t)(1+12t−1).1+\frac{2^j-1}{2t-1}=\left(1+\frac{2^{j-1}-1}{t}\right)\left(1+\frac1{2t-1}\right).По индукционното предположение първият множител вдясно се представя като произведение от j−1j-1 множителя от вида 1+1/mi1+1/m_i, а последният множител дава mj=2t−1m_j=2t-1. Ако n=2tn=2t, то1+2j−12t=(1+12t+2j−2)(1+2j−1−1t).1+\frac{2^j-1}{2t}=\left(1+\frac1{2t+2^j-2}\right)\left(1+\frac{2^{j-1}-1}{t}\right).Отново прилагаме индукционното предположение към втория множител и вземаме mj=2t+2j−2m_j=2t+2^j-2. В двата случая получаваме исканото представяне с jj положителни цели числа, което завършва индукцията.
Отвори задачатаMathNetISL 2013 N2Условие — източник

Задача N3

Пълен запис
Условие
Докажете, че съществуват безкрайно много положителни цели числа nn, за които най-големият прост делител на n4+n2+1n^4+n^2+1 е равен на най-големия прост делител на (n+1)4+(n+1)2+1(n+1)^4+(n+1)^2+1.
РешениеНека pnp_n е най-големият прост делител на n4+n2+1n^4+n^2+1, а qnq_n е най-големият прост делител на n2+n+1n^2+n+1. От разлаганетоn4+n2+1=(n2−n+1)(n2+n+1)=n^4+n^2+1=(n^2-n+1)(n^2+n+1)=((n−1)2+(n−1)+1)(n2+n+1)((n-1)^2+(n-1)+1)(n^2+n+1)следва, че за n≥2n\ge2pn=max⁡{qn−1,qn}.p_n=\max\{q_{n-1},q_n\}.Освен товаgcd⁡(n2+n+1,n2−n+1)=gcd⁡(2n,n2−n+1)=1,\gcd(n^2+n+1,n^2-n+1)=\gcd(2n,n^2-n+1)=1,така че qn≠qn−1q_n\ne q_{n-1}. Достатъчно е да докажем, че множествотоS={n∈Z≥2:qn>qn−1 и qn>qn+1}S=\{n\in\mathbb Z_{\ge2}:q_n\gt{}q_{n-1}\text{ и }q_n\gt{}q_{n+1}\}е безкрайно. Наистина, за всяко n∈Sn\in S имамеpn=max⁡{qn−1,qn}=qn=max⁡{qn,qn+1}=pn+1.p_n=\max\{q_{n-1},q_n\}=q_n=\max\{q_n,q_{n+1}\}=p_{n+1}.Да допуснем, че SS е крайно. То е непразно, понеже q2=7<13=q3q_2=7\lt{}13=q_3 и q3=13>7=q4q_3=13\gt{}7=q_4. Нека mm е най-големият му елемент. Последователността qm,qm+1,qm+2,…q_m,q_{m+1},q_{m+2},\ldots не може да бъде строго намаляваща безкрайно, затова съществува k≥mk\ge m с qk<qk+1q_k\lt{}q_{k+1}. Тя не може и да бъде строго растяща от kk нататък. Ако беше така, тоq(k+1)2=pk+1=max⁡{qk,qk+1}=qk+1,q_{(k+1)^2}=p_{k+1}=\max\{q_k,q_{k+1}\}=q_{k+1},което противоречи на (k+1)2>k+1(k+1)^2\gt{}k+1 и строгото нарастване. Следователно има най-малко ℓ≥k+1\ell\ge k+1, за което qℓ>qℓ+1q_\ell\gt{}q_{\ell+1}. По минималността на ℓ\ell имаме qℓ−1<qℓq_{\ell-1}\lt{}q_\ell, следователно ℓ∈S\ell\in S. Но ℓ>m\ell\gt{}m, противоречие. Значи SS е безкрайно и твърдението следва.
Отвори задачатаMathNetISL 2013 N3Условие — източник

Задача N4

Пълен запис
Условие
Да се определи дали има безкрайна редица от ненулеви цифри a1,a2,a3,…a_1,a_2,a_3,\ldots и положително цяло число NN, такива, че за всяко цяло число k>Nk\gt{}N числото akak−1…a1‾\overline{a_k a_{k-1}\ldots a_1} да е точен квадрат.
РешениеОтговорът е: не. Да допуснем, че такава редица a1,a2,a3,…a_1,a_2,a_3,\ldots съществува. За всяко положително цяло число kk означаваме yk=akak−1…a1‾.y_k=\overline{a_k a_{k-1}\ldots a_1}. По предположение за всяко k>Nk\gt{}N съществува положително цяло число xkx_k, такова че yk=xk2y_k=x_k^2. Нека за всяко nn числото 5γn5^{\gamma_n} е най-голямата степен на 55, която дели xnx_n. Първо ще докажем, че 2γn≥n2\gamma_n\ge n за всяко положително цяло число n>Nn\gt{}N. Да допуснем противното: за някое n>Nn\gt{}N имаме 2γn<n2\gamma_n\lt{}n. Тогаваyn+1=an+1an…a1‾=10nan+1+anan−1…a1‾=10nan+1+yn=52γn(2n5n−2γnan+1+yn52γn).\begin{aligned} y_{n+1}&=\overline{a_{n+1}a_n\ldots a_1}=10^n a_{n+1}+\overline{a_n a_{n-1}\ldots a_1}\\ &=10^n a_{n+1}+y_n\\ &=5^{2\gamma_n}\left(2^n5^{n-2\gamma_n}a_{n+1}+\frac{y_n}{5^{2\gamma_n}}\right). \end{aligned}Понеже 5∤yn/52γn5\nmid y_n/5^{2\gamma_n}, получаваме γn+1=γn<n<n+1\gamma_{n+1}=\gamma_n\lt{}n\lt{}n+1. Повтаряйки същия аргумент, намираме γn=γn+1=γn+2=⋯ .\gamma_n=\gamma_{n+1}=\gamma_{n+2}=\cdots. Да означим тази обща стойност с γ\gamma. За всяко k≥nk\ge n имаме(xk+1−xk)(xk+1+xk)=\left(x_{k+1}-x_k\right)\left(x_{k+1}+x_k\right)=xk+12−xk2=yk+1−yk=ak+1⋅10k.x_{k+1}^2-x_k^2=y_{k+1}-y_k=a_{k+1}\cdot10^k. Един от множителите xk+1−xkx_{k+1}-x_k и xk+1+xkx_{k+1}+x_k не се дели на 5γ+15^{\gamma+1}; иначе сборът им 2xk+12x_{k+1} също би се делил на 5γ+15^{\gamma+1}, невъзможно. От друга страна произведението им се дели на 5k5^k. Следователно един от двата множителя се дели на 5k−γ5^{k-\gamma}. Затова5k−γ≤max⁡{xk+1−xk,xk+1+xk}<5^{k-\gamma}\le\max\{x_{k+1}-x_k,x_{k+1}+x_k\}\lt{}2xk+1=2x2yk+1<2⋅10(k+1)/2.2x_{k+1}=2\sqrt{\vphantom{x^2}y_{k+1}}\lt{}2\cdot10^{(k+1)/2}.Оттук следва 52k<4⋅52γ⋅10k+1,5^{2k}\lt{}4\cdot5^{2\gamma}\cdot10^{k+1}, тоест (52)k<40⋅52γ.\left(\frac52\right)^k\lt{}40\cdot5^{2\gamma}. Това е невъзможно за достатъчно големи kk, противоречие. Значи наистина 2γn≥n2\gamma_n\ge n за всички n>Nn\gt{}N. Сега вземаме цяло число k>max⁡{N/2,2}.k\gt{}\max\{N/2,2\}. От вече доказаното получаваме γ2k+1≥k+1\gamma_{2k+1}\ge k+1 и γ2k+2≥k+1\gamma_{2k+2}\ge k+1. Следователно и y2k+1y_{2k+1}, и y2k+2y_{2k+2} се делят на 52k+25^{2k+2}. Ноy2k+2−y2k+1=a2k+2⋅102k+1,y_{2k+2}-y_{2k+1}=a_{2k+2}\cdot10^{2k+1},така че 52k+2∣a2k+2⋅102k+15^{2k+2}\mid a_{2k+2}\cdot10^{2k+1} и значи 5∣a2k+25\mid a_{2k+2}. Понеже a2k+2a_{2k+2} е ненулева цифра, получаваме a2k+2=5a_{2k+2}=5. Тогава(x2k+2−x2k+1)(x2k+2+x2k+1)=x2k+22−x2k+12=y2k+2−y2k+1=5⋅102k+1=22k+152k+2.\begin{aligned} \left(x_{2k+2}-x_{2k+1}\right)\left(x_{2k+2}+x_{2k+1}\right)&=x_{2k+2}^2-x_{2k+1}^2\\ &=y_{2k+2}-y_{2k+1}=5\cdot10^{2k+1}=2^{2k+1}5^{2k+2}. \end{aligned}Полагаме Ak=x2k+25k+1,Bk=x2k+15k+1,A_k=\frac{x_{2k+2}}{5^{k+1}},\qquad B_k=\frac{x_{2k+1}}{5^{k+1}}, които са цели числа. Получаваме(Ak−Bk)(Ak+Bk)=22k+1.(1)\left(A_k-B_k\right)\left(A_k+B_k\right)=2^{2k+1}.\tag{1}И AkA_k, и BkB_k са нечетни, защото иначе y2k+2y_{2k+2} или y2k+1y_{2k+1} би се деляло на 1010, което е невъзможно, тъй като a1≠0a_1\ne0. Следователно един от множителите Ak−BkA_k-B_k и Ak+BkA_k+B_k не се дели на 44. От (1) получаваме Ak−Bk=2,Ak+Bk=22k,A_k-B_k=2,\qquad A_k+B_k=2^{2k}, откъдето Ak=22k−1+1.A_k=2^{2k-1}+1. Затоваx2k+2=5k+1Ak=5k+1(22k−1+1)>10k+1,x_{2k+2}=5^{k+1}A_k=5^{k+1}\left(2^{2k-1}+1\right)\gt{}10^{k+1},понеже k≥2k\ge2. Тогава y2k+2=x2k+22>102k+2,y_{2k+2}=x_{2k+2}^2\gt{}10^{2k+2}, което е невъзможно, защото y2k+2y_{2k+2} има точно 2k+22k+2 цифри. Полученото противоречие доказва, че такава редица не съществува.
Отвори задачатаMathNetISL 2013 N4Условие — източник

Задача N5

Пълен запис
Условие
Фиксирано е цяло число k≥2k\ge2. Двама играчи, Ана и Банана, играят следната игра с числа. Първоначално на дъската е написано цяло число n≥kn\ge k. След това те ходят последователно, като Ана започва. Играчът на ход изтрива току-що написаното число mm и го заменя с число m′m', за което k≤m′<mk\le m'\lt{}m и gcd⁡(m,m′)=1\gcd(m,m')=1. Първият играч, който не може да направи ход, губи. Цяло число n≥kn\ge k се нарича добро, ако Банана има печеливша стратегия при начално число nn, и лошо в противен случай. Нека n,n′≥kn,n'\ge k са две цели числа със свойството, че за всяко просто число p≤kp\le k числото pp дели nn точно тогава, когато дели n′n'. Докажете, че или и двете числа nn и n′n' са добри, или и двете са лоши.
РешениеИграта винаги завършва, защото написаното число намалява. Затова всяка позиция е или добра, или лоша. Ако от nn има допустим ход към добро число, то nn е лошо; ако всички допустими ходове от nn водят към лоши числа, то nn е добро. В частност kk е добро и две различни добри числа не могат да бъдат взаимнопрости: по-голямото би имало ход към по-малкото. Ще наричаме простите числа p≤kp\le k малки, а останалите големи. Две числа a,b≥ka,b\ge k ще наричаме подобни, ако имат едни и същи малки прости делители. Лема. Ако b≥kb\ge k има малък прост делител, то съществува число xx, подобно на bb, за което k≤x≤bk\le x\le b и xx няма големи прости делители. Доказателство. Ако bb няма големи прости делители, вземаме x=bx=b. Иначе нека pp е малък, а qq голям прост делител на bb. Нека aa е произведението на различните малки прости делители на bb. Избираме най-малкото r≥0r\ge0, за което x=pra≥kx=p^r a\ge k. Тогава xx е подобно на bb и няма големи прости делители. Ако r=0r=0, ясно е x=a≤bx=a\le b. Ако r>0r\gt{}0, от минималността имаме x<pkx\lt{}pk, а понеже p≤ap\le a и k<qk\lt{}q, следва x<aq≤bx\lt{}aq\le b. Лемата е доказана. Да допуснем, че има подобни числа с различен тип, и изберем такава двойка (a,b)(a,b) с минимално max⁡(a,b)\max(a,b), където aa е лошо, а bb е добро. Понеже aa е лошо, има допустим ход a→ra\to r към добро число rr. Числата kk и rr са добри, следователно имат общ прост делител; той е малък, тъй като дели kk. По лемата съществува r′r', подобно на rr, с k≤r′≤rk\le r'\le r и без големи прости делители. От минималността на избора на (a,b)(a,b) числото r′r' също е добро, защото rr и r′r' са подобни и r<a≤max⁡(a,b)r\lt{}a\le\max(a,b). Двете добри числа r′r' и bb имат общ прост делител pp. Той е малък, понеже r′r' няма големи прости делители. От подобието на aa и bb следва p∣ap\mid a, а от подобието на rr и r′r' следва p∣rp\mid r. Това противоречи на допустимостта на хода a→ra\to r, където трябва да е gcd⁡(a,r)=1\gcd(a,r)=1. Противоречието показва, че подобни числа винаги имат един и същи тип. Това е точно твърдението.
Отвори задачатаMathNetISL 2013 N5Условие — източник

Задача N6

Пълен запис
Условие
Да се определят всички функции f:Q→Zf:\mathbb Q\to\mathbb Z, за коитоf(f(x)+ab)=f(x+ab)f\left(\frac{f(x)+a}{b}\right)=f\left(\frac{x+a}{b}\right)за всички x∈Qx\in\mathbb Q, a∈Za\in\mathbb Z и b∈Z>0b\in\mathbb Z_{\gt{}0}.
РешениеОтговорът е: всички константни функции, функцията f(x)=⌊x⌋f(x)=\lfloor x\rfloor и функцията f(x)=⌈x⌉f(x)=\lceil x\rceil. Тези функции непосредствено удовлетворяват условието. За пода например, акоq=⌊x+ab⌋,q=\left\lfloor\frac{x+a}{b}\right\rfloor,то bq≤x+a<b(q+1)bq\le x+a\lt{}b(q+1), а оттук и bq≤⌊x⌋+a<b(q+1)bq\le\lfloor x\rfloor+a\lt{}b(q+1); следователно⌊⌊x⌋+ab⌋=q.\left\lfloor\frac{\lfloor x\rfloor+a}{b}\right\rfloor=q.За тавана проверката е аналогична, а константните функции са очевидни решения. Нека сега ff е произволно решение. Първо разглеждаме случая, когато има цяло mm с f(m)=C≠mf(m)=C\ne m. Нека η∈{−1,1}\eta\in\{-1,1\} е знакът на C−mC-m, а b=∣C−m∣b=|C-m|. За всяко цяло rr, като заместим x=mx=m и a=rb−Ca=rb-C, получавамеf(r)=f(r−η).f(r)=f(r-\eta).Оттук всички цели числа имат една и съща стойност CC. Ако y=p/qy=p/q с p∈Zp\in\mathbb Z и q∈Z>0q\in\mathbb Z_{\gt{}0}, то заместването x=C−px=C-p, a=p−Ca=p-C, b=qb=q дава f(y)=f(0)=Cf(y)=f(0)=C. Значи ff е константна. Остава случаят f(t)=tf(t)=t за всяко цяло tt. При b=1b=1 получавамеf(x+a)=f(x)+a(x∈Q,a∈Z).(1)f(x+a)=f(x)+a\qquad(x\in\mathbb Q, a\in\mathbb Z).\tag{1}Нека S={x∈Q:f(x)=0}S=\{x\in\mathbb Q:f(x)=0\}. От (1) във всеки клас по модул Z\mathbb Z има точно един елемент на SS. Ако p/q∈Sp/q\in S, q>0q\gt{}0, то заместването x=p/qx=p/q, a=pa=p, b=q+1b=q+1 даваpq+1∈S.(2)\frac{p}{q+1}\in S.\tag{2}Оттук следва, че ако x>y>0x\gt{}y\gt{}0 и x∈Sx\in S, то y∈Sy\in S: пишем x=p/qx=p/q, y=r/sy=r/s с положителни p,q,r,sp,q,r,s и прилагаме (2) последователно къмprqr,prqr+1,…,prps.\frac{pr}{qr},\frac{pr}{qr+1},\ldots,\frac{pr}{ps}.По същия начин, ако x<y<0x\lt{}y\lt{}0 и x∈Sx\in S, то y∈Sy\in S. Следователно S⊂(−1,1)S\subset(-1,1); иначе за x∈Sx\in S с x>1x\gt{}1 бихме получили и x−1∈Sx-1\in S, а за x<−1x\lt{}-1 и x+1∈Sx+1\in S, противоречие с единствеността по модул Z\mathbb Z. Нека α=sup⁡S\alpha=\sup S. Тогава 0≤α≤10\le\alpha\le1. Ако 0<α<10\lt{}\alpha\lt{}1, избираме цяло K≥1K\ge1 с Kα<1≤(K+1)αK\alpha\lt{}1\le(K+1)\alpha и рационалноx∈(α,1+αK+1).x\in\left(\alpha,\frac{1+\alpha}{K+1}\right).Тогава y=(K+1)x−1y=(K+1)x-1 удовлетворява 0<y<α0\lt{}y\lt{}\alpha, така че f(y)=0f(y)=0, а f(x)=1f(x)=1. Заместването y,1,K+1y,1,K+1 в условието даваf(1K+1)=f(x)=1.f\left(\frac1{K+1}\right)=f(x)=1.Но 0<1/(K+1)≤α0\lt{}1/(K+1)\le\alpha, което е възможно само в граничния случай α=1/(K+1)\alpha=1/(K+1) и f(α)=1f(\alpha)=1. Тогава заместването x=αx=\alpha, a=0a=0, b=K+1b=K+1 дава1=f(1K+1)=f(αK+1)=0,1=f\left(\frac1{K+1}\right)=f\left(\frac{\alpha}{K+1}\right)=0,противоречие. Значи α\alpha е 00 или 11. Ако α=0\alpha=0, то S=(−1,0]∩QS=(-1,0]\cap\mathbb Q, и от (1) следва f(x)=⌈x⌉f(x)=\lceil x\rceil за всяко рационално xx. Ако α=1\alpha=1, то S=[0,1)∩QS=[0,1)\cap\mathbb Q, и от (1) следва f(x)=⌊x⌋f(x)=\lfloor x\rfloor за всяко рационално xx. Така списъкът с решения е пълен.
Отвори задачатаMathNetISL 2013 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека ν\nu е ирационално положително число, а mm е положително цяло число. Двойка (a,b)(a,b) от положителни цели числа се нарича добра, акоa⌈bν⌉−b⌊aν⌋=m.a\lceil b\nu\rceil-b\lfloor a\nu\rfloor=m.Добра двойка (a,b)(a,b) се нарича отлична, ако нито една от двойките (a−b,b)(a-b,b) и (a,b−a)(a,b-a) не е добра. Докажете, че броят на отличните двойки е равен на сумата на положителните делители на mm.
РешениеЗа положителни цели a,ba,b полагамеF(a,b)=a⌈bν⌉−b⌊aν⌋.F(a,b)=a\lceil b\nu\rceil-b\lfloor a\nu\rfloor.Ще казваме, че двойка е mm-добра или mm-отлична, ако условието е изпълнено за това mm. Първо описваме как се променя FF при преходите(a,b)↦(a+b,b),(a,b)↦(a,b+a).(a,b)\mapsto(a+b,b),\qquad (a,b)\mapsto(a,b+a).Ако дробните части на aνa\nu и bνb\nu имат сума, по-малка от 11, тоF(a+b,b)=F(a,b)+b,F(a,b+a)=F(a,b).F(a+b,b)=F(a,b)+b,\qquad F(a,b+a)=F(a,b).Ако сумата им е поне 11, тоF(a+b,b)=F(a,b),F(a,b+a)=F(a,b)+a.F(a+b,b)=F(a,b),\qquad F(a,b+a)=F(a,b)+a.Следователно от двете деца на всяка двойка точно едното запазва стойността на FF, а другото я увеличава със съответната стара координата. Наричаме (a+b,b)(a+b,b) и (a,b+a)(a,b+a) деца на (a,b)(a,b). Всяка двойка с различни координати има единствен родител, получен чрез изваждане на по-малката координата от по-голямата; диагоналните двойки (x,x)(x,x) нямат родител. Така всяка двойка има единствен диагонален предшественик. Ако (a,b)(a,b) е mm-отлична, то min⁡(a,b)≤m\min(a,b)\le m. Наистина, за диагонална двойка F(a,a)=aF(a,a)=a, а за недиагонална отлична двойка стойността mm е получена от родителя чрез увеличение с едната от координатите, което е по-малко или равно на mm. Нека SmS_m е множеството на двойките (a,b)(a,b), за които F(a,b)≤mF(a,b)\le m и min⁡(a,b)≤m\min(a,b)\le m. Всички mm-отлични двойки лежат в SmS_m, а заедно с всяка двойка от SmS_m там лежат и всички нейни предшественици. Множеството SmS_m е крайно. Иначе, например при безкрайно много двойки с втора координата >2m\gt{}2m, някоя двойка (a,b)(a,b) с m<b≤2mm\lt{}b\le2m би имала безкрайно много потомци от вида (a,b+ta)(a,b+ta) в SmS_m. Тогава редицата F(a,b+ta)F(a,b+ta), която не намалява и е ограничена от mm, би станала константна. Това би означавало, че дробните части на (b+ta)ν(b+ta)\nu остават в интервал с дължина по-малка от 11 при всички големи tt, което е невъзможно, защото aνa\nu е ирационално. Същият довод важи и при първа координата >2m\gt{}2m. Ще докажем лема. Ако F(a,b)≠mF(a,b)\ne m, то броят G(a,b)G(a,b) на mm-отличните потомци на (a,b)(a,b) е равен на броя H(a,b)H(a,b) на представяниятаm−F(a,b)=ra+sbm-F(a,b)=ra+sbс неотрицателни цели r,sr,s. Доказателството е с индукция по броя на потомците на (a,b)(a,b) в крайното множество SmS_m. Ако няма такива потомци, но има представяне, то m−F(a,b)≥min⁡(a,b)m-F(a,b)\ge\min(a,b). Тогава поне едно от децата на (a,b)(a,b) би лежало в SmS_m, противоречие. Значи и двата броя са 00. Нека вече има потомци. Без ограничение да приемемF(a+b,b)=F(a,b)+b,F(a,b+a)=F(a,b).F(a+b,b)=F(a,b)+b,\qquad F(a,b+a)=F(a,b).Ако F(a,b)+b≠mF(a,b)+b\ne m, по индукционното предположение за двете деца получавамеG(a,b)=G(a+b,b)+G(a,b+a)=G(a,b)=G(a+b,b)+G(a,b+a)=H(a+b,b)+H(a,b+a).H(a+b,b)+H(a,b+a).Представянията, броени от H(a+b,b)H(a+b,b), са точно тези представяния на m−F(a,b)=ra+sbm-F(a,b)=ra+sb, за които r<sr\lt{}s, а представянията, броени от H(a,b+a)H(a,b+a), са точно тези с r≥sr\ge s. Следователно сумата е H(a,b)H(a,b). Ако F(a,b)+b=mF(a,b)+b=m, детето (a+b,b)(a+b,b) е mm-отлично. Освен това представянето m−F(a,b)=bm-F(a,b)=b дава точно един допълнителен член, а останалите представяния се броят чрез детето (a,b+a)(a,b+a). Отново G(a,b)=H(a,b)G(a,b)=H(a,b). Лемата е доказана. Сега завършваме броенето. Диагоналната двойка (m,m)(m,m) е единствената mm-отлична диагонална двойка. Всяка друга mm-отлична двойка има единствен диагонален предшественик (x,x)(x,x) с x<mx\lt{}m. По лемата броят на нейните mm-отлични потомци е броят на представяниятаm−F(x,x)=m−x=(r+s)x.m-F(x,x)=m-x=(r+s)x.Този брой е 00, ако x∤mx\nmid m, и е m/xm/x, ако x∣mx\mid m. Следователно общият брой отлични двойки е1+∑x∣mx<mmx=∑d∣md,\begin{aligned}1+\sum_{\substack{x\mid m\\ x\lt{}m}}\frac mx=\sum_{d\mid m}d,\end{aligned}както се искаше.
Отвори задачатаMathNetISL 2013 N7Условие — източник