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

IMO Shortlisted Problems

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

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

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

2016

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

11-12

24 задачи

Задача A1

Пълен запис
Условие
Нека a,b,ca,b,c са положителни реални числа, за които min⁡{ab,bc,ca}≥1\min\{ab,bc,ca\}\ge1. Докажете, чеx2(a2+1)(b2+1)(c2+1)3≤\sqrt[3]{\vphantom{x^2}(a^2+1)(b^2+1)(c^2+1)}\le(a+b+c3)2+1.\left(\frac{a+b+c}{3}\right)^2+1.
РешениеПърво ще докажем следното твърдение: ако x,y>0x,y\gt{}0 и xy≥1xy\ge1, то(x2+1)(y2+1)≤((x+y2)2+1)2.(1)(x^2+1)(y^2+1)\le\left(\left(\frac{x+y}{2}\right)^2+1\right)^2.\tag{1}Наистина, от xy≥1xy\ge1 и AM-GM имаме (x+y2)2−1≥xy−1≥0\left(\frac{x+y}{2}\right)^2-1\ge xy-1\ge0. Следователно(x2+1)(y2+1)=(xy−1)2+(x+y)2≤((x+y2)2−1)2+(x+y)2=((x+y2)2+1)2.\begin{aligned} (x^2+1)(y^2+1)&=(xy-1)^2+(x+y)^2\\ &\le\left(\left(\frac{x+y}{2}\right)^2-1\right)^2+(x+y)^2\\ &=\left(\left(\frac{x+y}{2}\right)^2+1\right)^2. \end{aligned}Без ограничение на общността нека a≥b≥ca\ge b\ge c и положим d=a+b+c3d=\frac{a+b+c}{3}. Тогава ad=a2+ab+ac3≥1ad=\frac{a^2+ab+ac}{3}\ge1. Прилагайки (1) за двойките (a,d)(a,d) и (b,c)(b,c), получаваме(a2+1)(d2+1)(b2+1)(c2+1)≤(a^2+1)(d^2+1)(b^2+1)(c^2+1)\le((a+d2)2+1)2((b+c2)2+1)2.(2)\left(\left(\frac{a+d}{2}\right)^2+1\right)^2\left(\left(\frac{b+c}{2}\right)^2+1\right)^2.\tag{2}Освен товаa+d2⋅b+c2≥x2adx2bc≥1,\frac{a+d}{2}\cdot\frac{b+c}{2}\ge\sqrt{\vphantom{x^2}ad}\sqrt{\vphantom{x^2}bc}\ge1,така че отново по (1), приложено към a+d2\frac{a+d}{2} и b+c2\frac{b+c}{2}, дясната страна на (2) е най-много((a+b+c+d4)2+1)4=(d2+1)4.\left(\left(\frac{a+b+c+d}{4}\right)^2+1\right)^4=(d^2+1)^4.Следователно(a2+1)(b2+1)(c2+1)≤(d2+1)3.(a^2+1)(b^2+1)(c^2+1)\le(d^2+1)^3.След коренуване от трета степен получаваме исканото неравенство.
Отвори задачатаMathNetISL 2016 A1Условие — източник

Задача A2

Пълен запис
Условие
Да се намери най-малката реална константа CC, така че за всеки положителни реални числа a1,a2,a3,a4,a5a_1,a_2,a_3,a_4,a_5 (не непременно различни) могат да се изберат различни индекси i,j,k,li,j,k,l, за които∣aiaj−akal∣≤C.\left|\frac{a_i}{a_j}-\frac{a_k}{a_l}\right|\le C.
РешениеОтговорът еC=12.C=\frac12.Нека 0<a1≤a2≤a3≤a4≤a50\lt{}a_1\le a_2\le a_3\le a_4\le a_5. Разглеждаме петте дробиa1a2,a3a4,a1a5,a2a3,a4a5.\frac{a_1}{a_2},\quad \frac{a_3}{a_4},\quad \frac{a_1}{a_5},\quad \frac{a_2}{a_3},\quad \frac{a_4}{a_5}.Всички те лежат в интервала (0,1](0,1]. По принципа на Дирихле поне три от тях лежат едновременно в (0,12](0,\frac12] или едновременно в (12,1](\frac12,1]. В цикличния списък от пет дроби тогава има две съседни дроби, които лежат в интервал с дължина 12\frac12; тук считаме първата и последната дроб също за съседни. Всяка двойка съседни дроби използва четири различни индекса, затова за подходящ избор на i,j,k,li,j,k,l получаваме∣aiaj−akal∣≤12.\left|\frac{a_i}{a_j}-\frac{a_k}{a_l}\right|\le\frac12.Следователно C≤12C\le\frac12. Ще покажем, че по-малка константа не е възможна. Нека числата са 1,2,2,2,N1,2,2,2,N, където NN е голямо реално число. Възможните стойности на дроби от две от тези числа, подредени по големина, са1N,2N,12,1,2,N2,N.\frac1N,\quad \frac2N,\quad \frac12,\quad 1,\quad 2,\quad \frac N2,\quad N.Понеже четирите индекса трябва да са различни, дробите 1N\frac1N и 2N\frac2N не могат да се използват едновременно. Следователно най-малката възможна разлика между две допустими дроби е 12−2N\frac12-\frac2N. Когато N→∞N\to\infty, тази стойност клони към 12\frac12, така че CC не може да бъде по-малко от 12\frac12. Значи най-малката константа е 12\frac12.
Отвори задачатаMathNetISL 2016 A2Условие — източник

Задача A3

Пълен запис
Условие
Да се намерят всички цели числа n≥3n\ge3 със следното свойство: за всички реални числа a1,a2,…,ana_1,a_2,\ldots,a_n и b1,b2,…,bnb_1,b_2,\ldots,b_n, удовлетворяващи ∣ak∣+∣bk∣=1|a_k|+|b_k|=1 за 1≤k≤n1\le k\le n, съществуват числа x1,x2,…,xnx_1,x_2,\ldots,x_n, всяко от които е равно на −1-1 или 11, такива че∣∑k=1nxkak∣+∣∑k=1nxkbk∣≤1.\left|\sum_{k=1}^n x_ka_k\right|+\left|\sum_{k=1}^n x_kb_k\right|\le1.
РешениеОтговорът е: всички нечетни цели числа n≥3n\ge3. Нека първо n≥4n\ge4 е четно. Избирамеa1=a2=⋯=an−1=bn=0,a_1=a_2=\cdots=a_{n-1}=b_n=0,b1=b2=⋯=bn−1=an=1.\qquad b_1=b_2=\cdots=b_{n-1}=a_n=1.Тогава условието ∣ak∣+∣bk∣=1|a_k|+|b_k|=1 е изпълнено. Каквито и знаци xkx_k да изберем, първата сума е xnx_n, а втората е сума на нечетен брой числа, равни на −1-1 или 11. Значи и двете абсолютни стойности са поне 11, така че исканото неравенство не може да е вярно. Нека сега n≥3n\ge3 е нечетно. Можем да предполагаме, че bk≥0b_k\ge0 за всяко kk: ако bk<0b_k\lt{}0, заменяме едновременно (ak,bk)(a_k,b_k) с (−ak,−bk)(-a_k,-b_k) и по-късно сменяме знака на съответното xkx_k. След пренареждане некаa1≥a2≥⋯≥am≥0>am+1≥⋯≥an.a_1\ge a_2\ge\cdots\ge a_m\ge0\gt{}a_{m+1}\ge\cdots\ge a_n.Ще докажем, че изборът xk=(−1)k+1x_k=(-1)^{k+1} работи. Положимs=∑k=1mxkak,t=−∑k=m+1nxkak.s=\sum_{k=1}^m x_ka_k,\qquad t=-\sum_{k=m+1}^n x_ka_k.От монотонността на положителния блок получаваме0≤s≤a1≤1,0\le s\le a_1\le1,а по същия начин за отрицателния блок, използвайки че nn е нечетно,0≤t≤−an≤1.0\le t\le -a_n\le1.Понеже bk=1−akb_k=1-a_k за k≤mk\le m и bk=1+akb_k=1+a_k за k>mk\gt{}m, имаме∑k=1nxkak=s−t,∑k=1nxkbk=1−s−t.\sum_{k=1}^n x_ka_k=s-t,\qquad \sum_{k=1}^n x_kb_k=1-s-t.Остава да се провери, че∣s−t∣+∣1−s−t∣≤1(0≤s,t≤1).|s-t|+|1-s-t|\le1\qquad(0\le s,t\le1).По симетрия нека s≥ts\ge t. Ако 1−s−t≥01-s-t\ge0, лявата страна еs−t+1−s−t=1−2t≤1.s-t+1-s-t=1-2t\le1.Ако 1−s−t≤01-s-t\le0, тя еs−t−1+s+t=2s−1≤1.s-t-1+s+t=2s-1\le1.И в двата случая получаваме исканото неравенство. Следователно свойството е изпълнено точно за нечетните n≥3n\ge3.
Отвори задачатаMathNetISL 2016 A3Условие — източник

Задача A4

Пълен запис
Условие
Нека R>0\mathbb R_{\gt{}0} е множеството на положителните реални числа. Да се намерят всички функции f:R>0→R>0f:\mathbb R_{\gt{}0}\to\mathbb R_{\gt{}0}, за коитоxf(x2)f(f(y))+f(yf(x))=xf(x^2)f(f(y))+f(yf(x))=f(xy)(f(f(x2))+f(f(y2)))f(xy)\left(f(f(x^2))+f(f(y^2))\right)за всички положителни реални числа xx и yy.
РешениеОтговорът еf(x)=1x(x>0).f(x)=\frac1x\qquad(x\gt{}0).Поставяйки x=y=1x=y=1, получаваме f(1)=1f(1)=1. Ако разменим xx и yy в даденото равенство и сравним с него, намирамеxf(x2)f(f(y))+f(yf(x))=xf(x^2)f(f(y))+f(yf(x))=yf(y2)f(f(x))+f(xf(y)).(1)yf(y^2)f(f(x))+f(xf(y)).\tag{1}При y=1y=1 в (1) следваf(x2)=f(x)x.(2)f(x^2)=\frac{f(x)}x.\tag{2}От първоначалното равенство при y=1y=1, заедно с (2), получавамеf(f(x2))=f(f(x))f(x).(3)f(f(x^2))=\frac{f(f(x))}{f(x)}.\tag{3}Затова за всяко x>0x\gt{}0 е вярноf(f(x)2)=f(f(x))f(x)=f(f(x)^2)=\frac{f(f(x))}{f(x)}=f(f(x2))=f(f(x)x).(4)f(f(x^2))=f\left(\frac{f(x)}x\right).\tag{4}Ще докажем, че ff е инективна. С помощта на (2) и (3) началното равенство се записва катоf(x)f(f(y))+f(yf(x))=f(x)f(f(y))+f(yf(x))=f(xy)(f(f(x))f(x)+f(f(y))f(y)).(5)f(xy)\left(\frac{f(f(x))}{f(x)}+\frac{f(f(y))}{f(y)}\right).\tag{5}При x=yx=y в (5) получавамеf(xf(x))=f(f(x))(2x−f(x)).(6)f(xf(x))=f(f(x))\left(\frac2x-f(x)\right).\tag{6}От (1) и (2) имаме ощеf(x)f(f(y))+f(yf(x))=f(x)f(f(y))+f(yf(x))=f(y)f(f(x))+f(xf(y)).(7)f(y)f(f(x))+f(xf(y)).\tag{7}Нека f(x)=f(y)f(x)=f(y). Тогава (7) даваf(yf(y))=f(yf(x))=f(xf(y))=f(xf(x)).f(yf(y))=f(yf(x))=f(xf(y))=f(xf(x)).Използвайки (6) за xx и за yy, а също f(f(x))=f(f(y))f(f(x))=f(f(y)), получавамеf(f(x))(2y−f(x))=f(f(x))(2x−f(x)).f(f(x))\left(\frac2y-f(x)\right)=f(f(x))\left(\frac2x-f(x)\right).Понеже всички стойности на ff са положителни, следва x=yx=y. Значи ff е инективна. От (4) и инективността следваf(x)2=f(x)x,f(x)^2=\frac{f(x)}x,а понеже f(x)>0f(x)\gt{}0, получаваме f(x)=1/xf(x)=1/x. Накрая пряка проверка показва, че тази функция наистина удовлетворява даденото равенство.
Отвори задачатаMathNetISL 2016 A4Условие — източник

Задача A5

Пълен запис
Условие
(a) Докажете, че за всяко положително цяло число nn съществува дроб ab\frac ab, където aa и bb са цели числа, за която0<b≤x2n+1иn≤ab≤x2n+1.0\lt{}b\le\sqrt{\vphantom{x^2}n+1}\qquad\text{и}\qquad \sqrt n\le\frac ab\le\sqrt{\vphantom{x^2}n+1}.(b) Докажете, че има безброй много положителни цели числа nn, за които не съществува дроб ab\frac ab, където aa и bb са цели числа, за която0<b≤nиn≤ab≤x2n+1.0\lt{}b\le\sqrt n\qquad\text{и}\qquad \sqrt n\le\frac ab\le\sqrt{\vphantom{x^2}n+1}.
Решение(a) Нека rr е единственото положително цяло число, за коетоr2≤n<(r+1)2,r^2\le n\lt{}(r+1)^2,и нека n=r2+sn=r^2+s. Тогава 0≤s≤2r0\le s\le2r. Ако ss е четно, разглеждаме числото r+s2rr+\frac{s}{2r}. Имамеn=r2+s≤(r+s2r)2=r2+s+(s2r)2≤n+1,n=r^2+s\le\left(r+\frac{s}{2r}\right)^2=r^2+s+\left(\frac{s}{2r}\right)^2\le n+1,понеже s≤2rs\le2r. Следователноn≤r+s2r≤x2n+1.\sqrt n\le r+\frac{s}{2r}\le\sqrt{\vphantom{x^2}n+1}.Тъй като ss е четно, това число е дроб с цяло числител и знаменател r≤n≤x2n+1r\le\sqrt n\le\sqrt{\vphantom{x^2}n+1}. Ако ss е нечетно, разглеждаме числотоr+1−2r+1−s2(r+1).r+1-\frac{2r+1-s}{2(r+1)}.Тогаваn=r2+s≤(r+1−2r+1−s2(r+1))2≤n+1,n=r^2+s\le\left(r+1-\frac{2r+1-s}{2(r+1)}\right)^2\le n+1,защото 0≤2r+1−s≤2r0\le2r+1-s\le2r. Следователно това число лежи между n\sqrt n и x2n+1\sqrt{\vphantom{x^2}n+1}. Понеже ss е нечетно, 2r+1−s2\frac{2r+1-s}{2} е цяло число, така че получаваме дроб със знаменател r+1≤x2n+1r+1\le\sqrt{\vphantom{x^2}n+1}. Това доказва (a). (b) Ще покажем, че за всяко положително цяло число rr при n=r2+1n=r^2+1 такава дроб не съществува. Да допуснем противното. От b≤x2r2+1<r+1b\le\sqrt{\vphantom{x^2}r^2+1}\lt{}r+1 и целостта на bb следва b≤rb\le r. След повдигане на квадрат получаваме(br)2<b2(r2+1)≤a2≤(br)^2\lt{}b^2(r^2+1)\le a^2\leb2(r2+2)≤b2r2+2br<(br+1)2. b^2(r^2+2)\le b^2r^2+2br\lt{}(br+1)^2.Така квадратът a2a^2 се намира строго между два последователни квадрата, което е невъзможно. Следователно всички числа n=r2+1n=r^2+1 дават търсените безброй много примери.
Отвори задачатаMathNetISL 2016 A5Условие — източник

Задача A6

Пълен запис
Условие
На дъската е написано уравнението(x−1)(x−2)⋯(x−2016)=(x-1)(x-2)\cdots(x-2016)=(x−1)(x−2)⋯(x−2016).(x-1)(x-2)\cdots(x-2016).Опитваме се да изтрием някои линейни множители от двете страни така, че от всяка страна да остане поне един множител и полученото уравнение да няма реални корени. Да се намери най-малкият брой линейни множители, които трябва да се изтрият.
РешениеОтговорът е2016.2016.Понеже първоначално има 20162016 общи линейни множителя от двете страни, за всяко k=1,2,…,2016k=1,2,\ldots,2016 множителят x−kx-k трябва да се изтрие поне от едната страна; иначе x=kx=k ще бъде реален корен на полученото уравнение. Значи са нужни поне 20162016 изтривания. Ще покажем, че 20162016 изтривания стигат. От лявата страна изтриваме всички множители x−kx-k с k≡2,3(mod4)k\equiv2,3\pmod4, а от дясната - всички множители x−mx-m с m≡0,1(mod4)m\equiv0,1\pmod4. Остава да докажем, че уравнението∏j=0503(x−4j−1)(x−4j−4)=\prod_{j=0}^{503}(x-4j-1)(x-4j-4)=∏j=0503(x−4j−2)(x−4j−3)(1)\prod_{j=0}^{503}(x-4j-2)(x-4j-3)\tag{1}няма реални решения. Ако xx е едно от числата 1,2,…,20161,2,\ldots,2016, точно едната страна на (1) е нула, така че решение няма. Нека 4k+1<x<4k+24k+1\lt{}x\lt{}4k+2 или 4k+3<x<4k+44k+3\lt{}x\lt{}4k+4 за някое k=0,1,…,503k=0,1,\ldots,503. Тогава лявата страна на (1) е отрицателна, защото само множителите от блока с индекс kk дават отрицателно произведение, докато всяко произведение отдясно е положително. Това е невъзможно. Нека сега x<1x\lt{}1, x>2016x\gt{}2016 или 4k<x<4k+14k\lt{}x\lt{}4k+1 за някое k=1,2,…,503k=1,2,\ldots,503. Тогава можем да запишем (1) във вида1=1=∏j=0503(x−4j−1)(x−4j−4)(x−4j−2)(x−4j−3)=\prod_{j=0}^{503}\frac{(x-4j-1)(x-4j-4)}{(x-4j-2)(x-4j-3)}=∏j=0503(1−2(x−4j−2)(x−4j−3)).\prod_{j=0}^{503}\left(1-\frac2{(x-4j-2)(x-4j-3)}\right).В този случай (x−4j−2)(x−4j−3)>2(x-4j-2)(x-4j-3)\gt{}2 за всички jj, следователно всеки множител в последното произведение е строго между 00 и 11. Цялото произведение е по-малко от 11, противоречие. Остава случаят 4k+2<x<4k+34k+2\lt{}x\lt{}4k+3 за някое k=0,1,…,503k=0,1,\ldots,503. Тогава (1) се преобразува до1=1=x−1x−2⋅x−2016x−2015∏j=1503(x−4j)(x−4j−1)(x−4j+1)(x−4j−2).\frac{x-1}{x-2}\cdot\frac{x-2016}{x-2015}\prod_{j=1}^{503}\frac{(x-4j)(x-4j-1)}{(x-4j+1)(x-4j-2)}.Двата начални множителя са по-големи от 11, а за разглеждания интервал всеки множител в произведението също е по-голям от 11. Дясната страна е по-голяма от 11, отново противоречие. Следователно построеното уравнение няма реални корени и минималният брой изтривания е 20162016.
Отвори задачатаMathNetISL 2016 A6Условие — източник

Задача A7

Пълен запис
Условие
Нека R\mathbb R е множеството на реалните числа. Да се намерят всички функции f:R→Rf:\mathbb R\to\mathbb R, за които f(0)≠0f(0)\ne0 иf(x+y)2=f(x+y)^2=2f(x)f(y)+max⁡{f(x2)+f(y2),f(x2+y2)}2f(x)f(y)+\max\{f(x^2)+f(y^2),f(x^2+y^2)\}за всички реални числа xx и yy.
РешениеОтговорът еf(x)≡−1илиf(x)=x−1.f(x)\equiv -1\qquad\text{или}\qquad f(x)=x-1.При x=y=0x=y=0 получавамеf(0)2=2f(0)2+max⁡{2f(0),f(0)}.f(0)^2=2f(0)^2+\max\{2f(0),f(0)\}.Понеже f(0)≠0f(0)\ne0, това дава f(0)=−1f(0)=-1. Поставяйки y=0y=0, имамеf(x)2=−2f(x)+f(x2),f(x)^2=-2f(x)+f(x^2),или(f(x)+1)2=f(x2)+1.(1)(f(x)+1)^2=f(x^2)+1.\tag{1}Сравнявайки (1) за xx и за −x-x, получавамеf(x)=f(−x)илиf(x)+f(−x)=−2.(2)f(x)=f(-x)\qquad\text{или}\qquad f(x)+f(-x)=-2.\tag{2}От уравнението при (x,x)(x,x) и при (x,−x)(x,-x) следваf(2x)2−2f(x)2=1−2f(x)f(−x).(3)f(2x)^2-2f(x)^2=1-2f(x)f(-x).\tag{3}Комбинирайки (2) и (3), виждаме, че ако f(x)=f(−x)f(x)=f(-x), то f(2x)=±1f(2x)=\pm1, а ако f(x)+f(−x)=−2f(x)+f(-x)=-2, то f(2x)=±(2f(x)+1)f(2x)=\pm(2f(x)+1). Ще докажем, че всъщностf(x)+f(−x)=−2за всяко x∈R.(4)f(x)+f(-x)=-2\qquad\text{за всяко }x\in\mathbb R.\tag{4}Да допуснем противното. Тогава за някое aa имаме f(a)=f(−a)≠−1f(a)=f(-a)\ne-1; можем да приемем a>0a\gt{}0. Ако f(a)=1f(a)=1, то от (3) следва f(2a)2=1f(2a)^2=1, но от даденото уравнение при x=y=ax=y=a и от (1) получаваме f(2a)2≥2+2f(a2)=2+2⋅3f(2a)^2\ge 2+2f(a^2)=2+2\cdot3, противоречие. Значи f(a)≠±1f(a)\ne\pm1. Тогава от последното наблюдение, приложено за a/2a/2, имамеf(a)=±(2f(a2)+1),f(a)=\pm\left(2f\left(\frac a2\right)+1\right),f(−a)=±(2f(−a2)+1).\qquad f(-a)=\pm\left(2f\left(-\frac a2\right)+1\right).Ако f(a/2)=f(−a/2)f(a/2)=f(-a/2), то (3) би дало f(a)2=1f(a)^2=1, противоречие. Затова по (2) трябва да е f(a/2)+f(−a/2)=−2f(a/2)+f(-a/2)=-2. Тогава двете формули за равните числа f(a)f(a) и f(−a)f(-a) при всички избори на знаците водят или до непосредствено противоречие, или до f(a/2)=−1f(a/2)=-1, което пак би дало f(a)2=1f(a)^2=1. Това доказва (4). Сега заменяме x,yx,y с −x,−y-x,-y в първоначалното уравнение и сравняваме с него. Използвайки (4), получавамеf(x+y)=f(x)+f(y)+1.f(x+y)=f(x)+f(y)+1.Ако положим g(x)=f(x)+1g(x)=f(x)+1, тоg(x+y)=g(x)+g(y),g(x2)=g(x)2.g(x+y)=g(x)+g(y),\qquad g(x^2)=g(x)^2.В частност g(t)≥0g(t)\ge0 за всяко t≥0t\ge0, понеже t=x2t=x^2 за някое реално xx. Следователно адитивната функция gg е монотонна и има вид g(x)=cxg(x)=cx. От g(x2)=g(x)2g(x^2)=g(x)^2 получаваме c=0c=0 или c=1c=1. Така f(x)=−1f(x)=-1 за всички xx или f(x)=x−1f(x)=x-1 за всички xx. И двете функции се проверяват директно.
Отвори задачатаMathNetISL 2016 A7Условие — източник

Задача A8

Пълен запис
Условие
Да се определи най-голямото реално число aa, за което за всяко n≥1n\ge1 и всички реални числа x0,x1,…,xnx_0,x_1,\ldots,x_n, удовлетворяващи 0=x0<x1<x2<⋯<xn0=x_0\lt{}x_1\lt{}x_2\lt{}\cdots\lt{}x_n, е изпълнено1x1−x0+1x2−x1+⋯+1xn−xn−1≥\frac1{x_1-x_0}+\frac1{x_2-x_1}+\cdots+\frac1{x_n-x_{n-1}}\gea(2x1+3x2+⋯+n+1xn). a\left(\frac2{x_1}+\frac3{x_2}+\cdots+\frac{n+1}{x_n}\right).
РешениеОтговорът еa=49.a=\frac49.Първо ще докажем, че a=49a=\frac49 е допустимо. За всяко k=2,3,…,nk=2,3,\ldots,n от неравенството на Коши-Шварц имаме((k−1)2xk−1+32xk−xk−1)xk≥(k+2)2,\left(\frac{(k-1)^2}{x_{k-1}}+\frac{3^2}{x_k-x_{k-1}}\right)x_k\ge(k+2)^2,тоест9xk−xk−1≥(k+2)2xk−(k−1)2xk−1.(1)\frac9{x_k-x_{k-1}}\ge\frac{(k+2)^2}{x_k}-\frac{(k-1)^2}{x_{k-1}}.\tag{1}Сумираме (1) за k=2,3,…,nk=2,3,\ldots,n и добавяме 9x1\frac9{x_1} към двете страни. Получаваме телескопична оценка9∑k=1n1xk−xk−1≥9\sum_{k=1}^n\frac1{x_k-x_{k-1}}\ge4∑k=1nk+1xk+n2xn>4∑k=1nk+1xk.4\sum_{k=1}^n\frac{k+1}{x_k}+\frac{n^2}{x_n}\gt{}4\sum_{k=1}^n\frac{k+1}{x_k}.След деление на 99 следва търсеното неравенство с a=49a=\frac49. Остава да покажем, че по-голяма константа не е възможна. Некаx0=0,xk=xk−1+k(k+1)(k≥1),x_0=0,\qquad x_k=x_{k-1}+k(k+1)\quad(k\ge1),тоест xk=13k(k+1)(k+2)x_k=\frac13k(k+1)(k+2). Тогава лявата страна е∑k=1n1k(k+1)=1−1n+1,\sum_{k=1}^n\frac1{k(k+1)}=1-\frac1{n+1},а сумата в скобите отдясно е∑k=1nk+1xk=3∑k=1n1k(k+2)=\sum_{k=1}^n\frac{k+1}{x_k}=3\sum_{k=1}^n\frac1{k(k+2)}=32(1+12−1n+1−1n+2).\frac32\left(1+\frac12-\frac1{n+1}-\frac1{n+2}\right).Когато n→∞n\to\infty, лявата страна клони към 11, а сумата в скобите клони към 94\frac94. Следователно трябва да имаме 1≥94a1\ge\frac94a, т.е. a≤49a\le\frac49. Значи най-голямата възможна стойност е 49\frac49.
Отвори задачатаMathNetISL 2016 A8Условие — източник

Задача C1

Пълен запис
Условие
Ръководителят на отбор за IMO избира положителни цели числа nn и kk с n>kn\gt{}k и ги съобщава на заместник-ръководителя и на състезател. След това ръководителят тайно казва на заместник-ръководителя двоичен низ с дължина nn, а заместник-ръководителят записва всички двоични низове с дължина nn, които се различават от низа на ръководителя точно на kk позиции. Например, ако n=3n=3 и k=1k=1, а ръководителят избере 101101, заместник-ръководителят би записал 001001, 111111 и 100100. Състезателят може да види записаните низове и да познае низа на ръководителя. Какъв е минималният брой познавания, който гарантира правилен отговор, изразен чрез nn и kk?
РешениеОтговорът е 11, ако n≠2kn\ne2k, и 22, ако n=2kn=2k. Първо нека n≠2kn\ne2k. Да разгледаме произволна фиксирана позиция. Ако на тази позиция в тайния низ стои 11, то сред записаните низове точно(n−1k)\binom{n-1}{k}имат 11 на тази позиция и точно(n−1k−1)\binom{n-1}{k-1}имат 00 на нея. Ако пък в тайния низ стои 00, тези два броя се разменят. Понеже(n−1k)≠(n−1k−1)\binom{n-1}{k}\ne\binom{n-1}{k-1}точно когато n≠2kn\ne2k, състезателят може да определи всеки бит на тайния низ чрез броене. Следователно едно познаване е достатъчно. Нека сега n=2kn=2k. Ако XX е тайният низ, а X′X' е низът, получен от XX чрез смяна на всеки бит, то множеството от низове, които се различават от XX на kk позиции, е същото като множеството от низове, които се различават от X′X' на kk позиции. Значи поне две познавания са нужни. Остава да видим, че две познавания стигат. Случаят n=2n=2, k=1k=1 е очевиден. Нека n=2k>2n=2k\gt{}2. Състезателят може да установи дали първите два бита на тайния низ са равни. Ако са равни, сред записаните низове префиксите 0101 и 1010 се срещат по (2k−2k−1)\binom{2k-2}{k-1} пъти, а префиксите 0000 и 1111 - по (2k−2k)\binom{2k-2}{k} пъти. Ако първите два бита са различни, тези два броя се разменят. Понеже(2k−2k−1)≠(2k−2k),\binom{2k-2}{k-1}\ne\binom{2k-2}{k},състезателят разбира дали първите два бита са равни. По същия начин той намира отношението между първия бит и всеки друг бит. Така тайният низ се свежда до две възможности, които са допълващи се една на друга. Следователно две познавания са достатъчни.
Отвори задачатаMathNetISL 2016 C1Условие — източник

Задача C2

Пълен запис
Условие
Да се намерят всички положителни цели числа nn, за които всички положителни делители на nn могат да се поставят в клетките на правоъгълна таблица при следните условия: - всяка клетка съдържа различен делител; - сумите по всички редове са равни; - сумите по всички колони са равни.
РешениеОтговорът е 11. Да допуснем, че всички положителни делители на nn са подредени в таблица с kk реда и ll колони, като k≤lk\le l. Нека сумата във всяка колона е ss. Понеже числото nn стои в някоя колона, имаме s≥ns\ge n, като равенство е възможно само при n=1n=1. За j=1,2,…,lj=1,2,\ldots,l нека djd_j е най-голямото число в jj-тата колона. Без ограничение некаd1>d2>⋯>dl.d_1\gt{}d_2\gt{}\cdots\gt{}d_l.Това са различни делители на nn. За всеки от тях числото n/djn/d_j е положително цяло число, а от dj≥dld_j\ge d_l следва n/dj≤n/dln/d_j\le n/d_l. Следователно има поне ll положителни цели числа, не по-големи от n/dln/d_l, и затоваdl≤nl.(1)d_l\le\frac nl.\tag{1}От друга страна, понеже dld_l е най-големият елемент в последната колона, средната стойност на елементите в тази колона не надвишава dld_l. Следователноdl≥sk≥nk.(2)d_l\ge\frac sk\ge\frac nk.\tag{2}От (1) и (2) получаваме nl≥nk\frac nl\ge\frac nk, тоест k≥lk\ge l. Заедно с k≤lk\le l това дава k=lk=l. Тогава всички използвани неравенства са равенства. В частност s=ns=n, което, както отбелязахме, е възможно само при n=1n=1. За n=1n=1 таблицата от една клетка очевидно удовлетворява условията.
Отвори задачатаMathNetISL 2016 C2Условие — източник

Задача C3

Пълен запис
Условие
Нека nn е положително цяло число, взаимно просто с 66. Върховете на правилен nn-ъгълник са оцветени в три цвята така, че броят на върховете от всеки цвят е нечетен. Докажете, че съществува равнобедрен триъгълник, чиито три върха са в различни цветове.
РешениеЗа r=1,2,3r=1,2,3 нека ara_r е броят на равнобедрените триъгълници, чиито върхове съдържат точно rr цвята. Да допуснем противното, че a3=0a_3=0. Нека b,c,db,c,d са броевете на върховете от трите цвята; по условие те са нечетни. Ще преброим двойките (T,E)(T,E), където TT е равнобедрен триъгълник с върхове измежду върховете на многоъгълника, а EE е страна на TT, чиито краища са в различни цветове. От една страна, при допускането a3=0a_3=0 всеки такъв триъгълник съдържа точно два цвята. Тогава той допринася точно две страни с краища в различни цветове, така че броят на двойките е 2a22a_2. От друга страна, избираме два върха AA и BB в различни цветове. Тъй като nn е нечетно, има точно един равнобедрен триъгълник с основа ABAB, а още два се получават, когато ABAB е едно от равните бедра. Понеже gcd⁡(n,3)=1\gcd(n,3)=1, тези три триъгълника са различни. Следователно броят на двойките е3(bc+cd+db).3(bc+cd+db).Но 2a22a_2 е четно число, докато 3(bc+cd+db)3(bc+cd+db) е нечетно, защото b,c,db,c,d са нечетни. Получаваме противоречие. Следователно a3≥1a_3\ge1, тоест съществува търсеният равнобедрен триъгълник.
Отвори задачатаMathNetISL 2016 C3Условие — източник

Задача C4

Пълен запис
Условие
Да се намерят всички положителни цели числа nn, за които можем да попълним клетките на таблица n×nn\times n със следните свойства: - всяка клетка съдържа една от буквите II, MM и OO; - във всеки ред и във всяка колона буквите II, MM и OO се срещат равен брой пъти; - във всеки диагонал, чийто брой клетки е кратен на 33, буквите II, MM и OO се срещат равен брой пъти.
РешениеОтговорът е: всички кратни на 99 положителни цели числа. Първо ще построим таблица, когато nn е кратно на 99. Достатъчно е да дадем следната таблица 9×99\times9:IIIMMMOOOMMMOOOIIIOOOIIIMMMIIIMMMOOOMMMOOOIIIOOOIIIMMMIIIMMMOOOMMMOOOIIIOOOIIIMMM\begin{array}{ccccccccc} I&I&I&M&M&M&O&O&O\cr M&M&M&O&O&O&I&I&I\cr O&O&O&I&I&I&M&M&M\cr I&I&I&M&M&M&O&O&O\cr M&M&M&O&O&O&I&I&I\cr O&O&O&I&I&I&M&M&M\cr I&I&I&M&M&M&O&O&O\cr M&M&M&O&O&O&I&I&I\cr O&O&O&I&I&I&M&M&M \end{array}Тя се проверява непосредствено. Ако n=9qn=9q, построяваме таблица n×nn\times n от q×qq\times q копия на тази таблица. Във всеки ред и всяка колона във всеки блок от 99 последователни клетки има по три II, три MM и три OO. Освен това всеки диагонал с брой клетки, кратен на 33, пресича всяко копие на основната таблица в диагонал с брой клетки, кратен на 33 (възможно е и 00), така че и в такъв диагонал трите букви се срещат равен брой пъти. Остава да докажем, че други nn няма. От условието за редовете следва n=3kn=3k за някое положително цяло kk. Разделяме таблицата на k×kk\times k блока 3×33\times3. Ще наричаме централната клетка на такъв блок важна клетка, а всеки ред, колона или диагонал, който съдържа важна клетка, важна линия. Нека NN е броят на двойките (ℓ,c)(\ell,c), където ℓ\ell е важна линия, а cc е клетка от ℓ\ell, съдържаща буквата MM. Всеки важен ред и всяка важна колона съдържа точно kk букви MM, така че от важните редове и колони получаваме общо 2k22k^2 двойки. За диагоналите във всяка от двете посоки сумата от дължините на важните диагонали е3(1+2+⋯+(k−1)+k+(k−1)+⋯+2+1)=3k2,3(1+2+\cdots+(k-1)+k+(k-1)+\cdots+2+1)=3k^2,а във всеки такъв диагонал една трета от клетките съдържат MM. Следователно всяка посока дава още k2k^2 двойки иN=4k2.N=4k^2.От друга страна, в цялата таблица има 3k23k^2 букви MM. Всяка клетка лежи върху точно 11 или точно 44 важни линии. ЗатоваN≡3k2(mod3).N\equiv3k^2\pmod3.Понеже N=4k2N=4k^2, получаваме 4k2≡3k2(mod3)4k^2\equiv3k^2\pmod3, тоест 3∣k3\mid k. Следователно n=3kn=3k е кратно на 99.
Отвори задачатаMathNetISL 2016 C4Условие — източник

Задача C5

Пълен запис
Условие
Нека n≥3n\ge3 е положително цяло число. Да се намери максималният брой диагонали на правилен nn-ъгълник, които могат да се изберат така, че всеки два от тях или не се пресичат във вътрешността си, или са перпендикулярни.
РешениеОтговорът е n−2n-2, ако nn е четно, и n−3n-3, ако nn е нечетно. Нека първо nn е нечетно. Ще покажем, че няма две перпендикулярни диагонали. Да допуснем, че диагоналите ABAB и CDCD са перпендикулярни. Нека EE е върхът на правилния многоъгълник, който лежи на перпендикулярния симетрал на ABAB, и нека E′E' е диаметрално противоположната на EE точка от описаната окръжност. От перпендикулярността следва EC=E′DEC=E'D. Тъй като C,D,EC,D,E са върхове на правилния многоъгълник, това би наложило и E′E' да бъде негов връх. Но правилен многоъгълник с нечетен брой върхове няма диаметрално противоположни върхове. Противоречие. Следователно при нечетно nn избраните диагонали не могат да се пресичат във вътрешността си. Най-много такива диагонали има в триангулация на nn-ъгълник, а броят им е n−3n-3. Тази стойност се достига, като изберем всички диагонали от един фиксиран връх. Сега ще докажем, че при четно nn не могат да се изберат повече от n−2n-2 диагонала. Всъщност ще докажем по индукция по-силно твърдение: във всеки вписан nn-ъгълник, ако всеки две избрани диагонали или не се пресичат във вътрешността си, или са перпендикулярни, то избраните диагонали са най-много n−2n-2. За n=3n=3 твърдението е ясно. Нека n>3n\gt{}3. Ако има избран диагонал, който не се пресича с никой друг избран диагонал, той разделя многоъгълника на mm-ъгълник и ll-ъгълник, където m+l=n+2m+l=n+2. Можем да приемем, че mm-ъгълникът лежи от едната страна на някой диаметър на описаната окръжност. В него две диагонали не могат да се пресичат перпендикулярно, затова избраните диагонали вътре в него са най-много m−3m-3. За другия многоъгълник прилагаме индукционното предположение и получаваме най-много l−2l-2 диагонала. Заедно с разделящия диагонал това дава(m−3)+(l−2)+1=n−2.(m-3)+(l-2)+1=n-2.Остава случаят, когато всеки избран диагонал се пресича с поне един друг избран диагонал. Избираме две перпендикулярни избрани диагонали d1d_1 и d2d_2. Те разделят окръжността на четири дъги, всяка от които лежи в една полуокръжност. Ако две избрани диагонали се пресичат и нито една от тях не е успоредна на d1d_1 или d2d_2, техните краища лежат в една от тези дъги и те не могат да бъдат перпендикулярни. Следователно всички избрани диагонали са успоредни на една от посоките на d1d_1 и d2d_2. Вземаме най-дългия избран диагонал в едната посока. Нито един друг избран диагонал не може да има край в някой от неговите краища, защото тогава би се пресичал с по-дълъг диагонал от същата посока. Същото важи и за най-дългия избран диагонал в другата посока. След като изключим тези четири края, всеки от останалите n−4n-4 върха може да бъде край на най-много два избрани диагонала. Затова броят на избраните диагонали е най-много2(n−4)+42=n−2.\frac{2(n-4)+4}{2}=n-2.Накрая ще дадем конструкция за четно nn. Нека AA е произволен връх, а A′A' - диаметрално противоположният му връх. Избираме всички диагонали, излизащи от AA, и още диагонала, който свързва двата съседни върха на A′A'. Единствената пресичаща се двойка е този последен диагонал с диаметъра AA′AA', и те са перпендикулярни. Така получаваме n−2n-2 диагонала.
Отвори задачатаMathNetISL 2016 C5Условие — източник

Задача C6

Пълен запис
Условие
В един град има n≥3n\ge3 острова. Първоначално фериботната компания предлага маршрути между някои двойки острови така, че е невъзможно островите да се разделят на две групи, между които няма фериботен маршрут. След всяка година компанията закрива маршрут между някои два острова XX и YY. Едновременно с това, за да запази услугата си, тя открива нови маршрути по следното правило: за всеки остров, който е свързан с фериботен маршрут точно с един от XX и YY, се добавя нов маршрут между този остров и другия от XX и YY. Да предположим, че във всеки момент, при всяко разделяне на островите на две непразни групи, е известно, че след няколко години компанията ще закрие някакъв маршрут, който свързва острови от двете групи. Докажете, че след няколко години ще има остров, който е свързан с всички останали острови чрез фериботни маршрути.
РешениеЩе казваме, че две множества от острови A\mathcal A и B\mathcal B образуват мрежа, ако всеки остров от едното множество е свързан с всеки остров от другото. Първоначално избираме маршрут между два острова AA и BB. Поставяме AA в A\mathcal A, а BB в B\mathcal B. Понеже графът на маршрутите е свързан и n≥3n\ge3, без ограничение има още един остров CC, свързан с AA; поставяме го също в B\mathcal B. Така A\mathcal A и B\mathcal B образуват мрежа. Ще показваме, че можем да включваме островите в A∪B\mathcal A\cup\mathcal B един по един, запазвайки свойството да има такова разделяне на мрежа. Нека вече имаме мрежа A,B\mathcal A,\mathcal B с3≤∣A∪B∣<n.3\le |\mathcal A\cup\mathcal B|\lt{}n.Докато не се закрие маршрут между остров A∈AA\in\mathcal A и остров B∈BB\in\mathcal B, свойството на мрежа се запазва. Ако такъв маршрут бъде закрит, поставямеA′={A,B},B′=(A∪B)∖{A,B}.\mathcal A'=\{A,B\},\qquad \mathcal B'=(\mathcal A\cup\mathcal B)\setminus\{A,B\}.Множеството B′\mathcal B' е непразно. Нека C∈A∖{A}C\in\mathcal A\setminus\{A\}. Преди закриването CC е бил свързан с BB. Ако CC не е бил свързан с AA, правилото добавя маршрут между CC и AA; ако е бил свързан, маршрутът вече съществува. Значи след промяната CC е свързан и с AA, и с BB. Същото важи за всеки остров от B∖{B}\mathcal B\setminus\{B\}. Следователно A′\mathcal A' и B′\mathcal B' отново образуват мрежа върху същото множество острови. Понеже ∣A∪B∣<n|\mathcal A\cup\mathcal B|\lt{}n, има остров извън това множество. По условие след няколко години ще бъде закрит маршрут между някой остров A∈A∪BA\in\mathcal A\cup\mathcal B и някой остров DD извън A∪B\mathcal A\cup\mathcal B. Без ограничение нека A∈AA\in\mathcal A. Тогава всеки остров от B\mathcal B след тази промяна е свързан с DD, независимо дали е бил свързан с него преди това. Затова можем да добавим DD към A\mathcal A и пак да имаме мрежа, като размерът на A∪B\mathcal A\cup\mathcal B се увеличава с 11. Повтаряйки процеса, стигаме до мрежа, която съдържа всички острови. Сега нека всички острови са разделени на две множества A\mathcal A и B\mathcal B, които образуват мрежа. По условие след няколко години ще бъде закрит маршрут между някой A∈AA\in\mathcal A и някой B∈BB\in\mathcal B. След това поставяме AA и BB в A′\mathcal A', а всички останали острови - в B′\mathcal B'. Както по-горе, A′\mathcal A' и B′\mathcal B' образуват мрежа. Това свойство може да бъде нарушено само когато се закрие маршрут между един от островите A,BA,B и някой C∈B′C\in\mathcal B'. По условие това някога ще се случи. Ако закритият маршрут е между AA и CC, тогава правилото добавя всички липсващи маршрути между BB и островите от B′\mathcal B', а BB вече е свързан и с AA. Следователно BB е свързан с всички останали острови. Случаят със закрит маршрут между BB и CC е симетричен. Това доказва твърдението.
Отвори задачатаMathNetISL 2016 C6Условие — източник

Задача C7

Пълен запис
Условие
Нека n≥2n\ge2 е цяло число. В равнината са дадени nn отсечки така, че всеки две отсечки имат пресечна точка във вътрешността си и няма три отсечки, които се пресичат в една точка. Джеф поставя по един охлюв в един от краищата на всяка отсечка и пляска с ръце n−1n-1 пъти. Всеки път, когато плясне с ръце, всички охлюви се движат по своите отсечки и остават в следващите пресечни точки до следващото пляскане. Тъй като на всяка отсечка има n−1n-1 пресечни точки, след n−1n-1 пляскания всички охлюви ще стигнат най-далечните от началните си точки пресечни точки. (a) Докажете, че ако nn е нечетно, Джеф винаги може да постави охлювите така, че никои два от тях никога да не заемат една и съща пресечна точка. (b) Докажете, че ако nn е четно, при всяко поставяне на охлювите непременно има момент, в който някои два охлюва заемат една и съща пресечна точка.
РешениеВземаме голям диск, който съдържа всички отсечки, и продължаваме всяка отсечка до права lil_i, която пресича окръжността на диска в две точки AiA_i и BiB_i. (a) Нека nn е нечетно. Обхождаме окръжността на диска и маркираме последователно всяка от точките Ai,BiA_i,B_i с 'вътре' и 'вън'. За фиксирано ii между AiA_i и BiB_i по всяка от двете дъги има точно n−1n-1 от останалите точки, защото всяка друга права пресича lil_i вътре в диска. Понеже nn е нечетно, едната от точките Ai,BiA_i,B_i е маркирана с 'вътре', а другата - с 'вън'. Джеф поставя охлюва върху края на съответната отсечка, който е откъм маркираната с 'вътре' точка на правата. Ще докажем, че два охлюва върху lil_i и ljl_j не се срещат. Без ограничение нека те започват от страните на AiA_i и AjA_j, а PP е пресечната точка на lil_i и ljl_j. Понеже AiA_i и AjA_j са маркирани еднакво, по дъгата между тях има нечетен брой от отбелязаните точки. Всяка такава точка принадлежи на някоя права lsl_s, която пресича точно една от отсечките AiPA_iP и AjPA_jP. Всяка друга права пресича или и двете отсечки, или нито една от тях. Следователно общият брой пресечни точки върху AiPA_iP и AjPA_jP, без да броим PP, е нечетен. Ако двата охлюва стигнат в PP едновременно, броят на пресечните точки по пътя от началото до PP върху двете прави трябва да е един и същ, а тогава общият брой би бил четен. Това е противоречие. Значи охлювите не се срещат. (b) Нека nn е четно и да разгледаме произволно поставяне на охлювите. Маркираме всяка точка AiA_i или BiB_i с 'вътре' или 'вън' според посоката, в която тръгва охлювът по съответната права. Тогава има две съседни точки по окръжността, да ги наречем AiA_i и AjA_j, които са маркирани с 'вътре'. Наистина, ако такива нямаше, маркировките щяха да се редуват по цялата окръжност. Но при четно nn между двата края на всяка права има n−1n-1 точки, което при редуване би дало еднакви маркировки на двата края, невъзможно за посоката на един охлюв. Нека PP е пресечната точка на правите lil_i и ljl_j. Понеже AiA_i и AjA_j са съседни по окръжността, всяка друга права, която пресича една от отсечките AiPA_iP и AjPA_jP, пресича и другата. Следователно върху двете отсечки има равен брой пресечни точки преди PP. Двата охлюва, тръгнали от страните на AiA_i и AjA_j, стигат в PP едновременно. Това доказва (b).
Отвори задачатаMathNetISL 2016 C7Условие — източник

Задача C8

Пълен запис
Условие
Нека nn е положително цяло число. Да се определи най-малкото положително цяло число kk със следното свойство: възможно е да се маркират kk клетки на дъска 2n×2n2n\times2n така, че да съществува единствено покриване на дъската с домина 1×21\times2 и 2×12\times1, нито едно от които не съдържа две маркирани клетки.
РешениеОтговорът е 2n2n. Първо ще дадем пример с 2n2n маркирани клетки. Номерираме редовете и колоните с 1,2,…,2n1,2,\ldots,2n, а клетката в ii-тия ред и jj-тата колона означаваме с (i,j)(i,j). За i=1,2,…,ni=1,2,\ldots,n маркираме клетките (i,i)(i,i) и (i,i+1)(i,i+1). Това принуждава единствено покриване. Доминото, което покрива (1,1)(1,1), не може да покрива (1,2)(1,2), затова е вертикално. По същия начин последователно домината, които покриват (2,2),(3,3),…,(n,n)(2,2),(3,3),\ldots,(n,n), са вертикални и така лявата област, определена от двете главни диагонални посоки на дъската, се покрива вертикално. Съседните маркирани клетки (i,i+1)(i,i+1) принуждават хоризонталното покриване на горната област, а същият принуден ред около центъра определя и останалите две области. Следователно съществува покриване и то е единствено. Остава да докажем, че по-малко от 2n2n маркирани клетки не стигат. Да допуснем, че са маркирани k<2nk\lt{}2n клетки и че има допустимо покриване PP. Ще построим друго допустимо покриване. Нека dd е главният диагонал на дъската. Построяваме граф, чиито върхове са клетките на дъската, с ребра в два цвята. Свързваме две клетки с червено ребро, ако принадлежат на едно домино от PP. Свързваме две клетки със синьо ребро, ако отраженията им спрямо dd са свързани с червено ребро. Възможно е две клетки да са свързани и с двата цвята. Всеки връх има червена степен 11 и синя степен 11, следователно графът се разпада на цикли, в които цветовете на ребрата се редуват. Нека cc е клетка върху диагонала dd. Двете ребра от cc са симетрични спрямо dd и водят към различни клетки, така че цикълът C(c)C(c), който съдържа cc, има дължина поне 44. Вземаме част от този цикълc0,c1,…,cm,c_0,c_1,\ldots,c_m,където c0=cc_0=c и mm е най-малкият положителен индекс, за който cmc_m отново лежи върху dd. Тази клетка е различна от cc. От симетрията спрямо dd огледалният на този път път също лежи в графа, така че двата пътя заедно образуват целия цикъл C(c)C(c). Значи C(c)C(c) съдържа точно две клетки от диагонала dd. Диагоналът dd има 2n2n клетки, следователно те лежат в nn такива цикъла C1,C2,…,CnC_1,C_2,\ldots,C_n, всеки с дължина поне 44. Понеже k<2nk\lt{}2n, по принципа на Дирихле някой от тези цикли съдържа най-много една маркирана клетка. В този цикъл заменяме в покриването PP домината, съответстващи на червените ребра, с домината, съответстващи на сините ребра. Понеже цикълът има дължина поне 44, полученото покриване е различно от PP. И понеже цикълът съдържа най-много една маркирана клетка, нито едно ново домино не съдържа две маркирани клетки. Значи допустимото покриване не е единствено. Следователно трябва да се маркират поне 2n2n клетки.
Отвори задачатаMathNetISL 2016 C8Условие — източник

Задача N1

Пълен запис
Условие
За всяко положително цяло число kk нека S(k)S(k) означава сумата от цифрите на kk в десетичния му запис. Да се намерят всички полиноми P(x)P(x) с цели коефициенти, за които за всяко положително цяло число n≥2016n\ge2016 числото P(n)P(n) е положително цяло иS(P(n))=P(S(n)).S(P(n))=P(S(n)).
РешениеОтговорът еP(x)=c(1≤c≤9)илиP(x)=x.P(x)=c\quad(1\le c\le9)\qquad\text{или}\qquad P(x)=x.Първо нека P(x)=cP(x)=c е константен полином. Тогава условието става S(c)=cS(c)=c, което е вярно точно за целите числа cc с 1≤c≤91\le c\le9. Нека сега deg⁡P=1\deg P=1 и P(x)=ax+bP(x)=ax+b, където a,b∈Za,b\in\mathbb Z и a≠0a\ne0. Понеже P(n)>0P(n)\gt{}0 за всички достатъчно големи nn, имаме a≥1a\ge1. Ще използваме, че за положителни цели числа u,vu,v е вярноS(u+v)≤S(u)+S(v).(1)S(u+v)\le S(u)+S(v).\tag{1}От условието, приложено за n=2025n=2025 и n=2020n=2020, получавамеS(2025a+b)−S(2020a+b)=5a.S(2025a+b)-S(2020a+b)=5a.От друга страна, по (1)S(2025a+b)=S((2020a+b)+5a)≤S(2025a+b)=S((2020a+b)+5a)\leS(2020a+b)+S(5a). S(2020a+b)+S(5a).Следователно 5a≤S(5a)5a\le S(5a), което при a≥1a\ge1 е възможно само за a=1a=1. Остава P(x)=x+bP(x)=x+b и условието дава S(n+b)=S(n)+bS(n+b)=S(n)+b за всяко n≥2016n\ge2016. Ако b>0b\gt{}0, избираме nn така, че n+1+b=10kn+1+b=10^k за достатъчно голямо kk. Тогава всички цифри на n+bn+b са деветки иS(n+1+b)−S(n+b)=1−9k.S(n+1+b)-S(n+b)=1-9k.От условието същата разлика трябва да е S(n+1)−S(n)S(n+1)-S(n). Но n<10k−1n\lt{}10^k-1, така че S(n)<9kS(n)\lt{}9k и S(n+1)−S(n)≥2−9kS(n+1)-S(n)\ge2-9k, противоречие. Случаят b<0b\lt{}0 се третира аналогично, като вземем n+1n+1 да е голяма степен на 1010. Значи b=0b=0 и P(x)=xP(x)=x. Накрая нека deg⁡P=d≥2\deg P=d\ge2 и водещият коефициент е положителен. Вземаме n=10k−1n=10^k-1. Тогава S(n)=9kS(n)=9k, така че условието дава S(P(n))=P(9k)S(P(n))=P(9k). Лявата страна расте най-много линейно по kk, защото P(n)P(n) има O(k)O(k) цифри, докато дясната страна расте като константа по kdk^d. Това е невъзможно за достатъчно голямо kk. Следователно единствените решения са изброените по-горе.
Отвори задачатаMathNetISL 2016 N1Условие — източник

Задача N2

Пълен запис
Условие
Нека τ(n)\tau(n) е броят на положителните делители на nn, а τ1(n)\tau_1(n) - броят на положителните делители на nn, които дават остатък 11 при деление на 33. Да се намерят всички възможни цели стойности на дробтаτ(10n)τ1(10n).\frac{\tau(10n)}{\tau_1(10n)}.
РешениеОтговорът е: числото 22 и всички съставни положителни цели числа. Ще означаваме простите числа, сравними с 11 по модул 33, с pip_i, а простите числа, сравними с 22 по модул 33, с qjq_j. Некаm=3xp1a1⋯psasq1b1⋯qtbt.m=3^x p_1^{a_1}\cdots p_s^{a_s}q_1^{b_1}\cdots q_t^{b_t}.Делител на mm, който е 11 по модул 33, не съдържа фактора 33, може произволно да съдържа простите pip_i, а общият брой избрани множители от простите qjq_j трябва да е четен. Затоваτ1(m)=\tau_1(m)=∏i=1s(ai+1)⌈12∏j=1t(bj+1)⌉.(1)\prod_{i=1}^s(a_i+1)\left\lceil\frac12\prod_{j=1}^t(b_j+1)\right\rceil.\tag{1}Наистина, ако произведението ∏(bj+1)\prod(b_j+1) е четно, половината избори имат четна сума на показателите. Ако то е нечетно, всички bjb_j са четни и броят на четните избори е таванът на половината от общия брой. Сега запишемn=3x2y5zp1a1⋯psasq1b1⋯qtbt.n=3^x2^y5^z p_1^{a_1}\cdots p_s^{a_s}q_1^{b_1}\cdots q_t^{b_t}.Тогаваτ(10n)=\tau(10n)=(x+1)(y+2)(z+2)∏i=1s(ai+1)∏j=1t(bj+1),(x+1)(y+2)(z+2)\prod_{i=1}^s(a_i+1)\prod_{j=1}^t(b_j+1),(2)\tag{2}а от (1)τ1(10n)=\tau_1(10n)=∏i=1s(ai+1)⌈12(y+2)(z+2)∏j=1t(bj+1)⌉.(3)\prod_{i=1}^s(a_i+1)\left\lceil\frac12 (y+2)(z+2)\prod_{j=1}^t(b_j+1)\right\rceil.\tag{3}Некаc=(y+2)(z+2)∏j=1t(bj+1).c=(y+2)(z+2)\prod_{j=1}^t(b_j+1).Ако cc е четно, то от (2) и (3)τ(10n)τ1(10n)=2(x+1),\frac{\tau(10n)}{\tau_1(10n)}=2(x+1),така че получаваме всяко четно положително цяло число. Остава случаят cc нечетно. Тогава y,zy,z са нечетни и всички bjb_j са четни, аτ(10n)τ1(10n)=2(x+1)cc+1.(4)\frac{\tau(10n)}{\tau_1(10n)}=\frac{2(x+1)c}{c+1}.\tag{4}За да е това цяло число, трябва c+1∣2(x+1)c+1\mid2(x+1). Ако 2(x+1)=r(c+1)2(x+1)=r(c+1), то стойността в (4) е rcrc. Но y+2y+2 и z+2z+2 са нечетни числа поне 33, следователно cc е съставно, а значи и rcrc е съставно. Обратно, всяко нечетно съставно число може да се запише като abab с нечетни a,b≥3a,b\ge3. Вземамеn=3(ab−1)/22a−25b−2.n=3^{(ab-1)/2}2^{a-2}5^{b-2}.Тогава c=abc=ab и 2(x+1)=ab+1=c+12(x+1)=ab+1=c+1, откъдето дробта е равна на abab. Следователно възможните цели стойности са точно 22 и всички съставни положителни цели числа.
Отвори задачатаMathNetISL 2016 N2Условие — източник

Задача N3

Пълен запис
Условие
Дефинираме P(n)=n2+n+1P(n)=n^2+n+1. За положителни цели числа aa и bb множеството{P(a),P(a+1),P(a+2),…,P(a+b)}\{P(a),P(a+1),P(a+2),\ldots,P(a+b)\}се нарича ароматно, ако никой негов елемент не е взаимно прост с произведението на останалите елементи. Да се определи най-малкият размер на ароматно множество.
РешениеОтговорът е 66. Ще използваме следните три наблюдения. Първо, gcd⁡(P(n),P(n+1))=1\gcd(P(n),P(n+1))=1 за всяко nn. Наистина,gcd⁡(P(n),P(n+1))=gcd⁡(n2+n+1,2n+2),\gcd(P(n),P(n+1))=\gcd(n^2+n+1,2n+2),а n2+n+1n^2+n+1 е нечетно и е взаимно просто с n+1n+1. Второ,gcd⁡(P(n),P(n+2))=1\gcd(P(n),P(n+2))=1за n≢2(mod7)n\not\equiv2\pmod7, а при n≡2(mod7)n\equiv2\pmod7 този НОД е 77. Това следва от(2n+7)P(n)−(2n−1)P(n+2)=14(2n+7)P(n)-(2n-1)P(n+2)=14и пряка проверка по модул 77. Трето, gcd⁡(P(n),P(n+3))=1\gcd(P(n),P(n+3))=1 за n≢1(mod3)n\not\equiv1\pmod3, а при n≡1(mod3)n\equiv1\pmod3 този НОД е по-голям от 11. Това следва от(n+5)P(n)−(n−1)P(n+3)=18(n+5)P(n)-(n-1)P(n+3)=18и проверка по модул 33. Да допуснем, че има ароматно множество с най-много 55 елемента. Можем да разглеждаме петте числа P(a),P(a+1),…,P(a+4)P(a),P(a+1),\ldots,P(a+4), защото същият аргумент работи и при по-малко елементи. Числото P(a+2)P(a+2) е взаимно просто с P(a+1)P(a+1) и P(a+3)P(a+3). Следователно то трябва да има общ делител с P(a)P(a) или с P(a+4)P(a+4). Без ограничение нека gcd⁡(P(a),P(a+2))>1\gcd(P(a),P(a+2))\gt{}1. По второто наблюдение a≡2(mod7)a\equiv2\pmod7, а тогава gcd⁡(P(a+1),P(a+3))=1\gcd(P(a+1),P(a+3))=1. За да бъде множеството ароматно, трябва едновременноgcd⁡(P(a),P(a+3))>1и\gcd(P(a),P(a+3))\gt{}1\quad\text{и}\quadgcd⁡(P(a+1),P(a+4))>1.\gcd(P(a+1),P(a+4))\gt{}1.По третото наблюдение това изисква и a≡1(mod3)a\equiv1\pmod3, и a+1≡1(mod3)a+1\equiv1\pmod3, което е невъзможно. Значи ароматно множество с най-много 55 елемента няма. Остава да построим пример с 66 елемента. По китайската теорема за остатъците избираме положително цяло aa, за коетоa≡7(mod19),a+1≡2(mod7),a+2≡1(mod3).a\equiv7\pmod{19},\qquad a+1\equiv2\pmod7,\qquad a+2\equiv1\pmod3.Например a=197a=197. Тогава по второто наблюдение P(a+1)P(a+1) и P(a+3)P(a+3) се делят на 77, а по третото P(a+2)P(a+2) и P(a+5)P(a+5) се делят на 33. Освен това P(7)=57P(7)=57 и P(11)=133P(11)=133 се делят на 1919, следователно P(a)P(a) и P(a+4)P(a+4) се делят на 1919. Така всяко от шестте числа има общ прост делител с друго от тях. Следователно най-малкият възможен размер е 66.
Отвори задачатаMathNetISL 2016 N3Условие — източник

Задача N4

Пълен запис
Условие
Нека n,m,k,ln,m,k,l са положителни цели числа с n≠1n\ne1, за които nk+mnl+1n^k+mn^l+1 дели nk+l−1n^{k+l}-1. Докажете, че е изпълнено едно от следните две твърдения: - m=1m=1 и l=2kl=2k; - l∣kl\mid k и m=nk−l−1nl−1m=\dfrac{n^{k-l}-1}{n^l-1}.
РешениеОт дадената делимост имамеnk+mnl+1∣nk+l−1.(1)n^k+mn^l+1\mid n^{k+l}-1.\tag{1}Като прибавим делителя към дясната страна, получавамеnk+mnl+1∣nk+l+nk+mnl.(2)n^k+mn^l+1\mid n^{k+l}+n^k+mn^l.\tag{2}Понеже gcd⁡(n,nk+mnl+1)=1\gcd(n,n^k+mn^l+1)=1, можем да съкращаваме подходящи степени на nn в сравненията. Първи случай: l≥kl\ge k. От (2) следваnk+mnl+1∣nl+mnl−k+1.n^k+mn^l+1\mid n^l+mn^{l-k}+1.Но2(nk+mnl+1)>2mnl+1>nl+mnl−k+1,2(n^k+mn^l+1)\gt{}2mn^l+1\gt{}n^l+mn^{l-k}+1,затова делителят трябва да е равен на делимото:nk+mnl+1=nl+mnl−k+1.n^k+mn^l+1=n^l+mn^{l-k}+1.Това еm(nl−nl−k)=nl−nk.m(n^l-n^{l-k})=n^l-n^k.Ако m≥2m\ge2, то лявата страна е поне 2nl−2nl−k≥2nl−nl>nl−nk2n^l-2n^{l-k}\ge2n^l-n^l\gt{}n^l-n^k, противоречие. Следователно m=1m=1, а равенството дава l−k=kl-k=k, тоест l=2kl=2k. Втори случай: l<kl\lt{}k. От (2) следваnk+mnl+1∣nk+nk−l+m.n^k+mn^l+1\mid n^k+n^{k-l}+m.Същата оценка с удвояване показва, че делителят е равен на това число. Следователноnk+mnl+1=nk+nk−l+m,n^k+mn^l+1=n^k+n^{k-l}+m,откъдетоm=nk−l−1nl−1.m=\frac{n^{k-l}-1}{n^l-1}.Понеже това е цяло число, имаме nl−1∣nk−l−1n^l-1\mid n^{k-l}-1, което е възможно само ако l∣k−ll\mid k-l. Значи l∣kl\mid k. Двете възможности са точно търсените.
Отвори задачатаMathNetISL 2016 N4Условие — източник

Задача N5

Пълен запис
Условие
Нека aa е положително цяло число, което не е точен квадрат. Да означим с AA множеството от всички положителни цели числа kk, за коитоk=x2−ax2−y2k=\frac{x^2-a}{x^2-y^2}за някои цели числа x,yx,y с x>ax\gt{}\sqrt a. Да означим с BB множеството от всички положителни цели числа kk, за които същото равенство е изпълнено за някои цели числа x,yx,y с 0≤x<a0\le x\lt{}\sqrt a. Докажете, че A=BA=B.
РешениеРавенството е еквивалентно наky2−(k−1)x2=a.(1)ky^2-(k-1)x^2=a.\tag{1}Понеже aa не е точен квадрат, случаят k=1k=1 е невъзможен; следователно винаги k>1k\gt{}1. Ще използваме следното наблюдение. Ако (x0,y0)(x_0,y_0) е решение на (1), то за всеки избор на знак двойката((2k−1)x0±2ky0,(2k−1)y0±2(k−1)x0)\big((2k-1)x_0\pm2ky_0, (2k-1)y_0\pm2(k-1)x_0\big)също е решение. Това се проверява непосредствено чрез заместване:k((2k−1)y0±2(k−1)x0)2−(k−1)((2k−1)x0±2ky0)2=ky02−(k−1)x02=a.\begin{aligned} &k((2k-1)y_0\pm2(k-1)x_0)^2-(k-1)((2k-1)x_0\pm2ky_0)^2 \\ &\qquad=ky_0^2-(k-1)x_0^2=a. \end{aligned}Нека първо k∈Bk\in B. Имаме решение на (1) с 0≤x<a0\le x\lt{}\sqrt a; можем да вземем y≥0y\ge0. От първоначалната дроб следва y>xy\gt{}x. Прилагаме преобразуването със знак плюс:x1=(2k−1)x+2ky,y1=(2k−1)y+2(k−1)x.x_1=(2k-1)x+2ky,\qquad y_1=(2k-1)y+2(k-1)x.Получаваме ново решение и x1>xx_1\gt{}x. Повтаряйки крайно много пъти, стигаме до решение с x>ax\gt{}\sqrt a, следователно k∈Ak\in A. Нека сега k∈Ak\in A. Имаме решение с x>ax\gt{}\sqrt a; можем да вземем y≥0y\ge0. Тогава от дробта следва x>yx\gt{}y. Прилагаме преобразуването със знак минус и поставямеx1=∣(2k−1)x−2ky∣,y1=(2k−1)y−2(k−1)x.x_1=|(2k-1)x-2ky|,\qquad y_1=(2k-1)y-2(k-1)x.От (1) имаме ky2=(k−1)x2+a>(k−1)x2ky^2=(k-1)x^2+a\gt{}(k-1)x^2, откъдето ky>(k−1)xky\gt{}(k-1)x. Затова(2k−1)x−2ky<x.(2k-1)x-2ky\lt{}x.От y<xy\lt{}x пък следва(2k−1)x−2ky>−x.(2k-1)x-2ky\gt{}-x.Следователно 0≤x1<x0\le x_1\lt{}x, а новата двойка отново удовлетворява (1). Повтаряме този спад на xx; след краен брой стъпки получаваме решение с 0≤x<a0\le x\lt{}\sqrt a. Значи k∈Bk\in B. Доказахме B⊆AB\subseteq A и A⊆BA\subseteq B, следователно A=BA=B.
Отвори задачатаMathNetISL 2016 N5Условие — източник

Задача N6

Пълен запис
Условие
Нека N\mathbb N е множеството на положителните цели числа. Да се намерят всички функции f:N→Nf:\mathbb N\to\mathbb N, за които за всички положителни цели числа m,nm,n числото f(m)+f(n)−mnf(m)+f(n)-mn е ненулево и дели mf(m)+nf(n)mf(m)+nf(n).
РешениеОтговорът еf(n)=n2за всяко n∈N.f(n)=n^2\quad\text{за всяко }n\in\mathbb N.Дадено е, чеf(m)+f(n)−mn∣mf(m)+nf(n).(1)f(m)+f(n)-mn\mid mf(m)+nf(n).\tag{1}При m=n=1m=n=1 получаваме 2f(1)−1∣2f(1)2f(1)-1\mid2f(1), следователно 2f(1)−1∣12f(1)-1\mid1 и f(1)=1f(1)=1. Нека p≥7p\ge7 е просто число. При m=pm=p, n=1n=1 от (1) имамеf(p)−p+1∣pf(p)+1,f(p)-p+1\mid pf(p)+1,откъдетоf(p)−p+1∣pf(p)+1−p(f(p)−p+1)=p2−p+1.f(p)-p+1\mid pf(p)+1-p(f(p)-p+1)=p^2-p+1.Ако f(p)−p+1=p2−p+1f(p)-p+1=p^2-p+1, то f(p)=p2f(p)=p^2. В противен случай, понеже p2−p+1p^2-p+1 е нечетно положително число,p2−p+1≥3(f(p)−p+1),p^2-p+1\ge3(f(p)-p+1),тоестf(p)≤p2+2p−23.(2)f(p)\le\frac{p^2+2p-2}{3}.\tag{2}При m=n=pm=n=p от (1) следва2f(p)−p2∣2pf(p).2f(p)-p^2\mid2pf(p).Следователно2f(p)−p2∣2pf(p)−p(2f(p)−p2)=p3.2f(p)-p^2\mid2pf(p)-p(2f(p)-p^2)=p^3.Ако сме в случая (2), то−p2<2f(p)−p2≤23(p2+2p−2)−p2<−p-p^2\lt{}2f(p)-p^2\le\frac23(p^2+2p-2)-p^2\lt{}-pза p≥7p\ge7. Това е невъзможно за делител на p3p^3. Значи f(p)=p2f(p)=p^2 за всяко просто p≥7p\ge7. Сега фиксираме произволно положително цяло число nn и избираме достатъчно голямо просто pp. При m=pm=p от (1) получавамеf(p)+f(n)−pn∣f(p)+f(n)-pn\midpf(p)+nf(n)−n(f(p)+f(n)−pn). pf(p)+nf(n)-n(f(p)+f(n)-pn).Понеже f(p)=p2f(p)=p^2, това еp2−pn+f(n)∣p(p2−pn+n2).p^2-pn+f(n)\mid p(p^2-pn+n^2).За достатъчно голямо pp имаме p∤f(n)p\nmid f(n), следователно gcd⁡(p,p2−pn+f(n))=1\gcd(p,p^2-pn+f(n))=1. Значиp2−pn+f(n)∣p2−pn+n2,p^2-pn+f(n)\mid p^2-pn+n^2,а оттукp2−pn+f(n)∣n2−f(n).p^2-pn+f(n)\mid n^2-f(n).Лявата страна може да стане произволно голяма по абсолютна стойност, докато n2−f(n)n^2-f(n) е фиксирано число. Следователно n2−f(n)=0n^2-f(n)=0, тоест f(n)=n2f(n)=n^2. Накрая проверката е непосредствена:f(m)+f(n)−mn=m2+n2−mnf(m)+f(n)-mn=m^2+n^2-mnиmf(m)+nf(n)=m3+n3=(m+n)(m2+n2−mn).mf(m)+nf(n)=m^3+n^3=(m+n)(m^2+n^2-mn).Затова функцията f(n)=n2f(n)=n^2 наистина удовлетворява условието.
Отвори задачатаMathNetISL 2016 N6Условие — източник

Задача N7

Пълен запис
Условие
Нека nn е нечетно положително цяло число. В декартова координатна система е избран вписан многоъгълник PP с лице SS. Всички негови върхове имат цели координати и квадратите на дължините на всички негови страни се делят на nn. Докажете, че 2S2S е цяло число, което се дели на nn.
РешениеНека P=A1A2…AkP=A_1A_2\ldots A_k и Ak+i=AiA_{k+i}=A_i. По формулата на Гаус за лице на многоъгълник с цели координати числото 2S2S е цяло. Остава да докажем делимостта на 2S2S на nn. Достатъчно е да разгледаме случая n=ptn=p^t, където pp е нечетно просто число и t≥1t\ge1. Ще докажем твърдението с индукция по броя kk на върховете. За k=3k=3 нека квадратите на страните са ptap^t a, ptbp^t b, ptcp^t c. По формулата на Херон, записана чрез квадратите на страните,16S2=p2t(2ab+2bc+2ca−a2−b2−c2).16S^2=p^{2t}(2ab+2bc+2ca-a^2-b^2-c^2).Понеже pp е нечетно и 2S2S е цяло, оттук следва pt∣2Sp^t\mid2S. Нека k≥4k\ge4. Ако квадратът на дължината на някой диагонал се дели на ptp^t, този диагонал разделя многоъгълника на два по-малки вписани многоъгълника и индукционното предположение се прилага към тях. Затова можем да приемем, че нито един диагонал няма квадрат на дължината, делящ се на ptp^t. За точки X,YX,Y нека XY2XY^2 означава квадрата на разстоянието между тях, а νp(r)\nu_p(r) - показателя на pp в разлагането на ненулевото цяло число rr. Ще докажем, чеνp(A1Am2)>νp(A1Am+12)\nu_p(A_1A_m^2)\gt{}\nu_p(A_1A_{m+1}^2)\qquad(2≤m≤k−1).(1)(2\le m\le k-1).\tag{1}За m=2m=2 това е ясно: A1A2A_1A_2 е страна, а A1A3A_1A_3 е диагонал. Нека (1) е вярно до някое mm. Прилагаме теоремата на Птолемей към вписания четириъгълник A1Am−1AmAm+1A_1A_{m-1}A_mA_{m+1} и пренасяме единия член след повдигане в подходяща форма:A1Am+12⋅Am−1Am2=A1Am−12⋅AmAm+12+A1Am2⋅Am−1Am+12−2A1Am−1⋅AmAm+1⋅A1Am⋅Am−1Am+1.(2)\begin{aligned} &A_1A_{m+1}^2\cdot A_{m-1}A_m^2 \\ &=A_1A_{m-1}^2\cdot A_mA_{m+1}^2+A_1A_m^2\cdot A_{m-1}A_{m+1}^2 \\ &\quad -2A_1A_{m-1}\cdot A_mA_{m+1}\cdot A_1A_m\cdot A_{m-1}A_{m+1}.\tag{2} \end{aligned}Последният член е цяло число, защото е разлика на първите три цели члена. По индукционното предположениеνp(A1Am−12)>νp(A1Am2),\nu_p(A_1A_{m-1}^2)\gt{}\nu_p(A_1A_m^2),а понеже AmAm+1A_mA_{m+1} е страна и Am−1Am+1A_{m-1}A_{m+1} е диагонал,νp(AmAm+12)≥t>νp(Am−1Am+12).\nu_p(A_mA_{m+1}^2)\ge t\gt{}\nu_p(A_{m-1}A_{m+1}^2).Следователно първият член вдясно в (2) има по-голяма pp-адична оценка от втория. Същите две неравенства показват, че оценката на последния член е също по-голяма от оценката на втория. Значи оценката на цялата дясна страна е оценката на втория член, тоестνp(A1Am+12)+νp(Am−1Am2)=\nu_p(A_1A_{m+1}^2)+\nu_p(A_{m-1}A_m^2)=νp(A1Am2)+νp(Am−1Am+12).\nu_p(A_1A_m^2)+\nu_p(A_{m-1}A_{m+1}^2).Но Am−1AmA_{m-1}A_m е страна, докато Am−1Am+1A_{m-1}A_{m+1} е диагонал, така че отновоνp(Am−1Am2)≥t>νp(Am−1Am+12).\nu_p(A_{m-1}A_m^2)\ge t\gt{}\nu_p(A_{m-1}A_{m+1}^2).Получаваме νp(A1Am+12)<νp(A1Am2)\nu_p(A_1A_{m+1}^2)\lt{}\nu_p(A_1A_m^2), което доказва (1). От (1) следва веригаt>νp(A1A32)>νp(A1A42)>t\gt{}\nu_p(A_1A_3^2)\gt{}\nu_p(A_1A_4^2)\gt{}⋯>νp(A1Ak2)≥t,\cdots\gt{}\nu_p(A_1A_k^2)\ge t,защото A1A3,…,A1Ak−1A_1A_3,\ldots,A_1A_{k-1} са диагонали, а A1AkA_1A_k е страна. Това е противоречие. Следователно някой диагонал има квадрат на дължината, делящ се на ptp^t, и индукцията завършва доказателството.
Отвори задачатаMathNetISL 2016 N7Условие — източник

Задача N8

Пълен запис
Условие
Да се намерят всички полиноми P(x)P(x) с нечетна степен dd и цели коефициенти, които имат следното свойство: за всяко положително цяло число nn съществуват nn положителни цели числа x1,x2,…,xnx_1,x_2,\ldots,x_n, такива че12<P(xi)P(xj)<2\frac12\lt{}\frac{P(x_i)}{P(x_j)}\lt{}2и P(xi)P(xj)\frac{P(x_i)}{P(x_j)} е dd-та степен на рационално число за всяка двойка индекси i,ji,j с 1≤i,j≤n1\le i,j\le n.
РешениеОтговорът еP(x)=a(rx+s)d,P(x)=a(rx+s)^d,където a,r,sa,r,s са цели числа, a≠0a\ne0, r≥1r\ge1 и gcd⁡(r,s)=1\gcd(r,s)=1. НекаP(x)=adxd+ad−1xd−1+⋯+a0.P(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_0.Правим смянатаy=dadx+ad−1y=da_dx+a_{d-1}и дефинираме Q(y)=P(x)Q(y)=P(x). Тогава QQ е полином с рационални коефициенти и без член от степен d−1d-1:Q(y)=bdyd+bd−2yd−2+⋯+b0.Q(y)=b_dy^d+b_{d-2}y^{d-2}+\cdots+b_0.Нека B=max⁡∣bi∣B=\max |b_i|, като полагаме bd−1=0b_{d-1}=0. От условието следва, че за произволно големи nn има цели числа y1,…,yny_1,\ldots,y_n с12<Q(yi)Q(yj)<2\frac12\lt{}\frac{Q(y_i)}{Q(y_j)}\lt{}2и тези отношения са dd-ти степени на рационални числа. Можем да избираме тези yiy_i с достатъчно голяма абсолютна стойност. По теоремата на Дирихле избираме достатъчно голямо просто число pp с p≡2(modd)p\equiv2\pmod d; тогава gcd⁡(p−1,d)=1\gcd(p-1,d)=1. За достатъчно голямо nn принципът на Дирихле дава d+1d+1 от числата yiy_i, които са сравними по модул pp. Без ограничение некаy1≡y2≡⋯≡yd+1(modp).y_1\equiv y_2\equiv\cdots\equiv y_{d+1}\pmod p.Ще докажем, че за 2≤i≤d+12\le i\le d+1Q(yi)Q(y1)=yidy1d.(1)\frac{Q(y_i)}{Q(y_1)}=\frac{y_i^d}{y_1^d}.\tag{1}НекаQ(yi)Q(y1)=ldmd,\frac{Q(y_i)}{Q(y_1)}=\frac{l^d}{m^d},където l,ml,m са взаимно прости положителни цели числа. Тогаваbd(mdyid−ldy1d)=b_d(m^dy_i^d-l^dy_1^d)=−∑j=0d−2bj(mdyij−ldy1j).(2)-\sum_{j=0}^{d-2}b_j(m^dy_i^j-l^dy_1^j).\tag{2}Нека cc е общ знаменател на коефициентите на QQ. Можем да приемем p∤cp\nmid c. От yi≡y1(modp)y_i\equiv y_1\pmod p следваcQ(yi)≡cQ(y1)(modp).cQ(y_i)\equiv cQ(y_1)\pmod p.Ако p∣cQ(y1)p\mid cQ(y_1), то при съкращаване в дробта cQ(yi)/cQ(y1)cQ(y_i)/cQ(y_1) се губи поне един множител pp, откъдетоmd≤p−1∣cQ(y1)∣.m^d\le p^{-1}|cQ(y_1)|.Понеже ∣Q(y1)∣<2B∣y1∣d|Q(y_1)|\lt{}2B|y_1|^d за достатъчно голямо ∣y1∣|y_1|, получавамеm≤p−1/d(2cB)1/d∣y1∣.(3)m\le p^{-1/d}(2cB)^{1/d}|y_1|.\tag{3}От 1/2<Q(yi)/Q(y1)<21/2\lt{}Q(y_i)/Q(y_1)\lt{}2 следва също13<yidy1d<3(4)\frac13\lt{}\frac{y_i^d}{y_1^d}\lt{}3\tag{4}за достатъчно големи yi,y1y_i,y_1, а от отношението ld/mdl^d/m^d имаме12<ldmd<2.(5)\frac12\lt{}\frac{l^d}{m^d}\lt{}2.\tag{5}Ако myi−ly1≠0my_i-ly_1\ne0, лявата страна на (2), разложена катоbd(myi−ly1)(md−1yid−1+md−2yid−2ly1+⋯+ld−1y1d−1),b_d(my_i-ly_1)(m^{d-1}y_i^{d-1}+m^{d-2}y_i^{d-2}ly_1+\cdots+l^{d-1}y_1^{d-1}),има абсолютна стойност поне ∣bd∣md−1∣yi∣d−1|b_d|m^{d-1}|y_i|^{d-1}. Дясната страна на (2), използвайки (3), (4) и (5), има абсолютна стойност най-много21(d−1)Bp−1/d(2cB)1/dmd−1∣yi∣d−1.21(d-1)Bp^{-1/d}(2cB)^{1/d}m^{d-1}|y_i|^{d-1}.За достатъчно голямо pp това е невъзможно. Следователно myi=ly1my_i=ly_1. Остава случаят gcd⁡(p,cQ(y1))=1\gcd(p,cQ(y_1))=1. Тогава от сравнението по модул pp получаваме ld≡md(modp)l^d\equiv m^d\pmod p. Понеже gcd⁡(p−1,d)=1\gcd(p-1,d)=1, следва l≡m(modp)l\equiv m\pmod p, а значи p∣myi−ly1p\mid my_i-ly_1. Ако myi−ly1≠0my_i-ly_1\ne0, лявата страна на (2) има абсолютна стойност поне ∣bd∣pmd−1∣yi∣d−1|b_d|p m^{d-1}|y_i|^{d-1}, докато дясната страна се оценява както преди с константа, независеща от pp. За достатъчно голямо pp това отново е противоречие. Значи myi=ly1my_i=ly_1 и (1) е доказано. От (1) полиномътQ(y1)yd−y1dQ(y)Q(y_1)y^d-y_1^dQ(y)има корени y1,y2,…,yd+1y_1,y_2,\ldots,y_{d+1}, но степента му е най-много dd. Следователно той е нулевият полином и Q(y)=bdydQ(y)=b_dy^d. Връщайки смяната на променливата, получавамеP(x)=ad(x+ad−1dad)d.P(x)=a_d\left(x+\frac{a_{d-1}}{da_d}\right)^d.Записваме ad−1dad=s/r\frac{a_{d-1}}{da_d}=s/r с r≥1r\ge1 и gcd⁡(r,s)=1\gcd(r,s)=1. Тъй като PP има цели коефициенти, rd∣adr^d\mid a_d, тоест ad=rdaa_d=r^d a за някое цяло aa. ПолучавамеP(x)=a(rx+s)d.P(x)=a(rx+s)^d.Обратно, всеки полином от този вид има исканото свойство: за достатъчно големи положителни цели x1,…,xnx_1,\ldots,x_n отношениятаP(xi)P(xj)=(rxi+srxj+s)d\frac{P(x_i)}{P(x_j)}=\left(\frac{rx_i+s}{rx_j+s}\right)^dса dd-ти степени на рационални числа и могат да бъдат направени между 1/21/2 и 22.
Отвори задачатаMathNetISL 2016 N8Условие — източник