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

IMO Shortlisted Problems

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

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

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

2009

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

11-12

16 задачи

Задача A1

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа, за които 1a+1b+1c=a+b+c.\frac1a+\frac1b+\frac1c=a+b+c. Докажете, че 1(2a+b+c)2+1(2b+c+a)2\frac1{(2a+b+c)^2}+\frac1{(2b+c+a)^2}+1(2c+a+b)2≤+\frac1{(2c+a+b)^2}\le316.\frac3{16}.
РешениеЗа положителни реални числа x,y,zx,y,z от неравенството между средно аритметично и средно геометрично имаме 2x+y+z=(x+y)+(x+z)≥2x2(x+y)(x+z),2x+y+z=(x+y)+(x+z)\ge 2\sqrt{\vphantom{x^2}(x+y)(x+z)}, откъдето 1(2x+y+z)2≤14(x+y)(x+z).\frac1{(2x+y+z)^2}\le \frac1{4(x+y)(x+z)}. Прилагайки това към трите събираеми от лявата страна, получаваме 1(2a+b+c)2+1(2b+c+a)2+1(2c+a+b)2≤14(a+b)(a+c)+14(b+c)(b+a)+14(c+a)(c+b)=(b+c)+(c+a)+(a+b)4(a+b)(b+c)(c+a)=a+b+c2(a+b)(b+c)(c+a).(1)\begin{aligned}\frac1{(2a+b+c)^2}&+\frac1{(2b+c+a)^2}+\frac1{(2c+a+b)^2}\\&\le \frac1{4(a+b)(a+c)}+\frac1{4(b+c)(b+a)}+\frac1{4(c+a)(c+b)}\\&=\frac{(b+c)+(c+a)+(a+b)}{4(a+b)(b+c)(c+a)}=\frac{a+b+c}{2(a+b)(b+c)(c+a)}.\tag{1}\end{aligned}Отново от AM-GM получаваме a2b+a2c+b2a+b2c+c2a+c2b≥6abc,a^2b+a^2c+b^2a+b^2c+c^2a+c^2b\ge 6abc, което е еквивалентно на 9(a+b)(b+c)(c+a)≥9(a+b)(b+c)(c+a)\ge8(a+b+c)(ab+bc+ca).(2) 8(a+b+c)(ab+bc+ca).\tag{2} Условието може да се запише във вида ab+bc+ca=abc(a+b+c).(3)ab+bc+ca=abc(a+b+c).\tag{3} Освен това, прилагайки три пъти неравенството x2y2+x2z2≥2x2yzx^2y^2+x^2z^2\ge 2x^2yz, имаме a2b2+b2c2+c2a2≥a2bc+ab2c+abc2,a^2b^2+b^2c^2+c^2a^2\ge a^2bc+ab^2c+abc^2, тоест (ab+bc+ca)2≥3abc(a+b+c).(4)(ab+bc+ca)^2\ge 3abc(a+b+c).\tag{4}Комбинираме (1), (2), (3) и (4): a+b+c2(a+b)(b+c)(c+a)=(a+b+c)(ab+bc+ca)2(a+b)(b+c)(c+a)⋅ab+bc+caabc(a+b+c)⋅abc(a+b+c)(ab+bc+ca)2≤92⋅8⋅1⋅13=316.\begin{aligned}\frac{a+b+c}{2(a+b)(b+c)(c+a)}&=\frac{(a+b+c)(ab+bc+ca)}{2(a+b)(b+c)(c+a)}\cdot\frac{ab+bc+ca}{abc(a+b+c)}\cdot\frac{abc(a+b+c)}{(ab+bc+ca)^2}\\&\le \frac9{2\cdot8}\cdot 1\cdot\frac13=\frac3{16}.\end{aligned} Така исканото неравенство е доказано.
Отвори задачатаMathNetISL 2009 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека ff е произволна функция от множеството на реалните числа в множеството на реалните числа. Докажете, че съществуват реални числа xx и yy, за които f(x−f(y))>yf(x)+x.f(x-f(y))\gt{}yf(x)+x.
РешениеДа допуснем противното, тоест f(x−f(y))≤yf(x)+xза всички реални x,f(x-f(y))\le yf(x)+x\quad\text{за всички реални }x,y.(1)y.\tag{1} Нека a=f(0)a=f(0). При y=0y=0 в (1) получаваме f(x−a)≤xf(x-a)\le x за всяко реално xx, което е еквивалентно на f(y)≤y+aза всяко реално y.(2)f(y)\le y+a\quad\text{за всяко реално }y.\tag{2}При x=f(y)x=f(y) в (1) и с помощта на (2) имаме a=f(0)≤yf(f(y))+f(y)≤yf(f(y))+y+a.a=f(0)\le yf(f(y))+f(y)\le yf(f(y))+y+a. За y>0y\gt{}0 оттук следва f(f(y))≥−1.(3)f(f(y))\ge -1.\tag{3} От (2) и (3) получаваме −1≤f(f(y))≤f(y)+a-1\le f(f(y))\le f(y)+a за всяко y>0y\gt{}0, следователно f(y)≥−a−1за всяко y>0.(4)f(y)\ge -a-1\quad\text{за всяко }y\gt{}0.\tag{4}Сега ще докажем, че f(x)≤0за всяко реално x.(5)f(x)\le0\quad\text{за всяко реално }x.\tag{5} Да допуснем, че за някое xx е изпълнено f(x)>0f(x)\gt{}0. Избираме yy, такова че y<x−aиy<−a−x−1f(x).y\lt{}x-a\quad\text{и}\quad y\lt{}\frac{-a-x-1}{f(x)}. Тогава по (2) имаме x−f(y)≥x−(y+a)>0,x-f(y)\ge x-(y+a)\gt{}0, а от (1) и (4) следва yf(x)+x≥f(x−f(y))≥−a−1.yf(x)+x\ge f(x-f(y))\ge -a-1. Значи y≥−a−x−1f(x),y\ge \frac{-a-x-1}{f(x)}, което противоречи на избора на yy. Следователно (5) е доказано. От (5) при x=0x=0 получаваме a=f(0)≤0a=f(0)\le0, а от (2) следва f(x)≤xза всяко реално x.(6)f(x)\le x\quad\text{за всяко реално }x.\tag{6} Накрая избираме yy, такова че y>0y\gt{}0 и y>−f(−1)−1y\gt{}-f(-1)-1, и полагаме x=f(y)−1x=f(y)-1. От (1), (5) и (6) получаваме f(−1)=f(x−f(y))≤yf(x)+x=yf(f(y)−1)+f(y)−1≤y(f(y)−1)−1≤−y−1.\begin{aligned}f(-1)&=f(x-f(y))\le yf(x)+x\\&=yf(f(y)-1)+f(y)-1\le y(f(y)-1)-1\le -y-1. \end{aligned} Това дава y≤−f(−1)−1y\le -f(-1)-1, противоречие с избора на yy. Следователно допускането е невъзможно и търсените x,yx,y съществуват.
Отвори задачатаMathNetISL 2009 A2Условие — източник

Задача A3

Пълен запис
Условие
Намерете всички функции ff от множеството на реалните числа в множеството на реалните числа, за които за всички реални x,yx,y е изпълнено f(xf(x+y))=f(yf(x))+x2.f(xf(x+y))=f(yf(x))+x^2.
РешениеЛесно се проверява, че функциите f(x)=xf(x)=x и f(x)=−xf(x)=-x удовлетворяват уравнението. Ще докажем, че други решения няма. Нека ff е решение. Ясно е, че ff не може да е константна. Първо ще докажем, че f(0)=0f(0)=0. Ако f(0)≠0f(0)\ne0, то при заместване (x,y)=(0,tf(0))(x,y)=\left(0,\frac{t}{f(0)}\right) получаваме f(0)=f(t)f(0)=f(t) за всяко реално tt, противоречие. Следователно f(0)=0f(0)=0. За произволно реално tt заместваме (x,y)=(t,0)(x,y)=(t,0) и (x,y)=(t,−t)(x,y)=(t,-t) и получаваме съответно f(tf(t))=f(0)+t2=t2f(tf(t))=f(0)+t^2=t^2 и f(tf(0))=f(−tf(t))+t2.f(tf(0))=f(-tf(t))+t^2. Понеже f(0)=0f(0)=0, второто равенство дава f(−tf(t))=−t2.f(-tf(t))=-t^2. Значи f(tf(t))=t2,f(tf(t))=t^2,f(−tf(t))=−t2за всяко реално t.(1)\qquad f(-tf(t))=-t^2\quad\text{за всяко реално }t.\tag{1} Оттук следва, че ff е сюрективна. Освен това, ако f(t)=0f(t)=0, то от f(tf(t))=t2f(tf(t))=t^2 следва t=0t=0, така че 00 е единственият корен на ff. Ще докажем, че f(−s)=−f(s)за всяко реално s.(2)f(-s)=-f(s)\quad\text{за всяко реално }s.\tag{2} Ако f(s)=0f(s)=0, това е ясно, понеже тогава s=0s=0. Нека f(s)<0f(s)\lt{}0. Избираме t≠0t\ne0, за което f(s)=−t2f(s)=-t^2. Тъй като f(t)≠0f(t)\ne0, има реално aa с af(t)=saf(t)=s. При заместване (x,y)=(t,a)(x,y)=(t,a) получаваме f(tf(t+a))=f(af(t))+t2=f(s)+t2=0.f(tf(t+a))=f(af(t))+t^2=f(s)+t^2=0. Понеже единственият корен на ff е 00 и t≠0t\ne0, следва f(t+a)=0f(t+a)=0, тоест a=−ta=-t. Така s=−tf(t)s=-tf(t) и f(−s)=f(tf(t))=t2=−f(s).f(-s)=f(tf(t))=t^2=-f(s).Нека сега f(s)>0f(s)\gt{}0. Избираме t≠0t\ne0, за което f(s)=t2f(s)=t^2, и реално aa, такова че tf(a)=stf(a)=s. При заместване (x,y)=(t,a−t)(x,y)=(t,a-t) получаваме f(s)=f(tf(a))=f((a−t)f(t))+t2=f(s)=f(tf(a))=f((a-t)f(t))+t^2=f((a−t)f(t))+f(s).f((a-t)f(t))+f(s). Следователно f((a−t)f(t))=0f((a-t)f(t))=0, откъдето (a−t)f(t)=0(a-t)f(t)=0. Понеже f(t)≠0f(t)\ne0, имаме a=ta=t, значи s=tf(t)s=tf(t) и f(−s)=f(−tf(t))=−t2=−f(s).f(-s)=f(-tf(t))=-t^2=-f(s). Това доказва (2). Заместваме последователно (x,y)=(s,t)(x,y)=(s,t), (x,y)=(t,−s−t)(x,y)=(t,-s-t) и (x,y)=(−s−t,s)(x,y)=(-s-t,s) в даденото уравнение. Получаваме f(sf(s+t))=f(tf(s))+s2,f(sf(s+t))=f(tf(s))+s^2, f(tf(−s))=f((−s−t)f(t))+t2f(tf(-s))=f((-s-t)f(t))+t^2 и f((−s−t)f(−t))=f(sf(−s−t))+(s+t)2.f((-s-t)f(-t))=f(sf(-s-t))+(s+t)^2. С помощта на (2) пренаписваме последните две равенства и след прехвърляне на членовете получаваме f(tf(s))−f(sf(s+t))=−s2,f(tf(s))-f(sf(s+t))=-s^2, f(tf(s))−f((s+t)f(t))=−t2,f(tf(s))-f((s+t)f(t))=-t^2, f((s+t)f(t))+f(sf(s+t))=(s+t)2.f((s+t)f(t))+f(sf(s+t))=(s+t)^2. Сумирането на тези три равенства дава 2f(tf(s))=2ts,2f(tf(s))=2ts, тоест f(tf(s))=tsза всички реални s,t.(3)f(tf(s))=ts\quad\text{за всички реални }s,t.\tag{3}Понеже ff е сюрективна, можем да изберем ss с f(s)=1f(s)=1. Тогава от (3) следва f(t)=stf(t)=st за всяко реално tt. Замествайки f(x)=sxf(x)=sx в първоначалното уравнение, получаваме s2=1s^2=1, тоест s=1s=1 или s=−1s=-1. Следователно единствените решения са f(x)=xиf(x)=−x.f(x)=x\quad\text{и}\quad f(x)=-x.
Отвори задачатаMathNetISL 2009 A3Условие — източник

Задача C1

Пълен запис
Условие
Разглеждаме 20092009 карти, всяка от които има една златна и една черна страна, подредени успоредно върху дълга маса. Първоначално всички карти показват златните си страни. Двама играчи, застанали откъм една и съща дълга страна на масата, играят, като се редуват да правят ходове. Всеки ход се състои в избиране на блок от 5050 последователни карти, най-лявата от които показва златната си страна, и обръщане на всичките 5050 карти, така че златните страни стават черни, а черните стават златни. Играчът, който последен може да направи позволен ход, печели. а) Завършва ли играта непременно? б) Има ли печеливша стратегия за започващия играч?
Решениеа) Да. Ще тълкуваме карта с черната страна нагоре като цифрата 00, а карта със златната страна нагоре като цифрата 11. Така всяка позиция на 20092009-те карти, прочетена отляво надясно, съответства еднозначно на неотрицателно цяло число, записано в двоична бройна система с 20092009 цифри, като допускаме водещи нули. При всеки позволен ход най-лявата обърната карта е златна, тоест съответната най-значима променена двоична цифра се сменя от 11 на 00, а всички промени вдясно от нея имат по-малка тежест. Следователно съответното цяло число строго намалява. Затова не може да има безкрайна игра и играта непременно завършва. б) Не; печеливша стратегия има вторият играч. Номерираме картите отдясно наляво с 1,2,…,20091,2,\ldots,2009 и разглеждаме множеството S={50i∣i=1,2,…,40}.S=\{50i\mid i=1,2,\ldots,40\}. Нека gng_n е броят на картите от SS, които показват златната си страна след nn хода. Първоначално g0=40g_0=40. Всеки позволен ход обръща блок от 5050 последователни карти, а такъв блок съдържа точно една карта от SS. Следователно при всеки ход числото gng_n се променя с точно 11: ∣gn+1−gn∣=1,|g_{n+1}-g_n|=1, докато играта продължава. Значи след нечетен брой ходове gng_n е нечетно, в частност gn>0g_n\gt{}0. Тогава, когато е ред на втория играч, поне една карта от SS показва златната си страна. Ако тази карта има номер 50i50i отдясно, то тя е най-лявата карта на блок от 5050 последователни карти, а именно блока с номера 50i,50i−1,…,50i−4950i,50i-1,\ldots,50i-49 отдясно. Следователно вторият играч винаги има позволен ход, когато дойде негов ред. Понеже играта завършва, а вторият играч никога не остава без ход на своя ред, без ход остава първият играч. Следователно започващият играч няма печеливша стратегия.
Отвори задачатаMathNetISL 2009 C1Условие — източник

Задача C2

Пълен запис
Условие
За всяко цяло число n≥2n\ge2 нека N(n)N(n) е максималният брой на тройки (ai,bi,ci)(a_i,b_i,c_i), i=1,…,N(n)i=1,\ldots,N(n), съставени от неотрицателни цели числа ai,bi,cia_i,b_i,c_i, за които са изпълнени условията: (1) ai+bi+ci=na_i+b_i+c_i=n за всяко i=1,…,N(n)i=1,\ldots,N(n); (2) ако i≠ji\ne j, то ai≠aja_i\ne a_j, bi≠bjb_i\ne b_j и ci≠cjc_i\ne c_j. Определете N(n)N(n) за всяко n≥2n\ge2.
РешениеОтговорът еN(n)=⌊2n3⌋+1.N(n)=\left\lfloor\frac{2n}{3}\right\rfloor+1.Нека {T1,…,TN}\{T_1,\ldots,T_N\} е произволна система от тройки, удовлетворяваща условията. Понеже aa-координатите са две по две различни неотрицателни цели числа, имаме∑i=1Nai≥∑i=1N(i−1)=N(N−1)2.\sum_{i=1}^N a_i\ge\sum_{i=1}^N(i-1)=\frac{N(N-1)}2.Аналогично∑i=1Nbi≥N(N−1)2\sum_{i=1}^N b_i\ge\frac{N(N-1)}2\quadи∑i=1Nci≥N(N−1)2.\text{и}\quad \sum_{i=1}^N c_i\ge\frac{N(N-1)}2.Събираме трите неравенства и използваме ai+bi+ci=na_i+b_i+c_i=n:3N(N−1)2≤∑i=1N(ai+bi+ci)=nN.\frac{3N(N-1)}2\le \sum_{i=1}^N(a_i+b_i+c_i)=nN.Следователно N≤⌊2n3⌋+1N\le\left\lfloor\frac{2n}{3}\right\rfloor+1. Остава да покажем, че тази граница се достига. Разглеждаме трите остатъка на nn по модул 33. Ако n=3k−1n=3k-1, вземаме следните 2k2k тройки:(s,k+1+s,2k−2−2s)(0≤s≤k−1)(s,k+1+s,2k-2-2s)\quad(0\le s\le k-1)и(k+s,s,2k−1−2s)(0≤s≤k−1).(k+s,s,2k-1-2s)\quad(0\le s\le k-1).Ако n=3kn=3k, вземаме следните 2k+12k+1 тройки:(s,k+s,2k−2s)(0≤s≤k)(s,k+s,2k-2s)\quad(0\le s\le k)и(k+1+s,s,2k−1−2s)(0≤s≤k−1).(k+1+s,s,2k-1-2s)\quad(0\le s\le k-1).Ако n=3k+1n=3k+1, вземаме следните 2k+12k+1 тройки:(s,k+s,2k+1−2s)(0≤s≤k)(s,k+s,2k+1-2s)\quad(0\le s\le k)и(k+1+s,s,2k−2s)(0≤s≤k−1).(k+1+s,s,2k-2s)\quad(0\le s\le k-1).Във всеки от трите случая всички координати са неотрицателни цели числа, сумата на координатите във всяка тройка е nn, а във всяка от трите координатни позиции числата са две по две различни. Така построяваме точно ⌊2n3⌋+1\left\lfloor\frac{2n}{3}\right\rfloor+1 тройки и доказателството е завършено.
Отвори задачатаMathNetISL 2009 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека nn е положително цяло число. Дадена е редица ε1,…,εn−1\varepsilon_1,\ldots,\varepsilon_{n-1}, където εi=0\varepsilon_i=0 или εi=1\varepsilon_i=1 за всяко i=1,…,n−1i=1,\ldots,n-1. Редиците a0,…,ana_0,\ldots,a_n и b0,…,bnb_0,\ldots,b_n се построяват по правилатаa0=b0=1,a1=b1=7,ai+1={2ai−1+3ai,ако εi=0,3ai−1+ai,ако εi=1,i=1,…,n−1,bi+1={2bi−1+3bi,ако εn−i=0,3bi−1+bi,ако εn−i=1,i=1,…,n−1.\begin{gathered} a_0=b_0=1,\qquad a_1=b_1=7,\\ a_{i+1}=\begin{cases}2a_{i-1}+3a_i,&\text{ако }\varepsilon_i=0,\\3a_{i-1}+a_i,&\text{ако }\varepsilon_i=1,\end{cases}\quad i=1,\ldots,n-1,\\ b_{i+1}=\begin{cases}2b_{i-1}+3b_i,&\text{ако }\varepsilon_{n-i}=0,\\3b_{i-1}+b_i,&\text{ако }\varepsilon_{n-i}=1,\end{cases}\quad i=1,\ldots,n-1. \end{gathered}Докажете, че an=bna_n=b_n.
РешениеЗа двоична дума w=σ1…σnw=\sigma_1\ldots\sigma_n и буква σ∈{0,1}\sigma\in\{0,1\} пишем wσ=σ1…σnσw\sigma=\sigma_1\ldots\sigma_n\sigma, σw=σσ1…σn\sigma w=\sigma\sigma_1\ldots\sigma_n, а w‾=σn…σ1\overline w=\sigma_n\ldots\sigma_1. Нека ∅\emptyset е празната дума. За двойка реални числа (u,v)(u,v) дефинираме числа (u,v)w(u,v)^w чрез(u,v)∅=v,(u,v)0=2u+3v,(u,v)1=3u+v,(u,v)wσε={2(u,v)w+3(u,v)wσ,ако ε=0,3(u,v)w+(u,v)wσ,ако ε=1.\begin{gathered} (u,v)^\emptyset=v,\qquad (u,v)^0=2u+3v,\qquad (u,v)^1=3u+v,\\ (u,v)^{w\sigma\varepsilon}=\begin{cases}2(u,v)^w+3(u,v)^{w\sigma},&\text{ако }\varepsilon=0,\\3(u,v)^w+(u,v)^{w\sigma},&\text{ако }\varepsilon=1. \end{cases} \end{gathered}С индукция по дължината на ww лесно се проверяват две свойства. Първо, за всички реални u1,v1,u2,v2,λ1,λ2u_1,v_1,u_2,v_2,\lambda_1,\lambda_2 имаме(λ1u1+λ2u2,λ1v1+λ2v2)w=\left(\lambda_1u_1+\lambda_2u_2,\lambda_1v_1+\lambda_2v_2\right)^w=λ1(u1,v1)w+λ2(u2,v2)w.(1)\lambda_1(u_1,v_1)^w+\lambda_2(u_2,v_2)^w.\tag{1}Второ, за ε∈{0,1}\varepsilon\in\{0,1\} е изпълнено(u,v)εw=(v,(u,v)ε)w.(2)(u,v)^{\varepsilon w}=\left(v,(u,v)^\varepsilon\right)^w.\tag{2}Ако w=ε1…εn−1w=\varepsilon_1\ldots\varepsilon_{n-1}, то от самите рекурентни формули следваan=(1,7)wиbn=(1,7)w‾.a_n=(1,7)^w\quad\text{и}\quad b_n=(1,7)^{\overline w}.Затова е достатъчно да докажем, че(1,7)w=(1,7)w‾(3)(1,7)^w=(1,7)^{\overline w}\tag{3}за всяка двоична дума ww. Доказваме (3) с индукция по дължината на ww. За дължини 00 и 11 твърдението е очевидно. Нека wσεw\sigma\varepsilon е дума с дължина поне 22 и нека твърдението вече е доказано за всички по-къси думи. Забелязваме, че(2,1)σ=7=(1,7)∅(σ∈{0,1}),(2,1)^\sigma=7=(1,7)^\emptyset\quad(\sigma\in\{0,1\}),(1,7)0=23,(1,7)1=10.\qquad (1,7)^0=23,\qquad (1,7)^1=10.Ако ε=0\varepsilon=0, от индукционното предположение, (1) и (2) получаваме(1,7)wσ0=2(1,7)w+3(1,7)wσ=2(1,7)w‾+3(1,7)σw‾=2(2,1)σw‾+3(1,7)σw‾=(7,23)σw‾=(1,7)0σw‾.\begin{aligned} (1,7)^{w\sigma0}&=2(1,7)^w+3(1,7)^{w\sigma}\\ &=2(1,7)^{\overline w}+3(1,7)^{\sigma\overline w}\\ &=2(2,1)^{\sigma\overline w}+3(1,7)^{\sigma\overline w}\\ &=(7,23)^{\sigma\overline w}=(1,7)^{0\sigma\overline w}. \end{aligned}Това е точно равенството (3) за думата wσ0w\sigma0. Ако ε=1\varepsilon=1, аналогично(1,7)wσ1=3(1,7)w+(1,7)wσ=3(1,7)w‾+(1,7)σw‾=3(2,1)σw‾+(1,7)σw‾=(7,10)σw‾=(1,7)1σw‾.\begin{aligned} (1,7)^{w\sigma1}&=3(1,7)^w+(1,7)^{w\sigma}\\ &=3(1,7)^{\overline w}+(1,7)^{\sigma\overline w}\\ &=3(2,1)^{\sigma\overline w}+(1,7)^{\sigma\overline w}\\ &=(7,10)^{\sigma\overline w}=(1,7)^{1\sigma\overline w}. \end{aligned}Индукцията е завършена, следователно an=bna_n=b_n.
Отвори задачатаMathNetISL 2009 C3Условие — източник

Задача C4

Пълен запис
Условие
Нека m≥1m\ge1 е цяло число. Разглеждаме разбиения на шахматна дъска 2m×2m2^m\times2^m на правоъгълници, съставени от клетки на дъската, при които всяка от 2m2^m-те клетки по един диагонал е отделен правоъгълник със страна 11. Определете най-малката възможна сума от периметрите на всички правоъгълници в такова разбиение.
РешениеОтговорът е(m+1)2m+2.(m+1)2^{m+2}.За дъска k×kk\times k въвеждаме стандартни координати на върховете на клетките и нека клетката CijC_{ij} в ред ii и стълб jj има върхове (i−1,j−1)(i-1,j-1), (i−1,j)(i-1,j), (i,j−1)(i,j-1), (i,j)(i,j). Без ограничение нека отделните клетки са CiiC_{ii}, i=1,…,ki=1,\ldots,k. Тогава двете частиBk=⋃1≤i<j≤kCijB_k=\bigcup_{1\le i\lt{}j\le k}C_{ij}\quadиBk′=⋃1≤j<i≤kCij\text{и}\quad B'_k=\bigcup_{1\le j\lt{}i\le k}C_{ij}могат да се разглеждат отделно, защото правоъгълник не може едновременно да покрива клетки от двете страни на диагонала. Ще докажем, че за k=2mk=2^m най-малката обща сума от периметрите в правоъгълно разбиение на BkB_k е m2m+1m2^{m+1}. Тогава за цялата дъска получаваме2⋅m2m+1+4⋅2m=(m+1)2m+2,2\cdot m2^{m+1}+4\cdot2^m=(m+1)2^{m+2},понеже диагоналните 2m2^m единични клетки имат общ периметър 4⋅2m4\cdot2^m. Първо построяваме разбиение на B2mB_{2^m} с общ периметър m2m+1m2^{m+1}. За m=0m=0 областта е празна. При прехода от mm към m+1m+1 областта B2m+1B_{2^{m+1}} се състои от квадрат 2m×2m2^m\times2^m в долния десен ъгъл и две области, съответно конгруентни на B2mB_{2^m}, прилепени отляво и отгоре. Квадратът има периметър 4⋅2m4\cdot2^m, а по индукционното предположение двете останали части имат общ периметър 2⋅m2m+12\cdot m2^{m+1}. Получаваме4⋅2m+2m2m+1=(m+1)2m+2,4\cdot2^m+2m2^{m+1}=(m+1)2^{m+2},което дава нужната конструкция. Остава долната граница. НекаDk=2klog⁡2k.D_k=2k\log_2 k.Ще докажем с индукция по kk, че всяко правоъгълно разбиение на BkB_k има общ периметър поне DkD_k. За k=1k=1 твърдението е ясно. Нека е вярно за всички по-малки положителни kk и разгледаме оптимално разбиение на BkB_k. Нека RR е правоъгълникът, който покрива клетката C1kC_{1k}, и нека (i,j)(i,j) е горният ляв връх на RR. Ще покажем, че i=ji=j. Ако i<ji\lt{}j, то поне една от отсечките от (i,j)(i,j) до (i+1,j)(i+1,j) и от (i,j)(i,j) до (i,j−1)(i,j-1) лежи върху граница на правоъгълник; без ограничение нека това е първата отсечка. Ако по хоризонталната права от (i,j)(i,j) до (i,k)(i,k) няма друга такава гранична отсечка, то над RR има правоъгълник с обща страна с RR, и слепването на двата правоъгълника би намалило общия периметър. Това противоречи на оптималността. Ако има ll с j<l<kj\lt{}l\lt{}k, за което отсечката от (i,l)(i,l) до (i+1,l)(i+1,l) лежи върху граница, преместваме горната страна на RR с единица надолу, а долните страни на правоъгълниците, които лежат върху отсечката от (i,j)(i,j) до (i,k)(i,k), също преместваме надолу. Получаваме допустимо разбиение с по-малък общ периметър, отново противоречие. Следователно наистина i=ji=j. Тогава разбиението се състои от RR, от разбиение на област, конгруентна на BiB_i, и от разбиение на област, конгруентна на Bk−iB_{k-i}. По индукционното предположение общият периметър е поне2(k−i)+2i+Di+Dk−i=2(k-i)+2i+D_i+D_{k-i}=2k+2ilog⁡2i+2(k−i)log⁡2(k−i).2k+2i\log_2 i+2(k-i)\log_2(k-i).Функцията f(x)=2xlog⁡2xf(x)=2x\log_2x е изпъкнала за x>0x\gt{}0, затова по неравенството на Йенсен дясната страна е минимална при i=k/2i=k/2. Получаваме долна граница2k+2⋅k2log⁡2k2+2⋅k2log⁡2k2=2klog⁡2k=Dk.2k+2\cdot\frac{k}{2}\log_2\frac{k}{2}+2\cdot\frac{k}{2}\log_2\frac{k}{2}=2k\log_2 k=D_k.За k=2mk=2^m това е m2m+1m2^{m+1}, което заедно с конструкцията доказва отговора.
Отвори задачатаMathNetISL 2009 C4Условие — източник

Задача C5

Пълен запис
Условие
Пет еднакви празни кофи с вместимост 22 литра стоят във върховете на правилен петоъгълник. Пепеляшка и злата й мащеха играят поредица от рундове. В началото на всеки рунд мащехата взема един литър вода от близката река и го разпределя произволно между петте кофи. После Пепеляшка избира две съседни кофи, излива съдържанието им обратно в реката и ги поставя на местата им. След това започва следващият рунд. Целта на мащехата е да накара някоя кофа да прелее, а целта на Пепеляшка е да предотврати това. Може ли мащехата да принуди преливане на кофа?
РешениеНе, мащехата не може да принуди преливане; Пепеляшка може да играе безкрайно дълго. Означаваме кофите с B0,B1,B2,B3,B4B_0,B_1,B_2,B_3,B_4, като BkB_k е съседна на Bk−1B_{k-1} и Bk+1B_{k+1}, а индексите се разглеждат по модул 55. Пепеляшка ще поддържа следните три условия в началото на всеки рунд: (1) две съседни кофи, например B1B_1 и B2B_2, са празни; (2) двете кофи, съседни на тях отвън, тук B0B_0 и B3B_3, съдържат общо най-много 11 литър; (3) оставащата кофа, тук B4B_4, съдържа най-много 11 литър. В началото условията са изпълнени, защото всички кофи са празни. Да предположим, че Пепеляшка ги е поддържала до началото на някой rr-ти рунд. Нека xkx_k е количеството вода в BkB_k в началото на този рунд, а yky_k е количеството след като мащехата е разпределила своя литър вода. По условията можем да считаме, че x1=x2=0x_1=x_2=0, x0+x3≤1x_0+x_3\le1 и x4≤1x_4\le1. След като мащехата добави общо един литър, получавамеy0+y1+y2+y3≤2.y_0+y_1+y_2+y_3\le2.Оттук поне едно от двете неравенстваy0+y2≤1илиy1+y3≤1y_0+y_2\le1\quad\text{или}\quad y_1+y_3\le1е вярно. По симетрия разглеждаме втория случай. Тогава Пепеляшка изпразва кофите B0B_0 и B4B_4. В началото на следващия рунд B0B_0 и B4B_4 са празни, така че условие (1) е изпълнено. От y1+y3≤1y_1+y_3\le1 следва условие (2), а понеже x2=0x_2=0, имаме и y2≤1y_2\le1, което дава условие (3). Следователно Пепеляшка може да поддържа трите условия с индукция за всички рундове. В частност всяка кофа винаги съдържа най-много 11 литър вода, така че кофа с вместимост 22 литра никога не прелива.
Отвори задачатаMathNetISL 2009 C5Условие — източник

Задача C8

Пълен запис
Условие
За всяко цяло число n≥2n\ge2 построяваме цяло число h(n)h(n) по следната процедура, приложена към десетичния запис на nn. Нека rr е най-дясната цифра на nn. (1) Ако r=0r=0, десетичният запис на h(n)h(n) се получава от десетичния запис на nn, като премахнем тази най-дясна цифра 00. (2) Ако 1≤r≤91\le r\le9, разделяме десетичния запис на nn на максимална дясна част RR, съставена само от цифри, не по-малки от rr, и лява част LL, която е празна или завършва с цифра, строго по-малка от rr. Тогава десетичният запис на h(n)h(n) се състои от записа на LL, последван от две копия на записа на R−1R-1. Например за n=17 151 345 543n=17\,151\,345\,543 имаме L=17 151L=17\,151, R=345 543R=345\,543 и h(n)=17 151 345 542 345 542h(n)=17\,151\,345\,542\,345\,542. Докажете, че започвайки от произволно цяло число n≥2n\ge2, повторното прилагане на hh води до числото 11 след краен брой стъпки.
РешениеОтъждествяваме целите числа n≥2n\ge2 с десетичните им записи, разглеждани като непразни низове от цифри, и разширяваме дефиницията на hh за всички такива низове. Ще построим строго намаляваща величина. Рекурсивно дефинираме функции f0,f1,…,f9f_0,f_1,\ldots,f_9. Функцията f9f_9 е дефинирана за низове, съставени само от деветки, включително празния низ ε\varepsilon; ако низът съдържа mm деветки, полагаме f9(x)=m+1f_9(x)=m+1. За k≤8k\le8 функцията fkf_k е дефинирана за всички низове, чиито цифри са поне kk. Записваме такъв низ във видаx=x0kx1k⋯xm−1kxm,x=x_0kx_1k\cdots x_{m-1}kx_m,където низовете xsx_s съдържат само цифри, не по-малки от k+1k+1; възможно е някои от тях да са празни, както и m=0m=0. Полагамеfk(x)=∑s=0m4fk+1(xs).f_k(x)=\sum_{s=0}^m4^{f_{k+1}(x_s)}.Ще използваме три факта. Първо, ако xx не съдържа цифри, по-малки от kk, тоfi(x)=4fi+1(x)(0≤i≤k−1),f_i(x)=4^{f_{i+1}(x)}\quad(0\le i\le k-1),и в частност fi(ε)=49−if_i(\varepsilon)=4^{9-i} за i=0,1,…,9i=0,1,\ldots,9. Второ, ако непразният низ xx не съдържа цифри, по-малки от kk, то fi(x)>fi(ε)f_i(x)\gt{}f_i(\varepsilon) за всички 0≤i≤k0\le i\le k. Това следва с обратна индукция по kk. Основното твърдение еf0(n)>f0(h(n)).(1)f_0(n)\gt{}f_0(h(n)).\tag{1}Тогава при повторно прилагане на hh не може да имаме безкрайна редица от низове, защото стойностите на f0f_0 строго намаляват. Значи след краен брой стъпки се стига до празния низ. От низ без водещи нули празният низ може да се получи само през1→00→0→ε,1\to00\to0\to\varepsilon,така че числото 11 непременно се появява по пътя. Остава да докажем (1). Ако последната цифра на nn е 00, записвамеn=x00x10⋯xm−10ε,n=x_0 0x_1 0\cdots x_{m-1}0\varepsilon,където низовете xix_i не съдържат цифрата 00. Тогава h(n)=x00x10⋯xm−1h(n)=x_0 0x_1 0\cdots x_{m-1} иf0(n)−f0(h(n))=f0(ε)>0.f_0(n)-f_0(h(n))=f_0(\varepsilon)\gt{}0.Нека сега последната цифра е r≥1r\ge1. Пишем дясната част като R=zrR=zr, където zz съдържа само цифри, не по-малки от rr. Ако лявата част LL е празна, достатъчно е да сравнимfr−1(zr)иfr−1(z(r−1)z(r−1)),f_{r-1}(zr)\quad\text{и}\quad f_{r-1}(z(r-1)z(r-1)),което ще бъде направено по-долу. Иначе пишем L=ykL=yk, където k≤r−1k\le r-1, и получавамеn=ykzr,h(n)=ykz(r−1)z(r−1).n=ykzr,\qquad h(n)=ykz(r-1)z(r-1).За празния низ приемаме условно d(ε)=9d(\varepsilon)=9, а иначе нека d(y)d(y) е най-малката цифра в yy. Първо разглеждаме случая d(y)≥kd(y)\ge k. Тогаваfk(n)−fk(h(n))=f_k(n)-f_k(h(n))=fk(zr)−fk(z(r−1)z(r−1)).f_k(zr)-f_k(z(r-1)z(r-1)).По първия факт е достатъчно да докажемfr−1(zr)>fr−1(z(r−1)z(r−1)).f_{r-1}(zr)\gt{}f_{r-1}(z(r-1)z(r-1)).Имаме, като при r=9r=9 приемаме f10(ε)=0f_{10}(\varepsilon)=0,fr−1(zr)=4fr(zr)=4fr(z)+4fr+1(ε)≥4⋅4fr(z)>4fr(z)+4fr(z)+4fr(ε)=fr−1(z(r−1)z(r−1)).\begin{aligned} f_{r-1}(zr)&=4^{f_r(zr)}=4^{f_r(z)+4^{f_{r+1}(\varepsilon)}}\\ &\ge4\cdot4^{f_r(z)}\\ &\gt{}4^{f_r(z)}+4^{f_r(z)}+4^{f_r(\varepsilon)}\\ &=f_{r-1}(z(r-1)z(r-1)). \end{aligned}Следователно fk(n)>fk(h(n))f_k(n)\gt{}f_k(h(n)), а отново по първия факт получаваме f0(n)>f0(h(n))f_0(n)\gt{}f_0(h(n)). Остава случаят d(y)<kd(y)\lt{}k. Ще докажем с низходяща индукция по d(y)=k,k−1,…,0d(y)=k,k-1,\ldots,0, че fi(n)>fi(h(n))f_i(n)\gt{}f_i(h(n)) за всички 0≤i≤d(y)0\le i\le d(y). Базата d(y)=kd(y)=k е вече доказаният случай. Нека t=d(y)<kt=d(y)\lt{}k и пишем y=utvy=utv, където vv не съдържа цифри, не по-големи от tt. По индукционното предположениеft+1(vkzr)>ft+1(vkz(r−1)z(r−1)).f_{t+1}(vkzr)\gt{}f_{t+1}(vkz(r-1)z(r-1)).Затоваft(n)−ft(h(n))=ft(vkzr)−ft(vkz(r−1)z(r−1))=4ft+1(vkzr)−4ft+1(vkz(r−1)z(r−1))>0.\begin{aligned} f_t(n)-f_t(h(n))&=f_t(vkzr)-f_t(vkz(r-1)z(r-1))\\ &=4^{f_{t+1}(vkzr)}-4^{f_{t+1}(vkz(r-1)z(r-1))}\gt{}0. \end{aligned}Това завършва индукцията и доказва (1).
Отвори задачатаMathNetISL 2009 C8Условие — източник

Задача N1

Пълен запис
Условие
В социален клуб има nn членове с членски номера 1,2,…,n1,2,\ldots,n. От време на време членовете изпращат подаръци на други членове, включително предмети, които вече са получили като подаръци. За да се избегне неловката ситуация някой да получи подарък, който сам е изпратил, клубът въвежда следното правило: член с номер aa има право да изпрати подарък на член с номер bb тогава и само тогава, когато a(b−1)a(b-1) се дели на nn. Докажете, че ако всички спазват това правило, никой няма да получи от друг член подарък, който преди това е изпратил. Еквивалентно: нека GG е насочен граф с върхове v1,v2,…,vnv_1,v_2,\ldots,v_n, като има ребро от vav_a към vbv_b тогава и само тогава, когато aa и bb са различни и a(b−1)a(b-1) се дели на nn. Докажете, че GG няма насочен цикъл.
РешениеЩе докажем еквивалентната графова формулировка. Да допуснем, че има насочен цикълvi1→vi2→⋯→vir→vi1.v_{i_1}\to v_{i_2}\to\cdots\to v_{i_r}\to v_{i_1}.От реброто vis→vis+1v_{i_s}\to v_{i_{s+1}} следваn∣is(is+1−1),n\mid i_s(i_{s+1}-1),тоестis≡isis+1(modn).i_s\equiv i_s i_{s+1}\pmod n.Прилагайки това последователно по цикъла, получаваме за всеки ssis≡isis+1≡isis+1is+2≡i_s\equiv i_s i_{s+1}\equiv i_s i_{s+1}i_{s+2}\equiv⋯≡i1i2⋯ir(modn),\cdots\equiv i_1i_2\cdots i_r\pmod n,където индексите се четат циклично. Следователноi1≡i2≡⋯≡ir(modn).i_1\equiv i_2\equiv\cdots\equiv i_r\pmod n.Но всички isi_s са между 11 и nn, така че те трябва да са равни. Това е невъзможно за насочен цикъл от различни върхове. Противоречието доказва твърдението.
Отвори задачатаMathNetISL 2009 N1Условие — източник

Задача N2

Пълен запис
Условие
Цяло положително число NN се нарича балансирано, ако N=1N=1 или ако може да се представи като произведение на четен брой, не непременно различни, прости числа. Дадени са положителни цели числа aa и bb, а полиномът PP е дефиниран сP(x)=(x+a)(x+b).P(x)=(x+a)(x+b).а) Докажете, че съществуват различни положителни цели числа aa и bb, за които всички числа P(1),P(2),…,P(50)P(1),P(2),\ldots,P(50) са балансирани. б) Докажете, че ако P(n)P(n) е балансирано за всяко положително цяло число nn, то a=ba=b.
РешениеДефинираме функция ff върху положителните цели числа с f(n)=0f(n)=0, ако nn е балансирано, и f(n)=1f(n)=1 в противен случай. Тогава за всички положителни цели n,mn,m имамеf(nm)≡f(n)+f(m)(mod2).f(nm)\equiv f(n)+f(m)\pmod 2.а) За всяко положително цяло число nn разглеждаме двоичната редица(f(n+1),f(n+2),…,f(n+50)).(f(n+1),f(n+2),\ldots,f(n+50)).Има само 2502^{50} такива редици, затова по принципа на Дирихле съществуват две различни положителни цели числа aa и bb, за които(f(a+1),f(a+2),…,f(a+50))=(f(a+1),f(a+2),\ldots,f(a+50))=(f(b+1),f(b+2),…,f(b+50)).(f(b+1),f(b+2),\ldots,f(b+50)).Тогава за 1≤k≤501\le k\le50 получавамеf(P(k))≡f(a+k)+f(b+k)=2f(a+k)≡0(mod2),f(P(k))\equiv f(a+k)+f(b+k)=2f(a+k)\equiv0\pmod 2,така че всички P(1),P(2),…,P(50)P(1),P(2),\ldots,P(50) са балансирани. б) Да допуснем, че P(n)P(n) е балансирано за всяко положително цяло число nn и че a<ba\lt{}b. За достатъчно голямо kk полагамеn=k(b−a)−a,n=k(b-a)-a,така че nn е положително. ТогаваP(n)=k(k+1)(b−a)2.P(n)=k(k+1)(b-a)^2.Понеже (b−a)2(b-a)^2 е балансирано, от балансираността на P(n)P(n) следваf(k)=f(k+1)f(k)=f(k+1)за всички достатъчно големи kk. Значи редицата f(k)f(k) трябва да стане константна от някой член нататък. Това е невъзможно, защото има произволно големи прости числа pp, за които f(p)=1f(p)=1, и произволно големи точни квадрати t2t^2, за които f(t2)=0f(t^2)=0. Следователно a=ba=b.
Отвори задачатаMathNetISL 2009 N2Условие — източник

Задача N3

Пълен запис
Условие
Нека ff е неконстантна функция от множеството на положителните цели числа в себе си, такава че a−ba-b дели f(a)−f(b)f(a)-f(b) за всеки две различни положителни цели числа aa и bb. Докажете, че съществуват безкрайно много прости числа pp, за които pp дели f(c)f(c) за някое положително цяло число cc.
РешениеДа допуснем противното: само крайно много прости числа p1,p2,…,pmp_1,p_2,\ldots,p_m делят някоя стойност на ff. За просто число pp нека vp(x)v_p(x) е показателят на pp в разлагането на положителното цяло число xx. Има безкрайно много положителни цели числа aa, за коитоvpi(a)>vpi(f(1))(i=1,2,…,m);v_{p_i}(a)\gt{}v_{p_i}(f(1))\quad(i=1,2,\ldots,m);например можем да вземем a=(p1p2⋯pm)αa=(p_1p_2\cdots p_m)^\alpha с достатъчно голямо α\alpha. За такова aa условието на задачата, приложено към числата a+1a+1 и 11, даваa∣f(a+1)−f(1).a\mid f(a+1)-f(1).Ще докажем, че непременно f(a+1)=f(1)f(a+1)=f(1). Ако това не е вярно, то поне за едно ii имамеvpi(f(a+1))≠vpi(f(1)),v_{p_i}(f(a+1))\ne v_{p_i}(f(1)),иначе двете положителни числа f(a+1)f(a+1) и f(1)f(1) биха имали едно и също разлагане на прости множители чрез p1,…,pmp_1,\ldots,p_m. За това ii получавамеvpi(f(a+1)−f(1))=v_{p_i}(f(a+1)-f(1))=min⁡{vpi(f(a+1)),vpi(f(1))}≤\min\{v_{p_i}(f(a+1)),v_{p_i}(f(1))\}\levpi(f(1))<vpi(a), v_{p_i}(f(1))\lt{}v_{p_i}(a),което противоречи на a∣f(a+1)−f(1)a\mid f(a+1)-f(1). Следователно f(a+1)=f(1)f(a+1)=f(1) за всички такива aa. Сега фиксираме произволно положително цяло число bb. За безкрайно много от горните стойности на aa имаме a+1≠ba+1\ne b, а условието на задачата даваa+1−b∣f(a+1)−f(b)=f(1)−f(b).a+1-b\mid f(a+1)-f(b)=f(1)-f(b).Лявата страна приема безкрайно много различни по абсолютна стойност стойности, а дясната страна е фиксирано цяло число. Това е възможно само ако f(1)−f(b)=0f(1)-f(b)=0. Значи f(b)=f(1)f(b)=f(1) за всяко положително цяло число bb, тоест ff е константна. Това противоречи на условието, така че първоначалното допускане е невярно.
Отвори задачатаMathNetISL 2009 N3Условие — източник

Задача N4

Пълен запис
Условие
Намерете всички положителни цели числа nn, за които съществува редица от положителни цели числа a1,a2,…,ana_1,a_2,\ldots,a_n, удовлетворяващаak+1=ak2+1ak−1+1−1a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1за всяко kk с 2≤k≤n−12\le k\le n-1.
РешениеОтговорът еn=1,2,3,4.n=1,2,3,4.Ако такава редица съществува за някое nn, то нейният начален отрязък дава редица за всяко по-малко положително цяло число. Затова е достатъчно да дадем пример за n=4n=4 и да докажем, че n=5n=5 е невъзможно. За n=4n=4 работи напримерa1=4,a2=33,a3=217,a4=1384,a_1=4,\qquad a_2=33,\qquad a_3=217,\qquad a_4=1384,което се проверява директно. Да допуснем, че има редица a1,a2,a3,a4,a5a_1,a_2,a_3,a_4,a_5 от положителни цели числа. Тогаваa22+1=(a1+1)(a3+1),a32+1=(a2+1)(a4+1),a42+1=(a3+1)(a5+1).\begin{aligned} a_2^2+1&=(a_1+1)(a_3+1),\\ a_3^2+1&=(a_2+1)(a_4+1),\\ a_4^2+1&=(a_3+1)(a_5+1). \end{aligned}Ако a1a_1 е нечетно, то a2a_2 също е нечетно, а от a22+1≡2(mod4)a_2^2+1\equiv2\pmod4 следва, че a3a_3 е четно. Тогава обаче четното число a2+1a_2+1 дели нечетното число a32+1a_3^2+1, невъзможно. Следователно a1a_1 е четно. Ако a2a_2 е нечетно, то от делимостта a2+1∣a32+1a_2+1\mid a_3^2+1 следва, че a3a_3 е нечетно, а после аналогично и a4a_4 е нечетно. Тогава a32+1=(a2+1)(a4+1)a_3^2+1=(a_2+1)(a_4+1) е произведение на две четни числа и се дели на 44, но за нечетно a3a_3 имаме a32+1≡2(mod4)a_3^2+1\equiv2\pmod4, противоречие. Значи a2a_2 е четно. Оттук последователно a3+1a_3+1 дели нечетното число a22+1a_2^2+1, после a4+1a_4+1 дели нечетното число a32+1a_3^2+1, и накрая a5+1a_5+1 дели нечетното число a42+1a_4^2+1. Следователно a3,a4,a5a_3,a_4,a_5 също са четни. Полагаме x=a2x=a_2 и y=a3y=a_3. Получаваме две положителни четни числа, за коитоx+1∣y2+1иy+1∣x2+1.(1)x+1\mid y^2+1\quad\text{и}\quad y+1\mid x^2+1.\tag{1}Ще докажем, че такива x,yx,y не съществуват. Да допуснем, че съществува двойка положителни четни числа (x0,y0)(x_0,y_0), удовлетворяваща (1). Тогава x0+1x_0+1 дели x02+y02x_0^2+y_0^2, защото дели и x02−1x_0^2-1, и y02+1y_0^2+1. Аналогично y0+1y_0+1 дели x02+y02x_0^2+y_0^2. Всеки общ делител на нечетните числа x0+1x_0+1 и y0+1y_0+1 дели(x02+1)+(y02+1)−(x02+y02)=2,(x_0^2+1)+(y_0^2+1)-(x_0^2+y_0^2)=2,следователно тези две числа са взаимно прости. Значи за някое положително цяло число kk уравнениетоk(x+1)(y+1)=x2+y2(2)k(x+1)(y+1)=x^2+y^2\tag{2}има решение в положителни четни числа. Избираме решение (x1,y1)(x_1,y_1) на (2) с минимална сума x1+y1x_1+y_1 и без ограничение нека x1≥y1x_1\ge y_1. Разглеждаме (2) като квадратно уравнение по xx при y=y1y=y_1:x2−k(y1+1)x+y12−k(y1+1)=0.x^2-k(y_1+1)x+y_1^2-k(y_1+1)=0.Нека x2x_2 е вторият му корен. По формулите на Виетx1+x2=k(y1+1),x1x2=y12−k(y1+1).x_1+x_2=k(y_1+1),\qquad x_1x_2=y_1^2-k(y_1+1).Ако x2=0x_2=0, то y12=k(y1+1)y_1^2=k(y_1+1), което е невъзможно, понеже y1+1>1y_1+1\gt{}1 е взаимно просто с y12y_1^2. Освен това(x1+1)(x2+1)=x1x2+x1+x2+1=y12+1,(x_1+1)(x_2+1)=x_1x_2+x_1+x_2+1=y_1^2+1,така че x2+1=(y12+1)/(x1+1)>0x_2+1=(y_1^2+1)/(x_1+1)\gt{}0. Следователно x2x_2 е положително цяло число. Понеже дясната страна y12+1y_1^2+1 е нечетна, а x1+1x_1+1 е нечетно, числото x2+1x_2+1 също е нечетно, тоест x2x_2 е четно. Накраяx2+1=y12+1x1+1≤y12+1y1+1≤y1,x_2+1=\frac{y_1^2+1}{x_1+1}\le\frac{y_1^2+1}{y_1+1}\le y_1,затова x2<y1x_2\lt{}y_1. Но тогава (y1,x2)(y_1,x_2) е ново решение на (2) в положителни четни числа иy1+x2<x1+y1,y_1+x_2\lt{}x_1+y_1,което противоречи на минималността. Следователно (1) няма решение в положителни четни числа. Полученото противоречие показва, че редица с пет члена не съществува. Значи възможните стойности на nn са точно 1,2,3,41,2,3,4.
Отвори задачатаMathNetISL 2009 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека P(x)P(x) е неконстантен полином с цели коефициенти. Докажете, че не съществува функция TT от множеството на целите числа в себе си, такава че броят на целите числа xx, за които Tn(x)=xT^n(x)=x, да е равен на P(n)P(n) за всяко n≥1n\ge1, където TnT^n означава nn-кратното прилагане на TT.
РешениеДа допуснем, че такава функция TT и такъв полином PP съществуват. За всяко положително цяло число nn некаA(n)={x∈Z:Tn(x)=x}A(n)=\{x\in\mathbb Z:T^n(x)=x\}и нека B(n)B(n) е множеството от тези x∈Zx\in\mathbb Z, за които Tn(x)=xT^n(x)=x, но Tm(x)≠xT^m(x)\ne x за всяко 1≤m<n1\le m\lt{}n. По условие множествата A(n)A(n) са крайни, а оттук и B(n)B(n) са крайни. Всеки елемент на A(n)A(n) има минимален положителен период dd, който дели nn. Обратно, всеки елемент с минимален период d∣nd\mid n принадлежи на A(n)A(n). СледователноP(n)=∣A(n)∣=∑d∣n∣B(d)∣.(1)P(n)=|A(n)|=\sum_{d\mid n}|B(d)|.\tag{1}Освен това TT разбива B(n)B(n) на цикли с дължина точно nn, затоваn∣∣B(n)∣.(2)n\mid |B(n)|.\tag{2}Нека pp и qq са две различни прости числа. От (1) и (2) получавамеP(pq)=∣B(1)∣+∣B(p)∣+∣B(q)∣+∣B(pq)∣≡P(pq)=|B(1)|+|B(p)|+|B(q)|+|B(pq)|\equiv∣B(1)∣+∣B(p)∣(modq). |B(1)|+|B(p)|\pmod q.Понеже PP има цели коефициенти, имаме и P(pq)≡P(0)(modq)P(pq)\equiv P(0)\pmod q. ЗначиP(0)−∣B(1)∣−∣B(p)∣P(0)-|B(1)|-|B(p)|се дели на qq. При фиксирано pp можем да избираме произволно големи прости q≠pq\ne p, следователно последното цяло число трябва да е 00. ТакаP(p)=∣A(p)∣=∣B(1)∣+∣B(p)∣=P(0)P(p)=|A(p)|=|B(1)|+|B(p)|=P(0)за всяко просто число pp. Полиномът P(x)−P(0)P(x)-P(0) има безкрайно много корени, понеже се анулира за всички прости числа. Следователно той е нулевият полином и PP е константен, което противоречи на условието. Значи търсената функция TT не съществува.
Отвори задачатаMathNetISL 2009 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека kk е положително цяло число. Докажете, че ако съществува редица a0,a1,…a_0,a_1,\ldots от цели числа, удовлетворяващаan=an−1+nknза всяко n≥1,a_n=\frac{a_{n-1}+n^k}{n}\qquad\text{за всяко }n\ge1,то k−2k-2 се дели на 33.
РешениеПърво ще извлечем полином от рекурентната връзка. За фиксирано kk ще построим полиномP(x)=bk−1xk−1+⋯+b1x+b0∈Z[x]P(x)=b_{k-1}x^{k-1}+\cdots+b_1x+b_0\in\mathbb Z[x]и цяло число qq, за коитоxP(x)=xk+P(x−1)+q.(1)xP(x)=x^k+P(x-1)+q.\tag{1}Наистина, коефициентите bk−1,bk−2,…,b0b_{k-1},b_{k-2},\ldots,b_0 се определят последователно, като сравняваме коефициентите пред xk,xk−1,…,xx^{k},x^{k-1},\ldots,x. Така първо получаваме bk−1=1b_{k-1}=1, а после всеки следващ коефициент е целочислена линейна комбинация на вече намерените. Накрая остава константната разлика qq. Нека сега a0,a1,…a_0,a_1,\ldots е редица от цели числа, удовлетворяваща условието, и положим cn=an−P(n)c_n=a_n-P(n). От рекурентната връзка и (1) следваq+ncn=cn−1(n≥1).(2)q+nc_n=c_{n-1}\qquad(n\ge1).\tag{2}Затова чрез индукция получавамеcn=c0n!−q0!+1!+⋯+(n−1)!n!.(3)c_n=\frac{c_0}{n!}-q\frac{0!+1!+\cdots+(n-1)!}{n!}.\tag{3}Понеже ana_n и P(n)P(n) са цели числа, всички cnc_n са цели числа. От (3) виждаме, че cn→0c_n\to0, следователно cn=0c_n=0 за всички достатъчно големи nn. Тогава от (2), приложено за две последователни достатъчно големи стойности на nn, получаваме q=0q=0, а после (2) връща назад cn=0c_n=0 за всяко n≥0n\ge0. Следователно необходимото условие за съществуването на такава целочислена редица еq=0,тоестxP(x)=xk+P(x−1).(4)q=0,\qquad\text{тоест}\qquad xP(x)=x^k+P(x-1).\tag{4}Остава да покажем, че (4) налага k≡2(mod3)k\equiv2\pmod3. Разглеждаме тъждеството (4) в полето F4={0,1,α,α+1}\mathbb F_4=\{0,1,\alpha,\alpha+1\}, където α2=α+1\alpha^2=\alpha+1 и α(α+1)=1\alpha(\alpha+1)=1. Замествайки x=αx=\alpha и x=α+1x=\alpha+1, получавамеαP(α)=αk+P(α+1)\alpha P(\alpha)=\alpha^k+P(\alpha+1)и(α+1)P(α+1)=(α+1)k+P(α).(\alpha+1)P(\alpha+1)=(\alpha+1)^k+P(\alpha).ТогаваP(α)=(α+1)αP(α)=(α+1)P(α+1)+(α+1)αk=P(α)+(α+1)k+(α+1)αk.\begin{aligned} P(\alpha)&=(\alpha+1)\alpha P(\alpha)\\ &=(\alpha+1)P(\alpha+1)+(\alpha+1)\alpha^k\\ &=P(\alpha)+(\alpha+1)^k+(\alpha+1)\alpha^k. \end{aligned}Следователно(α+1)k=(α+1)αk,(\alpha+1)^k=(\alpha+1)\alpha^k,тоест(α+1)k−1=αk.(5)(\alpha+1)^{k-1}=\alpha^k.\tag{5}Но ненулевите елементи на F4\mathbb F_4 имат ред 33, а α+1=α2\alpha+1=\alpha^2. От (5) следваα2k−2=αk,\alpha^{2k-2}=\alpha^k,така че αk−2=1\alpha^{k-2}=1. Следователно 3∣k−23\mid k-2, както трябваше да се докаже.
Отвори задачатаMathNetISL 2009 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека aa и bb са различни цели числа, по-големи от 11. Докажете, че съществува положително цяло число nn, за което(an−1)(bn−1)(a^n-1)(b^n-1)не е точен квадрат.
РешениеЩе използваме разлагането(1−α)1/2(1−β)1/2=(1−12α−18α2−⋯ )⋅(1−12β−18β2−⋯ )=∑k,ℓ≥0ck,ℓαkβℓ(α,β∈(0,1))(1)\begin{aligned} (1-\alpha)^{1/2}(1-\beta)^{1/2}&=\left(1-\frac12\alpha-\frac18\alpha^2-\cdots\right)\\ &\quad\cdot\left(1-\frac12\beta-\frac18\beta^2-\cdots\right)\\ &=\sum_{k,\ell\ge0}c_{k,\ell}\alpha^k\beta^\ell\qquad(\alpha,\beta\in(0,1)) \end{aligned}\tag{1}където c0,0=1c_{0,0}=1. Да допуснем противното: за всяко положително цяло число nn числотоxn=x2(an−1)(bn−1)x_n=\sqrt{\vphantom{x^2}(a^n-1)(b^n-1)}е цяло. Ако заменим aa с a2a^2 и bb с b2b^2, това свойство остава вярно за всички nn, затова можем да предполагаме, че aa и bb са точни квадрати. Тогава x2ab\sqrt{\vphantom{x^2}ab} е цяло число. Първо разглеждаме случая, в който aμ≠bνa^\mu\ne b^\nu за всички положителни цели числа μ,ν\mu,\nu. От (1) имамеxn=(x2ab)n(1−1an)1/2(1−1bn)1/2=x_n=(\sqrt{\vphantom{x^2}ab})^n\left(1-\frac1{a^n}\right)^{1/2}\left(1-\frac1{b^n}\right)^{1/2}=∑k,ℓ≥0ck,ℓ(x2abakbℓ)n.(2)\sum_{k,\ell\ge0}c_{k,\ell}\left(\frac{\sqrt{\vphantom{x^2}ab}}{a^k b^\ell}\right)^n.\tag{2}Избираме k0k_0 и ℓ0\ell_0, така че ak0>x2aba^{k_0}\gt{}\sqrt{\vphantom{x^2}ab} и bℓ0>x2abb^{\ell_0}\gt{}\sqrt{\vphantom{x^2}ab}, и дефинираме полиномаP(x)=P(x)=∏k=0k0−1∏ℓ=0ℓ0−1(akbℓx−x2ab)=\prod_{k=0}^{k_0-1}\prod_{\ell=0}^{\ell_0-1}\left(a^k b^\ell x-\sqrt{\vphantom{x^2}ab}\right)=∑i=0k0ℓ0dixi.\sum_{i=0}^{k_0\ell_0}d_i x^i.Коефициентите did_i са цели. Освен това корените x2ab/(akbℓ)\sqrt{\vphantom{x^2}ab}/(a^k b^\ell), където 0≤k<k00\le k\lt{}k_0 и 0≤ℓ<ℓ00\le\ell\lt{}\ell_0, са различни заради предположението aμ≠bνa^\mu\ne b^\nu. Разглеждаме целочислената редицаyn=∑i=0k0ℓ0dixn+i(n=1,2,…).(3)y_n=\sum_{i=0}^{k_0\ell_0}d_i x_{n+i}\qquad(n=1,2,\ldots).\tag{3}От (2) и избора на PP всички членове с k<k0k\lt{}k_0 и ℓ<ℓ0\ell\lt{}\ell_0 се унищожават, така чеyn=y_n=∑k,ℓ≥0k≥k0 или ℓ≥ℓ0ek,ℓ(x2abakbℓ)n(4)\begin{aligned}\sum_{\substack{k,\ell\ge0\\ k\ge k_0\text{ или }\ell\ge\ell_0}}e_{k,\ell}\left(\frac{\sqrt{\vphantom{x^2}ab}}{a^k b^\ell}\right)^n\tag{4}\end{aligned}за подходящи реални числа ek,ℓe_{k,\ell}. Тази редица е крайна линейна комбинация от абсолютно сходящите редове в (1), следователно сумата на абсолютните стойности в (4) е крайна при n=1n=1. Некаλ=max⁡{x2abak0,x2abbℓ0}<1.\lambda=\max\left\{\frac{\sqrt{\vphantom{x^2}ab}}{a^{k_0}},\frac{\sqrt{\vphantom{x^2}ab}}{b^{\ell_0}}\right\}\lt{}1.За всички членове в (4) имамеx2abakbℓ≤λ,\frac{\sqrt{\vphantom{x^2}ab}}{a^k b^\ell}\le\lambda,понеже k≥k0k\ge k_0 или ℓ≥ℓ0\ell\ge\ell_0. Затова ∣yn∣→0|y_n|\to0. Но yny_n е цяло число за всяко nn, следователно yn=0y_n=0 за всички достатъчно големи nn. Така редицата xnx_n от някой момент нататък удовлетворява линейна рекурентна връзка с характеристични корени точно числатаx2abakbℓ(0≤k<k0,0≤ℓ<ℓ0).\frac{\sqrt{\vphantom{x^2}ab}}{a^k b^\ell}\qquad(0\le k\lt{}k_0, 0\le\ell\lt{}\ell_0).От стандартната теория на линейните рекурентни редици следва, че за всички достатъчно големи nnxn=x_n=∑k=0k0−1∑ℓ=0ℓ0−1fk,ℓ(x2abakbℓ)n\sum_{k=0}^{k_0-1}\sum_{\ell=0}^{\ell_0-1}f_{k,\ell}\left(\frac{\sqrt{\vphantom{x^2}ab}}{a^k b^\ell}\right)^nза някакви реални числа fk,ℓf_{k,\ell}. Сравнявайки с единственото разлагане (2) по различните основи x2ab/(akbℓ)\sqrt{\vphantom{x^2}ab}/(a^k b^\ell), получаваме fk,ℓ=ck,ℓf_{k,\ell}=c_{k,\ell} за k<k0k\lt{}k_0, ℓ<ℓ0\ell\lt{}\ell_0, а ck,ℓ=0c_{k,\ell}=0, ако k≥k0k\ge k_0 или ℓ≥ℓ0\ell\ge\ell_0. Следователно (1) би било краен полином:(1−α)1/2(1−β)1/2=(1-\alpha)^{1/2}(1-\beta)^{1/2}=∑k=0k0−1∑ℓ=0ℓ0−1ck,ℓαkβℓ.(5)\sum_{k=0}^{k_0-1}\sum_{\ell=0}^{\ell_0-1}c_{k,\ell}\alpha^k\beta^\ell.\tag{5}Избираме максимално k∗k^*, за което съществува ii с ck∗,i≠0c_{k^*,i}\ne0, а после максимално i∗i^* с ck∗,i∗≠0c_{k^*,i^*}\ne0. Като повдигнем (5) на квадрат и сравним коефициента пред α2k∗β2i∗\alpha^{2k^*}\beta^{2i^*}, виждаме, че ако k∗>0k^*\gt{}0, дясната страна има ненулев такъв коефициент, докато лявата страна (1−α)(1−β)(1-\alpha)(1-\beta) няма. Значи k∗=0k^*=0. Тогава дясната страна на (5) не зависи от α\alpha, което е невъзможно. Получихме противоречие в първия случай. Остава случаят, когато aμ=bνa^\mu=b^\nu за някои положителни цели числа μ,ν\mu,\nu. Можем да вземем gcd⁡(μ,ν)=1\gcd(\mu,\nu)=1; тогава съществува положително цяло число cc, за което a=cνa=c^\nu и b=cμb=c^\mu. Повтаряйки горния аргумент с едномерното разлаганеxn=∑j≥0gj(x2cμ+νcj)n,x_n=\sum_{j\ge0}g_j\left(\frac{\sqrt{\vphantom{x^2}c^{\mu+\nu}}}{c^j}\right)^n,получаваме, че gj=0g_j=0 за всички достатъчно големи jj. Значи за някое j0j_0 имаме(1−xμ)1/2(1−xν)1/2=∑j=0j0gjxj(1-x^\mu)^{1/2}(1-x^\nu)^{1/2}=\sum_{j=0}^{j_0}g_jx^j\qquad(0<x<1).(0\lt{}x\lt{}1).След повдигане на квадрат следва, че (1−xμ)(1−xν)(1-x^\mu)(1-x^\nu) е квадрат на полином. Тогава всичките му комплексни корени трябва да са с четна кратност. Това е възможно само ако множествата от корени на 1−xμ1-x^\mu и 1−xν1-x^\nu съвпадат, тоест μ=ν\mu=\nu. Понеже gcd⁡(μ,ν)=1\gcd(\mu,\nu)=1, получаваме μ=ν=1\mu=\nu=1, а оттук a=ba=b, противоречие. И в двата случая предположението, че всички числа (an−1)(bn−1)(a^n-1)(b^n-1) са точни квадрати, води до противоречие. Следователно съществува положително цяло число nn, за което това произведение не е точен квадрат.
Отвори задачатаMathNetISL 2009 N7Условие — източник