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

IMO Shortlisted Problems

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

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

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

2012

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

11-12

21 задачи

Задача A1

Пълен запис
Условие
Да се намерят всички функции f:Z→Zf:\mathbb{Z}\to\mathbb{Z}, за коитоf(a)2+f(b)2+f(c)2=f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a)2f(a)f(b)+2f(b)f(c)+2f(c)f(a)за всички цели числа a,b,ca,b,c, удовлетворяващи a+b+c=0a+b+c=0.
РешениеОтговорът е следният. За произволно цяло число KK работят точно функциите (i) f(x)=Kx2f(x)=Kx^2; (ii) f(x)=0f(x)=0 за четно xx и f(x)=Kf(x)=K за нечетно xx; (iii) f(x)=0f(x)=0 за x≡0(mod4)x\equiv0\pmod4, f(x)=Kf(x)=K за нечетно xx и f(x)=4Kf(x)=4K за x≡2(mod4)x\equiv2\pmod4. От a=b=c=0a=b=c=0 получаваме f(0)=0f(0)=0. При b=−ab=-a и c=0c=0 следва f(a)=f(−a)f(a)=f(-a), т.е. ff е четна. Ако f(r)=0f(r)=0 за някое r≥1r\ge1, то от тройката (a,r,−a−r)(a,r,-a-r) получаваме(f(a+r)−f(a))2=0,(f(a+r)-f(a))^2=0,така че ff е периодична с период rr. Освен това от тройката (a,a,−2a)(a,a,-2a) следваf(2a)=0илиf(2a)=4f(a).(1)f(2a)=0\quad\text{или}\quad f(2a)=4f(a).\tag{1}Ако f(1)=0f(1)=0, периодът е 11 и f≡0f\equiv0. Нека занапред K=f(1)≠0K=f(1)\ne0. От (1) имаме f(2)=0f(2)=0 или f(2)=4Kf(2)=4K. В първия случай периодът е 22, откъдето получаваме функцията (ii). Нека f(2)=4Kf(2)=4K. Отново от (1) имаме f(4)=0f(4)=0 или f(4)=16Kf(4)=16K. Ако f(4)=0f(4)=0, периодът е 44 и, понеже ff е четна, получаваме функцията (iii). Остава случаят f(4)=16Kf(4)=16K. От тройките (1,2,−3)(1,2,-3) и (1,3,−4)(1,3,-4) получаваме съответноf(3)∈{K,9K},f(3)∈{9K,25K},f(3)\in\{K,9K\},\qquad f(3)\in\{9K,25K\},следователно f(3)=9Kf(3)=9K. Ще докажем по индукция, че f(x)=Kx2f(x)=Kx^2 за всички неотрицателни цели xx. Това вече е вярно за 0,1,2,3,40,1,2,3,4. Ако е вярно до n≥4n\ge4, то тройките (n,1,−n−1)(n,1,-n-1) и (n−1,2,−n−1)(n-1,2,-n-1) даватf(n+1)∈{K(n+1)2,K(n−1)2},f(n+1)\in\{K(n+1)^2,K(n-1)^2\},f(n+1)∈{K(n+1)2,K(n−3)2}.f(n+1)\in\{K(n+1)^2,K(n-3)^2\}.Понеже K≠0K\ne0 и n≥4n\ge4, вторите възможности са различни, затова остава само f(n+1)=K(n+1)2f(n+1)=K(n+1)^2. Четността на ff довършва доказателството за всички цели xx. Накрая проверката е пряка. За f(x)=Kx2f(x)=Kx^2 се използва тъждествотоa4+b4+c4=2a2b2+2b2c2+2c2a2(a+b+c=0).a^4+b^4+c^4=2a^2b^2+2b^2c^2+2c^2a^2\quad(a+b+c=0).За (ii) при a+b+c=0a+b+c=0 или трите числа са четни, или едно е четно и две са нечетни. За (iii) по симетрия остава да се проверят само възможните тройки от стойности (0,0,0)(0,0,0), (0,K,K)(0,K,K), (0,4K,4K)(0,4K,4K) и (4K,K,K)(4K,K,K); всички удовлетворяват равенството.
Отвори задачатаMathNetISL 2012 A1Условие — източник

Задача A2

Пълен запис
Условие
Нека Z\mathbb{Z} и Q\mathbb{Q} са съответно множествата на целите и рационалните числа. а) Съществува ли разбиване на Z\mathbb{Z} на три непразни подмножества A,B,CA,B,C, за което множествата A+BA+B, B+CB+C, C+AC+A са две по две непресичащи се? б) Съществува ли разбиване на Q\mathbb{Q} на три непразни подмножества A,B,CA,B,C, за което множествата A+BA+B, B+CB+C, C+AC+A са две по две непресичащи се? Тук X+YX+Y означава множеството {x+y:x∈X, y∈Y}\{x+y:x\in X,\ y\in Y\}.
РешениеОтговорът е: за а) да, за б) не. За целите числа вземаме класовете по модул 33:A={3k:k∈Z},B={3k+1:k∈Z},A=\{3k:k\in\mathbb{Z}\},\quad B=\{3k+1:k\in\mathbb{Z}\},C={3k+2:k∈Z}.\quad C=\{3k+2:k\in\mathbb{Z}\}.Тогава A+BA+B, B+CB+C и C+AC+A са трите различни класа по модул 33. Да допуснем, че такова разбиване на Q\mathbb{Q} съществува. За a∈Aa\in A, b∈Bb\in B, c∈Cc\in C имамеa+b−c∈C,b+c−a∈A,c+a−b∈B.(1)a+b-c\in C,\qquad b+c-a\in A,\qquad c+a-b\in B.\tag{1}Наистина, например a+b−ca+b-c не може да е в AA, защото тогава a+ba+b би лежало едновременно в A+BA+B и A+CA+C; не може да е и в BB по същата причина. От (1) следва A+B⊂C+CA+B\subset C+C, B+C⊂A+AB+C\subset A+A, C+A⊂B+BC+A\subset B+B. Обратните включвания също са верни. Например, ако a,a′∈Aa,a'\in A, b∈Bb\in B, c∈Cc\in C, то a′+c−b∈Ba'+c-b\in B и послеa+a′−b=a+(a′+c−b)−c∈C,a+a'-b=a+(a'+c-b)-c\in C,откъдето a+a′∈B+Ca+a'\in B+C. СледователноA+A=B+C,B+B=C+A,C+C=A+B.(2)A+A=B+C,\qquad B+B=C+A,\qquad C+C=A+B.\tag{2}Без ограничение нека 0∈A0\in A. Тогава B⊂A+BB\subset A+B и C⊂A+CC\subset A+C. Понеже B+CB+C е непресичащо се с A+BA+B и с A+CA+C, получаваме B+C⊂AB+C\subset A. От (2) имаме A+A⊂AA+A\subset A, а понеже 0∈A0\in A, и A⊂A+AA\subset A+A. ЗначиA=A+A=B+C.A=A+A=B+C.ТогаваA+B+C=A+A+A=A.A+B+C=A+A+A=A.От (2) следва ощеB+B+B=A,C+C+C=A.B+B+B=A,\qquad C+C+C=A.Затова за всяко рационално число rr числото 3r3r принадлежи на AA. Но ако изберем b∈Bb\in B, то за r=b/3r=b/3 получаваме b=3r∈Ab=3r\in A, противоречие. Следователно такова разбиване на Q\mathbb{Q} не съществува.
Отвори задачатаMathNetISL 2012 A2Условие — източник

Задача A3

Пълен запис
Условие
Нека a2,…,ana_2,\ldots,a_n са n−1n-1 положителни реални числа, където n≥3n\ge3, иa2a3⋯an=1.a_2a_3\cdots a_n=1.Докажете, че(1+a2)2(1+a3)3⋯(1+an)n>nn.(1+a_2)^2(1+a_3)^3\cdots(1+a_n)^n\gt{}n^n.
РешениеЗа всяко k=2,3,…,nk=2,3,\ldots,n прилагаме неравенството между средно аритметично и средно геометрично към kk положителни числа: k−1k-1 копия на 1/(k−1)1/(k-1) и числото aka_k. Получаваме1+akk≥x2ak(k−1)k−1k,\frac{1+a_k}{k}\ge\sqrt[k]{\vphantom{x^2}\frac{a_k}{(k-1)^{k-1}}},т.е.(1+ak)k≥kk(k−1)k−1ak.(1+a_k)^k\ge\frac{k^k}{(k-1)^{k-1}}a_k.Умножаваме тези неравенства за k=2,3,…,nk=2,3,\ldots,n и използваме a2a3⋯an=1a_2a_3\cdots a_n=1:(1+a2)2(1+a3)3⋯(1+an)n≥nn.(1+a_2)^2(1+a_3)^3\cdots(1+a_n)^n\ge n^n.Ако имаше равенство, за всяко kk трябваше да е изпълнено ak=1/(k−1)a_k=1/(k-1). Тогаваa2a3⋯an=1(n−1)!≠1,a_2a_3\cdots a_n=\frac1{(n-1)!}\ne1,понеже n≥3n\ge3. Следователно поне едно от използваните неравенства е строго и получаваме исканото >nn\gt{}n^n.
Отвори задачатаMathNetISL 2012 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека ff и gg са два ненулеви полинома с цели коефициенти и deg⁡f>deg⁡g\deg f\gt{}\deg g. Да предположим, че за безбройно много прости числа pp полиномът pf+gpf+g има рационален корен. Докажете, че ff има рационален корен.
РешениеНека d=deg⁡fd=\deg f и нека aa е старшият коефициент на ff. Ако d=1d=1, твърдението е очевидно, защото всеки линеен полином с цели коефициенти има рационален корен. Занапред нека d≥2d\ge2. Понеже deg⁡f>deg⁡g\deg f\gt{}\deg g, съществува реално число RR, такова че за ∣z∣>R|z|\gt{}R имаме ∣g(z)∣<∣f(z)∣|g(z)|\lt{}|f(z)| за всички комплексни zz. Следователно за всяко просто p≥2p\ge2 всички комплексни корени на pf+gpf+g лежат в диска ∣z∣≤R|z|\le R. Пренебрегваме крайно многото прости делители на aa и разглеждаме само останалите прости pp, за които pf+gpf+g има рационален корен. По лемата на Гаус полиномът pf+gpf+g се разлага над Z\mathbb{Z} като произведение на линеен фактор и фактор от степен d−1d-1. Старшите коефициенти на тези два фактора имат произведение papa; понеже p∤ap\nmid a, старшият коефициент на един от двата фактора дели aa. Нека наречем този фактор hph_p. Сред безбройно многото такива pp можем да изберем безбройно подмножество, за което deg⁡hp\deg h_p и старшият коефициент на hph_p са едни и същи. Всички корени на hph_p лежат в ∣z∣≤R|z|\le R, затова по формулите на Виет коефициентите на hph_p са ограничени. Те са цели числа, следователно са възможни само крайно много полиноми hph_p. Значи един и същ полином hh съвпада с hph_p за безбройно много прости pp. Ако pp и qq са две различни такива прости числа, то hh дели и pf+gpf+g, и qf+gqf+g, следователно дели (p−q)f(p-q)f, а значи дели ff над Q\mathbb{Q}. Ако deg⁡h=1\deg h=1, веднага получаваме рационален корен на ff. Ако deg⁡h=d−1\deg h=d-1, то частното f/hf/h е линеен полином над Q\mathbb{Q}, който също дава рационален корен на ff.
Отвори задачатаMathNetISL 2012 A4Условие — източник

Задача A5

Пълен запис
Условие
Да се намерят всички функции f:R→Rf:\mathbb{R}\to\mathbb{R}, за коитоf(1+xy)−f(x+y)=f(x)f(y)f(1+xy)-f(x+y)=f(x)f(y)за всички x,y∈Rx,y\in\mathbb{R} и f(−1)≠0f(-1)\ne0.
РешениеОтговорът е единственоf(x)=x−1(x∈R).f(x)=x-1\qquad(x\in\mathbb{R}).Поставяме g(x)=f(x)+1g(x)=f(x)+1. Тогаваg(1+xy)−g(x+y)=(g(x)−1)(g(y)−1)(1)g(1+xy)-g(x+y)=(g(x)-1)(g(y)-1)\tag{1}за всички реални x,yx,y, а C=g(−1)−1=f(−1)≠0C=g(-1)-1=f(-1)\ne0. При y=−1y=-1 получавамеg(1−x)−g(x−1)=C(g(x)−1).(2)g(1-x)-g(x-1)=C(g(x)-1).\tag{2}От (2) за x=1,0,2x=1,0,2 следват съответноg(1)=1,g(0)=0,g(2)=2.g(1)=1,\qquad g(0)=0,\qquad g(2)=2.Ще докажем две помощни равенства. В (2) заменяме xx с 1−x1-x, а после в полученото равенство заменяме xx с −x-x. Получавамеg(x)−g(−x)=C(g(1−x)−1),g(x)-g(-x)=C(g(1-x)-1),g(−x)−g(x)=C(g(1+x)−1).g(-x)-g(x)=C(g(1+x)-1).След събиране и понеже C≠0C\ne0 намирамеg(x)+g(2−x)=2(x∈R).(3)g(x)+g(2-x)=2\qquad(x\in\mathbb{R}).\tag{3}Нека u+v=1u+v=1. Прилагаме (1) към двойките (u,v)(u,v) и (2−u,2−v)(2-u,2-v). Десните страни са равни по (3), затоваg(3+uv)−g(1+uv)=g(3)−g(1).g(3+uv)-g(1+uv)=g(3)-g(1).Всяко x≤5/4x\le5/4 може да се представи като x=1+uvx=1+uv при u+v=1u+v=1, следователно g(x+2)−g(x)=g(3)−g(1)g(x+2)-g(x)=g(3)-g(1) за x≤5/4x\le5/4. При x=0x=0 получаваме g(3)−g(1)=g(2)−g(0)=2g(3)-g(1)=g(2)-g(0)=2. Значиg(x+2)−g(x)=2(x≤5/4).g(x+2)-g(x)=2\qquad(x\le5/4).Ако x>5/4x\gt{}5/4, прилагаме вече доказаното към −x-x и използваме (3); така пак получавамеg(x+2)−g(x)=2(x∈R).(4)g(x+2)-g(x)=2\qquad(x\in\mathbb{R}).\tag{4}От (3) с xx заменено с −x-x и от (4) следваg(−x)+g(x+2)=2,g(x+2)=g(x)+2,g(-x)+g(x+2)=2,\qquad g(x+2)=g(x)+2,т.е.g(−x)=−g(x).(5)g(-x)=-g(x).\tag{5}Сега прилагаме (1) към двойките (−x,y)(-x,y) и (x,−y)(x,-y) и събираме получените равенства. Поради (5) членовете g(y−x)g(y-x) и g(x−y)g(x-y) се унищожават и получавамеg(1−xy)=1−g(x)g(y).g(1-xy)=1-g(x)g(y).От (3), приложено за 1−xy1-xy, следваg(1+xy)=1+g(x)g(y).(6)g(1+xy)=1+g(x)g(y).\tag{6}Замествайки (6) в (1), намирамеg(x+y)=g(x)+g(y),g(x+y)=g(x)+g(y),т.е. gg е адитивна. Освен това от адитивността и (6) имамеg(xy)=g(x)g(y).g(xy)=g(x)g(y).Затова g(x2)=g(x)2≥0g(x^2)=g(x)^2\ge0 за всяко xx, т.е. gg е неотрицателна върху [0,+∞)[0,+\infty). Адитивна функция, която е ограничена отдолу върху интервал, е линейна; понеже g(1)=1g(1)=1, следва g(x)=xg(x)=x за всички реални xx. Следователно f(x)=g(x)−1=x−1f(x)=g(x)-1=x-1. Пряка проверка показва, че тази функция удовлетворява условието.
Отвори задачатаMathNetISL 2012 A5Условие — източник

Задача A6

Пълен запис
Условие
Нека f:N→Nf:\mathbb{N}\to\mathbb{N} е функция и нека fmf^m означава mm-кратно прилагане на ff. Да предположим, че за всяко n∈Nn\in\mathbb{N} съществува k∈Nk\in\mathbb{N}, за коетоf2k(n)=n+k,f^{2k}(n)=n+k,и нека knk_n е най-малкото такова kk. Докажете, че редицата k1,k2,…k_1,k_2,\ldots е неограничена.
РешениеРазглеждаме множествотоS={1,f(1),f2(1),…}.S=\{1,f(1),f^2(1),\ldots\}.То е неограничено: ако n∈Sn\in S, то за някое k>0k\gt{}0 числото f2k(n)=n+kf^{2k}(n)=n+k също е в SS и е по-голямо от nn. Освен това ff е инективна върху SS; иначе орбитата 1,f(1),f2(1),…1,f(1),f^2(1),\ldots би станала периодична и SS би било крайно. За n∈Sn\in S дефинирамеg(n)=f2kn(n)=n+kn.g(n)=f^{2k_n}(n)=n+k_n.Ще покажем, че gg е инективна върху SS. Ако g(a)=g(b)g(a)=g(b) и a<ba\lt{}b, тоa+ka=b+kb,a+k_a=b+k_b,следователно ka>kbk_a\gt{}k_b. Понеже ff е инективна върху SS, отf2ka(a)=f2kb(b)f^{2k_a}(a)=f^{2k_b}(b)получавамеf2(ka−kb)(a)=b=a+(ka−kb),f^{2(k_a-k_b)}(a)=b=a+(k_a-k_b),което противоречи на минималността на kak_a. Нека TT е множеството от елементите на SS, които не са от вида g(n)g(n) за n∈Sn\in S. То е непразно, защото 1∈T1\in T. За t∈Tt\in T наричамеCt={t,g(t),g2(t),…}C_t=\{t,g(t),g^2(t),\ldots\}веригата, започваща от tt. Понеже gg е инективна, различните вериги са непресичащи се. Всеки елемент на SS лежи в някоя от тях: ако n∉Tn\notin T, тогава n=g(n′)n=g(n') с n′<nn'\lt{}n, и след краен брой такива стъпки стигаме до елемент на TT. Ако t=fnt(1)t=f^{n_t}(1) и fn(1)∈Ctf^n(1)\in C_t, то всяко преминаване u↦g(u)u\mapsto g(u) увеличава индекса в орбитата с 2ku2k_u и стойността с kuk_u. Затоваfn(1)=t+n−nt2.(1)f^n(1)=t+\frac{n-n_t}{2}.\tag{1}Ще докажем, че TT е безкрайно. Ако T={t1,…,tr}T=\{t_1,\ldots,t_r\} е крайно и trt_r е най-големият му елемент, то от (1) следва, че всички различни числа1,f(1),…,fN(1)1,f(1),\ldots,f^N(1)са най-много tr+N/2t_r+N/2. Това е невъзможно за достатъчно голямо NN, защото те са N+1N+1 различни положителни цели числа. Накрая нека KK е произволно положително цяло число. Вземаме първите K+1K+1 елемента на безкрайното множество TT и нека tt е най-големият от тях. Всяка от съответните K+1K+1 вериги съдържа елемент, не по-голям от tt. Сред KK-те числа t+1,t+2,…,t+Kt+1,t+2,\ldots,t+K поне една от тези вериги не съдържа нито едно число. В тази верига има преход n↦g(n)n\mapsto g(n), който прескача целия интервал, следователноkn=g(n)−n>K.k_n=g(n)-n\gt{}K.Тъй като KK беше произволно, редицата k1,k2,…k_1,k_2,\ldots е неограничена.
Отвори задачатаMathNetISL 2012 A6Условие — източник

Задача A7

Пълен запис
Условие
Казваме, че функция f:Rk→Rf:\mathbb{R}^k\to\mathbb{R} е метаполином, ако за някои положителни цели числа mm и nn може да се представи във видаf(x1,…,xk)=f(x_1,\ldots,x_k)=max⁡i=1,…,m min⁡j=1,…,nPi,j(x1,…,xk),\max_{i=1,\ldots,m}\ \min_{j=1,\ldots,n} P_{i,j}(x_1,\ldots,x_k),където Pi,jP_{i,j} са многопроменливи полиноми. Докажете, че произведението на два метаполинома също е метаполином.
РешениеНека M\mathcal M е множеството на всички метаполиноми. Ще използваме факта, че в представяне на метаполином броят на редовете или колоните може да се увеличава чрез повтаряне на вече съществуващи полиноми. Първо доказваме помощна лема. За произволни реални числа ai,ja_{i,j}, i∈{1,…,m}i\in\{1,\ldots,m\}, j∈{1,…,n}j\in\{1,\ldots,n\}, е изпълненоmin⁡imax⁡jai,j=max⁡j1,…,jmmin⁡iai,ji.\min_i\max_j a_{i,j}=\max_{j_1,\ldots,j_m}\min_i a_{i,j_i}.Действително, ако за всеки ii изберем jij_i така, че ai,ji=max⁡jai,ja_{i,j_i}=\max_j a_{i,j}, дясната страна е поне лявата. Обратното неравенство следва от ai,ji≤max⁡jai,ja_{i,j_i}\le\max_j a_{i,j} за всеки ii и после вземане на минимум по ii. От лемата следва, че ако f=max⁡imin⁡jPi,jf=\max_i\min_j P_{i,j} е в M\mathcal M, то−f=min⁡imax⁡j(−Pi,j)-f=\min_i\max_j(-P_{i,j})също е в M\mathcal M. Следователно M\mathcal M е затворено относно максимум и минимум на краен брой свои елементи. То е затворено и относно събиране, защото акоf=max⁡imin⁡jPi,j,g=max⁡smin⁡tQs,t,f=\max_i\min_j P_{i,j},\qquad g=\max_s\min_t Q_{s,t},тоf+g=max⁡i,smin⁡j,t(Pi,j+Qs,t).f+g=\max_{i,s}\min_{j,t}(P_{i,j}+Q_{s,t}).За реално число uu пишем u+=max⁡{u,0}u^+=\max\{u,0\}. Ще ни трябва явната формулаu+v+=u^+v^+=max⁡{0,min⁡{uv,u,v},min⁡{uv,uv2,u2v},min⁡{uv,u,u2v},min⁡{uv,uv2,v}}.(1)\max\{0,\min\{uv,u,v\},\min\{uv,uv^2,u^2v\},\min\{uv,u,u^2v\},\min\{uv,uv^2,v\}\}.\tag{1}Ако u≤0u\le0 или v≤0v\le0, дясната страна е 00. Ако u,v≥0u,v\ge0, тя е най-много uvuv, а равенство се достига съответно в случаите 0≤u,v≤10\le u,v\le1, 1≤u,v1\le u,v, 0≤v≤1≤u0\le v\le1\le u и 0≤u≤1≤v0\le u\le1\le v. Значи (1) е доказана. Понеже дясната страна използва само полиноми, минимуми и максимуми, от (1) следва, че P+Q+∈MP^+Q^+\in\mathcal M за всеки два полинома P,QP,Q. Сега нека f,g∈Mf,g\in\mathcal M и f,g≥0f,g\ge0. Можем да пишемf=max⁡imin⁡jPi,j+,g=max⁡smin⁡tQs,t+,f=\max_i\min_j P_{i,j}^+,\qquad g=\max_s\min_t Q_{s,t}^+,защото вземането на положителна част на всеки Pi,jP_{i,j} заменя всеки вътрешен минимум с неговата положителна част, а f≥0f\ge0. Всички участващи величини са неотрицателни, затоваfg=max⁡i,smin⁡j,t(Pi,j+Qs,t+).fg=\max_{i,s}\min_{j,t}\left(P_{i,j}^+Q_{s,t}^+\right).Всеки множител Pi,j+Qs,t+P_{i,j}^+Q_{s,t}^+ е метаполином по (1), а вече знаем, че M\mathcal M е затворено относно крайни минимуми и максимуми. Следователно fg∈Mfg\in\mathcal M. За произволни f,g∈Mf,g\in\mathcal M разглеждаме положителните и отрицателните частиf+=max⁡{f,0},f−=max⁡{−f,0},f^+=\max\{f,0\},\quad f^-=\max\{-f,0\},g+=max⁡{g,0},g−=max⁡{−g,0}.\quad g^+=\max\{g,0\},\quad g^-=\max\{-g,0\}.Те са в M\mathcal M и са неотрицателни, аfg=f+g+−f+g−−f−g++f−g−.fg=f^+g^+-f^+g^--f^-g^++f^-g^-.Вече доказаният неотрицателен случай и затвореността относно събиране и противоположна функция дават fg∈Mfg\in\mathcal M.
Отвори задачатаMathNetISL 2012 A7Условие — източник

Задача C1

Пълен запис
Условие
Няколко положителни цели числа са записани в редица. На всяка стъпка Алиса избира две съседни числа xx и yy, за които x>yx\gt{}y и xx е вляво от yy, и заменя двойката (x,y)(x,y) или с (y+1,x)(y+1,x), или с (x−1,x)(x-1,x). Докажете, че тя може да извърши само краен брой такива стъпки.
РешениеПърво забелязваме, че разрешената операция не променя максимума MM на началната редица. Нека в някакъв момент числата саa1,a2,…,an.a_1,a_2,\ldots,a_n.Разглеждаме суматаS=a1+2a2+⋯+nan.S=a_1+2a_2+\cdots+na_n.Ще докажем, че при всяка операция SS нараства с положително цяло число. Нека операцията заменя двойката (ai,ai+1)(a_i,a_{i+1}) с (c,ai)(c,a_i), където ai>ai+1a_i\gt{}a_{i+1} и c=ai+1+1c=a_{i+1}+1 или c=ai−1c=a_i-1. Новата стойност на SS минус старата еd=(ic+(i+1)ai)−(iai+(i+1)ai+1)=ai−ai+1+i(c−ai+1).\begin{aligned} d&=\left(ic+(i+1)a_i\right)-\left(ia_i+(i+1)a_{i+1}\right)\\ &=a_i-a_{i+1}+i(c-a_{i+1}). \end{aligned}Тук ai−ai+1≥1a_i-a_{i+1}\ge1, а c−ai+1≥0c-a_{i+1}\ge0, следователно dd е положително цяло число. От друга страна, всички членове на редицата остават положителни цели числа, ненадминаващи MM, така чеS≤(1+2+⋯+n)M.S\le(1+2+\cdots+n)M.Значи SS нараства поне с 11 на всяка стъпка, но никога не надхвърля фиксираната константа (1+2+⋯+n)M(1+2+\cdots+n)M. Следователно процесът не може да продължи безкрайно.
Отвори задачатаMathNetISL 2012 C1Условие — източник

Задача C2

Пълен запис
Условие
Нека n≥1n\ge1 е цяло число. Какъв е максималният брой несвързани двойки от елементи на множеството {1,2,…,n}\{1,2,\ldots,n\}, такива че сумите на различните двойки са различни цели числа, ненадминаващи nn?
РешениеДа разгледаме xx такива двойки. Сумата SS на участващите 2x2x числа е поне1+2+⋯+2x,1+2+\cdots+2x,понеже двойките са несвързани. От друга страна, сумите на двойките са различни и не надминават nn, затова сборът на тези xx суми е най-многоn+(n−1)+⋯+(n−x+1).n+(n-1)+\cdots+(n-x+1).Следователно2x(2x+1)2≤nx−x(x−1)2,\frac{2x(2x+1)}2\le nx-\frac{x(x-1)}2,откъдетоx≤2n−15.x\le\frac{2n-1}{5}.Значи търсеният брой е най-много⌊2n−15⌋.\left\lfloor\frac{2n-1}{5}\right\rfloor.Остава да покажем, че тази оценка се достига. Първо нека n=5k+3n=5k+3, където k≥0k\ge0. Тогава трябва да построим 2k+12k+1 двойки. Вземаме двойките(3k+1,2),(3k,4),…,(2k+2,2k)(3k+1,2),(3k,4),\ldots,(2k+2,2k)и(4k+2,1),(4k+1,3),…,(4k+2,1),(4k+1,3),\ldots,(3k+3,2k−1),(3k+2,2k+1),(3k+3,2k-1),(3k+2,2k+1),като празните части при малки kk просто се пропускат. Тези 2k+12k+1 двойки използват числата от 11 до 4k+24k+2, а сумите им са точно всички числа от 3k+33k+3 до 5k+35k+3. Същата конструкция работи без промяна за n=5k+4n=5k+4 и n=5k+5n=5k+5, защото в тези два случая⌊2n−15⌋=2k+1\left\lfloor\frac{2n-1}{5}\right\rfloor=2k+1и всички използвани числа и суми не надминават 5k+3≤n5k+3\le n. Ако n=5k+2n=5k+2, са нужни 2k2k двойки; получаваме ги от горната конструкция, като премахнем последната двойка, чиято сума е 5k+35k+3. Ако n=5k+1n=5k+1, отново са нужни 2k2k двойки; премахваме последната двойка и после намаляваме с 11 всяко число в първата координата на останалите двойки. Така всички числа остават различни положителни цели числа, а сумите остават различни и не надминават 5k+15k+1. Следователно максималният брой е⌊2n−15⌋.\boxed{\left\lfloor\frac{2n-1}{5}\right\rfloor}.
Отвори задачатаMathNetISL 2012 C2Условие — източник

Задача C3

Пълен запис
Условие
В квадратна таблица 999×999999\times999 някои клетки са бели, а останалите са червени. Нека TT е броят на тройките (C1,C2,C3)(C_1,C_2,C_3) от клетки, при които първите две клетки са в един и същи ред, последните две са в един и същи стълб, C1C_1 и C3C_3 са бели, а C2C_2 е червена. Намерете максималната възможна стойност на TT.
РешениеЩе докажем по-общо, че за квадратна таблица n×nn\times n броят на такива тройки е най-много 4n427.\frac{4n^4}{27}.Нека в ред ii има aia_i бели клетки, а в стълб jj има bjb_j бели клетки. Да означим с RR множеството от червените клетки. Ако C2=(i,j)C_2=(i,j) е червена клетка, то имаме aia_i избора за бяла клетка C1C_1 в същия ред и bjb_j избора за бяла клетка C3C_3 в същия стълб. Следователно T=∑(i,j)∈Raibj.T=\sum_{(i,j)\in R}a_i b_j.От неравенството 2ab≤a2+b22ab\le a^2+b^2 получавамеT≤12∑(i,j)∈R(ai2+bj2)=12∑i=1n(n−ai)ai2+12∑j=1n(n−bj)bj2,\begin{aligned} T&\le\frac12\sum_{(i,j)\in R}\left(a_i^2+b_j^2\right)\\ &=\frac12\sum_{i=1}^n(n-a_i)a_i^2+\frac12\sum_{j=1}^n(n-b_j)b_j^2, \end{aligned}защото в ред ii има n−ain-a_i червени клетки, а в стълб jj има n−bjn-b_j червени клетки. Остава да оценим дясната страна. По неравенството AM-GM,(n−x)x2=12(2n−2x)⋅x⋅x≤(n-x)x^2=\frac12(2n-2x)\cdot x\cdot x\le12(2n3)3=4n327,\frac12\left(\frac{2n}{3}\right)^3=\frac{4n^3}{27},като равенство има точно при x=2n3x=\frac{2n}{3}. СледователноT≤n2⋅4n327+n2⋅4n327=4n427.T\le\frac n2\cdot\frac{4n^3}{27}+\frac n2\cdot\frac{4n^3}{27}=\frac{4n^4}{27}.За n=999n=999 равенството се достига. Номерираме редовете и стълбовете по модул 999999 и оцветяваме клетката (i,j)(i,j) в бяло точно когато i−j≡1,2,…,666(mod999);i-j\equiv1,2,\ldots,666\pmod{999}; останалите клетки оцветяваме в червено. Тогава във всеки ред и във всеки стълб има точно 666=2⋅9993666=\frac{2\cdot999}{3} бели клетки, така че всички използвани неравенства стават равенства. Затова максималната стойност е 4⋅999427.\frac{4\cdot999^4}{27}.
Отвори задачатаMathNetISL 2012 C3Условие — източник

Задача C4

Пълен запис
Условие
Играчите AA и BB играят игра с N≥2012N\ge2012 монети и 20122012 кутии, подредени в кръг. Първоначално AA разпределя монетите в кутиите така, че във всяка кутия има поне по една монета. След това двамата правят ходове в реда B,A,B,A,…B,A,B,A,\ldots по следните правила: - на всеки свой ход BB премества по 11 монета от всяка кутия в съседна кутия; - на всеки свой ход AA избира няколко монети, които не са участвали в предишния ход на BB и се намират в различни кутии, и премества всяка избрана монета в съседна кутия. Целта на AA е след всеки неин ход във всяка кутия да има поне по една монета, независимо как играе BB и колко хода са направени. Намерете най-малката стойност на NN, за която AA може да постигне това.
РешениеЩе решим задачата за общ брой n≥7n\ge7 кутии и ще докажем, че минималният брой монети е 2n−22n-2. За n=2012n=2012 това даваNmin⁡=4022.N_{\min}=4022.Първо ще покажем, че при N=2n−2N=2n-2 играч AA може да постигне целта си. Нека тя започне с регулярно разпределение: n−2n-2 кутии съдържат по 22 монети, а 22 кутии съдържат по 11 монета. Ще наричаме тези два вида кутии съответно червени и бели. Ще докажем, че след първия ход на BB, какъвто и да е той, AA може отново да получи регулярно разпределение. Тя действа според това дали след хода MM на BB е налице следната ситуация SS: в началното разпределение има червена кутия RR с две бели съседни кутии и при хода MM кутията RR не получава монета от тях. Да предположим първо, че SS не настъпва. В дадена червена кутия XX точно една от двете й монети, да кажем c1c_1, участва в хода MM. Ако MM премества c1c_1 към десния съсед на XX, то AA премества другата монета c2c_2 към левия съсед; в обратния случай прави обратното. Като направи това за всички червени кутии, AA извършва допустим ход M′M'. Двата хода MM и M′M' заедно преместват двете монети от всяка червена кутия в противоположни посоки. Следователно след тези два хода всеки съсед на червена кутия съдържа точно една монета, която първоначално е била в нея, и затова всяка кутия с червен съсед е непразна. Ако първоначално има кутия XX с две бели съседни кутии, то XX е единствена червена кутия с това свойство; понеже SS не настъпва, тя получава монета от поне една от белите си съседки при хода MM. Тази монета не участва в M′M', така че и XX остава непразна. Освен това всяка кутия YY е дала началното си съдържание при ходовете MM и M′M'. Червен съсед добавя в нея точно 11 монета, а бял съсед добавя най-много 11 монета, понеже не участва в M′M'. Значи след M′M' във всяка кутия има 11 или 22 монети. Тъй като общият брой е 2n−22n-2, полученото разпределение пак е регулярно. Нека сега ситуация SS настъпи. Тогава AA не пипа изключителната червена кутия RR. С всички останали червени кутии тя постъпва както в предишния случай и така прави допустим ход M′′M''. Кутията RR не получава монети от съседите си в нито един от двата хода, следователно след M′′M'' в нея има точно 11 монета. Както по-горе, ходовете MM и M′′M'' заедно пращат точно по 11 монета от всяка червена кутия, различна от RR, към всеки от двата й съседа. Всяка кутия освен RR има червен съсед, различен от RR, така че всички кутии са непразни след M′′M''. Освен това всяка кутия Y≠RY\ne R е изгубила началното си съдържание; червен съсед добавя в нея най-много 11 монета, а бял съсед също добавя най-много 11 монета, защото не участва в M′′M''. Значи отново всяка кутия съдържа 11 или 22 монети и разпределението е регулярно. Така AA може след всеки свой ход да възстановява регулярно разпределение и следователно N=2n−2N=2n-2 е достатъчно. Остава да докажем, че при N≤2n−3N\le2n-3 играч BB може да принуди празна кутия след някой ход на AA. Нека α\alpha е множество от ℓ\ell последователни кутии, съдържащи общо N(α)N(\alpha) монети. Ще наричаме α\alpha дъга, акоℓ≤n−2иN(α)≤2ℓ−3.\ell\le n-2\quad\text{и}\quad N(\alpha)\le2\ell-3.От последното условие следва ℓ≥2\ell\ge2. Ако двата края на α\alpha са непразни, то N(α)≥2N(\alpha)\ge2, така че ℓ≥3\ell\ge3. Освен това, ако краен елемент XX на дъгата има повече от 11 монета, можем да го премахнем и да получим по-къса дъга. Следователно всяка дъга съдържа дъга, чиито крайни кутии имат най-много по 11 монета. Номерираме кутиите по часовниковата стрелка с 1,2,…,n1,2,\ldots,n и нека кутиите 1,2,…,ℓ1,2,\ldots,\ell образуват дъга α\alpha, където ℓ≤n−2\ell\le n-2 и N(α)≤2ℓ−3N(\alpha)\le2\ell-3. Да предположим също, че всички n≥7n\ge7 кутии са непразни. Ще покажем, че BB може да играе така, че след всеки отговор на AA да се появи дъга α′\alpha' с N(α′)<N(α)N(\alpha')\lt{}N(\alpha). По предходното наблюдение можем да считаме, че в кутии 11 и ℓ\ell има точно по 11 монета. Нека BB премести по една монета обратно на часовниковата стрелка от кутии 11 и nn, а от всяка останала кутия премести по една монета по часовниковата стрелка. Тогава в кутиите на α\alpha остават N(α)−2N(\alpha)-2 монети. Освен това, понеже 3≤ℓ≤n−23\le\ell\le n-2, в кутия ℓ\ell има точно една монета cc, получена от кутия ℓ−1\ell-1. Нека следващият ход MM на AA премести k≤2k\le2 монети от външността на α\alpha към кутиите 1,2,…,ℓ1,2,\ldots,\ell. Само кутии 11 и ℓ\ell могат да получат такива монети, най-много по една всяка. Ако k<2k\lt{}2, то след хода MM кутиите 1,2,…,ℓ1,2,\ldots,\ell образуват дъга α′\alpha' с N(α′)<N(α)N(\alpha')\lt{}N(\alpha). Ако k=2k=2, то MM добавя монета в кутия ℓ\ell. Освен това MM не премества монетата cc от ℓ\ell, защото тя е участвала в предишния ход на BB. Така кутиите 1,2,…,ℓ1,2,\ldots,\ell пак съдържат N(α)N(\alpha) монети и образуват дъга, но в крайния й елемент ℓ\ell вече има 22 монети. Премахваме този краен елемент и получаваме по-къса дъга α′\alpha' с N(α′)<N(α)N(\alpha')\lt{}N(\alpha). Да разгледаме произволно начално разпределение без празни кутии. Понеже N≤2n−3N\le2n-3, поне три кутии съдържат точно по 11 монета. От n≥7n\ge7 следва, че две от тях могат да се изберат като краища на някаква дъга α\alpha. Тогава BB прилага описания ход и след отговора на AA получава дъга α′\alpha' с N(α′)<N(α)N(\alpha')\lt{}N(\alpha). Ако всички кутии в новото разпределение са непразни, той повтаря същото. Понеже N(α)N(\alpha) не може да намалява безкрайно, след някой ход на AA непременно ще се появи празна кутия. Следователно най-малкият възможен брой монети при 20122012 кутии е2⋅2012−2=4022.2\cdot2012-2=4022.
Отвори задачатаMathNetISL 2012 C4Условие — източник

Задача C5

Пълен запис
Условие
Стълбовете и редовете на квадратна дъска 3n×3n3n\times3n са номерирани с 1,2,…,3n1,2,\ldots,3n. Всяко квадратче (x,y)(x,y), където 1≤x,y≤3n1\le x,y\le3n, е оцветено в аспержово, византийско или цитриново според това дали остатъкът на x+yx+y по модул 33 е съответно 00, 11 или 22. Върху всяко квадратче е поставен един жетон, оцветен в един от тези три цвята, като има по 3n23n^2 жетона от всеки цвят. Да предположим, че жетоните могат да се пермутират така, че всеки жетон да се премести на разстояние най-много dd от първоначалното си място, всеки аспержов жетон да замести византийски жетон, всеки византийски жетон да замести цитринов жетон и всеки цитринов жетон да замести аспержов жетон. Докажете, че жетоните могат да се пермутират така, че всеки жетон да се премести на разстояние най-много d+2d+2 от първоначалното си място и всяко квадратче да съдържа жетон със същия цвят като квадратчето.
РешениеБез ограничение е достатъчно да докажем, че аспержовите жетони могат да се преместят върху различни аспержови квадратчета така, че всеки от тях да измине разстояние най-много d+2d+2. С други думи, трябва ни перфектно съчетание между 3n23n^2-те аспержови квадратчета и 3n23n^2-те аспержови жетона, при което разстоянието във всяка съчетана двойка е най-много d+2d+2. Ще построим двуделен граф. В едната му част са аспержовите квадратчета, а в другата са аспержовите жетони. Разделяме дъската на хоризонтални тримина с размер 3×13\times1; всяко такова тримино съдържа точно едно аспержово квадратче. Нека π\pi е дадената пермутация на жетоните, която праща аспержови жетони на местата на византийски жетони, византийски жетони на местата на цитринови жетони и цитринови жетони на местата на аспержови жетони, като всяко преместване е на разстояние най-много dd. За аспержово квадратче SS и аспержов жетон TT свързваме SS и TT с ребро, ако някой от жетоните TT, π(T)\pi(T) или π−1(T)\pi^{-1}(T) се намира в триминото, съдържащо SS. Допускаме кратни ребра. Възможно е дори едно и също квадратче и един и същ жетон да са свързани с три ребра. Ясно е, че дължината на всяко ребро, тоест разстоянието между аспержовото квадратче и аспержовия жетон, който то свързва, е най-много d+2d+2. Всеки аспержов жетон TT е свързан с трите аспержови квадратчета, чиито тримина съдържат съответно TT, π(T)\pi(T) и π−1(T)\pi^{-1}(T). Следователно всички жетони имат степен 33 в графа. Ще покажем, че същото важи и за аспержовите квадратчета. Нека SS е произволно аспержово квадратче и нека T1,T2,T3T_1,T_2,T_3 са трите жетона в триминото, съдържащо SS. За i=1,2,3i=1,2,3 ако TiT_i е аспержов жетон, то SS е свързано с TiT_i; ако TiT_i е византийски жетон, то SS е свързано с π−1(Ti)\pi^{-1}(T_i); а ако TiT_i е цитринов жетон, то SS е свързано с π(Ti)\pi(T_i). Значи и всички аспержови квадратчета имат степен 33. Нека S\mathcal S е произволно множество от аспержови квадратчета. От тях излизат точно 3∣S∣3|\mathcal S| ребра. Тези ребра завършват в поне ∣S∣|\mathcal S| аспержови жетона, защото всеки аспержов жетон има степен 33. Следователно всяко множество S\mathcal S от аспержови квадратчета има поне ∣S∣|\mathcal S| съседи сред аспержовите жетони. По теоремата на Хол графът съдържа перфектно съчетание между двете си части. Това дава съчетаване на аспержовите квадратчета с аспержовите жетони, при което всяко ребро има дължина най-много d+2d+2. Прилагайки същия аргумент за другите два цвята, получаваме пермутацията, която поставя върху всяко квадратче жетон със същия цвят и премества всеки жетон на разстояние най-много d+2d+2.
Отвори задачатаMathNetISL 2012 C5Условие — източник

Задача C6

Пълен запис
Условие
Нека kk и nn са фиксирани положителни цели числа. В играта на отгатване с лъжи Ейми избира цели числа xx и NN с 1≤x≤N1\le x\le N. Тя казва на Бен какво е NN, но не и какво е xx. След това Бен може многократно да пита Ейми дали x∈Sx\in S за произволни множества SS от цели числа. Ейми винаги отговаря с „да“ или „не“, но може да лъже. Единственото ограничение е, че тя може да излъже най-много kk пъти поред. След като зададе колкото въпроси желае, Бен трябва да посочи множество от най-много nn положителни цели числа. Ако xx е в това множество, той печели; иначе губи. Докажете, че: а) ако n≥2kn\ge 2^k, Бен винаги може да спечели; б) за достатъчно големи kk съществува n≥1.99kn\ge 1.99^k, за което Бен не може да си гарантира победа.
РешениеДа разгледаме отговор A∈{да,не}A\in\{\text{да},\text{не}\} на въпрос от вида „xx принадлежи ли на множеството SS?“. Ще казваме, че AA е несъвместим с число ii, ако A=даA=\text{да} и i∉Si\notin S, или ако A=неA=\text{не} и i∈Si\in S. Отговор, несъвместим с търсеното число xx, е лъжа. а) Да предположим, че Бен е установил множество TT с mm елемента, което съдържа xx. В началото това е вярно за m=Nm=N и T={1,2,…,N}T=\{1,2,\ldots,N\}. Ще покажем, че ако m>2km\gt{}2^k, Бен може да намери число y∈Ty\in T, различно от xx. Повтаряйки тази стъпка, той може да свие TT до размер 2k≤n2^k\le n и така да спечели. Понеже е важен само размерът m>2km\gt{}2^k на TT, можем да считаме, че T={0,1,…,2k,…,m−1}T=\{0,1,\ldots,2^k,\ldots,m-1\}. Първо Бен пита многократно дали xx е равно на 2k2^k. Ако Ейми отговори „не“ k+1k+1 пъти поред, то поне един от тези отговори е истинен, следователно x≠2kx\ne 2^k. Иначе Бен спира да пита за 2k2^k при първия отговор „да“. След това за всяко i=1,2,…,ki=1,2,\ldots,k той пита дали в двоичния запис на xx цифрата на ii-тата позиция е 00. Каквито и да са тези kk отговора, съществува число y∈{0,1,…,2k−1}y\in\{0,1,\ldots,2^k-1\}, с което всички те са несъвместими: просто избираме всяка двоична цифра на yy противоположно на съответния отговор. Предходният отговор „да“ за числото 2k2^k също е несъвместим с yy, понеже y≠2ky\ne2^k. Ако беше y=xy=x, последните k+1k+1 отговора щяха да бъдат лъжи, което е невъзможно. Значи y≠xy\ne x. И в двата случая Бен намира число от TT, което е различно от xx. Така част а) е доказана. б) Ще докажем, че ако 1<λ<21\lt{}\lambda\lt{}2 иn=⌊(2−λ)λk+1⌋−1,n=\left\lfloor(2-\lambda)\lambda^{k+1}\right\rfloor-1,то Бен не може да си гарантира победа. За да завършим, е достатъчно да изберем λ\lambda с 1.99<λ<21.99\lt{}\lambda\lt{}2 и после kk достатъчно голямо, така чеn=⌊(2−λ)λk+1⌋−1≥1.99k.n=\left\lfloor(2-\lambda)\lambda^{k+1}\right\rfloor-1\ge1.99^k.Да опишем стратегията на Ейми. Най-напред тя избира N=n+1N=n+1 и произволно x∈{1,2,…,n+1}x\in\{1,2,\ldots,n+1\}. След всеки свой отговор тя определя за всяко i=1,2,…,n+1i=1,2,\ldots,n+1 броя mim_i на последователните последни отговори, които са несъвместими с ii. За да избере следващия си отговор, тя използва величинатаϕ=∑i=1n+1λmi.\phi=\sum_{i=1}^{n+1}\lambda^{m_i}.Независимо какъв е следващият въпрос на Бен, Ейми избира отговора, който минимизира ϕ\phi. Твърдим, че при тази стратегия винаги ще имаме ϕ<λk+1\phi\lt{}\lambda^{k+1}. Тогава никой показател mim_i в сумата не може да надхвърли kk, следователно Ейми никога не дава повече от kk последователни отговора, несъвместими с едно и също ii. В частност това важи за търсеното число xx, така че тя никога не лъже повече от kk пъти поред. Значи, ако твърдението е вярно, стратегията на Ейми е допустима. Тя не зависи от избраното xx, затова Бен не може да изключи никоя от стойностите 1,2,…,n+11,2,\ldots,n+1; поне една от тях остава извън всяко множество с най-много nn числа, което той посочи. Следователно той не може да си гарантира победа. Остава да докажем, че ϕ<λk+1\phi\lt{}\lambda^{k+1} във всеки момент. В началото всички mim_i са равни на 00, така чеϕ=n+1=⌊(2−λ)λk+1⌋<λk+1,\phi=n+1=\left\lfloor(2-\lambda)\lambda^{k+1}\right\rfloor\lt{}\lambda^{k+1},понеже 1<λ<21\lt{}\lambda\lt{}2. Да предположим, че в някакъв момент ϕ<λk+1\phi\lt{}\lambda^{k+1} и Бен пита дали x∈Sx\in S. Ако Ейми отговори съответно „да“ или „не“, новата стойност на ϕ\phi ще бъдеϕ1=∑i∈S1+∑i∉Sλmi+1\phi_1=\sum_{i\in S}1+\sum_{i\notin S}\lambda^{m_i+1}илиϕ2=∑i∈Sλmi+1+∑i∉S1.\phi_2=\sum_{i\in S}\lambda^{m_i+1}+\sum_{i\notin S}1.Понеже Ейми избира по-малката от двете стойности,min⁡(ϕ1,ϕ2)≤ϕ1+ϕ22=λϕ+n+12.\min(\phi_1,\phi_2)\le\frac{\phi_1+\phi_2}{2}=\frac{\lambda\phi+n+1}{2}.От ϕ<λk+1\phi\lt{}\lambda^{k+1}, λ<2\lambda\lt{}2 и n+1≤(2−λ)λk+1n+1\le(2-\lambda)\lambda^{k+1} получавамеmin⁡(ϕ1,ϕ2)<λk+2+(2−λ)λk+12=λk+1.\min(\phi_1,\phi_2)\lt{}\frac{\lambda^{k+2}+(2-\lambda)\lambda^{k+1}}2=\lambda^{k+1}.Това доказва твърдението и завършва решението.
Отвори задачатаMathNetISL 2012 C6Условие — източник

Задача C7

Пълен запис
Условие
Дадени са 25002^{500} точки върху окръжност, означени с 1,2,…,25001,2,\ldots,2^{500} в някакъв ред. Докажете, че могат да се изберат 100100 две по две непресичащи се хорди, свързващи някои от тези точки, така че 100100-те суми на двойките числа в краищата на избраните хорди да са равни.
РешениеДоказателството се основава на следния общ факт. Лема. Нека в граф GG всеки връх vv има степен dvd_v. Тогава GG съдържа независимо множество SS от върхове, такова че ∣S∣≥f(G)|S|\ge f(G), къдетоf(G)=∑v∈G1dv+1.f(G)=\sum_{v\in G}\frac1{d_v+1}.Доказателство на лемата. Ще използваме индукция по ∣G∣|G|. Случаят ∣G∣=1|G|=1 е ясен. За индукционната стъпка избираме връх v0v_0 с минимална степен dd. Изтриваме v0v_0 и всичките му съседи v1,…,vdv_1,\ldots,v_d и получаваме нов граф G′G'. По индукционното предположение G′G' съдържа независимо множество S′S', за което ∣S′∣≥f(G′)|S'|\ge f(G'). Понеже никой връх от S′S' не е съседен на v0v_0 в GG, множеството S=S′∪{v0}S=S'\cup\{v_0\} е независимо в GG. Нека dv′d'_v е степента на връх vv в G′G'. Ясно е, че dv′≤dvd'_v\le d_v за всеки останал връх vv, а от минималността на v0v_0 имаме dvi≥dd_{v_i}\ge d за i=0,1,…,di=0,1,\ldots,d. Следователноf(G′)=∑v∈G′1dv′+1≥f(G')=\sum_{v\in G'}\frac1{d'_v+1}\ge∑v∈G′1dv+1=f(G)−∑i=0d1dvi+1≥\sum_{v\in G'}\frac1{d_v+1}=f(G)-\sum_{i=0}^d\frac1{d_{v_i}+1}\gef(G)−d+1d+1=f(G)−1. f(G)-\frac{d+1}{d+1}=f(G)-1.Затова ∣S∣=∣S′∣+1≥f(G′)+1≥f(G)|S|=|S'|+1\ge f(G')+1\ge f(G) и индукцията е завършена. Връщаме се към задачата. За удобство нека n=2499n=2^{499}, така че дадените точки са 2n2n. Построяваме всички хорди, определени от тези 2n2n точки. Оцветяваме всяка хорда с един от цветовете 3,4,…,4n−13,4,\ldots,4n-1 според сумата на числата в краищата й. Хорди с общ край имат различни цветове. За всеки цвят cc разглеждаме граф GcG_c. Неговите върхове са хордите с цвят cc, а две хорди са съседни в GcG_c, ако се пресичат. Нека f(Gc)f(G_c) има същия смисъл като в лемата. Всяка хорда ℓ\ell разделя окръжността на две дъги и едната от тях съдържа m(ℓ)≤n−1m(\ell)\le n-1 от дадените точки. В частност m(ℓ)=0m(\ell)=0, ако ℓ\ell свързва две съседни точки. За всяко i=0,1,…,n−2i=0,1,\ldots,n-2 има точно 2n2n хорди ℓ\ell с m(ℓ)=im(\ell)=i. Такава хорда има степен най-много ii в съответния граф. Наистина, нека A1,…,AiA_1,\ldots,A_i са всички дадени точки върху една от дъгите, определени от хорда ℓ\ell с m(ℓ)=im(\ell)=i и цвят cc. Всяка точка AjA_j може да бъде край на най-много една хорда с цвят cc, понеже другият край е определен еднозначно от сумата cc. Следователно най-много ii хорди с цвят cc пресичат ℓ\ell. Оттук за всяко i=0,1,…,n−2i=0,1,\ldots,n-2 тези 2n2n хорди с m(ℓ)=im(\ell)=i дават принос поне 2n/(i+1)2n/(i+1) към сумата ∑cf(Gc)\sum_c f(G_c). Сумирайки по ii, получаваме∑cf(Gc)≥2n∑i=1n−11i.\sum_c f(G_c)\ge 2n\sum_{i=1}^{n-1}\frac1i.Цветовете са общо 4n−34n-3, затова по принципа на средното съществува цвят cc, за койтоf(Gc)≥2n4n−3∑i=1n−11i>f(G_c)\ge\frac{2n}{4n-3}\sum_{i=1}^{n-1}\frac1i\gt{}12∑i=1n−11i.\frac12\sum_{i=1}^{n-1}\frac1i.По лемата в GcG_c има поне 12∑i=1n−11/i\frac12\sum_{i=1}^{n-1}1/i две по две несъседни върха, тоест две по две непресичащи се хорди с един и същ цвят cc. Това означава, че сумите на числата в краищата им са равни. Остава да проверим, че при n=2499n=2^{499} тези хорди са поне 100100. Наистина,∑i=1n−11i>\sum_{i=1}^{n-1}\frac1i\gt{}1+∑r=1400∑i=2r−1+12r1i>1+\sum_{r=1}^{400}\sum_{i=2^{r-1}+1}^{2^r}\frac1i\gt{}1+∑r=14002r−12r=201>200.1+\sum_{r=1}^{400}\frac{2^{r-1}}{2^r}=201\gt{}200.Следователно половината от тази сума е по-голяма от 100100, което дава нужните 100100 хорди.
Отвори задачатаMathNetISL 2012 C7Условие — източник

Задача N1

Пълен запис
Условие
Ще наричаме множество AA от цели числа допустимо, ако има следното свойство: ако x,y∈Ax,y\in A (възможно е x=yx=y), то x2+kxy+y2∈Ax^2+kxy+y^2\in A за всяко цяло число kk. Определете всички двойки ненулеви цели числа m,nm,n, за които единственото допустимо множество, съдържащо и mm, и nn, е множеството на всички цели числа.
РешениеОтговорът е: точно двойките с gcd⁡(m,n)=1\gcd(m,n)=1. Първо нека gcd⁡(m,n)=d>1\gcd(m,n)=d\gt{}1. Тогава множествотоA={…,−2d,−d,0,d,2d,…}A=\{\ldots,-2d,-d,0,d,2d,\ldots\}е допустимо, защото ако dd дели xx и yy, то дели и x2+kxy+y2x^2+kxy+y^2 за всяко цяло kk. Освен това m,n∈Am,n\in A, но A≠ZA\ne\mathbb Z. Значи такива двойки не вършат работа. Нека сега gcd⁡(m,n)=1\gcd(m,n)=1 и нека AA е допустимо множество, съдържащо mm и nn. Ще използваме две прости следствия от допустимостта: 1. ако x∈Ax\in A, то kx2∈Akx^2\in A за всяко цяло число kk; 2. ако x,y∈Ax,y\in A, то (x+y)2∈A(x+y)^2\in A. Първото следва, като в определението вземем y=xy=x, понеже тогава получаваме произволно цяло кратно на x2x^2. Второто следва при k=2k=2. Понеже gcd⁡(m,n)=1\gcd(m,n)=1, имаме и gcd⁡(m2,n2)=1\gcd(m^2,n^2)=1. Следователно съществуват цели числа a,ba,b, за коитоam2+bn2=1.am^2+bn^2=1.От първото наблюдение am2∈Aam^2\in A и bn2∈Abn^2\in A. По второто наблюдение получаваме1=(am2+bn2)2∈A.1=(am^2+bn^2)^2\in A.Накрая отново по първото наблюдение, приложено към x=1x=1, следва, че всяко цяло число принадлежи на AA. Значи A=ZA=\mathbb Z, както трябваше.
Отвори задачатаMathNetISL 2012 N1Условие — източник

Задача N2

Пълен запис
Условие
Да се намерят всички тройки (x,y,z)(x,y,z) от положителни цели числа, за които x≤y≤zx\le y\le z иx3(y3+z3)=2012(xyz+2).x^3(y^3+z^3)=2012(xyz+2).
РешениеОтговорът е единствената тройка(x,y,z)=(2,251,252).(x,y,z)=(2,251,252).Първо забелязваме, че xx дели 2012⋅2=23⋅5032012\cdot2=2^3\cdot503. Наистина, от даденото равенство следва, че x3x^3 дели 2012(xyz+2)2012(xyz+2), а xyz+2≡2(modx)xyz+2\equiv2\pmod x. Ако 503∣x503\mid x, то дясната страна на равенството се дели на 5033503^3, откъдето 5032∣xyz+2503^2\mid xyz+2. Това е невъзможно, понеже тогава xyz+2≡2(mod503)xyz+2\equiv2\pmod{503}. Следователно x=2mx=2^m за някое m∈{0,1,2,3}m\in\{0,1,2,3\}. Ако m≥2m\ge2, то 262^6 трябва да дели 2012(xyz+2)2012(xyz+2). Но v2(2012)=2v_2(2012)=2, а xyz+2=2myz+2xyz+2=2^m yz+2 се дели точно на 22, когато m≥2m\ge2. Противоречие. Значи x=1x=1 или x=2x=2. Получаваме съответно двете уравненияy3+z3=2012(yz+2)(1)y^3+z^3=2012(yz+2)\tag{1}иy3+z3=503(yz+1).(2)y^3+z^3=503(yz+1).\tag{2}И в двата случая простото число 503=3⋅167+2503=3\cdot167+2 дели y3+z3y^3+z^3. Ще докажем, че 503∣y+z503\mid y+z. Ако 503503 дели едното от числата y,zy,z, то от 503∣y3+z3503\mid y^3+z^3 дели и другото, така че твърдението е ясно. Нека сега 503∤yz503\nmid yz. По малката теорема на Ферма имаме y502≡z502(mod503)y^{502}\equiv z^{502}\pmod{503}, а от y3≡−z3(mod503)y^3\equiv-z^3\pmod{503} следваy501≡−z501(mod503).y^{501}\equiv-z^{501}\pmod{503}.Делим тези две сравнения и получаваме y≡−z(mod503)y\equiv-z\pmod{503}. Значи y+z=503ky+z=503k за някое k≥1k\ge1. Понежеy3+z3=(y+z)((y−z)2+yz),y^3+z^3=(y+z)((y-z)^2+yz),уравненията (1) и (2) стават съответноk(y−z)2+(k−4)yz=8(3)k(y-z)^2+(k-4)yz=8\tag{3}иk(y−z)2+(k−1)yz=1.(4)k(y-z)^2+(k-1)yz=1.\tag{4}Нека първо разгледаме (3). От (k−4)yz≤8(k-4)yz\le8 следва k≤4k\le4: ако k>4k\gt{}4, то 1≤(k−4)yz≤81\le(k-4)yz\le8, откъдето y,z≤8y,z\le8, невъзможно заради y+z=503k≥503y+z=503k\ge503. Освен това в (1) числото y3+z3y^3+z^3 е четно, следователно y+z=503ky+z=503k е четно и kk е четно. Така k=2k=2 или k=4k=4. При k=4k=4 от (3) получаваме 4(y−z)2=84(y-z)^2=8, което няма цели решения. При k=2k=2 уравнението (3) е еквивалентно на(y+z)2−5yz=4.(y+z)^2-5yz=4.Но тогава 5yz=5032⋅22−45yz=503^2\cdot2^2-4, а дясната страна не се дели на 55. Следователно (1) не дава решения. Остава (4). От 0≤(k−1)yz≤10\le(k-1)yz\le1 получаваме k=1k=1 или k=2k=2, а от 0≤k(y−z)2≤10\le k(y-z)^2\le1 следва, че при k=2k=2 непременно y=zy=z. Тогава обаче (4) би дало yz=1yz=1, което противоречи на y+z=503k≥503y+z=503k\ge503. Значи k=1k=1, и (4) се свежда до(y−z)2=1.(y-z)^2=1.Понеже y≤zy\le z, имаме z−y=1z-y=1, а заедно с y+z=503y+z=503 това дава y=251y=251 и z=252z=252. При x=2x=2, y=251y=251, z=252z=252 уравнението наистина е изпълнено, затова това е единственото решение.
Отвори задачатаMathNetISL 2012 N2Условие — източник

Задача N3

Пълен запис
Условие
Да се намерят всички цели числа m≥2m\ge2 със следното свойство: за всяко цяло число nn, за коетоm3≤n≤m2,\frac m3\le n\le\frac m2,числото nn дели биномния коефициент (nm−2n)\binom n{m-2n}.
РешениеОтговорът е: всички прости числа. Първо ще проверим, че всяко просто число работи, и дори ще докажем малко по-силно твърдение. Нека pp е просто число. Ще покажем, че за всяко цяло число nn с 1≤n≤p/21\le n\le p/2 числото nn дели(np−2n).\binom n{p-2n}.За p=2p=2 има само n=1n=1 и твърдението е очевидно. Нека pp е нечетно просто число. Тогава p−2np-2n е положително и имаме тъждеството(p−2n)(np−2n)=n(n−1p−2n−1).(p-2n)\binom n{p-2n}=n\binom{n-1}{p-2n-1}.Ако d=gcd⁡(p−2n,n)d=\gcd(p-2n,n), то dd дели pp, но d≤n<pd\le n\lt{}p, следователно d=1d=1. Значи p−2np-2n и nn са взаимнопрости. От горното тъждество следва, че nn дели (p−2n)(np−2n)(p-2n)\binom n{p-2n}, а поради взаимната простота всъщност nn дели (np−2n)\binom n{p-2n}. Така всички прости pp удовлетворяват условието от задачата. Остава да изключим съставните числа mm. Ако m=2km=2k с k>1k\gt{}1, избираме n=kn=k. Тогава m/3≤n≤m/2m/3\le n\le m/2, но(nm−2n)=(k0)=1\binom n{m-2n}=\binom k0=1не се дели на kk. Нека сега mm е нечетно съставно число. Тогава има нечетно просто число pp и цяло число k≥1k\ge1, за коитоm=p(2k+1).m=p(2k+1).Избираме n=pkn=pk. Имаме m/3≤n≤m/2m/3\le n\le m/2, а m−2n=pm-2n=p. Ще покажем, че nn не дели (nm−2n)=(pkp)\binom n{m-2n}=\binom{pk}p. Действително,1n(nm−2n)=1pk(pkp)=\frac1n\binom n{m-2n}=\frac1{pk}\binom{pk}p=(pk−1)(pk−2)⋯(pk−(p−1))p!.\frac{(pk-1)(pk-2)\cdots(pk-(p-1))}{p!}.В знаменателя има множител pp, а никой от множителите в числителя не се дели на pp. Следователно последната дроб не е цяло число. Значи условието не е изпълнено за нито едно съставно mm. Така търсените числа mm са точно простите числа.
Отвори задачатаMathNetISL 2012 N3Условие — източник

Задача N4

Пълен запис
Условие
Цяло число aa се нарича дружелюбно, ако уравнението(m2+n)(n2+m)=a(m−n)3(m^2+n)(n^2+m)=a(m-n)^3има решение в положителни цели числа m,nm,n. а) Докажете, че в множеството {1,2,…,2012}\{1,2,\ldots,2012\} има поне 500500 дружелюбни числа. б) Решете дали a=2a=2 е дружелюбно.
Решениеа) Ще покажем, че всяко число от вида a=4k−3a=4k-3 при k≥2k\ge2 е дружелюбно. Наистина, вземамеm=2k−1,n=k−1.m=2k-1,\qquad n=k-1.Тогава m,nm,n са положителни цели числа и((2k−1)2+(k−1))((k−1)2+(2k−1))=((2k-1)^2+(k-1))((k-1)^2+(2k-1))=(4k−3)k3=a(m−n)3.(4k-3)k^3=a(m-n)^3.Значи числата5,9,13,…,20095,9,13,\ldots,2009са дружелюбни. Те са 502502 на брой, така че в {1,2,…,2012}\{1,2,\ldots,2012\} има поне 500500 дружелюбни числа. б) Ще докажем, че a=2a=2 не е дружелюбно. Да допуснем противното. Тогава за някои положителни цели m,nm,n е изпълнено(m2+n)(n2+m)=2(m−n)3.(m^2+n)(n^2+m)=2(m-n)^3.Дясната страна е положителна, следователно m>nm\gt{}n. Записваме лявата страна като разлика на квадрати:14((m2+n+n2+m)2−(m2+n−n2−m)2)=\frac14\left((m^2+n+n^2+m)^2-(m^2+n-n^2-m)^2\right)=2(m−n)3.2(m-n)^3.Понежеm2+n−n2−m=(m−n)(m+n−1),m^2+n-n^2-m=(m-n)(m+n-1),получаваме(m2+n+n2+m)2=(m−n)2(8(m−n)+(m+n−1)2).(m^2+n+n^2+m)^2=(m-n)^2\left(8(m-n)+(m+n-1)^2\right).Затова числото 8(m−n)+(m+n−1)28(m-n)+(m+n-1)^2 е точен квадрат. То е по-голямо от (m+n−1)2(m+n-1)^2 и има същата четност като m+n−1m+n-1, следователно за някое цяло s≥1s\ge1 имаме(m+n−1+2s)2=8(m−n)+(m+n−1)2.(m+n-1+2s)^2=8(m-n)+(m+n-1)^2.След изваждане на квадратите получавамеs(m+n−1+s)=2(m−n).s(m+n-1+s)=2(m-n).Но m+n−1+s>m−nm+n-1+s\gt{}m-n, откъдето s<2s\lt{}2. Значи s=1s=1, а тогава от последното равенство следва m=3nm=3n. При m=3nm=3n лявата страна на първоначалното уравнение е по-голяма от m3=27n3m^3=27n^3, докато дясната страна е2(m−n)3=16n3.2(m-n)^3=16n^3.Това е противоречие. Следователно a=2a=2 не е дружелюбно.
Отвори задачатаMathNetISL 2012 N4Условие — източник

Задача N5

Пълен запис
Условие
За неотрицателно цяло число nn дефинираме rad⁡(n)=1\operatorname{rad}(n)=1, ако n=0n=0 или n=1n=1, и rad⁡(n)=p1p2⋯pk\operatorname{rad}(n)=p_1p_2\cdots p_k, където p1<p2<⋯<pkp_1\lt{}p_2\lt{}\cdots\lt{}p_k са всички прости делители на nn. Намерете всички полиноми f(x)f(x) с неотрицателни цели коефициенти, за които rad⁡(f(n))\operatorname{rad}(f(n)) дели rad⁡(f(nrad⁡(n)))\operatorname{rad}\left(f\left(n^{\operatorname{rad}(n)}\right)\right) за всяко неотрицателно цяло число nn.
РешениеОтговорът еf(x)=axm,f(x)=ax^m,където aa и mm са неотрицателни цели числа. Нулевият полином също е включен, като вземем a=0a=0. Такива полиноми очевидно работят: простите делители на anma n^m се съдържат сред простите делители на aa и nn, а същото важи и за a(nrad⁡(n))ma\left(n^{\operatorname{rad}(n)}\right)^m. Остава да докажем, че други няма. Ще използваме следното твърдение. Твърдение. Нека f(x)∈Z[x]f(x)\in\mathbb Z[x] има даденото свойство. Ако ξ\xi е корен на ff, то ξd\xi^d също е корен на ff за всяко положително цяло число dd. Достатъчно е да докажем твърдението за просто d=qd=q, защото всяко dd е произведение на прости числа. Нека g(x)g(x) е неприводим множител на f(x)f(x) над Z\mathbb Z, за който g(ξ)=0g(\xi)=0. Ако ξ=0\xi=0 или ξ=1\xi=1, няма какво да доказваме. Затова можем да приемем, че g(0)g(1)≠0g(0)g(1)\ne0. Ще докажем, че g(x)g(x) дели f(xq)f(x^q). Да допуснем противното. Тогава, след тъждеството на Безу над Q[x]\mathbb Q[x] и умножение с общ знаменател, съществуват полиноми A(x),B(x)∈Z[x]A(x),B(x)\in\mathbb Z[x] и ненулево цяло число NN, такива чеA(x)g(x)+B(x)f(xq)=N.(1)A(x)g(x)+B(x)f(x^q)=N.\tag{1}За всяко k≥0k\ge0 имаме rad⁡(qk)=q\operatorname{rad}(q^k)=q. От условието следва, че всеки прост делител на f(qk)f(q^k) дели f(qqk)f(q^{qk}). Понеже всеки прост делител на g(qk)g(q^k) дели f(qk)f(q^k), от (1) при x=qkx=q^k заключаваме, че всеки прост делител на g(qk)g(q^k) дели фиксираното число NN. Нека ℓ1,…,ℓs\ell_1,\ldots,\ell_s са простите делители на NN, различни от qq, и нека αi=vℓi(g(1))\alpha_i=v_{\ell_i}(g(1)). Избираме kk кратно наφ(ℓ1α1+1⋯ℓsαs+1).\varphi\left(\ell_1^{\alpha_1+1}\cdots \ell_s^{\alpha_s+1}\right).Тогава qk≡1(modℓiαi+1)q^k\equiv1\pmod{\ell_i^{\alpha_i+1}} за всяко ii, следователноg(qk)≡g(1)(modℓiαi+1).g(q^k)\equiv g(1)\pmod{\ell_i^{\alpha_i+1}}.Значи най-високата степен на ℓi\ell_i, която дели g(qk)g(q^k), е най-много фиксираната степен ℓiαi\ell_i^{\alpha_i}. От друга страна, за достатъчно голямо kk най-високата степен на qq, която дели g(qk)g(q^k), е ограничена от фиксирано число, зависещо само от g(0)≠0g(0)\ne0. Получаваме, че за безкрайно много kk числото g(qk)g(q^k) дели едно фиксирано ненулево цяло число. Това е невъзможно, защото ∣g(qk)∣|g(q^k)| расте неограничено. Следователно g(x)∣f(xq)g(x)\mid f(x^q) и от g(ξ)=0g(\xi)=0 следва f(ξq)=0f(\xi^q)=0. Твърдението е доказано. Сега се връщаме към задачата. Ако ξ≠0\xi\ne0 е корен на ff, то всички числа ξd\xi^d са корени на ff. Понеже един ненулев полином има краен брой корени, ξ\xi трябва да е корен на единицата. Тогава за някое dd имаме ξd=1\xi^d=1, следователно 11 също е корен на ff. Но ако ff не е нулевият полином и всичките му коефициенти са неотрицателни, то f(1)>0f(1)\gt{}0. Значи ненулевите корени са невъзможни и единственият възможен корен е 00. Следователно ненулевият ff има вида axmax^m с a>0a\gt{}0 и m≥0m\ge0. Заедно с нулевия полином това дава точно посочения отговор.
Отвори задачатаMathNetISL 2012 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека xx и yy са положителни цели числа. Ако x2n−1x^{2^n}-1 се дели на 2ny+12^ny+1 за всяко положително цяло число nn, докажете, че x=1x=1.
РешениеПърво ще докажем следния факт: за всяко положително цяло число yy съществуват безброй много прости числа p≡3(mod4)p\equiv3\pmod4, които делят някое число от вида 2ny+12^ny+1. Достатъчно е да разгледаме случая, когато yy е нечетно. Нека2y+1=p1e1⋯prer2y+1=p_1^{e_1}\cdots p_r^{e_r}е разлагането на 2y+12y+1 на прости множители. Да допуснем, че има само краен брой прости числаpr+1,…,pr+s≡3(mod4),p_{r+1},\ldots,p_{r+s}\equiv3\pmod4,които делят някое число от вида 2ny+12^ny+1, но не делят 2y+12y+1. Ще изберем nn, така че piei∥2ny+1p_i^{e_i}\Vert 2^ny+1 за 1≤i≤r1\le i\le r, а pi∤2ny+1p_i\nmid2^ny+1 за r+1≤i≤r+sr+1\le i\le r+s. Достатъчно е да вземемn=1+φ(p1e1+1⋯prer+1pr+1⋯pr+s),n=1+\varphi\left(p_1^{e_1+1}\cdots p_r^{e_r+1}p_{r+1}\cdots p_{r+s}\right),защото тогава2ny+1≡2y+1(modp1e1+1⋯prer+1pr+1⋯pr+s).2^ny+1\equiv2y+1\pmod{p_1^{e_1+1}\cdots p_r^{e_r+1}p_{r+1}\cdots p_{r+s}}.Следователно разлагането на 2ny+12^ny+1 съдържа точно степените p1e1,…,prerp_1^{e_1},\ldots,p_r^{e_r} от старите прости делители и евентуално степени на прости числа, които са 11 по модул 44. Понеже yy е нечетно, получаваме2ny+1≡p1e1⋯prer≡2y+1≡3(mod4).2^ny+1\equiv p_1^{e_1}\cdots p_r^{e_r}\equiv2y+1\equiv3\pmod4.Това е противоречие, защото n>1n\gt{}1 и тогава 2ny+1≡1(mod4)2^ny+1\equiv1\pmod4. Фактът е доказан. Сега нека pp е прост делител на някое 2ny+12^ny+1. От условието следваx2n≡1(modp).x^{2^n}\equiv1\pmod p.По малката теорема на Ферма имаме и xp−1≡1(modp)x^{p-1}\equiv1\pmod p, освен в тривиалния случай p∣xp\mid x, който е невъзможен от първото сравнение. Значиxgcd⁡(2n,p−1)≡1(modp).x^{\gcd(2^n,p-1)}\equiv1\pmod p.Ако p≡3(mod4)p\equiv3\pmod4, то gcd⁡(2n,p−1)=2\gcd(2^n,p-1)=2, следователноx2≡1(modp).x^2\equiv1\pmod p.От доказания факт има безброй много такива прости числа p≡3(mod4)p\equiv3\pmod4, които делят някое 2ny+12^ny+1. Всички те делят x2−1x^2-1. Ако x>1x\gt{}1, това е невъзможно, защото ненулевото цяло число x2−1x^2-1 има само краен брой прости делители. Следователно x=1x=1.
Отвори задачатаMathNetISL 2012 N6Условие — източник

Задача N7

Пълен запис
Условие
Докажете, че за всяко просто число p>100p\gt{}100 и всяко цяло число rr съществуват цели числа aa и bb, такива, че pp дели a2+b5−ra^2+b^5-r.
РешениеФиксираме pp и нека P={0,1,…,p−1}\mathcal P=\{0,1,\ldots,p-1\} е множеството от класовете остатъци по модул pp. За всеки r∈Pr\in\mathcal P полагаме Sr={(a,b)∈P×P∣a2+b5≡r(modp)}S_r=\{(a,b)\in\mathcal P\times\mathcal P\mid a^2+b^5\equiv r\pmod p\} и sr=∣Sr∣s_r=|S_r|. Трябва да докажем, че sr>0s_r\gt{}0 за всяко r∈Pr\in\mathcal P. Ще използваме следния стандартен факт: за всеки клас остатъци r∈Pr\in\mathcal P и всяко положително цяло число kk сравнението xk≡r(modp)x^k\equiv r\pmod p има най-много kk решения x∈Px\in\mathcal P. Лема. Нека NN е броят на четворките (a,b,c,d)∈P4(a,b,c,d)\in\mathcal P^4, за които a2+b5≡c2+d5(modp).a^2+b^5\equiv c^2+d^5\pmod p. ТогаваN=∑r∈Psr2N=\sum_{r\in\mathcal P}s_r^2иN≤p(p2+4p−4).N\le p(p^2+4p-4).Доказателство на лемата. За фиксиран клас rr има точно srs_r двойки (a,b)(a,b), за които a2+b5≡r(modp)a^2+b^5\equiv r\pmod p, и точно srs_r двойки (c,d)(c,d), за които c2+d5≡r(modp)c^2+d^5\equiv r\pmod p. Следователно броят на четворките с обща стойност rr е sr2s_r^2, а сумирането по r∈Pr\in\mathcal P дава първото равенство. За оценката избираме произволна двойка (b,d)∈P2(b,d)\in\mathcal P^2 и броим възможните двойки (a,c)(a,c). Нека kk е броят на двойките (b,d)(b,d), за които b5≡d5(modp)b^5\equiv d^5\pmod p. Ако b≡0b\equiv0, то само d=0d=0 е възможно; ако b≢0b\not\equiv0, тогава за dd има най-много 55 възможности. Значи k≤1+5(p−1)=5p−4.k\le1+5(p-1)=5p-4.При b5≡d5(modp)b^5\equiv d^5\pmod p трябва да имаме a2≡c2(modp)a^2\equiv c^2\pmod p, тоест a≡±c(modp)a\equiv\pm c\pmod p, което дава точно 2p−12p-1 двойки (a,c)(a,c). При b5≢d5(modp)b^5\not\equiv d^5\pmod p уравнението става (a−c)(a+c)≡d5−b5(modp).(a-c)(a+c)\equiv d^5-b^5\pmod p. Тогава a−ca-c не може да е нула и всяка от p−1p-1 ненулеви стойности на a−ca-c определя еднозначно a+ca+c, а оттам и a,ca,c. СледователноN=k(2p−1)+(p2−k)(p−1)=p2(p−1)+kp≤p2(p−1)+(5p−4)p=p(p2+4p−4).\begin{aligned} N&=k(2p-1)+(p^2-k)(p-1)\\ &=p^2(p-1)+kp\\ &\le p^2(p-1)+(5p-4)p=p(p^2+4p-4). \end{aligned}Лемата е доказана. Сега да допуснем противното: Sr=∅S_r=\emptyset за някое r∈Pr\in\mathcal P. Ясно е, че r≢0(modp)r\not\equiv0\pmod p. Нека T={x10∣x∈P∖{0}}T=\{x^{10}\mid x\in\mathcal P\setminus\{0\}\} е множеството от ненулевите десети степени по модул pp. Понеже всеки клас остатъци е десета степен на най-много 1010 елемента от P\mathcal P, имаме ∣T∣≥p−110≥4.|T|\ge\frac{p-1}{10}\ge4.За всяко t∈Tt\in T имаме Str=∅S_{tr}=\emptyset. Наистина, ако (x,y)∈Str(x,y)\in S_{tr} и t≡z10(modp)t\equiv z^{10}\pmod p, то(z−5x)2+(z−2y)5≡t−1(x2+y5)≡r(modp),(z^{-5}x)^2+(z^{-2}y)^5\equiv t^{-1}(x^2+y^5)\equiv r\pmod p,което би дало елемент на SrS_r, противоречие. Следователно поне ∣T∣≥4|T|\ge4 от множествата SqS_q са празни. Всички p2p^2 двойки (a,b)(a,b) лежат в останалите най-много p−4p-4 множества. По неравенството между квадратичното и аритметичното средно получавамеN=∑q∈P∖rTsq2≥N=\sum_{q\in\mathcal P\setminus rT}s_q^2\ge1p−4(∑q∈P∖rTsq)2=p4p−4.\frac1{p-4}\left(\sum_{q\in\mathcal P\setminus rT}s_q\right)^2=\frac{p^4}{p-4}.Но при p>100p\gt{}100 имаме p4p−4>p(p2+4p−4),\frac{p^4}{p-4}\gt{}p(p^2+4p-4), което противоречи на лемата. Следователно всяко SrS_r е непразно, както искахме да докажем.
Отвори задачатаMathNetISL 2012 N7Условие — източник