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

IMO Shortlisted Problems

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

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

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

2006

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

11-12

18 задачи

Задача A1

Пълен запис
Условие
Нека редицата от реални числа a0,a1,a2,…a_0,a_1,a_2,\ldots е зададена с формулата ai+1=⌊ai⌋⋅⟨ai⟩за i≥0,a_{i+1}=\left\lfloor a_i\right\rfloor\cdot\left\langle a_i\right\rangle\quad\text{за }i\ge0, където a0a_0 е произволно реално число, ⌊ai⌋\left\lfloor a_i\right\rfloor означава най-голямото цяло число, ненадминаващо aia_i, а ⟨ai⟩=ai−⌊ai⌋\left\langle a_i\right\rangle=a_i-\left\lfloor a_i\right\rfloor. Докажете, че ai=ai+2a_i=a_{i+2} за всички достатъчно големи ii.
РешениеПърво да отбележим, че ако a0≥0a_0\ge0, то всички ai≥0a_i\ge0. Когато ai≥1a_i\ge1, от ⟨ai⟩<1\left\langle a_i\right\rangle\lt{}1 и ⌊ai⌋>0\left\lfloor a_i\right\rfloor\gt{}0 получаваме ⌊ai+1⌋≤ai+1=⌊ai⌋⋅⟨ai⟩<⌊ai⌋.\left\lfloor a_{i+1}\right\rfloor\le a_{i+1}=\left\lfloor a_i\right\rfloor\cdot\left\langle a_i\right\rangle\lt{}\left\lfloor a_i\right\rfloor. Следователно редицата ⌊ai⌋\left\lfloor a_i\right\rfloor строго намалява, докато членовете й са в [1,∞)[1,\infty). Значи в някакъв момент се появява член от интервала [0,1)[0,1), а след него всички следващи членове са 00. Остава по-интересният случай a0<0a_0\lt{}0. Тогава всички ai≤0a_i\le0. Ако редицата някога стане 00, заключението е ясно, затова нека тя никога не приема стойност 00. Тогава ⌊ai⌋≤−1\left\lfloor a_i\right\rfloor\le-1 за всяко ii и 1+⌊ai+1⌋>ai+1=⌊ai⌋⋅⟨ai⟩>⌊ai⌋.1+\left\lfloor a_{i+1}\right\rfloor\gt{}a_{i+1}=\left\lfloor a_i\right\rfloor\cdot\left\langle a_i\right\rangle\gt{}\left\lfloor a_i\right\rfloor. Това означава, че редицата от цели числа ⌊ai⌋\left\lfloor a_i\right\rfloor е ненамаляваща. Понеже всичките й членове са в (−∞,−1](-\infty,-1], тя е константна от някой член нататък: ⌊ai⌋=cза i≥i0,\left\lfloor a_i\right\rfloor=c\quad\text{за }i\ge i_0, където cc е отрицателно цяло число. За i≥i0i\ge i_0 рекурентната формула става ai+1=c⟨ai⟩=c(ai−c)=cai−c2.a_{i+1}=c\left\langle a_i\right\rangle=c(a_i-c)=ca_i-c^2. Разглеждаме редицата bi=ai−c2c−1.b_i=a_i-\frac{c^2}{c-1}. Тогава bi+1=ai+1−c2c−1=cai−c2−c2c−1=cbi,b_{i+1}=a_{i+1}-\frac{c^2}{c-1}=ca_i-c^2-\frac{c^2}{c-1}=cb_i, откъдето bi=ci−i0bi0за i≥i0.b_i=c^{i-i_0}b_{i_0}\quad\text{за }i\ge i_0. От друга страна всички aia_i за i≥i0i\ge i_0 лежат в [c,c+1)[c,c+1), така че редицата (bi)(b_i) е ограничена. Това е възможно само ако bi0=0b_{i_0}=0 или ∣c∣=1|c|=1, тоест c=−1c=-1. В първия случай bi=0b_i=0 за всяко i≥i0i\ge i_0, следователно ai=c2c−1за i≥i0,a_i=\frac{c^2}{c-1}\quad\text{за }i\ge i_0, така че редицата е константна от някой член нататък. Във втория случай c=−1c=-1 и формулата за bib_i дава ai=−12+(−1)i−i0bi0.a_i=-\frac12+(-1)^{i-i_0}b_{i_0}. Значи от някой момент нататък редицата се редува между две стойности от интервала (−1,0)(-1,0). И в двата случая получаваме ai=ai+2a_i=a_{i+2} за всички достатъчно големи ii.
Отвори задачатаMathNetISL 2006 A1Условие — източник

Задача A2

Пълен запис
Условие
Редицата от реални числа a0,a1,a2,…a_0,a_1,a_2,\ldots е зададена рекурентно чрез a0=−1,∑k=0nan−kk+1=0за n≥1.a_0=-1,\quad \sum_{k=0}^n \frac{a_{n-k}}{k+1}=0\quad\text{за }n\ge1. Докажете, че an>0a_n\gt{}0 за всяко n≥1n\ge1.
РешениеЩе докажем твърдението с индукция. За n=1n=1 рекурентната формула дава a1=12a_1=\frac12. Нека n≥1n\ge1 и да предположим, че a1,a2,…,an>0a_1,a_2,\ldots,a_n\gt{}0. Записваме рекурентната формула за nn и за n+1n+1 във вида ∑k=0nakn−k+1=0и∑k=0n+1akn−k+2=0.\sum_{k=0}^n \frac{a_k}{n-k+1}=0\quad\text{и}\quad \sum_{k=0}^{n+1}\frac{a_k}{n-k+2}=0. Изваждаме подходящо умножени равенства и получаваме 0=(n+2)∑k=0n+1akn−k+2−(n+1)∑k=0nakn−k+1=(n+2)an+1+∑k=0n(n+2n−k+2−n+1n−k+1)ak.\begin{aligned}0&=(n+2)\sum_{k=0}^{n+1}\frac{a_k}{n-k+2}-(n+1)\sum_{k=0}^n\frac{a_k}{n-k+1}\\&=(n+2)a_{n+1}+\sum_{k=0}^n\left(\frac{n+2}{n-k+2}-\frac{n+1}{n-k+1}\right)a_k.\end{aligned} Коефициентът пред a0a_0 е нула, следователно an+1=a_{n+1}=1n+2∑k=1n(n+1n−k+1−n+2n−k+2)ak.\frac1{n+2}\sum_{k=1}^n\left(\frac{n+1}{n-k+1}-\frac{n+2}{n-k+2}\right)a_k. Но n+1n−k+1−n+2n−k+2=k(n−k+1)(n−k+2)>0\frac{n+1}{n-k+1}-\frac{n+2}{n-k+2}=\frac{k}{(n-k+1)(n-k+2)}\gt{}0 за 1≤k≤n1\le k\le n. Значи an+1a_{n+1} е положителна линейна комбинация на положителните числа a1,a2,…,ana_1,a_2,\ldots,a_n с положителен множител 1n+2\frac1{n+2}, откъдето an+1>0a_{n+1}\gt{}0. Индукцията е завършена.
Отвори задачатаMathNetISL 2006 A2Условие — източник

Задача A3

Пълен запис
Условие
Редицата c0,c1,…,cn,…c_0,c_1,\ldots,c_n,\ldots е зададена с c0=1c_0=1, c1=0c_1=0 и cn+2=cn+1+cnc_{n+2}=c_{n+1}+c_n за n≥0n\ge0. Нека SS е множеството от наредени двойки (x,y)(x,y), за които съществува крайно множество JJ от положителни цели числа, такова че x=∑j∈Jcj,y=∑j∈Jcj−1.x=\sum_{j\in J}c_j,\qquad y=\sum_{j\in J}c_{j-1}. Докажете, че съществуват реални числа α,β,m,M\alpha,\beta,m,M със следното свойство: наредена двойка от неотрицателни цели числа (x,y)(x,y) удовлетворява неравенството m<αx+βy<Mm\lt{}\alpha x+\beta y\lt{}M тогава и само тогава, когато (x,y)∈S(x,y)\in S. Бележка. Сборът по елементите на празното множество се счита за 00.
РешениеНека φ=1+52,ψ=1−52\varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2} са корените на уравнението t2−t−1=0t^2-t-1=0. Тогава φψ=−1\varphi\psi=-1, φ+ψ=1\varphi+\psi=1 и 1+ψ=ψ21+\psi=\psi^2. Лесна индукция дава cn=φn−1−ψn−1φ−ψза n≥0.c_n=\frac{\varphi^{n-1}-\psi^{n-1}}{\varphi-\psi}\quad\text{за }n\ge0.Ако α,β,m,M\alpha,\beta,m,M имат исканото свойство, то понеже (cn,cn−1)∈S(c_n,c_{n-1})\in S за всяко n≥1n\ge1, изразът αcn+βcn−1=\alpha c_n+\beta c_{n-1}=15((αφ+β)φn−2−(αψ+β)ψn−2)\frac1{\sqrt5}\left((\alpha\varphi+\beta)\varphi^{n-2}-(\alpha\psi+\beta)\psi^{n-2}\right) трябва да е ограничен при n→∞n\to\infty. Тъй като φ>1\varphi\gt{}1 и −1<ψ<0-1\lt{}\psi\lt{}0, получаваме αφ+β=0\alpha\varphi+\beta=0. Ще вземем например α=ψ,β=1.\alpha=\psi,\qquad \beta=1.За това избиране имаме cnψ+cn−1=ψn−1(n≥1).c_n\psi+c_{n-1}=\psi^{n-1}\quad(n\ge1). За крайно множество J⊂NJ\subset\mathbb N да означим aJ=∑j∈Jcj,bJ=∑j∈Jcj−1.a_J=\sum_{j\in J}c_j,\qquad b_J=\sum_{j\in J}c_{j-1}. Тогава за всяка двойка (aJ,bJ)∈S(a_J,b_J)\in S е изпълнено ψaJ+bJ=∑j∈Jψj−1.(1)\psi a_J+b_J=\sum_{j\in J}\psi^{j-1}.\tag{1} Понеже −1<ψ<0-1\lt{}\psi\lt{}0, имаме −1=∑r=0∞ψ2r+1<∑j∈Jψj−1<-1=\sum_{r=0}^{\infty}\psi^{2r+1}\lt{}\sum_{j\in J}\psi^{j-1}\lt{}∑r=0∞ψ2r=1−ψ=φ.\sum_{r=0}^{\infty}\psi^{2r}=1-\psi=\varphi. Следователно всяка двойка от SS удовлетворява −1<ψx+y<φ,-1\lt{}\psi x+y\lt{}\varphi, така че можем да вземем m=−1m=-1 и M=φM=\varphi. Остава обратната посока. Ще докажем лема: ако x,yx,y са неотрицателни цели числа и −1<ψx+y<φ,-1\lt{}\psi x+y\lt{}\varphi, то съществува множество J⊂NJ\subset\mathbb N, за което ψx+y=∑j∈Jψj−1.(2)\psi x+y=\sum_{j\in J}\psi^{j-1}.\tag{2}При x=y=0x=y=0 вземаме J=∅J=\emptyset. Нека поне едно от x,yx,y е ненулево. Числото ψx+y\psi x+y може да се представи като ψx+y=ψi1+⋯+ψik,\psi x+y=\psi^{i_1}+\cdots+\psi^{i_k}, където i1≤⋯≤iki_1\le\cdots\le i_k са неотрицателни цели числа; например вземаме xx събираеми ψ\psi и yy събираеми 11. Сред всички такива представяния избираме представяне с минимална дължина kk, а сред тях лексикографски минимална редица от показатели j1≤⋯≤jkj_1\le\cdots\le j_k. Достатъчно е да докажем, че j1,…,jkj_1,\ldots,j_k са различни. Да допуснем, че jr=jr+1j_r=j_{r+1} за някое rr. Ако jr≥2j_r\ge2, използваме равенството 2ψ2=1+ψ32\psi^2=1+\psi^3 и заменяме двата показателя jr,jr+1j_r,j_{r+1} с jr−2j_r-2 и jr+1j_r+1. Това не променя сбора, понеже 2ψjr=ψjr−2(1+ψ3)=ψjr−2+ψjr+1,2\psi^{j_r}=\psi^{j_r-2}(1+\psi^3)=\psi^{j_r-2}+\psi^{j_r+1}, но прави редицата от показатели по-малка, противоречие. Ако jr=jr+1=0j_r=j_{r+1}=0, в минимално представяне не може да има показател 11, защото 1+ψ=ψ21+\psi=\psi^2 би намалило броя на събираемите. Затова ψx+y≥2+ψ3+ψ5+ψ7+⋯=2−ψ2=φ,\psi x+y\ge 2+\psi^3+\psi^5+\psi^7+\cdots=2-\psi^2=\varphi, против условието. Ако jr=jr+1=1j_r=j_{r+1}=1, аналогично няма показатели 00 и 22, и получаваме ψx+y≤2ψ+ψ4+ψ6+ψ8+⋯=2ψ−ψ3=−1,\psi x+y\le 2\psi+\psi^4+\psi^6+\psi^8+\cdots=2\psi-\psi^3=-1, пак против условието. Лемата е доказана. Нека сега (x,y)(x,y) е двойка от неотрицателни цели числа с −1<ψx+y<φ-1\lt{}\psi x+y\lt{}\varphi. По лемата има J⊂NJ\subset\mathbb N, за което (2) е изпълнено. От (1) за съответните aJ,bJa_J,b_J имаме ψx+y=ψaJ+bJ.\psi x+y=\psi a_J+b_J. Понеже ψ\psi е ирационално, а x,y,aJ,bJx,y,a_J,b_J са цели числа, следва x=aJx=a_J и y=bJy=b_J. Значи (x,y)∈S(x,y)\in S и избраните α=ψ,β=1,m=−1,M=φ\alpha=\psi,\quad \beta=1,\quad m=-1,\quad M=\varphi вършат работа.
Отвори задачатаMathNetISL 2006 A3Условие — източник

Задача A4

Пълен запис
Условие
Докажете неравенството ∑i<jaiajai+aj≤\sum_{i\lt{}j}\frac{a_i a_j}{a_i+a_j}\len2(a1+a2+⋯+an)∑i<jaiaj \frac{n}{2(a_1+a_2+\cdots+a_n)}\sum_{i\lt{}j}a_i a_j за положителни реални числа a1,a2,…,ana_1,a_2,\ldots,a_n.
РешениеНека S=∑iai.S=\sum_i a_i. Да означим с LL и RR съответно лявата и дясната страна на исканото неравенство. Ще използваме тъждеството ∑i<j(ai+aj)=(n−1)∑iai=(n−1)S.(1)\sum_{i\lt{}j}(a_i+a_j)=(n-1)\sum_i a_i=(n-1)S.\tag{1}За лявата страна имаме L=∑i<jaiajai+aj=∑i<j14(ai+aj−(ai−aj)2ai+aj)=n−14S−14∑i<j(ai−aj)2ai+aj.(2)\begin{aligned}L&=\sum_{i\lt{}j}\frac{a_i a_j}{a_i+a_j}=\sum_{i\lt{}j}\frac14\left(a_i+a_j-\frac{(a_i-a_j)^2}{a_i+a_j}\right)\\&=\frac{n-1}{4}S-\frac14\sum_{i\lt{}j}\frac{(a_i-a_j)^2}{a_i+a_j}.\tag{2}\end{aligned}Сега изразяваме ∑i<jaiaj\sum_{i\lt{}j}a_i a_j по два начина: ∑i<jaiaj=12(S2−∑iai2)\sum_{i\lt{}j}a_i a_j=\frac12\left(S^2-\sum_i a_i^2\right) и, прилагайки (1) към квадратите ai2a_i^2, ∑i<jaiaj=12∑i<j(ai2+aj2−(ai−aj)2)=\sum_{i\lt{}j}a_i a_j=\frac12\sum_{i\lt{}j}\left(a_i^2+a_j^2-(a_i-a_j)^2\right)=n−12∑iai2−12∑i<j(ai−aj)2.\frac{n-1}{2}\sum_i a_i^2-\frac12\sum_{i\lt{}j}(a_i-a_j)^2. Умножаваме първото равенство по n−1n-1 и прибавяме второто. Получаваме n∑i<jaiaj=n−12S2−12∑i<j(ai−aj)2.n\sum_{i\lt{}j}a_i a_j=\frac{n-1}{2}S^2-\frac12\sum_{i\lt{}j}(a_i-a_j)^2. Следователно R=n2S∑i<jaiaj=R=\frac{n}{2S}\sum_{i\lt{}j}a_i a_j=n−14S−14∑i<j(ai−aj)2S.(3)\frac{n-1}{4}S-\frac14\sum_{i\lt{}j}\frac{(a_i-a_j)^2}{S}.\tag{3}Остава да сравним (2) и (3). За всяка двойка i<ji\lt{}j имаме S≥ai+ajS\ge a_i+a_j, откъдето 1S≤1ai+aj.\frac1S\le\frac1{a_i+a_j}. Понеже в (2) и (3) изваждаме неотрицателни членове, оттук следва L≤RL\le R, както трябваше да се докаже.
Отвори задачатаMathNetISL 2006 A4Условие — източник

Задача A5

Пълен запис
Условие
Нека a,b,ca,b,c са страните на триъгълник. Докажете, че x2b+c−ab+c−a+x2c+a−bc+a−b\frac{\sqrt{\vphantom{x^2}b+c-a}}{\sqrt b+\sqrt c-\sqrt a}+\frac{\sqrt{\vphantom{x^2}c+a-b}}{\sqrt c+\sqrt a-\sqrt b}+x2a+b−ca+b−c≤+\frac{\sqrt{\vphantom{x^2}a+b-c}}{\sqrt a+\sqrt b-\sqrt c}\le3.3.
РешениеПърво да отбележим, че всички знаменатели са положителни; например a+b>x2a+b>c.\sqrt a+\sqrt b\gt{}\sqrt{\vphantom{x^2}a+b}\gt{}\sqrt c. Нека x=b+c−a,y=c+a−b,z=a+b−c.x=\sqrt b+\sqrt c-\sqrt a,\qquad y=\sqrt c+\sqrt a-\sqrt b,\qquad z=\sqrt a+\sqrt b-\sqrt c. Тогава b+c−a=(z+x2)2+(x+y2)2−(y+z2)2=b+c-a=\left(\frac{z+x}{2}\right)^2+\left(\frac{x+y}{2}\right)^2-\left(\frac{y+z}{2}\right)^2=x2−12(x−y)(x−z).x^2-\frac12(x-y)(x-z). Следователно x2b+c−ab+c−a=x21−(x−y)(x−z)2x2≤\frac{\sqrt{\vphantom{x^2}b+c-a}}{\sqrt b+\sqrt c-\sqrt a}=\sqrt{\vphantom{x^2}1-\frac{(x-y)(x-z)}{2x^2}}\le1−(x−y)(x−z)4x2,1-\frac{(x-y)(x-z)}{4x^2}, където използвахме неравенството x21+2u≤1+u\sqrt{\vphantom{x^2}1+2u}\le1+u. Аналогично получаваме x2c+a−bc+a−b≤1−(z−x)(z−y)4z2\frac{\sqrt{\vphantom{x^2}c+a-b}}{\sqrt c+\sqrt a-\sqrt b}\le1-\frac{(z-x)(z-y)}{4z^2} и x2a+b−ca+b−c≤1−(y−z)(y−x)4y2.\frac{\sqrt{\vphantom{x^2}a+b-c}}{\sqrt a+\sqrt b-\sqrt c}\le1-\frac{(y-z)(y-x)}{4y^2}. Значи е достатъчно да докажем (x−y)(x−z)x2+(y−z)(y−x)y2\frac{(x-y)(x-z)}{x^2}+\frac{(y-z)(y-x)}{y^2}+(z−x)(z−y)z2≥+\frac{(z-x)(z-y)}{z^2}\ge0.(1)0.\tag{1}По симетрия можем да считаме, че x≤y≤zx\le y\le z. Тогава (x−y)(x−z)x2=(y−x)(z−x)x2≥\frac{(x-y)(x-z)}{x^2}=\frac{(y-x)(z-x)}{x^2}\ge(y−x)(z−y)y2=−(y−z)(y−x)y2,\frac{(y-x)(z-y)}{y^2}=-\frac{(y-z)(y-x)}{y^2}, а също (z−x)(z−y)z2≥0.\frac{(z-x)(z-y)}{z^2}\ge0. Това доказва (1), а с него и исканото неравенство.
Отвори задачатаMathNetISL 2006 A5Условие — източник

Задача A6

Пълен запис
Условие
Намерете най-малкото число MM, за което неравенството ∣ab(a2−b2)+bc(b2−c2)+ca(c2−a2)∣≤\left|ab(a^2-b^2)+bc(b^2-c^2)+ca(c^2-a^2)\right|\leM(a2+b2+c2)2 M(a^2+b^2+c^2)^2 е изпълнено за всички реални числа a,b,ca,b,c.
РешениеЩе докажем, че най-малката константа е M=9232.M=\frac{9\sqrt2}{32}.Първо разглеждаме кубичния полином P(t)=tb(t2−b2)+bc(b2−c2)+ct(c2−t2).P(t)=tb(t^2-b^2)+bc(b^2-c^2)+ct(c^2-t^2). Лесно се проверява, че P(b)=P(c)=P(−b−c)=0P(b)=P(c)=P(-b-c)=0. Понеже старшият коефициент е b−cb-c, получаваме P(t)=(b−c)(t−b)(t−c)(t+b+c).P(t)=(b-c)(t-b)(t-c)(t+b+c). Следователно лявата страна на неравенството е ∣P(a)∣=∣(b−c)(a−b)(a−c)(a+b+c)∣.|P(a)|=|(b-c)(a-b)(a-c)(a+b+c)|. Задачата се свежда до намиране на най-малкото MM, за което ∣(b−c)(a−b)(a−c)(a+b+c)∣≤|(b-c)(a-b)(a-c)(a+b+c)|\leM(a2+b2+c2)2.(1) M(a^2+b^2+c^2)^2.\tag{1}Изразът вляво е симетричен по a,b,ca,b,c, затова можем да приемем a≤b≤ca\le b\le c. Тогава ∣(a−b)(b−c)∣=(b−a)(c−b)≤|(a-b)(b-c)|=(b-a)(c-b)\le((b−a)+(c−b)2)2=(c−a)24,\left(\frac{(b-a)+(c-b)}2\right)^2=\frac{(c-a)^2}{4},(2)\tag{2} като равенство има точно когато 2b=a+c2b=a+c. Освен това 3(c−a)2≤2((b−a)2+(c−b)2+(c−a)2),(3)3(c-a)^2\le2\left((b-a)^2+(c-b)^2+(c-a)^2\right),\tag{3} отново с равенство точно когато 2b=a+c2b=a+c. От (2) и (3) следва ∣(b−c)(a−b)(a−c)(a+b+c)∣≤14∣(c−a)3(a+b+c)∣≤14x2(2((b−a)2+(c−b)2+(c−a)2)3)3(a+b+c)2.\begin{aligned}|(b-c)(a-b)(a-c)(a+b+c)|&\le\frac14\left|(c-a)^3(a+b+c)\right|\\&\le\frac14\sqrt{\vphantom{x^2}\left(\frac{2((b-a)^2+(c-b)^2+(c-a)^2)}3\right)^3(a+b+c)^2}. \end{aligned} Прилагаме претегленото AM-GM неравенство и получаваме ∣(b−c)(a−b)(a−c)(a+b+c)∣≤22((b−a)2+(c−b)2+(c−a)2+(a+b+c)24)2=9232(a2+b2+c2)2.\begin{aligned}|(b-c)(a-b)(a-c)(a+b+c)|&\le\frac{\sqrt2}{2}\left(\frac{(b-a)^2+(c-b)^2+(c-a)^2+(a+b+c)^2}{4}\right)^2\\&=\frac{9\sqrt2}{32}(a^2+b^2+c^2)^2. \end{aligned} Значи (1) е вярно за M=9232M=\frac{9\sqrt2}{32}. Остава да видим, че тази константа не може да се намали. Равенство в горната оценка се получава, когато 2b=a+c2b=a+c и (b−a)2+(c−b)2+(c−a)23=(a+b+c)2.\frac{(b-a)^2+(c-b)^2+(c-a)^2}{3}=(a+b+c)^2. След заместване b=(a+c)/2b=(a+c)/2 второто условие става 2(c−a)2=9(a+c)2,2(c-a)^2=9(a+c)^2, тоест условията за равенство са 2b=a+c,(c−a)2=18b2.2b=a+c,\qquad (c-a)^2=18b^2. Ако вземем b=1b=1, получаваме a=1−322,c=1+322.a=1-\frac32\sqrt2,\qquad c=1+\frac32\sqrt2. За тази тройка, а също и за всички пропорционални на нея тройки и техните пермутации, има равенство. Следователно най-малката възможна стойност е M=9232.M=\frac{9\sqrt2}{32}.
Отвори задачатаMathNetISL 2006 A6Условие — източник

Задача C1

Пълен запис
Условие
Имаме n≥2n\ge2 лампи L1,…,LnL_1,\ldots,L_n в редица; всяка от тях е или включена, или изключена. Всяка секунда едновременно променяме състоянието на всяка лампа по следния начин: - ако лампата LiL_i и нейните съседи (само един съсед за i=1i=1 или i=ni=n, два съседи за останалите ii) са в едно и също състояние, тогава LiL_i се изключва; - в противен случай LiL_i се включва. Първоначално всички лампи са изключени освен най-лявата, която е включена. а) Докажете, че има безброй много цели числа nn, за които в някой момент всички лампи ще бъдат изключени. б) Докажете, че има безброй много цели числа nn, за които лампите никога няма да бъдат всички изключени.
Решениеа) Опитите с малки nn подсказват, че всяко nn от вида 2k2^k трябва да върши работа. Това наистина е така. Нека AkA_k е матрицата с размери 2k×2k2^k\times2^k, чиито редове описват развитието на системата с елементи 00 и 11 съответно за изключена и включена лампа. Първият ред е началното състояние [1,0,0,…,0][1,0,0,\ldots,0], а последният ред е състоянието след 2k−12^k-1 секунди. Ще докажем, чепоследният ред на Ak е [1,1,1,…,1].\text{последният ред на }A_k\text{ е }[1,1,1,\ldots,1].Тогава още една промяна дава [0,0,0,…,0][0,0,0,\ldots,0], което е достатъчно. Доказваме твърдението с индукция по kk. Случаят k=1k=1 е очевиден. Нека твърдението е вярно за някое k≥1k\ge1 и да запишем Ak+1A_{k+1} в блоков видAk+1=(AkOkBkCk),A_{k+1}=\begin{pmatrix}A_k&O_k\\ B_k&C_k\end{pmatrix},където четирите блока са с размери 2k×2k2^k\times2^k. След mm секунди последната единица в реда може да бъде най-много на позиция m+1m+1, следователно OkO_k е нулевата матрица. По индукционното предположение последният ред на [Ak Ok][A_k\ O_k] е [1,…,1,0,…,0][1,\ldots,1,0,\ldots,0], с 2k2^k единици и 2k2^k нули. Следващият ред е[0,…,0⏟2k−1,1,1,0,…,0⏟2k−1].[\underbrace{0,\ldots,0}_{2^k-1},1,1,\underbrace{0,\ldots,0}_{2^k-1}].Той е симетричен спрямо средата си и тази симетрия се запазва във всички следващи редове, защото правилото за промяна е симетрично наляво-надясно. Значи BkB_k е огледален образ на CkC_k. В частност най-дясната колона на BkB_k съвпада с най-лявата колона на CkC_k. Сега си представяме матрицата CkC_k отделно от останалата част на Ak+1A_{k+1}. Ако я развиваме по същото правило, първият елемент на всеки ред зависи само от първите два елемента на предходния ред според това дали са равни. Когато върнем CkC_k обратно в Ak+1A_{k+1}, елементите вляво от тази първа колона са точно техни копия. Следователно развитието вътре в CkC_k е същото, независимо дали гледаме CkC_k отделно или като блок в Ak+1A_{k+1}. Тъй като първият ред на CkC_k е [1,0,…,0][1,0,\ldots,0], получаваме Ck=AkC_k=A_k. Последният ред на AkA_k е [1,1,…,1][1,1,\ldots,1]; същият е последният ред на CkC_k, а значи и на BkB_k, който е негов огледален образ. Следователно последният ред на Ak+1A_{k+1} се състои само от единици и индукцията е завършена. б) Един възможен безкраен клас е n=2k+1n=2^k+1 за k≥1k\ge1. Развитието може да се представи с матрица A\mathcal A с ширина 2k+12^k+1 и безкрайно много редове. Първите 2k2^k реда образуват разгледаната по-горе матрица AkA_k, към която вдясно е добавена една нулева колона. В следващия ред получаваме [0,0,…,0,1,1][0,0,\ldots,0,1,1]. Това обаче е вторият ред на A\mathcal A, записан в обратен ред. Следващите редове ще бъдат огледални копия на предишните, започвайки от втория ред. Затова конфигурацията [1,1,0,…,0,0][1,1,0,\ldots,0,0], тоест вторият ред на A\mathcal A, ще се появи отново. Оттук нататък редовете се повтарят периодично и нулев ред няма да се появи.
Отвори задачатаMathNetISL 2006 C1Условие — източник

Задача C2

Пълен запис
Условие
Диагонал на правилен 20062006-ъгълник се нарича нечетен, ако краищата му разделят контура на две части, всяка от които съдържа нечетен брой страни. Страните също се считат за нечетни диагонали. Нека 20062006-ъгълникът е разбит на триъгълници чрез 20032003 непресичащи се диагонала. Намерете най-големия възможен брой равнобедрени триъгълници с две нечетни страни.
РешениеЩе наричаме равнобедрен триъгълник нечетен, ако има две нечетни страни, а триъгълник от разбирането, който е едновременно равнобедрен и нечетен, ще наричаме за краткост изо-нечетен. Лема. Нека ABAB е един от диагоналите на разбирането и нека L\mathcal L е по-късата част от контура на 20062006-ъгълника с краища A,BA,B. Ако L\mathcal L се състои от nn отсечки, то броят на изо-нечетните триъгълници с върхове върху L\mathcal L не надминава n/2n/2. Доказателство. За n=2n=2 това е очевидно. Нека 2<n≤10032\lt{}n\le1003 и да предположим твърдението за всички по-къси дъги. Нека L\mathcal L с краища A,BA,B се състои от nn отсечки. Избираме най-дългия диагонал PQPQ, който е страна на изо-нечетен триъгълник PQSPQS с всички върхове върху L\mathcal L; ако такъв триъгълник няма, няма какво да доказваме. Всеки триъгълник с върхове върху L\mathcal L е тъпоъгълен или правоъгълен, така че SS е върхът при равните страни на PQSPQS. Можем да считаме, че точките A,P,S,Q,BA,P,S,Q,B лежат върху L\mathcal L в този ред и я разделят на четири части LAP\mathcal L_{AP}, LPS\mathcal L_{PS}, LSQ\mathcal L_{SQ}, LQB\mathcal L_{QB}, като крайните части може да се свеждат до точка. По избора на PQPQ изо-нечетен триъгълник не може да има върхове едновременно върху LAP\mathcal L_{AP} и LQB\mathcal L_{QB}. Затова всеки изо-нечетен триъгълник вътре в L\mathcal L, различен от PQSPQS, има всичките си върхове върху една от четирите части. Прилагаме индукционното предположение към всяка част и събираме оценките. Получаваме, че броят на тези триъгълници не надминава n/2n/2, като понеже LPS\mathcal L_{PS} и LSQ\mathcal L_{SQ} съдържат нечетен брой страни, съответните две оценки са строги и оставят общ запас 1/2+1/21/2+1/2. Този запас покрива и самия триъгълник PQSPQS. Лемата е доказана. Сега разглеждаме най-дългия диагонал XYXY от разбирането. Нека LXY\mathcal L_{XY} е по-късата от двете части на контура с краища X,YX,Y, а XYZXYZ е триъгълникът от разбирането с връх ZZ извън LXY\mathcal L_{XY}. Триъгълникът XYZXYZ е остроъгълен или правоъгълен; иначе някоя от отсечките XZ,YZXZ,YZ би била по-дълга от XYXY. Ако означим с LXZ\mathcal L_{XZ} и LYZ\mathcal L_{YZ} двете съответни части, лемата, приложена към LXY\mathcal L_{XY}, LXZ\mathcal L_{XZ} и LYZ\mathcal L_{YZ}, показва, че общо има не повече от 2006/22006/2 изо-нечетни триъгълници, освен евентуално ако XYZXYZ е такъв. Но ако XYZXYZ е изо-нечетен, тогава XZXZ и YZYZ са нечетни диагонали и съответните оценки са строги, така че и с включен XYZXYZ общият брой пак не надминава 10031003. Оценката се достига. Достатъчно е да изберем един връх на 20062006-ъгълника и да прокараме начупена линия, която свързва всеки втори връх, започвайки от избрания. Понеже 20062006 е четно, линията се затваря. Така вече получаваме нужните 10031003 изо-нечетни триъгълника, а останалата част може да се триангулира произволно.
Отвори задачатаMathNetISL 2006 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека SS е крайно множество от точки в равнината, като никои три от тях не лежат на една права. За всеки изпъкнал многоъгълник PP с върхове от SS нека a(P)a(P) е броят на върховете на PP, а b(P)b(P) е броят на точките от SS, които са извън PP. Докажете, че за всяко реално число xx е изпълнено∑Pxa(P)(1−x)b(P)=1,\sum_P x^{a(P)}(1-x)^{b(P)}=1,където сумата е по всички изпъкнали многоъгълници с върхове от SS. Бележка. Отсечка, точка и празното множество се считат за изпъкнали многоъгълници съответно с 22, 11 и 00 върха.
РешениеЗа всеки изпъкнал многоъгълник PP с върхове от SS нека c(P)c(P) е броят на точките от SS, които са вътре в PP. Тогава a(P)+b(P)+c(P)=na(P)+b(P)+c(P)=n, където n=∣S∣n=|S|. Да означим 1−x1-x с yy. Имаме∑Pxa(P)yb(P)=∑Pxa(P)yb(P)(x+y)c(P)=\sum_P x^{a(P)}y^{b(P)}=\sum_P x^{a(P)}y^{b(P)}(x+y)^{c(P)}=∑P∑i=0c(P)(c(P)i)xa(P)+iyb(P)+c(P)−i.\sum_P\sum_{i=0}^{c(P)}\binom{c(P)}i x^{a(P)+i}y^{b(P)+c(P)-i}.Разглеждаме този израз като хомогенен полином от степен nn по независимите променливи x,yx,y. След разкриване той е сума от членове xryn−rx^r y^{n-r} за 0≤r≤n0\le r\le n, умножени по неотрицателни цели коефициенти. За фиксирано rr коефициентът пред xryn−rx^r y^{n-r} брои начините да изберем изпъкнал многоъгълник PP и след това част от точките на SS вътре в PP, така че броят на върховете на PP плюс броят на избраните вътрешни точки да е rr. Това е същото като просто да изберем rr-елементно подмножество TT на SS. Съответствието е биекция: всяко такова TT се разлага по единствен начин на върховете на изпъкналата си обвивка и на част от точките вътре в тази обвивка. Следователно коефициентът пред xryn−rx^r y^{n-r} е (nr)\binom nr. Получаваме∑Pxa(P)yb(P)=\sum_P x^{a(P)}y^{b(P)}=∑r=0n(nr)xryn−r=(x+y)n=1,\sum_{r=0}^n\binom nr x^r y^{n-r}=(x+y)^n=1,както трябваше да се докаже.
Отвори задачатаMathNetISL 2006 C3Условие — източник

Задача C4

Пълен запис
Условие
Торта има форма на квадрат n×nn\times n, съставен от n2n^2 единични квадратчета. В някои единични квадратчета има ягоди, така че всеки ред и всяка колона съдържат точно една ягода; да наречем тази конфигурация A\mathcal A. Нека B\mathcal B е друга такава конфигурация. Да предположим, че всеки мрежов правоъгълник с един връх в горния ляв ъгъл на тортата съдържа не по-малко ягоди от конфигурацията B\mathcal B, отколкото от конфигурацията A\mathcal A. Докажете, че B\mathcal B може да се получи от A\mathcal A чрез краен брой превключвания, дефинирани така: Едно превключване избира мрежов правоъгълник само с две ягоди, разположени в горния десен и долния ляв ъгъл на този правоъгълник, и премества тези две ягоди в другите два ъгъла.
РешениеЩе означаваме единичните квадратчета с главни букви; OO е горното ляво квадратче. За две квадратчета X,YX,Y нека [XY][XY] е най-малкият мрежов правоъгълник, който ги съдържа. Поставяме слива във всяко квадратче от целевата конфигурация B\mathcal B. За квадратче XX нека a(X)a(X) и b(X)b(X) са съответно броят на ягодите и сливите в [OX][OX]. По условие a(X)≤b(X)a(X)\le b(X) за всяко XX, като ако никъде няма строго неравенство, двете конфигурации съвпадат и няма какво да доказваме. Ще покажем, че с едно допустимо превключване можем да получим конфигурация A′\mathcal A' такава, чеa(X)≤a′(X)≤b(X)за всяко X,a(X)\le a'(X)\le b(X)\quad\text{за всяко }X,∑Xa(X)<∑Xa′(X).(1)\qquad \sum_X a(X)\lt{}\sum_X a'(X).\tag{1}Тук a′(X)a'(X) е дефинирано аналогично, а сумите са по всички единични квадратчета. Това е достатъчно, защото после прилагаме същия аргумент към A′\mathcal A', после към A′′\mathcal A'' и т.н. Строго нарастващите суми са ограничени от ∑Xb(X)\sum_X b(X), така че процесът завършва с конфигурация, в която всички ягоди съвпадат със сливите. Избираме най-горния ред, в който слива и ягода стоят в различни квадратчета PP и SS; ясно е, че PP е вляво от SS. В колоната през PP нека TT е горното, а BB долното квадратче. Ягодата в тази колона е под сливата, защото над реда на PP позициите на ягодите и сливите съвпадат. Следователно в областта [BS][BS] под [PS][PS] има поне една ягода. Нека VV е най-горната такава ягода. Нека WW е квадратчето в пресечната точка на реда през VV и колоната през SS, а RR е квадратчето, съседно на WW по връх нагоре-наляво. Твърдим, чеa(X)<b(X)за всяко X∈[PR].(2)a(X)\lt{}b(X)\quad\text{за всяко }X\in[PR].\tag{2}Наистина, ако X∈[PR]X\in[PR], то частта на [OX][OX] вляво от колоната през PP съдържа поне толкова сливи, колкото ягоди, по условие. В частта над реда през PP и SS има пълен баланс, а в оставащата част, тоест в правоъгълника [PX][PX], има слива в PP и няма ягода. Сега правим нужното превключване. Нека UU е квадратчето в пресечната точка на реда през PP и колоната през VV; някои от P,U,RP,U,R може да съвпадат. Преместваме ягодите от SS и VV в UU и WW. Тогаваa′(X)=a(X)+1за X∈[UR],a'(X)=a(X)+1\quad\text{за }X\in[UR],a′(X)=a(X)за останалите X.\qquad a'(X)=a(X)\quad\text{за останалите }X.Понеже [UR]⊂[PR][UR]\subset[PR], от (2) следва, че все още a′(X)≤b(X)a'(X)\le b(X) за всички XX. Условията (1) са изпълнени и доказателството е завършено.
Отвори задачатаMathNetISL 2006 C4Условие — източник

Задача C5

Пълен запис
Условие
(n,k)(n,k)-турнир е състезание с nn участници, проведено в kk кръга, такова че: (i) всеки участник играе във всеки кръг и всеки двама участници се срещат най-много веднъж; (ii) ако участник AA среща участник BB в кръг ii, участник CC среща участник DD в кръг ii, а участник AA среща участник CC в кръг jj, тогава участник BB среща участник DD в кръг jj. Намерете всички двойки (n,k)(n,k), за които съществува (n,k)(n,k)-турнир.
РешениеЗа всяко kk нека tkt_k е единственото цяло число, за което2tk−1<k+1≤2tk.2^{t_k-1}\lt{}k+1\le2^{t_k}.Ще докажем, че (n,k)(n,k)-турнир съществува тогава и само тогава, когато 2tk2^{t_k} дели nn. Първо да покажем достатъчност. Ако n=2tn=2^t, тогава има (n,k)(n,k)-турнир за всяко k≤2t−1k\le2^t-1. Нека SS е множеството от всички 00-11 редици с дължина tt. Означаваме участниците с елементите на SS. Ако α,β∈S\alpha,\beta\in S, нека α+β\alpha+\beta е почленното събиране по модул 22. За i=1,…,2t−1i=1,\ldots,2^t-1 нека ω(i)∈S\omega(i)\in S е двоичният запис на ii, допълнен с водещи нули до дължина tt. В кръг ii участникът α\alpha играе с участника α+ω(i)\alpha+\omega(i). Това е добре дефинирано, защото α+ω(i)=β+ω(i)\alpha+\omega(i)=\beta+\omega(i) влече α=β\alpha=\beta, а [α+ω(i)]+ω(i)=α[\alpha+\omega(i)]+\omega(i)=\alpha. Всеки участник играе във всеки кръг. Двама участници се срещат най-много веднъж, защото ω(i)≠ω(j)\omega(i)\ne\omega(j) за i≠ji\ne j. Остава да проверим (ii). Нека α\alpha среща β\beta в кръг ii, γ\gamma среща δ\delta в кръг ii, а α\alpha среща γ\gamma в кръг jj. Тогава β=α+ω(i)\beta=\alpha+\omega(i), δ=γ+ω(i)\delta=\gamma+\omega(i) и γ=α+ω(j)\gamma=\alpha+\omega(j). В кръг jj участникът β\beta играе сβ+ω(j)=[α+ω(i)]+ω(j)=\beta+\omega(j)=[\alpha+\omega(i)]+\omega(j)=[α+ω(j)]+ω(i)=γ+ω(i)=δ,[\alpha+\omega(j)]+\omega(i)=\gamma+\omega(i)=\delta,както се изисква. Ако n=2tsn=2^t s и k≤2t−1k\le2^t-1, вземаме ss несвързани копия на построения (2t,k)(2^t,k)-турнир и във всеки кръг обединяваме съответните срещи. Така получаваме (2ts,k)(2^t s,k)-турнир. Следователно условието 2tk∣n2^{t_k}\mid n е достатъчно. Да докажем необходимост. В произволен (n,k)(n,k)-турнир представяме участниците с точки и след всеки кръг свързваме с ребро всяка двойка, която е играла в този кръг. Нека GiG_i е графът след първите ii кръга. Казваме, че участник QQ е ii-съсед на PP, ако в GiG_i има път от PP до QQ; множеството на всички ii-съседи на участник наричаме негова ii-компонента. Две ii-компоненти са или равни, или не се пресичат. Ще покажем, че всяка kk-компонента има размер, делящ се на 2tk2^{t_k}. Нека Γ\Gamma е ii-компонентата на участник AA, а в кръг i+1i+1 участник AA среща участник BB с ii-компонента Δ\Delta. Твърдим, че в кръг i+1i+1 всеки участник от Γ\Gamma среща участник от Δ\Delta, и обратно. Нека C∈ΓC\in\Gamma и в кръг i+1i+1 той среща DD. Има редица A=X1,X2,…,Xm=CA=X_1,X_2,\ldots,X_m=C, в която XjX_j и Xj+1X_{j+1} са играли в някой от първите ii кръга. Нека XjX_j среща YjY_j в кръг i+1i+1; тогава Y1=BY_1=B и Ym=DY_m=D. Ако XjX_j и Xj+1X_{j+1} са играли в кръг r≤ir\le i, условие (ii) дава, че YjY_j и Yj+1Y_{j+1} също са играли в кръг rr. Следователно B=Y1,Y2,…,Ym=DB=Y_1,Y_2,\ldots,Y_m=D е път в GiG_i, така че D∈ΔD\in\Delta. По симетрия всеки участник от Δ\Delta среща участник от Γ\Gamma, откъдето ∣Γ∣=∣Δ∣|\Gamma|=|\Delta|. След кръг i+1i+1 компонентата на AA е Γ∪Δ\Gamma\cup\Delta. Понеже Γ\Gamma и Δ\Delta са или равни, или непресичащи се, размерът на компонентата или се запазва, или се удвоява. Ако Γ1,…,Γk\Gamma_1,\ldots,\Gamma_k са последователните компоненти на даден участник, то ∣Γ1∣=2|\Gamma_1|=2 и всеки следващ размер е или същият, или два пъти по-голям. Значи ∣Γk∣=2u|\Gamma_k|=2^u за някое uu. От друга страна този участник е играл с kk различни противници, всички в Γk\Gamma_k, така че ∣Γk∣≥k+1|\Gamma_k|\ge k+1. От определението на tkt_k следва u≥tku\ge t_k. Следователно всяка kk-компонента има размер, делящ се на 2tk2^{t_k}, а понеже компонентите разделят множеството от участници, получаваме 2tk∣n2^{t_k}\mid n. Това завършва доказателството.
Отвори задачатаMathNetISL 2006 C5Условие — източник

Задача N1

Пълен запис
Условие
Определете всички двойки цели числа (x,y)(x,y), удовлетворяващи уравнението 1+2x+22x+1=y2.1+2^x+2^{2x+1}=y^2.
РешениеОтговорът е (x,y)=(0,2),(0,−2),(4,23),(4,−23).(x,y)=(0,2),(0,-2),(4,23),(4,-23).Ако x<0x\lt{}0, лявата страна не може да бъде квадрат на цяло число: при x=−1x=-1 тя е 22, а при x≤−2x\le-2 дори не е цяло число. Значи x≥0x\ge0. Освен това заедно с всяко решение (x,y)(x,y) получаваме и решение (x,−y)(x,-y). При x=0x=0 имаме y2=4y^2=4, откъдето идват решенията (0,2)(0,2) и (0,−2)(0,-2). Нека занапред x>0x\gt{}0 и, по симетрия, y>0y\gt{}0. Преписваме уравнението като2x(1+2x+1)=(y−1)(y+1).2^x(1+2^{x+1})=(y-1)(y+1).Тук yy е нечетно, така че y−1y-1 и y+1y+1 са четни, като точно едно от тях се дели на 44. Следователно x≥3x\ge3, а един от двата множителя y−1y-1 и y+1y+1 се дели на 2x−12^{x-1}, но не и на 2x2^x. Затова можем да запишемy=2x−1m+ε,y=2^{x-1}m+\varepsilon,m е нечетно положително число,\qquad m\text{ е нечетно положително число},ε∈{−1,1}.\qquad \varepsilon\in\{-1,1\}.Заместваме това в уравнението и получаваме2x(1+2x+1)=(2x−1m+ε)2−1=2^x(1+2^{x+1})=(2^{x-1}m+\varepsilon)^2-1=22x−2m2+2xmε,2^{2x-2}m^2+2^xm\varepsilon,тоест1+2x+1=2x−2m2+mε.1+2^{x+1}=2^{x-2}m^2+m\varepsilon. Следователно1−εm=2x−2(m2−8).1-\varepsilon m=2^{x-2}(m^2-8).Ако ε=1\varepsilon=1, то при m≥3m\ge3 лявата страна е отрицателна, а дясната е положителна; случаят m=1m=1 също не удовлетворява последното равенство. Значи ε≠1\varepsilon\ne1. Остава ε=−1\varepsilon=-1. Тогава1+m=2x−2(m2−8).1+m=2^{x-2}(m^2-8).Дясната страна е положителна, следователно m≥3m\ge3. Понеже x≥3x\ge3, имаме1+m≥2(m2−8),1+m\ge2(m^2-8),откъдето 2m2−m−17≤02m^2-m-17\le0. Значи m≤3m\le3, а понеже mm е нечетно и m≥3m\ge3, получаваме m=3m=3. Последното равенство става 4=2x−24=2^{x-2}, така че x=4x=4, а после y=23⋅3−1=23y=2^3\cdot3-1=23. Заедно със симетричното решение y=−23y=-23 това дава пълния списък.
Отвори задачатаMathNetISL 2006 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека за x∈(0,1)x\in(0,1) числото y∈(0,1)y\in(0,1) е определено така: nn-тата цифра след десетичната запетая на yy е (2n)\left(2^n\right)-тата цифра след десетичната запетая на xx. Докажете, че ако xx е рационално, то и yy е рационално.
РешениеПонеже xx е рационално, можем да изберем десетичния му запис така, че от някой разряд нататък цифрите му да се повтарят периодично. Ще докажем, че същото е вярно и за десетичния запис на yy. Нека dd е дължината на периода на xx и нека d=2u⋅v,d=2^u\cdot v, където vv е нечетно. Ако v=1v=1, вземаме w=1w=1; иначе по теоремата на Ойлер съществува положително цяло число ww, например w=φ(v)w=\varphi(v), такова че 2w≡1(modv).2^w\equiv1\pmod{v}. Тогава за всяко nn имаме 2n+w=2n⋅2w≡2n(modv).2^{n+w}=2^n\cdot2^w\equiv2^n\pmod{v}. Освен това за n≥un\ge u е изпълнено 2n+w≡2n≡0(mod2u).2^{n+w}\equiv2^n\equiv0\pmod{2^u}. Следователно за всички n≥un\ge u получаваме 2n+w≡2n(modd).2^{n+w}\equiv2^n\pmod{d}.За достатъчно големи nn позициите 2n2^n и 2n+w2^{n+w} вече са след началната непериодична част на десетичния запис на xx. Понеже тези позиции са в един и същи клас по модул dd, съответните цифри на xx са равни. Но това точно означава, че (n+w)(n+w)-тата цифра на yy е равна на nn-тата цифра на yy за всички достатъчно големи nn. Значи десетичният запис на yy също е периодичен от някой разряд нататък, откъдето yy е рационално.
Отвори задачатаMathNetISL 2006 N2Условие — източник

Задача N3

Пълен запис
Условие
Редицата f(1),f(2),f(3),…f(1),f(2),f(3),\ldots е дефинирана чрезf(n)=1n(⌊n1⌋+⌊n2⌋+⋯+⌊nn⌋),f(n)=\frac1n\left(\left\lfloor\frac n1\right\rfloor+\left\lfloor\frac n2\right\rfloor+\cdots+\left\lfloor\frac nn\right\rfloor\right),където ⌊x⌋\lfloor x\rfloor означава цялата част на xx. а) Докажете, че f(n+1)>f(n)f(n+1)\gt{}f(n) за безброй много nn. б) Докажете, че f(n+1)<f(n)f(n+1)\lt{}f(n) за безброй много nn.
РешениеНека g(n)=nf(n)g(n)=nf(n) за n≥1n\ge1 и g(0)=0g(0)=0. За k=1,…,nk=1,\ldots,n имаме⌊nk⌋−⌊n−1k⌋=0,\left\lfloor\frac nk\right\rfloor-\left\lfloor\frac{n-1}k\right\rfloor=0,ако kk не дели nn, и⌊nk⌋−⌊n−1k⌋=1,\left\lfloor\frac nk\right\rfloor-\left\lfloor\frac{n-1}k\right\rfloor=1,ако kk дели nn. Следователно, ако d(n)d(n) е броят на положителните делители на nn, тоg(n)=⌊n1⌋+⌊n2⌋+⋯+⌊nn−1⌋+⌊nn⌋=⌊n−11⌋+⌊n−12⌋+⋯+⌊n−1n−1⌋+⌊n−1n⌋+d(n)=g(n−1)+d(n).\begin{aligned}g(n)&=\left\lfloor\frac n1\right\rfloor+\left\lfloor\frac n2\right\rfloor+\cdots+\left\lfloor\frac n{n-1}\right\rfloor+\left\lfloor\frac nn\right\rfloor\\&=\left\lfloor\frac{n-1}1\right\rfloor+\left\lfloor\frac{n-1}2\right\rfloor+\cdots+\left\lfloor\frac{n-1}{n-1}\right\rfloor+\left\lfloor\frac{n-1}n\right\rfloor+d(n)\\&=g(n-1)+d(n).\end{aligned}Оттукg(n)=d(1)+d(2)+⋯+d(n),g(n)=d(1)+d(2)+\cdots+d(n),тоестf(n)=d(1)+d(2)+⋯+d(n)n.f(n)=\frac{d(1)+d(2)+\cdots+d(n)}n.Значи f(n)f(n) е средното аритметично на d(1),d(2),…,d(n)d(1),d(2),\ldots,d(n). Достатъчно е да докажем, че неравенствата d(n+1)>f(n)d(n+1)\gt{}f(n) и d(n+1)<f(n)d(n+1)\lt{}f(n) се случват безброй много пъти. Имаме d(1)=1d(1)=1, а за n>1n\gt{}1 е вярно d(n)≥2d(n)\ge2, като равенство има точно когато nn е просто. Понеже f(6)=7/3>2f(6)=7/3\gt{}2, следва f(n)>2f(n)\gt{}2 за всички n≥6n\ge6. Има безброй много прости числа, така че за безброй много nn имаме d(n+1)=2<f(n)d(n+1)=2\lt{}f(n); това доказва б). За а) използваме, че редицата d(1),d(2),d(3),…d(1),d(2),d(3),\ldots е неограничена, например d(2k)=k+1d(2^k)=k+1. Следователно за безброй много nn е изпълненоd(n+1)>max⁡{d(1),d(2),…,d(n)},d(n+1)\gt{}\max\{d(1),d(2),\ldots,d(n)\},а за такива nn имаме d(n+1)>f(n)d(n+1)\gt{}f(n). Доказателството е завършено.
Отвори задачатаMathNetISL 2006 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека PP е полином от степен n>1n\gt{}1 с цели коефициенти и нека kk е произволно положително цяло число. Разглеждаме полиномаQ(x)=P(P(…P(P(x))…)),Q(x)=P(P(\ldots P(P(x))\ldots)),където има kk двойки скоби. Докажете, че QQ има не повече от nn цели неподвижни точки, тоест цели числа, удовлетворяващи Q(x)=xQ(x)=x.
РешениеТвърдението е очевидно, ако всяка цяла неподвижна точка на QQ е неподвижна точка и на PP. Затова нека съществува цяло x0x_0, за което Q(x0)=x0Q(x_0)=x_0, но P(x0)≠x0P(x_0)\ne x_0. Дефинираме xi+1=P(xi)x_{i+1}=P(x_i) за i=0,1,2,…i=0,1,2,\ldots; тогава xk=x0x_k=x_0. Ще използваме факта, чеP(u)−P(v) се дели на u−v за различни цели u,P(u)-P(v)\text{ се дели на }u-v\text{ за различни цели }u,v.(1)v.\tag{1}Наистина, ако P(x)=∑aixiP(x)=\sum a_i x^i, то всяко ai(ui−vi)a_i(u^i-v^i) се дели на u−vu-v. Следователно всеки член във веригата от ненулеви разликиx0−x1,x1−x2,…,x_0-x_1,\quad x_1-x_2,\quad \ldots,xk−1−xk,xk−xk+1(2)\quad x_{k-1}-x_k,\quad x_k-x_{k+1}\tag{2}дели следващия. Понеже xk−xk+1=x0−x1x_k-x_{k+1}=x_0-x_1, всички тези разлики имат равни абсолютни стойности. Ако xm=min⁡(x1,…,xk)x_m=\min(x_1,\ldots,x_k), то xm−1−xm=−(xm−xm+1)x_{m-1}-x_m=-(x_m-x_{m+1}), следователно xm−1=xm+1≠xmx_{m-1}=x_{m+1}\ne x_m. Значи последователните разлики в (2) са с противоположни знаци и редицата x0,x1,x2,…x_0,x_1,x_2,\ldots се редува между две различни стойности. Така всяка цяла неподвижна точка на QQ, която не е неподвижна за PP, е неподвижна точка на P(P(x))P(P(x)). Достатъчно е да докажем, че такива цели точки са най-много nn. Нека aa е една от тях и b=P(a)≠ab=P(a)\ne a, така че a=P(b)a=P(b). Вземаме друга цяла неподвижна точка α\alpha на P(P(x))P(P(x)) и пишем P(α)=βP(\alpha)=\beta, P(β)=αP(\beta)=\alpha. Числата α\alpha и β\beta може да съвпадат, но всяко от тях е различно от aa и bb. Прилагайки (1) към двойките (α,a)(\alpha,a), (β,b)(\beta,b), (α,b)(\alpha,b) и (β,a)(\beta,a), получаваме, че α−a\alpha-a и β−b\beta-b се делят взаимно, а също α−b\alpha-b и β−a\beta-a се делят взаимно. Следователноα−b=±(β−a),α−a=±(β−b).(3)\alpha-b=\pm(\beta-a),\qquad \alpha-a=\pm(\beta-b).\tag{3}Ако и в двете равенства знакът е плюс, изваждането дава a−b=b−aa-b=b-a, противоречие. Значи поне едно от равенствата в (3) е със знак минус, а тогава α+β=a+b\alpha+\beta=a+b, тоестa+b−α−P(α)=0.a+b-\alpha-P(\alpha)=0.Означаваме a+ba+b с CC. Показахме, че всяка цяла неподвижна точка на QQ е корен на полиномаF(x)=C−x−P(x).F(x)=C-x-P(x).Това е вярно и за aa и bb. Понеже PP има степен n>1n\gt{}1, полиномът FF също има степен nn, така че има най-много nn корена. Следователно QQ има най-много nn цели неподвижни точки.
Отвори задачатаMathNetISL 2006 N4Условие — източник

Задача N5

Пълен запис
Условие
Намерете всички цели решения на уравнениетоx7−1x−1=y5−1.\frac{x^7-1}{x-1}=y^5-1.
РешениеУравнението няма цели решения. Първо доказваме лема. Лема. Ако xx е цяло число и простото число pp дели x7−1x−1\frac{x^7-1}{x-1}, то или p≡1(mod7)p\equiv1\pmod7, или p=7p=7. Доказателство. По условие pp дели x7−1x^7-1, а по малката теорема на Ферма pp дели xp−1−1x^{p-1}-1. Ако 7∤p−17\nmid p-1, то gcd⁡(p−1,7)=1\gcd(p-1,7)=1, следователно съществуват цели k,mk,m с 7k+(p−1)m=17k+(p-1)m=1. Тогаваx≡x7k+(p−1)m≡(x7)k(xp−1)m≡1(modp).x\equiv x^{7k+(p-1)m}\equiv (x^7)^k(x^{p-1})^m\equiv1\pmod p.Затоваx7−1x−1=1+x+⋯+x6≡7(modp).\frac{x^7-1}{x-1}=1+x+\cdots+x^6\equiv7\pmod p.Следователно pp дели 77, тоест p=7p=7. Лемата е доказана. От лемата следва, че всеки положителен делител dd на x7−1x−1\frac{x^7-1}{x-1} удовлетворява d≡0(mod7)d\equiv0\pmod7 или d≡1(mod7)d\equiv1\pmod7. Да допуснем, че (x,y)(x,y) е цяло решение. Имаме y−1>0y-1\gt{}0, защото x7−1x−1>0\frac{x^7-1}{x-1}\gt{}0 за x≠1x\ne1. Понеже y−1y-1 дели x7−1x−1=y5−1\frac{x^7-1}{x-1}=y^5-1, от предходния абзац следва y≡1(mod7)y\equiv1\pmod7 или y≡2(mod7)y\equiv2\pmod7. В първия случай1+y+y2+y3+y4≡5(mod7),1+y+y^2+y^3+y^4\equiv5\pmod7,а във втория1+y+y2+y3+y4≡3(mod7).1+y+y^2+y^3+y^4\equiv3\pmod7.И двете възможности противоречат на факта, че положителният делител 1+y+y2+y3+y41+y+y^2+y^3+y^4 на x7−1x−1\frac{x^7-1}{x-1} трябва да е сравним с 00 или 11 по модул 77. Следователно цели решения няма.
Отвори задачатаMathNetISL 2006 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека a>b>1a\gt{}b\gt{}1 са взаимнопрости положителни цели числа. Теглото на цяло число cc, означено с w(c)w(c), е най-малката възможна стойност на ∣x∣+∣y∣|x|+|y| по всички двойки цели числа x,yx,y, за коитоax+by=c.ax+by=c.Цяло число cc се нарича локален шампион, ако w(c)≥w(c±a)w(c)\ge w(c\pm a) и w(c)≥w(c±b)w(c)\ge w(c\pm b). Намерете всички локални шампиони и определете броя им.
РешениеЩе наричаме двойката цели числа (x,y)(x,y) представяне на cc, ако ax+by=cax+by=c и ∣x∣+∣y∣=w(c)|x|+|y|=w(c). Характеризираме локалните шампиони чрез три наблюдения. Лема 1. Ако (x,y)(x,y) е представяне на локален шампион cc, то xy<0xy\lt{}0. Доказателство. Да допуснем първо, че x≥0x\ge0 и y≥0y\ge0. Всички представяния на cc и c+ac+a са от видаc=a(x−kb)+b(y+ka),c=a(x-kb)+b(y+ka),c+a=a(x+1−kb)+b(y+ka),\qquad c+a=a(x+1-kb)+b(y+ka),където kk е цяло число. От минималността на x+yx+y имамеx+y=∣x∣+∣y∣≤∣x−kb∣+∣y+ka∣x+y=|x|+|y|\le |x-kb|+|y+ka|за всяко kk. От w(c+a)≤w(c)w(c+a)\le w(c) съществува kk, за което∣x+1−kb∣+∣y+ka∣≤x+y.|x+1-kb|+|y+ka|\le x+y.Тогава(x+1−kb)+(y+ka)≤∣x+1−kb∣+∣y+ka∣≤(x+1-kb)+(y+ka)\le |x+1-kb|+|y+ka|\lex+y≤∣x−kb∣+∣y+ka∣. x+y\le |x-kb|+|y+ka|.Сравнявайки първия и третия израз, получаваме k(a−b)+1≤0k(a-b)+1\le0, откъдето k<0k\lt{}0. Сравнявайки втория и четвъртия, получаваме ∣x+1−kb∣≤∣x−kb∣|x+1-kb|\le |x-kb|, откъдето kb>xkb\gt{}x, противоречие. Случаят x,y≤0x,y\le0 се свежда до този чрез замяна на c,x,yc,x,y с −c,−x,−y-c,-x,-y. Лемата е доказана. Оттук нататък пишем c=ax−byc=ax-by и разглеждаме случаите, в които xx и yy са ненулеви и с един и същ знак; по лема 1 не губим общност. Лема 2. Нека c=ax−byc=ax-by, където ∣x∣+∣y∣|x|+|y| е минимално и x,yx,y са с един и същ знак. Числото cc е локален шампион тогава и само тогава, когато ∣x∣<b|x|\lt{}b и∣x∣+∣y∣=⌊a+b2⌋.|x|+|y|=\left\lfloor\frac{a+b}{2}\right\rfloor.Доказателство. Без ограничение нека x,y>0x,y\gt{}0. Имамеc−a=a(x−1)−by,c+b=ax−b(y−1),c-a=a(x-1)-by,\qquad c+b=ax-b(y-1),така че w(c−a)<w(c)w(c-a)\lt{}w(c) и w(c+b)<w(c)w(c+b)\lt{}w(c). Ако cc е локален шампион, разглеждаме w(c+a)w(c+a). Съществува цяло kk, за коетоc+a=a(x+1−kb)−b(y−ka),c+a=a(x+1-kb)-b(y-ka),∣x+1−kb∣+∣y−ka∣≤x+y.\qquad |x+1-kb|+|y-ka|\le x+y.Това не е възможно за k≤0k\le0, следователно k>0k\gt{}0. Разглеждаме изпъкналата функцияF(t)=∣x+1−bt∣+∣y−at∣−(x+y).F(t)=|x+1-bt|+|y-at|-(x+y).Имаме F(0)=1F(0)=1 и F(k)≤0F(k)\le0. По изпъкналост F(1)≤(1−1/k)F(0)+(1/k)F(k)<1F(1)\le (1-1/k)F(0)+(1/k)F(k)\lt{}1, а F(1)F(1) е цяло число, следователно F(1)≤0F(1)\le0. Значи∣x+1−b∣+∣y−a∣≤x+y.|x+1-b|+|y-a|\le x+y.От друга страна, от c=a(x−b)−b(y−a)c=a(x-b)-b(y-a) и минималността следваx+y≤∣x−b∣+∣y−a∣.x+y\le |x-b|+|y-a|.Комбинирайки тези неравенства, получаваме ∣x+1−b∣≤∣x−b∣|x+1-b|\le |x-b|, което е равносилно на x<bx\lt{}b. Аналогично от w(c−b)w(c-b) получаваме y<ay\lt{}a. Сега ∣x−b∣=b−x|x-b|=b-x, ∣x+1−b∣=b−x−1|x+1-b|=b-x-1 и ∣y−a∣=a−y|y-a|=a-y, затоваa+b−12≤x+y≤a+b2,\frac{a+b-1}{2}\le x+y\le\frac{a+b}{2},откъдето x+y=⌊a+b2⌋x+y=\left\lfloor\frac{a+b}{2}\right\rfloor. Обратно, нека 0<x<b0\lt{}x\lt{}b и x+y=⌊a+b2⌋x+y=\left\lfloor\frac{a+b}{2}\right\rfloor. Тогава и 0<y<a0\lt{}y\lt{}a. Имамеw(c+a)≤w(c+a)\le∣x+1−b∣+∣y−a∣=a+b−1−(x+y)≤x+y=w(c) |x+1-b|+|y-a|=a+b-1-(x+y)\le x+y=w(c)иw(c−b)≤∣x−b∣+∣y+1−a∣=a+b−1−(x+y)≤w(c-b)\le |x-b|+|y+1-a|=a+b-1-(x+y)\lex+y=w(c). x+y=w(c).Следователно cc е локален шампион. Лемата е доказана. Лема 3. Ако c=ax−byc=ax-by, числата x,yx,y са с един и същ знак, ∣x∣<b|x|\lt{}b, ∣y∣<a|y|\lt{}a и ∣x∣+∣y∣=⌊a+b2⌋|x|+|y|=\left\lfloor\frac{a+b}{2}\right\rfloor, то w(c)=∣x∣+∣y∣w(c)=|x|+|y|. Доказателство. За x,y>0x,y\gt{}0 имамеw(c)=min⁡k∈Z{∣x−kb∣+∣y−ka∣}.w(c)=\min_{k\in\mathbb Z}\{|x-kb|+|y-ka|\}.Ако k≤0k\le0, сумата е поне x+yx+y. Ако k≥1k\ge1, то∣x−kb∣+∣y−ka∣=|x-kb|+|y-ka|=(kb−x)+(ka−y)=k(a+b)−(x+y)≥(kb-x)+(ka-y)=k(a+b)-(x+y)\ge(2k−1)(x+y)≥x+y.(2k-1)(x+y)\ge x+y.Така w(c)=x+yw(c)=x+y; случаят с отрицателни x,yx,y е същият. Лемата е доказана. От трите леми следва, че множеството на локалните шампиони еC={±(ax−by):0<x<b, x+y=⌊a+b2⌋}.C=\left\{\pm(ax-by):0\lt{}x\lt{}b,\ x+y=\left\lfloor\frac{a+b}{2}\right\rfloor\right\}.Нека C+C^+ и C−C^- са частите, получени съответно със знаците ++ и −-. И двете са аритметични прогресии с дължина b−1b-1 и разлика a+ba+b. Ако aa и bb са нечетни, тогава C+=C−C^+=C^-. Наистина a(−x)−b(−y)=a(b−x)−b(a−y)a(-x)-b(-y)=a(b-x)-b(a-y), а x+y=(a+b)/2x+y=(a+b)/2 е равносилно на (b−x)+(a−y)=(a+b)/2(b-x)+(a-y)=(a+b)/2. В този случай има b−1b-1 локални шампиона. Ако aa и bb са с различна четност, тогава a+ba+b е нечетно и за c1∈C+c_1\in C^+, c2∈C−c_2\in C^- имаме2c1≡−2c2≡2(aa+b−12−b⋅0)≡−a(moda+b),2c_1\equiv -2c_2\equiv 2\left(a\frac{a+b-1}{2}-b\cdot0\right)\equiv -a\pmod{a+b},а следователно2c1−2c2≡−2a(moda+b).2c_1-2c_2\equiv -2a\pmod{a+b}.Тъй като a+ba+b е взаимнопросто с aa, множествата C+C^+ и C−C^- лежат в различни класове по модул a+ba+b. Значи CC е обединение на две непресичащи се аритметични прогресии и броят на локалните шампиони е 2(b−1)2(b-1). Отговорът е: локалните шампиони са точно числата±(ax−by)за 0<x<b и x+y=⌊a+b2⌋,\pm(ax-by)\quad\text{за }0\lt{}x\lt{}b\text{ и }x+y=\left\lfloor\frac{a+b}{2}\right\rfloor,като броят им е b−1b-1, ако aa и bb са нечетни, и 2(b−1)2(b-1) в противен случай.
Отвори задачатаMathNetISL 2006 N6Условие — източник

Задача N7

Пълен запис
Условие
Докажете, че за всяко положително цяло число nn съществува цяло число mm, такова че 2m+m2^m+m се дели на nn.
РешениеЩе докажем по индукция по dd следното по-силно твърдение: за всяко положително цяло число NN съществуват положителни цели числа b0,b1,…,bd−1b_0,b_1,\ldots,b_{d-1}, такива че за всяко i=0,1,…,d−1i=0,1,\ldots,d-1 имаме bi>Nb_i\gt{}N и2bi+bi≡i(modd).2^{b_i}+b_i\equiv i\pmod d.За i=0i=0 това дава търсеното твърдение. Базата d=1d=1 е тривиална. Нека a>1a\gt{}1 и да предположим, че твърдението е вярно за всички d<ad\lt{}a. Остатъците на 2i2^i по модул aa от някакъв момент нататък се повтарят периодично; нека MM е начало на периодичността, а kk е дължината на периода. Това означава, че 2M+k′≡2M(moda)2^{M+k'}\equiv2^M\pmod a точно когато k′k' е кратно на kk. Периодът не може да съдържа всичките aa остатъка, защото 00 или липсва, или е единственият нулев остатък в периода. Значи k<ak\lt{}a. Нека d=gcd⁡(a,k)d=\gcd(a,k), a′=a/da'=a/d и k′=k/dk'=k/d. Тогава 0<d<a0\lt{}d\lt{}a. По индукционното предположение съществуват b0,b1,…,bd−1b_0,b_1,\ldots,b_{d-1}, за които bi>max⁡(2M,N)b_i\gt{}\max(2^M,N) и2bi+bi≡i(modd)за i=0,1,…,d−1.(1)2^{b_i}+b_i\equiv i\pmod d\quad\text{за }i=0,1,\ldots,d-1.\tag{1}За всяко ii разглеждаме редицата от a′a' числа2bi+bi,2bi+k+(bi+k),…,2^{b_i}+b_i,\quad 2^{b_i+k}+(b_i+k),\quad \ldots,2bi+(a′−1)k+(bi+(a′−1)k).(2)\quad 2^{b_i+(a'-1)k}+(b_i+(a'-1)k).\tag{2}По модул aa тези числа са съответно сравними с2bi+bi,2bi+bi+k,2^{b_i}+b_i,\quad 2^{b_i}+b_i+k,…,2bi+bi+(a′−1)k,\quad \ldots,\quad 2^{b_i}+b_i+(a'-1)k,защото bi>2M>Mb_i\gt{}2^M\gt{}M и добавянето на кратно на периода kk не променя остатъка на степента на 22. Всички dd редици съдържат общо a′d=aa'd=a числа. Ще докажем, че те дават различни остатъци по модул aa. Нека2bi+bi+mk≡2bj+bj+nk(moda)2^{b_i}+b_i+mk\equiv2^{b_j}+b_j+nk\pmod aза i,j∈{0,1,…,d−1}i,j\in\{0,1,\ldots,d-1\} и m,n∈{0,1,…,a′−1}m,n\in\{0,1,\ldots,a'-1\}. Понеже d∣ad\mid a и d∣kd\mid k, от (1) следва i≡j(modd)i\equiv j\pmod d, тоест i=ji=j. Тогава mk≡nk(moda)mk\equiv nk\pmod a, следователно mk′≡nk′(moda′)mk'\equiv nk'\pmod{a'}. Понеже gcd⁡(a′,k′)=1\gcd(a',k')=1, получаваме m≡n(moda′)m\equiv n\pmod{a'}, а от избора на m,nm,n следва m=nm=n. Значи числата в (2), за всички ii, дават всички остатъци по модул aa. Освен това всички са по-големи от NN. Това доказва индукционната стъпка и с нея твърдението.
Отвори задачатаMathNetISL 2006 N7Условие — източник