IMO Shortlisted Problems

Задача A1

Пълен запис

Условие

Намерете всички функции

f:\mathbb R_{\gt{}0}\to\mathbb R_{\gt{}0}

, такива че

\frac{f(p)^2+f(q)^2}{f(r^2)+f(s^2)}=\frac{p^2+q^2}{r^2+s^2}

за всички

p,q,r,s\gt{}0

с

pq=rs

.

Решение

Отговорът е

f(x)=x\quad\text{за всички }x\gt{}0,

или

f(x)=\frac1x\quad\text{за всички }x\gt{}0.

Двете функции непосредствено удовлетворяват условието. Нека

f

е произволно решение. Поставяме

p=q=r=s=1

. Получаваме

f(1)^2=f(1)

, а понеже стойностите са положителни,

f(1)=1

. Сега фиксираме

x\gt{}0

и поставяме

p=x

,

q=1

,

r=s=\sqrt x

. Тогава

pq=rs=x

и

\frac{f(x)^2+1}{2f(x)}=\frac{x^2+1}{2x}.

След умножение получаваме

xf(x)^2+x=(x^2+1)f(x),

тоест

(f(x)-x)(xf(x)-1)=0.

Значи за всяко

x\gt{}0

е вярно

f(x)=x\quad\text{или}\quad f(x)=\frac1x.\tag{1}

Остава да покажем, че двата избора не могат да се смесват. Да допуснем противното. Тогава съществуват

a,b\gt{}0

, за които

f(a)=1/a

и

f(b)=b

; непременно

a\ne1

и

b\ne1

. Прилагаме условието за

p=a

,

q=b

,

r=s=\sqrt{\vphantom{x^2}ab}

. Получаваме

\frac{a^{-2}+b^2}{2f(ab)}=\frac{a^2+b^2}{2ab},

следователно

f(ab)=\frac{ab(a^{-2}+b^2)}{a^2+b^2}.\tag{2}

По (1) имаме

f(ab)=ab

или

f(ab)=1/(ab)

. Ако

f(ab)=ab

, от (2) следва

a^{-2}+b^2=a^2+b^2

, откъдето

a=1

, противоречие. Ако

f(ab)=1/(ab)

, от (2) следва

a^2b^2(a^{-2}+b^2)=a^2+b^2,

тоест

a^2b^4=a^2

, откъдето

b=1

, отново противоречие. Следователно изборът в (1) е един и същ за всички положителни

x

, което дава точно двете посочени функции.

Отвори задачатаMathNetISL 2008 A1Условие — източник

Задача A2

Пълен запис

Условие

Нека

x,y,z

са реални числа, различни от

1

, за които

xyz=1

. а) Докажете неравенството

\frac{x^2}{(x-1)^2}+\frac{y^2}{(y-1)^2}+\frac{z^2}{(z-1)^2}\ge1.

б) Покажете, че съществуват безкрайно много тройки от рационални числа

x,y,z

, за които в това неравенство има равенство.

Решение

Поставяме

a=\frac{x}{x-1},\qquad b=\frac{y}{y-1},\qquad c=\frac{z}{z-1}.

Тогава

x=a/(a-1)

и аналогично за

y,z

, като

a,b,c\ne1

. Условието

xyz=1

става

(a-1)(b-1)(c-1)=abc.

След разкриване това е еквивалентно на

a+b+c-1=ab+bc+ca.

Оттук

\begin{aligned} a^2+b^2+c^2-1&=(a+b+c)^2-2(ab+bc+ca)-1\\ &=(a+b+c)^2-2(a+b+c-1)-1\\ &=(a+b+c-1)^2\ge0. \end{aligned}

Но лявата страна на исканото неравенство е

a^2+b^2+c^2

, така че част а) е доказана. За равенство е необходимо и достатъчно

a^2+b^2+c^2=1\quad\text{и}\quad a+b+c=1.

Тогава от

a+b+c-1=ab+bc+ca

получаваме също

ab+bc+ca=0

. Обратно, условията

a+b+c=1,\qquad ab+bc+ca=0

водят до равенство. Ще построим безкрайно много рационални тройки

(a,b,c)

с тези свойства. Елиминираме

c=1-a-b

и получаваме

a^2+ab+b^2=a+b,

или, като квадратно уравнение за

b

,

b^2+(a-1)b+a(a-1)=0.

Дискриминантата е

\Delta=(a-1)^2-4a(a-1)=(1-a)(1+3a).

Нека

k\gt{}1

е цяло число и положим

m=k^2-k+1,\qquad a=\frac{k}{m}.

Тогава

\Delta=\frac{(k^2-1)^2}{m^2}

е квадрат на рационално число. Избирайки по-големия корен, получаваме

b=\frac{m-1}{m},\qquad c=1-a-b=\frac{1-k}{m}.

Така

a,b,c

са рационални, удовлетворяват

a+b+c=1

и

ab+bc+ca=0

, а за

k\gt{}1

нито едно от тях не е равно на

1

. Връщайки се към първоначалните променливи, получаваме рационалната тройка

x=\frac{a}{a-1}=-\frac{k}{(k-1)^2},

\qquad y=\frac{b}{b-1}=k-k^2,\qquad z=\frac{c}{c-1}=\frac{k-1}{k^2}.

За всяко цяло

k\gt{}1

тя дава равенство в неравенството. Понеже тези стойности са безкрайно много различни, част б) е доказана.

Отвори задачатаMathNetISL 2008 A2Условие — източник

Задача A3

Пълен запис

Условие

Нека

S\subseteq\mathbb{R}

е множество от реални числа. Ще казваме, че двойка

(f,g)

от функции от

S

в

S

е испанска двойка върху

S

, ако са изпълнени следните условия: (i) и двете функции са строго растящи, тоест

f(x)\lt{}f(y)

и

g(x)\lt{}g(y)

за всички

x,y\in S

с

x\lt{}y

; (ii) за всяко

x\in S

е изпълнено неравенството

f(g(g(x)))\lt{}g(f(x))

. Да се определи дали съществува испанска двойка: а) върху множеството

S=\mathbb{N}

на положителните цели числа; б) върху множеството

S=\{a-1/b\mid a,b\in\mathbb{N}\}

.

Решение

Отговорът е: не в а) и да в б). а) За

k\ge0

ще пишем

g_k(x)

за

k

-кратното прилагане на

g

, като

g_0(x)=x

. Да допуснем, че съществува испанска двойка

(f,g)

върху

\mathbb{N}

. От строгата монотонност следва

f(x)\ge x

и

g(x)\ge x

за всяко

x\in\mathbb{N}

. Ще докажем, че

g_k(x)\le f(x)

за всички

k\ge0

и всички положителни цели числа

x

. Базата

k=0

е ясна. За прехода от

k

към

k+1

прилагаме индукционното предположение към

g_2(x)

вместо към

x

и после използваме условие (ii):

g\left(g_{k+1}(x)\right)=g_k\left(g_2(x)\right)\le

f\left(g_2(x)\right)\lt{}g(f(x)).

Понеже

g

е строго растяща, получаваме

g_{k+1}(x)\lt{}f(x)

. Ако

g(x)=x

за всяко

x\in\mathbb{N}

, то

f(g(g(x)))=f(x)=g(f(x))

, което противоречи на (ii). Следователно съществува

x_0

, за което

x_0\lt{}g(x_0)

. Тогава редицата

x_0,g(x_0),g_2(x_0),\ldots

е строго растяща редица от положителни цели числа. От вече доказаното обаче всички нейни членове са не по-големи от

f(x_0)

, невъзможно. Значи върху

\mathbb{N}

испанска двойка не съществува. б) Върху

S=\{a-1/b\mid a,b\in\mathbb{N}\}

дефинираме

f(a-1/b)=a+1-1/b,\qquad g(a-1/b)=a-\frac1{b+3^a}.

Тези функции изпращат

S

в

S

и са строго растящи. Остава да проверим (ii). За всеки елемент

a-1/b\in S

имаме

f(g(g(a-1/b)))=(a+1)-\frac1{b+2\cdot3^a}\lt{}

(a+1)-\frac1{b+3^{a+1}}=g(f(a-1/b)),

защото

b+2\cdot3^a\lt{}b+3^{a+1}

. Следователно върху това множество съществува испанска двойка.

Отвори задачатаMathNetISL 2008 A3Условие — източник

Задача A4

Пълен запис

Условие

За цяло число

m

означаваме с

t(m)

единственото число от множеството

\{1,2,3\}

, за което

m+t(m)

се дели на

3

. Функция

f:\mathbb{Z}\to\mathbb{Z}

удовлетворява

f(-1)=0

,

f(0)=1

,

f(1)=-1

и

f(2^n+m)=f(2^n-t(m))-f(m)

за всички цели числа

m,n\ge0

с

2^n\gt{}m

. Да се докаже, че

f(3p)\ge0

за всяко цяло число

p\ge0

.

Решение

Дадените условия определят функцията еднозначно върху неотрицателните цели числа. Първо ще разгледаме стойностите от вида

f(2^n-t(m))

. Нека положителното цяло число

u

има двоичен запис

u=2^{a_0}+2^{a_1}+\cdots+2^{a_k},\qquad a_0\gt{}a_1\gt{}\cdots\gt{}a_k\ge0.

Многократното прилагане на рекурентната формула показва, че

f(u)

може да се изрази чрез алтернираща сума от стойности от вида

f(2^{a_j}-t(u_{j+1}))

плюс

(-1)^{k+1}

. Точната формула няма да ни трябва. Ще се съсредоточим върху стойностите

f(2^n-1)

,

f(2^n-2)

и

f(2^n-3)

. Лесно се проверява, че

\begin{gathered} t(2^{2k}-3)=2,\quad t(2^{2k}-2)=1,\quad t(2^{2k}-1)=3,\\ t(2^{2k+1}-3)=1,\quad t(2^{2k+1}-2)=3,\quad t(2^{2k+1}-1)=2. \end{gathered}

Твърдение. За всяко цяло число

k\ge0

са изпълнени равенствата

\begin{array}{lll} f(2^{2k+1}-3)=0,& f(2^{2k+1}-2)=3^k,& f(2^{2k+1}-1)=-3^k,\cr f(2^{2k+2}-3)=-3^k,& f(2^{2k+2}-2)=-3^k,& f(2^{2k+2}-1)=2\cdot3^k. \end{array}

Доказателството е с индукция по

k

. При

k=0

то се свежда до директното намиране на

f(2)=-1

и

f(3)=2

от началните стойности. Нека твърдението е вярно за

k-1

. Тогава от рекурентната формула получаваме

\begin{aligned} f(2^{2k+1}-3)&=f(2^{2k}+(2^{2k}-3))=f(2^{2k}-2)-f(2^{2k}-3)=-3^{k-1}+3^{k-1}=0,\\ f(2^{2k+1}-2)&=f(2^{2k}+(2^{2k}-2))=f(2^{2k}-1)-f(2^{2k}-2)=2\cdot3^{k-1}+3^{k-1}=3^k,\\ f(2^{2k+1}-1)&=f(2^{2k}+(2^{2k}-1))=f(2^{2k}-3)-f(2^{2k}-1)=-3^{k-1}-2\cdot3^{k-1}=-3^k. \end{aligned}

След това, използвайки току-що получените три равенства, намираме

\begin{aligned} f(2^{2k+2}-3)&=f(2^{2k+1}+(2^{2k+1}-3))=f(2^{2k+1}-1)-f(2^{2k+1}-3)=-3^k,\\ f(2^{2k+2}-2)&=f(2^{2k+1}+(2^{2k+1}-2))=f(2^{2k+1}-3)-f(2^{2k+1}-2)=-3^k,\\ f(2^{2k+2}-1)&=f(2^{2k+1}+(2^{2k+1}-1))=f(2^{2k+1}-2)-f(2^{2k+1}-1)=2\cdot3^k. \end{aligned}

Твърдението е доказано. От него следват две важни оценки. За всички

m,n\ge0

имаме: (i) ако

2^n+m

се дели на

3

, то

f(2^n-t(m))\ge3^{(n-1)/2}

; (ii) ако

2^n+m

не се дели на

3

, то

f(2^n-t(m))\le0

. Освен това от същото твърдение следва

|f(2^n-t(m))|\le \frac23\cdot3^{n/2}

за всички

m,n\ge0

. Сега доказваме с индукция по

n

, че

|f(m)|\le3^{n/2}

за всички цели

m,n\ge0

с

2^n\gt{}m

. Базата е ясна, понеже

f(0)=1

. За прехода, ако

m\lt{}2^n

, използваме индукционното предположение. Ако

m\ge2^n

, пишем

m=2^n+k

, където

0\le k\lt{}2^n

. Тогава

|f(m)|=|f(2^n-t(k))-f(k)|\le

\frac23\cdot3^{n/2}+3^{n/2}\lt{}3^{(n+1)/2}.

Остава да докажем исканото. За

p=0

имаме

f(0)=1\ge0

. Нека

p\gt{}0

. Числото

3p

не е степен на

2

, следователно двоичният му запис има поне две единици. Можем да запишем

3p=2^a+2^b+c,\qquad a\gt{}b,\quad 0\le c\lt{}2^b.

Прилагайки рекурентната формула два пъти, получаваме

f(3p)=f(2^a+2^b+c)=

f(2^a-t(2^b+c))-f(2^b-t(c))+f(c).

Понеже

2^a+2^b+c

се дели на

3

, от (i) следва

f(2^a-t(2^b+c))\ge3^{(a-1)/2}

. Понеже

2^b+c

не се дели на

3

, от (ii) следва

f(2^b-t(c))\le0

. Накрая

|f(c)|\le3^{b/2}

, защото

c\lt{}2^b

. Следователно

f(3p)\ge3^{(a-1)/2}-3^{b/2}\ge0,

тъй като

a\gt{}b

. Това доказва твърдението.

Отвори задачатаMathNetISL 2008 A4Условие — източник

Задача A5

Пълен запис

Условие

Нека

a,b,c,d

са положителни реални числа, такива че

abcd=1\qquad\text{и}\qquad a+b+c+d\gt{}\frac ab+\frac bc+\frac cd+\frac da.

Да се докаже, че

a+b+c+d\lt{}\frac ba+\frac cb+\frac dc+\frac ad.

Решение

Ще докажем, че при условието

abcd=1

сумата

a+b+c+d

не надминава подходяща претеглена средна на изразите

\frac ab+\frac bc+\frac cd+\frac da\qquad\text{и}\qquad \frac ba+\frac cb+\frac dc+\frac ad.

От неравенството между средно аритметично и средно геометрично, приложено към числата

\frac ab,\frac ab,\frac bc,\frac ad

, получаваме

a=\sqrt[4]{\vphantom{x^2}\frac{a^4}{abcd}}=

\sqrt[4]{\vphantom{x^2}\frac ab\cdot\frac ab\cdot\frac bc\cdot\frac ad}\le

\frac14\left(\frac ab+\frac ab+\frac bc+\frac ad\right).

Аналогично

b\le\frac14\left(\frac bc+\frac bc+\frac cd+\frac ba\right),

c\le\frac14\left(\frac cd+\frac cd+\frac da+\frac cb\right),

\qquad d\le\frac14\left(\frac da+\frac da+\frac ab+\frac dc\right).

Събирайки тези четири оценки, намираме

a+b+c+d\le

\frac34\left(\frac ab+\frac bc+\frac cd+\frac da\right)+\frac14\left(\frac ba+\frac cb+\frac dc+\frac ad\right).

Ако сега

a+b+c+d\gt{}\frac ab+\frac bc+\frac cd+\frac da

, последното неравенство веднага дава

a+b+c+d\lt{}\frac ba+\frac cb+\frac dc+\frac ad,

както се искаше.

Отвори задачатаMathNetISL 2008 A5Условие — източник

Задача A6

Пълен запис

Условие

Нека

f:\mathbb{R}\to\mathbb{N}

е функция, такава че

f\left(x+\frac1{f(y)}\right)=f\left(y+\frac1{f(x)}\right)

за всички

x,y\in\mathbb{R}

. Да се докаже, че съществува положително цяло число, което не е стойност на

f

.

Решение

Да допуснем противното:

f(\mathbb{R})=\mathbb{N}

. Ще изведем противоречие. Първо можем да считаме, че

f(0)=1

. Наистина, ако

f(a)=1

, то функцията

g(x)=f(x+a)

удовлетворява същото функционално уравнение и има същото множество от стойности като

f

, а

g(0)=1

. Затова по-нататък приемаме

f(0)=1

. Твърдение 1. За всяко фиксирано

c\in\mathbb{R}

имаме

\{f(c+1/n)\mid n\in\mathbb{N}\}=\mathbb{N}.

От функционалното уравнение и от

f(\mathbb{R})=\mathbb{N}

следва

f(\mathbb{R})=\left\{f\left(x+\frac1{f(c)}\right)\mid x\in\mathbb{R}\right\}=

\left\{f\left(c+\frac1{f(x)}\right)\mid x\in\mathbb{R}\right\}\subseteq \{f(c+1/n)\mid n\in\mathbb{N}\}\subseteq f(\mathbb{R}),

което доказва твърдението. В частност ще използваме

\{f(1/n)\mid n\in\mathbb{N}\}=

\left\{f\left(\frac13+\frac1n\right)\mid n\in\mathbb{N}\right\}=\mathbb{N}.\tag{1}

Твърдение 2. Ако

f(u)=f(v)

, то

f(u+q)=f(v+q)

за всяко неотрицателно рационално число

q

. Освен това, ако

q

е неотрицателно рационално число и

f(q)=1

, то

f(kq)=1

за всяко

k\in\mathbb{N}

. За всяко

x\in\mathbb{R}

имаме

f\left(u+\frac1{f(x)}\right)=f\left(x+\frac1{f(u)}\right)=

f\left(x+\frac1{f(v)}\right)=f\left(v+\frac1{f(x)}\right).

Понеже

f(x)

приема всички положителни цели стойности, получаваме

f(u+1/n)=f(v+1/n)

за всяко

n\in\mathbb{N}

. Повтаряйки тази стъпка

k

пъти, получаваме

f(u+k/n)=f(v+k/n)

, което доказва първата част. Втората част следва, като започнем от

f(0)=f(q)=1

и последователно приложим първата част. Твърдение 3. За всяко неотрицателно рационално число

q

е вярно

f(q)=f(q+1)

. От (1) съществува

m\in\mathbb{N}

с

f(1/m)=1

. По втората част на Твърдение 2 получаваме

f(1)=1

. Понеже

f(0)=f(1)=1

, първата част на Твърдение 2 дава

f(q)=f(q+1)

за всяко неотрицателно рационално

q

. Твърдение 4. За всяко

n\in\mathbb{N}

имаме

f(1/n)=n

. Нека

q

е неотрицателно рационално число. Във функционалното уравнение поставяме

x=q

и

y=0

и използваме Твърдение 3:

f\left(\frac1{f(q)}\right)=f\left(q+\frac1{f(0)}\right)=f(q+1)=f(q).

От (1), за всяко

n\in\mathbb{N}

съществува

k\in\mathbb{N}

, такова че

f(1/k)=n

. Прилагайки последното равенство към

q=1/k

, получаваме

n=f(1/k)=f\left(\frac1{f(1/k)}\right)=f(1/n),

както твърдим. Сега избираме

n\in\mathbb{N}

, за което

f(1/3+1/n)=1

; такова съществува по (1). Нека

\frac13+\frac1n=\frac st,

където

s,t\in\mathbb{N}

и

(s,t)=1

. Имаме

t\gt{}1

, защото

1/3+1/n

не е цяло число. Избираме

k,l\in\mathbb{N}

с

ks-lt=1

. От

f(0)=f(s/t)=1

и Твърдение 2 следва

f(ks/t)=1

. Но

\frac{ks}{t}=\frac1t+l,

следователно, чрез Твърдение 3, имаме

f(ks/t)=f(1/t+l)=f(1/t)

. По Твърдение 4 последното е равно на

t

. Така получаваме

t=1

, противоречие. Следователно

f

не може да приема всички положителни цели стойности.

Отвори задачатаMathNetISL 2008 A6Условие — източник

Задача A7

Пълен запис

Условие

Да се докаже, че за всеки четири положителни реални числа

a,b,c,d

е изпълнено неравенството

\frac{(a-b)(a-c)}{a+b+c}+\frac{(b-c)(b-d)}{b+c+d}

+\frac{(c-d)(c-a)}{c+d+a}+\frac{(d-a)(d-b)}{d+a+b}\ge

0.

Да се намерят всички случаи на равенство.

Решение

Да означим четирите събираеми съответно с

A,B,C,D

. Разделяме

2A

на две части:

2A=A'+A'',\qquad A'=\frac{(a-c)^2}{a+b+c},

\qquad A''=\frac{(a-c)(a-2b+c)}{a+b+c}.

По същия начин дефинираме

B',B'',C',C'',D',D''

. Нека

s=a+b+c+d

. Тогава знаменателите са

s-d,s-a,s-b,s-c

. От неравенството на Коши-Шварц получаваме

\left(2|a-c|+2|b-d|\right)^2\le3s(A'+B'+C'+D'),

следователно

A'+B'+C'+D'\ge\frac{16|a-c||b-d|}{3s}.\tag{1}

Остава да оценим втората сума. Събирайки по двойки, намираме

A''+C''=\frac{3(a-c)(d-b)(a+c)}{M},

\qquad M=s(a+c)+bd,

а по цикличност

B''+D''=\frac{3(b-d)(a-c)(b+d)}{N},

\qquad N=s(b+d)+ca.

Затова

A''+B''+C''+D''=

3(a-c)(b-d)\left(\frac{b+d}{N}-\frac{a+c}{M}\right)=\frac{3(a-c)(b-d)W}{MN},

\tag{2}

където

W=bd(b+d)-ac(a+c).

Имаме

MN\gt{}s\bigl(ac(a+c)+bd(b+d)\bigr)\ge s|W|,

и от (2) следва

|A''+B''+C''+D''|\le\frac{3|a-c||b-d|}{s}.\tag{3}

От (1) и (3) заключаваме

\begin{aligned} 2(A+B+C+D)&=(A'+B'+C'+D')+(A''+B''+C''+D'')\\ &\ge\frac{16|a-c||b-d|}{3s}-\frac{3|a-c||b-d|}{s}\\ &=\frac{7|a-c||b-d|}{3s}\ge0. \end{aligned}

Това доказва неравенството. От последната оценка равенство може да има само ако

a=c

или

b=d

. Заедно с условията за равенство в използваната оценка това дава едновременно

a=c

и

b=d

. Обратно, при

a=c

и

b=d

четирите събираеми дават сума

0

. Следователно равенство има точно когато

a=c

и

b=d

.

Отвори задачатаMathNetISL 2008 A7Условие — източник

Задача C1

Пълен запис

Условие

В равнината разглеждаме правоъгълници със страни, успоредни на координатните оси, и с положителни дължини на страните. Такъв правоъгълник ще наричаме кутия. Две кутии се пресичат, ако имат обща точка във вътрешността си или върху границата си. Намерете най-голямото

n

, за което съществуват

n

кутии

B_1,\ldots,B_n

, такива че

B_i

и

B_j

се пресичат тогава и само тогава, когато

i\not\equiv j\pm1\pmod n.

Решение

Отговорът е

6

. Първо даваме построение за

n=6

без рисунка. Нека

B_i=I_i\times J_i

, където

\begin{array}{c|cccccc} i&1&2&3&4&5&6\cr \hline I_i&[1,4]&[5,6]&[1,2]&[3,6]&[1,6]&[1,6]\cr J_i&[3,6]&[1,6]&[1,6]&[1,4]&[5,6]&[1,2] \end{array}

Преките проверки показват, че съседните по цикъл двойки

B_1,B_2

;

B_2,B_3

;

B_3,B_4

;

B_4,B_5

;

B_5,B_6

;

B_6,B_1

имат несечащи се проекции върху поне една ос, а всяка несъседна двойка има сечащи се проекции и върху двете оси. Следователно тези шест кутии удовлетворяват условието. Ще докажем, че повече от

6

кутии не са възможни. Нека

I_k

и

J_k

са съответно проекциите на

B_k

върху осите

x

и

y

. Две кутии се пресичат точно когато и двете двойки проекции се пресичат. Значи две кутии са несечащи се точно когато поне по една от координатните оси съответните им проекции са несечащи се. Ще наричаме две кутии или два интервала съседни, ако индексите им се различават с

1

по модул

n

. По условие всяка съседна двойка кутии е несечаща се, така че за всеки

k

поне една от двойките

(I_k,I_{k+1})

и

(J_k,J_{k+1})

е двойка несечащи се интервали. Следователно общият брой на несечащите се съседни двойки сред интервалите

I_1,\ldots,I_n

и

J_1,\ldots,J_n

е поне

n

. Ще използваме следната лема. Ако

\Delta_1,\Delta_2,\ldots,\Delta_n

са интервали на права и всеки два несъседни интервала се пресичат, то най-много три от съседните двойки

(\Delta_1,\Delta_2),\ldots,(\Delta_n,\Delta_1)

са несечащи се. Доказателство на лемата. Нека

\Delta_k=[a_k,b_k]

. Избираме най-десния ляв край и най-левия десен край:

\alpha=\max(a_1,\ldots,a_n),\qquad \beta=\min(b_1,\ldots,b_n).

След циклично преименуване можем да считаме, че

\alpha=a_2

. Ако

\alpha\le\beta

, тогава всички интервали съдържат точката

\alpha

, така че няма несечаща се двойка. Нека

\beta\lt{}\alpha

. Тогава

\beta=b_i

за някое

i

и интервалите

\Delta_2

и

\Delta_i

са несечащи се. Понеже

\Delta_2

се пресича с всички несъседни на него интервали, възможно е само

i=1

или

i=3

. По симетрия нека

i=3

, тоест

\beta=b_3

. Всеки от интервалите

\Delta_4,\ldots,\Delta_n

се пресича с

\Delta_2

, а левият му край е не по-голям от

\alpha

. Затова всички те съдържат

\alpha

. От друга страна, всеки от интервалите

\Delta_5,\ldots,\Delta_n,\Delta_1

се пресича с

\Delta_3

, а десният му край е поне

\beta

, така че всички те съдържат

\beta

. Следователно единствените съседни двойки, които могат да бъдат несечащи се, са

(\Delta_1,\Delta_2)

,

(\Delta_2,\Delta_3)

и

(\Delta_3,\Delta_4)

. Лемата е доказана. Прилагаме лемата към семейството

I_1,\ldots,I_n

и после към

J_1,\ldots,J_n

. Понеже всяка несъседна двойка кутии се пресича, несъседните им проекции се пресичат и по двете оси. Следователно сред съседните двойки на

I

-интервалите има най-много

3

несечащи се двойки, и същото важи за

J

-интервалите. Общо те са най-много

6

, но по-горе видяхме, че са поне

n

. Значи

n\le6

.

Отвори задачатаMathNetISL 2008 C1Условие — източник

Задача C2

Пълен запис

Условие

За всяко положително цяло число

n

да се определи броят на пермутациите

(a_1,a_2,\ldots,a_n)

на множеството

\{1,2,\ldots,n\}

със следното свойство:

2(a_1+a_2+\cdots+a_k)\quad\text{се дели на }k\quad\text{за }k=1,

2,\ldots,n.

Решение

Нека

F_n

е броят на пермутациите с исканото свойство; ще ги наричаме добри. За

n=1,2,3

всяка пермутация е добра, така че

F_1=1

,

F_2=2

,

F_3=6

. Нека

n\gt{}3

и

(a_1,a_2,\ldots,a_n)

е добра пермутация на

\{1,2,\ldots,n\}

. За

k=n-1

числото

\begin{aligned} 2(a_1+a_2+\cdots+a_{n-1})&=2((1+2+\cdots+n)-a_n)\\ &=n(n+1)-2a_n=(n+2)(n-1)+(2-2a_n) \end{aligned}

трябва да се дели на

n-1

. Следователно

2a_n-2

се дели на

n-1

, откъдето

a_n=1\qquad\text{или}\qquad a_n=\frac{n+1}{2}\qquad\text{или}\qquad a_n=n.

Да допуснем, че

a_n=(n+1)/2

. Тогава, използвайки условието за

k=n-2

, получаваме

\begin{aligned} 2(a_1+a_2+\cdots+a_{n-2})&=n(n+1)-(n+1)-2a_{n-1}\\ &=(n+2)(n-2)+(3-2a_{n-1}). \end{aligned}

Значи

2a_{n-1}-3

се дели на

n-2

. Възможните стойности

0

и

2n-4

са изключени по четност, а стойността

n-2

би дала

a_{n-1}=(n+1)/2=a_n

, невъзможно. Следователно

a_n

не може да бъде

(n+1)/2

, т.е.

a_n=1

или

a_n=n

. Ако

a_n=n

, то

(a_1,a_2,\ldots,a_{n-1})

е добра пермутация на

\{1,2,\ldots,n-1\}

, и обратно всяка такава пермутация дава добра пермутация на

\{1,2,\ldots,n\}

чрез добавяне на

n

в края. Ако

a_n=1

, то

(a_1-1,a_2-1,\ldots,a_{n-1}-1)

е добра пермутация на

\{1,2,\ldots,n-1\}

, защото

2((a_1-1)+\cdots+(a_k-1))=2(a_1+\cdots+a_k)-2k

се дели на

k

за всяко

k\le n-1

. И обратно, всяка добра пермутация

(b_1,b_2,\ldots,b_{n-1})

на

\{1,2,\ldots,n-1\}

дава добра пермутация

(b_1+1,b_2+1,\ldots,b_{n-1}+1,1)

. Получихме по

F_{n-1}

добри пермутации в двата случая, следователно

F_n=2F_{n-1}

за

n\gt{}3

. От

F_3=6

следва

F_n=3\cdot2^{n-2}\quad\text{за }n\ge3,

а отделно

F_1=1

и

F_2=2

.

Отвори задачатаMathNetISL 2008 C2Условие — източник

Задача C3

Пълен запис

Условие

В координатната равнина разглеждаме множеството

S

от всички точки с цели координати. За положително цяло число

k

две различни точки

A,B\in S

ще наричаме

k

-приятели, ако съществува точка

C\in S

, такава че лицето на триъгълника

ABC

е равно на

k

. Множество

T\subset S

ще наричаме

k

-клика, ако всеки две точки от

T

са

k

-приятели. Да се намери най-малкото положително цяло число

k

, за което съществува

k

-клика с повече от

200

елемента.

Решение

Първо ще опишем точките

B\in S

, които са

k

-приятели с началото

(0,0)

. Ако

B=(u,v)

, то условието е еквивалентно на съществуването на

C=(x,y)\in S

с

\frac12|uy-vx|=k.

Съществуват цели

x,y

с

|uy-vx|=2k

точно когато

\operatorname{gcd}(u,v)

дели

2k

. Следователно

B=(u,v)

е

k

-приятел с

(0,0)

точно когато

\operatorname{gcd}(u,v)\mid2k

. Транслация с вектор с цели координати не променя това свойство. Значи две точки

A=(s,t)

и

B=(u,v)

са

k

-приятели точно когато

\operatorname{gcd}(u-s,v-t)\mid2k.

Нека

n

е положително цяло число, което не дели

2k

. Тогава

k

-клика не може да има повече от

n^2

елемента. Наистина, точките с цели координати се разделят на

n^2

класа според остатъците на двете координати по модул

n

. Ако

T

има повече от

n^2

елемента, две негови точки попадат в един и същи клас, така че

n

дели и двете разлики на координатите им. Тогава техният най-голям общ делител не дели

2k

, следователно тези две точки не са

k

-приятели. Нека

M(k)

е най-малкото положително цяло число, което не дели

2k

, и да положим

M(k)=m

. Множеството от всички точки

(x,y)

с

0\le x,y\lt{}m

има

m^2

елемента и е

k

-клика. Ако две различни точки в него са

(s,t)

и

(u,v)

, то поне една от разликите

|u-s|,|v-t|

е положителна и всяка положителна такава разлика е по-малка от

m

, следователно дели

2k

. Значи и

\operatorname{gcd}(u-s,v-t)

дели

2k

. И така, максималният размер на

k

-клика е

M(k)^2

. Търсим най-малкото

k

, за което

M(k)^2\gt{}200

. Това дава

M(k)\ge15

. Стойността

M(k)=15

е невъзможна, защото тогава

2k

трябва да се дели на

3

и на

5

, но не и на

15

. Пробваме

M(k)=16

. Тогава

2k

трябва да се дели на

1,2,\ldots,15

, т.е. на тяхното най-малко общо кратно

L

, но не и на

16

. Понеже

L=\operatorname{lcm}(1,2,\ldots,15)

не се дели на

16

, най-малкото такова

k

е

L/2

. Ако

M(k)\ge17

, то

2k

трябва да се дели на

\operatorname{lcm}(1,2,\ldots,16)=2L

, откъдето

k\gt{}L/2

. Следователно търсеното най-малко число е

\frac{L}{2}=180180.

Отвори задачатаMathNetISL 2008 C3Условие — източник

Задача C4

Пълен запис

Условие

Нека

n

и

k

са фиксирани положителни цели числа с една и съща четност, като

k\ge n

. Дадени са

2n

лампи, номерирани от

1

до

2n

, всяка от които може да бъде включена или изключена. Първоначално всички лампи са изключени. Разглеждаме редици от

k

стъпки, като на всяка стъпка една лампа се превключва. Нека

N

е броят на редиците от

k

стъпки, които завършват в състояние, в което лампите

1,\ldots,n

са включени, а лампите

n+1,\ldots,2n

са изключени. Нека

M

е броят на редиците от

k

стъпки със същото крайно състояние, но в които лампите

n+1,\ldots,2n

изобщо не се пипат. Намерете отношението

N/M

.

Решение

Отговорът е

\frac NM=2^{k-n}.

Ще наричаме допустим всеки процес от

k

превключвания, който завършва в описаното крайно състояние. Ако освен това в процеса не се пипат лампите

n+1,\ldots,2n

, ще го наричаме ограничен. Значи допустимите процеси са

N

, а ограничените допустими процеси са

M

. Първо

M\gt{}0

: превключваме веднъж всяка от лампите

1,\ldots,n

, а останалите

k-n

превключвания правим върху лампа

1

; това е възможно, защото

k-n

е четно. Фиксираме ограничен допустим процес. Нека лампа

i

,

1\le i\le n

, се превключва

c_i

пъти. Понеже в края тази лампа е включена,

c_i

е нечетно, а

c_1+c_2+\cdots+c_n=k.

За всяко

i

избираме четен брой от

c_i

-те появи на превключването на лампа

i

и ги заменяме с превключване на лампа

n+i

. Броят на изборите е

2^{c_i-1}

, защото половината подмножества на множество с нечетен брой елементи имат четна мощност. След тези замени лампа

i

пак е превключена нечетен брой пъти, а лампа

n+i

е превключена четен брой пъти. Следователно крайното състояние остава същото. За фиксирания ограничен процес получаваме

\prod_{i=1}^n2^{c_i-1}=2^{k-n}

допустими процеса. Обратно, нека е даден произволен допустим процес. Заменяме всяко превключване на лампа

n+i

с превключване на лампа

i

. Понеже в допустим процес лампа

n+i

завършва изключена, тя е била превключена четен брой пъти; затова тази замяна не променя крайната четност на превключванията на лампа

i

. Получаваме ограничен допустим процес. Ясно е, че първата конструкция възстановява точно всички допустими процеси, които се свеждат до него. Значи всеки ограничен допустим процес има точно

2^{k-n}

прообраза сред всички допустими процеси, откъдето

N=2^{k-n}M

.

Отвори задачатаMathNetISL 2008 C4Условие — източник

Задача C5

Пълен запис

Условие

Нека

S=\{x_1,x_2,\ldots,x_{k+\ell}\}

е множество от

k+\ell

реални числа в интервала

[0,1]

, където

k

и

\ell

са положителни цели числа. Едно

k

-елементно подмножество

A\subset S

се нарича хубаво, ако

\left|\frac1k\sum_{x_i\in A}x_i-\frac1\ell\sum_{x_j\in S\setminus A}x_j\right|\le

\frac{k+\ell}{2k\ell}.

Докажете, че броят на хубавите подмножества е поне

\frac{2}{k+\ell}\binom{k+\ell}{k}.

Решение

За

k

-елементно подмножество

A\subset S

полагаме

f(A)=\frac1k\sum_{x_i\in A}x_i-\frac1\ell\sum_{x_j\in S\setminus A}x_j,

\qquad d=\frac{k+\ell}{2k\ell}.

Тогава

A

е хубаво точно когато

|f(A)|\le d

. Фиксираме произволна пермутация

(y_1,y_2,\ldots,y_{k+\ell})

на множеството

S

. На нея съпоставяме

k+\ell

подмножества

A_i=\{y_i,y_{i+1},\ldots,y_{i+k-1}\},

\qquad i=1,2,\ldots,k+\ell,

където индексите се разглеждат по модул

k+\ell

. Това са всички блокове от

k

последователни елемента, ако елементите на пермутацията са наредени по окръжност. Ще докажем, че сред

A_1,\ldots,A_{k+\ell}

винаги има поне две хубави множества. Съседните блокове

A_i

и

A_{i+1}

се различават само по елементите

y_i

и

y_{i+k}

. Следователно, понеже

y_i,y_{i+k}\in[0,1]

,

|f(A_{i+1})-f(A_i)|=

\left|\left(\frac1k+\frac1\ell\right)(y_{i+k}-y_i)\right|\le

\frac1k+\frac1\ell=2d.\tag{1}

Всеки елемент

y_i

участва в точно

k

от множествата

A_1,\ldots,A_{k+\ell}

. Значи в

k

от числата

f(A_1),\ldots,f(A_{k+\ell})

коефициентът пред

y_i

е

1/k

, а в останалите

\ell

е

-1/\ell

. Общият принос на

y_i

към сумата е

0

, така че

f(A_1)+f(A_2)+\cdots+f(A_{k+\ell})=0.\tag{2}

Нека

f(A_p)

е минималната, а

f(A_q)

максималната от тези стойности. От (2) имаме

f(A_p)\le0\le f(A_q)

. Ако

-d\le f(A_p)

и

f(A_q)\le d

, всички разглеждани стойности са в интервала

[-d,d]

, така че има поне две хубави множества. Ако

f(A_p)\lt{}-d

и

f(A_q)\gt{}d

, разглеждаме двете дъги по цикъла от

A_p

до

A_q

. По (1) при преминаване от стойност под

-d

към стойност над

d

със стъпки с големина най-много

2d

непременно се среща стойност в

[-d,d]

. Това става и по двете дъги, следователно отново имаме поне две хубави множества. Остава случаят

f(A_p)\lt{}-d

и

f(A_q)\le d

; симетричният случай е аналогичен. Тогава

f(A_q)\ge0

, така че

A_q

е хубаво. Освен това от

f(A_p)+f(A_q)\lt{}0

и (2) следва, че има индекс

r\ne q

с

f(A_r)\gt{}0

. Понеже

f(A_r)\le f(A_q)\le d

, множеството

A_r

също е хубаво. Така във всички случаи всяка пермутация дава поне две хубави множества. Прилагаме това към всички

(k+\ell)!

пермутации на

S

. Получаваме поне

2(k+\ell)!

появи на хубави множества, броени с кратности. От друга страна, всяко фиксирано

k

-елементно множество

A

се появява точно в

(k+\ell)k!\ell!

пермутации: избираме началната позиция на блока, нареждаме елементите на

A

в него и нареждаме елементите на

S\setminus A

извън него. Следователно броят на хубавите множества е поне

\frac{2(k+\ell)!}{(k+\ell)k!\ell!}=\frac{2}{k+\ell}\binom{k+\ell}{k},

както се искаше.

Отвори задачатаMathNetISL 2008 C5Условие — източник

Задача C6

Пълен запис

Условие

За

n\ge2

нека

S_1,S_2,\ldots,S_{2^n}

са

2^n

подмножества на

A=\{1,2,3,\ldots,2^{n+1}\},

които удовлетворяват следното условие: не съществуват индекси

a\lt{}b

и елементи

x,y,z\in A

с

x\lt{}y\lt{}z

, такива че

y,z\in S_a

и

x,z\in S_b

. Докажете, че поне едно от множествата

S_1,S_2,\ldots,S_{2^n}

съдържа не повече от

4n

елемента.

Решение

Ще докажем, че средната мощност на множествата е най-много

4n

. За

k\in\{1,\ldots,n\}

ще казваме, че елемент

z\in A

е

k

-добър за множество

S_a

, ако

z\in S_a

и в

S_a

има два други елемента

x\lt{}y\lt{}z

, такива че

z-y\lt{}2^k\qquad\text{и}\qquad z-x\ge2^k.

Ще казваме, че

z

е добър за

S_a

, ако е

k

-добър за

S_a

за някое

k=1,\ldots,n

. Фиксираме

z\in A

и

k

. Твърдим, че

z

може да бъде

k

-добър за най-много едно от множествата. Наистина, нека

z

е

k

-добър едновременно за

S_a

и

S_b

, където

a\lt{}b

. Тогава съществуват

y_a\in S_a

и

x_b\in S_b

с

y_a\lt{}z

,

x_b\lt{}z

,

z-y_a\lt{}2^k,\qquad z-x_b\ge2^k.

Понеже

z\in S_a\cap S_b

, условието на задачата забранява да има елемент на

S_a

строго между

x_b

и

z

. Следователно

y_a\le x_b

, откъдето

z-y_a\ge z-x_b

, противоречие. Значи за всяко фиксирано

z

броят на множествата, за които

z

е добър, е най-много

n

. Сега фиксираме едно множество

S_a

и нека

u_1\lt{}u_2\lt{}\cdots\lt{}u_p

са всички негови елементи, които не са добри за

S_a

. Ще покажем, че за всяко

m\ge3

е изпълнено

u_m-u_1\gt{}2(u_{m-1}-u_1).\tag{1}

Ако не, то

2(u_m-u_{m-1})\le u_m-u_1.

Избираме

k

така, че

2^k\le u_m-u_1\lt{}2^{k+1}.

Това е възможно с

1\le k\le n

, защото

m\ge3

дава

u_m-u_1\ge2

, а

u_m-u_1\lt{}2^{n+1}

. От горните неравенства следва

u_m-u_{m-1}\lt{}2^k\qquad\text{и}\qquad u_m-u_1\ge2^k.

Така

z=u_m

,

y=u_{m-1}

и

x=u_1

показват, че

u_m

е

k

-добър за

S_a

, противоречие. Следователно (1) е вярно. От (1) редицата

u_2-u_1, u_3-u_1, \ldots, u_p-u_1

расте повече от два пъти на всяка следваща стъпка. Затова

u_p-u_1\gt{}2^{p-2}(u_2-u_1)\ge2^{p-2}.

От друга страна

u_p-u_1\lt{}2^{n+1}

, понеже всички елементи са в

\{1,2,\ldots,2^{n+1}\}

. Следователно

p\le n+2

. Значи всяко множество

S_a

има най-много

n+2

елемента, които не са добри за него. Оцветяваме всички срещания на елементи в множествата: ако дадено срещане е добро за съответното множество, го броим като червено, иначе като синьо. За всеки фиксиран

z\in A

червените му срещания са най-много

n

, а елементите

z

са

2^{n+1}

. Значи общият брой червени срещания е най-много

n\cdot2^{n+1}.

Сините срещания във всяко от

2^n

-те множества са най-много

n+2

, така че общият им брой е най-много

(n+2)2^n.

Следователно

\sum_{a=1}^{2^n}|S_a|\le n2^{n+1}+(n+2)2^n=(3n+2)2^n.

Затова средната мощност е най-много

3n+2

. Понеже

n\ge2

, имаме

3n+2\le4n

, и следователно поне едно от множествата има не повече от

4n

елемента.

Отвори задачатаMathNetISL 2008 C6Условие — източник

Задача G1

Пълен запис

Условие

Даден е трапец

ABCD

с успоредни основи

AB

и

CD

. Да предположим, че съществуват точки

E

върху правата

BC

извън отсечката

BC

и

F

във вътрешността на отсечката

AD

, такива че

\angle DAE=\angle CBF

. Нека

I

е пресечната точка на

CD

и

EF

, а

J

- пресечната точка на

AB

и

EF

. Нека

K

е средата на отсечката

EF

и да предположим, че

K

не лежи на правата

AB

. Докажете, че

I

лежи върху описаната окръжност на

ABK

тогава и само тогава, когато

K

лежи върху описаната окръжност на

CDJ

.

Решение

Ще разглеждаме разположението на точките в естествения ред по правата

EF

. От условието имаме

\angle EBF=180^\circ-\angle CBF=180^\circ-\angle EAF,

следователно четириъгълникът

AEBF

е вписан. Значи

AJ\cdot JB=FJ\cdot JE.\tag{1}

От (1) следва, че

I

лежи върху описаната окръжност на

ABK

тогава и само тогава, когато

IJ\cdot JK=FJ\cdot JE.

Понеже

IJ=IF+FJ,\qquad JE=FE-FJ,\qquad JK=\frac12FE-FJ,

получаваме, че

I

лежи върху описаната окръжност на

ABK

тогава и само тогава, когато

FJ=\frac{IF\cdot FE}{2IF+FE}.\tag{2}

Отново, понеже

AEBF

е вписан и

AB\parallel CD

, имаме

\angle FEC=\angle FAB=180^\circ-\angle CDF.

Следователно четириъгълникът

CDFE

също е вписан и

ID\cdot IC=IF\cdot IE.\tag{3}

От (3) следва, че

K

лежи върху описаната окръжност на

CDJ

тогава и само тогава, когато

IJ\cdot IK=IF\cdot IE.

Сега

IJ=IF+FJ,\qquad IK=IF+\frac12FE,\qquad IE=IF+FE,

и след заместване получаваме, че

K

лежи върху описаната окръжност на

CDJ

тогава и само тогава, когато отново е изпълнено (2). Двете условия са еквивалентни, което доказва твърдението.

Отвори задачатаMathNetISL 2008 G1Условие — източник

Задача G2

Пълен запис

Условие

Нека

ABCD

е изпъкнал четириъгълник и нека

P

и

Q

са точки във вътрешността на

ABCD

, такива че

PQDA

и

QPBC

са вписани четириъгълници. Да предположим, че съществува точка

E

върху отсечката

PQ

, за която

\angle PAE=\angle QDE\qquad\text{и}\qquad \angle PBE=\angle QCE.

Докажете, че четириъгълникът

ABCD

е вписан.

Решение

Нека

F

е точката върху правата

AD

, за която

EF\parallel PA

. Понеже

PQDA

е вписан, ако

F

лежи между

A

и

D

, то

\angle EFD=\angle PAD=180^\circ-\angle EQD;

точките

F

и

Q

са от различни страни на правата

DE

, следователно

EFDQ

е вписан. Ако пък

D

лежи между

A

и

F

, аналогично получаваме

\angle EFD=\angle EQD

, но тогава

F

и

Q

са от една и съща страна на

DE

, така че

EDFQ

е вписан. И в двата случая получаваме

\angle EFQ=\angle EDQ=\angle PAE,

откъдето

FQ\parallel AE

. Следователно триъгълникът

EFQ

е образ на

PAE

чрез преобразуване

f

, което изпраща

P

в

E

и

E

в

Q

и е или хомотетия, или транслация. Това преобразуване е еднозначно определено само от положението на точките

P,E,Q

. Нека сега

G

е точката върху правата

BC

, за която

EG\parallel PB

. Същото разсъждение, приложено към точките

B,C

вместо

A,D

, показва, че триъгълникът

EGQ

е образ на

PBE

чрез същото преобразуване

f

. Значи

f

изпраща четирите точки

A,P,B,E

съответно в

F,E,G,Q

. Ако

PE\ne QE

, то

f

е хомотетия с център

X

. Тогава правите

AF

,

PE

и

BG

, тоест правите

AD

,

PQ

и

BC

, се пресичат в

X

. Понеже

PQDA

и

QPBC

са вписани, имаме

XA\cdot XD=XP\cdot XQ=XB\cdot XC,

следователно и

ABCD

е вписан. Остава случаят

PE=QE

. Тогава

f

е транслация, откъдето

AD\parallel PQ\parallel BC

. Следователно

PQDA

и

QPBC

са равнобедрени трапеци. Значи и

ABCD

е равнобедрен трапец, а всеки равнобедрен трапец е вписан. Това завършва доказателството.

Отвори задачатаMathNetISL 2008 G2Условие — източник

Задача G3

Пълен запис

Условие

Нека

k

и

n

са цели числа с

0\le k\le n-2

. Дадено е множество

L

от

n

прави в равнината, така че никои две от тях не са успоредни и никои три не минават през една точка. Нека

I

е множеството от пресечните точки на правите от

L

. Нека

O

е точка в равнината, която не лежи на никоя права от

L

. Точка

X\in I

се оцветява в червено, ако отворената отсечка

OX

пресича най-много

k

прави от

L

. Докажете, че

I

съдържа поне

\frac12(k+1)(k+2)

червени точки.

Решение

Понеже

n\ge k+2

, множеството

I

съдържа поне

\frac12(k+1)(k+2)

пресечни точки. За точка

P\in I

ще наричаме ред на

P

броя на правите от

L

, които пресичат отворената отсечка

OP

. По определение

P

е червена точно когато редът й е най-много

k

. Винаги съществува точка от

I

с ред

0

. Наистина, правите от

L

разделят равнината на области и точката

O

лежи в една от тях; всеки връх на тази област е точка от

I

с ред

0

. Лема. Нека две точки

P,Q\in I

лежат върху една и съща права от

L

, и нека никоя друга права от

L

не пресича отворената отсечка

PQ

. Тогава редовете на

P

и

Q

се различават с най-много

1

. Доказателство. Нека редовете на

P

и

Q

са съответно

p

и

q

, като

p\ge q

. Разглеждаме триъгълника

OPQ

. Числото

p

е броят на правите от

L

, които пресичат вътрешността на страната

OP

. Никоя от тези прави не пресича вътрешността на

PQ

, а най-много една от тях може да минава през

Q

. Всички останали трябва да пресичат вътрешността на

OQ

, откъдето

q\ge p-1

. Лемата е доказана. Сега доказваме твърдението с индукция по

k

. При

k=0

то е ясно от съществуването на точка с ред

0

. Да предположим, че твърдението е вярно за

k-1

. Избираме точка

P\in I

с ред

0

и една от правите

\ell\in L

, които минават през

P

. Върху

\ell

има

n-1

пресечни точки, една от които е

P

. Сред останалите

n-2

точки вземаме

k

-те най-близки до

P

. По лемата редовете им са най-много

k

, следователно върху

\ell

има поне

k+1

червени точки. Премахваме правата

\ell

заедно с всички пресечни точки върху нея. По индукционното предположение в получената конфигурация има поне

\frac12k(k+1)

точки с ред най-много

k-1

. Когато върнем

\ell

, върху всяка отсечка от

O

до една от тези точки се появява най-много една нова пресечена права, така че редът на такава точка в първоначалната конфигурация е най-много

k

. Общо получаваме поне

k+1+\frac12k(k+1)=\frac12(k+1)(k+2)

точки с ред най-много

k

, т.е. поне толкова червени точки.

Отвори задачатаMathNetISL 2008 G3Условие — източник

Задача N1

Пълен запис

Условие

Нека

n

е положително цяло число, а

p

е просто число. Да се докаже, че ако целите числа

a,b,c

удовлетворяват

a^n+pb=b^n+pc=c^n+pa,

то

a=b=c

.

Решение

Ако две от числата

a,b,c

са равни, веднага следва, че и трите са равни. Затова допускаме, че са две по две различни. Изваждайки равенствата, получаваме

a^n-b^n=-p(b-c)

и двете циклични аналогични равенства. След умножение и деление на

(a-b)(b-c)(c-a)

следва

\frac{a^n-b^n}{a-b}\cdot\frac{b^n-c^n}{b-c}\cdot\frac{c^n-a^n}{c-a}=-p^3.\tag{1}

Ако

n

е нечетно, всеки от трите множителя вляво е положителен, а дясната страна е отрицателна. Следователно

n

е четно; пишем

n=2k

. Да предположим първо, че

p

е нечетно. Тогава от (1) всеки множител вляво е нечетен. Но

\frac{a^n-b^n}{a-b}=a^{n-1}+a^{n-2}b+\cdots+b^{n-1}

е сума от четен брой събираеми и е нечетна само ако

a

и

b

са с различна четност. Същото би важало за двойките

(b,c)

и

(c,a)

, което е невъзможно. Значи

p=2

. При

p=2

първоначалната система показва, че

a,b,c

са с една и съща четност. Разделяме (1) на

2^3

и получаваме произведение на шест цели числа:

\frac{a^k+b^k}{2}\cdot\frac{a^k-b^k}{a-b}\cdot\frac{b^k+c^k}{2}\cdot\frac{b^k-c^k}{b-c}\cdot\frac{c^k+a^k}{2}\cdot\frac{c^k-a^k}{c-a}=

-1.

Всеки от тези множители е равен на

1

или

-1

. В частност

a^k+b^k=\pm2

. Ако

k

е четно, това дава

a^k+b^k=2

, откъдето

|a|=|b|=1

, но тогава

a^k-b^k=0

, противоречие. Ако

k

е нечетно, числото

a^k+b^k

, равно на

\pm2

, се дели на

a+b

. Понеже

a

и

b

са с една и съща четност, получаваме

a+b=\pm2

. Аналогично

b+c=\pm2

и

c+a=\pm2

. Две от тези три равенства имат еднакъв знак, което налага две от числата

a,b,c

да са равни. Противоречието доказва твърдението.

Отвори задачатаMathNetISL 2008 N1Условие — източник

Задача N2

Пълен запис

Условие

Нека

a_1,a_2,\ldots,a_n

са различни положителни цели числа,

n\ge3

. Да се докаже, че съществуват различни индекси

i

и

j

, за които

a_i+a_j

не дели никое от числата

3a_1,3a_2,\ldots,3a_n

.

Решение

Без ограничение нека

0\lt{}a_1\lt{}a_2\lt{}\cdots\lt{}a_n

. Можем също да считаме, че най-големият общ делител на числата

a_1,a_2,\ldots,a_n

е

1

; иначе делим всички числа на този общ делител. Да допуснем, че твърдението е невярно. Тогава за всяко

i\lt{}n

съществува индекс

j

, за който

a_n+a_i

дели

3a_j

. Ако

a_n+a_i

не се дели на

3

, то

a_n+a_i

би деляло

a_j

, което е невъзможно, понеже

0\lt{}a_j\le a_n\lt{}a_n+a_i

. Значи

a_n+a_i

се дели на

3

за

i=1,2,\ldots,n-1

. Следователно

a_1,a_2,\ldots,a_{n-1}

са сравними с

-a_n

по модул

3

. Числото

a_n

не се дели на

3

, защото иначе всички

a_i

биха се делели на

3

, против избора на общ делител

1

. Значи

a_n\equiv r\pmod3

за

r\in\{1,2\}

, а

a_i\equiv3-r\pmod3

за всички

i\lt{}n

. Разглеждаме сума

a_{n-1}+a_i

с

1\le i\le n-2

. Тя не се дели на

3

, понеже

a_{n-1}+a_i\equiv2a_i\not\equiv0\pmod3

. По допускането има

j

, за което

a_{n-1}+a_i

дели

3a_j

, следователно дели

a_j

. Тогава

a_{n-1}+a_i\le a_j

, откъдето

a_{n-1}\lt{}a_j\le a_n

, тоест

j=n

. Така

a_n

се дели на всички суми

a_{n-1}+a_i

за

1\le i\le n-2

, и в частност

a_{n-1}+a_i\le a_n\quad\text{за }1\le i\le n-2.\tag{1}

Нека

j

е такъв, че

a_n+a_{n-1}

дели

3a_j

. Ако

j\le n-2

, то

a_n+a_{n-1}\le3a_j\lt{}a_j+2a_{n-1},

следователно

a_n\lt{}a_{n-1}+a_j

, което противоречи на (1). Значи

j=n-1

или

j=n

. Ако

j=n-1

, имаме

3a_{n-1}=q(a_n+a_{n-1})

за някое цяло

q

. От

0\lt{}a_{n-1}\lt{}a_n

лесно следва, че единствената възможност е

q=1

, т.е.

a_n=2a_{n-1}

. Ако

j=n

, аналогично от

3a_n=q(a_n+a_{n-1})

единствената възможност е

q=2

, и пак

a_n=2a_{n-1}

. Тогава сумата

a_{n-1}+a_1

е строго между

a_n/2

и

a_n

. Понеже

a_{n-1}

и

a_1

са различни, от вече доказаното тя трябва да дели

a_n

. Това е невъзможно за делител на

a_n

, който е строго между

a_n/2

и

a_n

. Полученото противоречие завършва доказателството.

Отвори задачатаMathNetISL 2008 N2Условие — източник

Задача N3

Пълен запис

Условие

Нека

a_0,a_1,a_2,\ldots

е редица от положителни цели числа, такава че най-големият общ делител на всеки два съседни члена е по-голям от предходния член, тоест

\gcd(a_i,a_{i+1})\gt{}a_{i-1}\quad\text{за всяко }i\ge1.

Докажете, че

a_n\ge2^n

за всяко

n\ge0

.

Решение

Понеже

a_i\ge\gcd(a_i,a_{i+1})\gt{}a_{i-1}

за всяко

i\ge1

, редицата е строго растяща. В частност

a_0\ge1

и

a_1\ge2

. Освен това

a_i

и

a_{i+1}

са кратни на

\gcd(a_i,a_{i+1})

, затова

a_{i+1}-a_i\ge\gcd(a_i,a_{i+1})\gt{}a_{i-1}

и следователно

a_{i+1}\ge a_i+a_{i-1}+1.\tag{1}

Оттук

a_2\ge4

и

a_3\ge7

. Ако

a_3=7

, то в предходните оценки трябва да има равенство, откъдето

a_1=2

и

a_2=4

; но тогава

\gcd(a_2,a_3)=\gcd(4,7)=1

не е по-голямо от

a_1

. Следователно

a_3\ge8

, така че твърдението е вярно за

n=0,1,2,3

. Ще довършим с индукция. Нека

n\ge3

и да предположим, че

a_i\ge2^i

за

i=0,1,\ldots,n

. Трябва да докажем, че

a_{n+1}\ge2^{n+1}

. Полагаме

d=\gcd(a_n,a_{n+1}).

Имаме

d\gt{}a_{n-1}

. Ако

a_{n+1}\ge4d

, то

a_{n+1}\gt{}4a_{n-1}\ge4\cdot2^{n-1}=2^{n+1}.

Ако

a_n\ge3d

, то от

a_{n+1}\ge a_n+d

следва

a_{n+1}\ge4d\gt{}4a_{n-1}\ge2^{n+1}.

Ако пък

a_n=d

, то

a_{n+1}\ge a_n+d=2a_n\ge2^{n+1}.

Значи единственият случай, който още не е покрит, е

a_n=2d,\qquad a_{n+1}=3d.\tag{2}

Нека сега

d'=\gcd(a_{n-1},a_n).

Тогава

d'\gt{}a_{n-2}

. Записваме

a_n=md'

с цяло

m

. Понеже

d'\le a_{n-1}\lt{}d

и

a_n=2d

, получаваме

m\ge3

. Освен това

a_{n-1}\lt{}d=\frac12md',\qquad a_{n+1}=3d=\frac32md'.

Ако

m\ge6

, то

a_{n+1}=\frac32md'\ge9d'\gt{}9a_{n-2}\ge9\cdot2^{n-2}\gt{}2^{n+1}.

Ако

3\le m\le4

, тогава

a_{n-1}\lt{}2d'

, а понеже

d'

дели

a_{n-1}

, имаме

a_{n-1}=d'

. Следователно

a_{n+1}=\frac32m a_{n-1}\ge

\frac92a_{n-1}\ge\frac92\cdot2^{n-1}\gt{}2^{n+1}.

Остава само

m=5

. Тогава

a_n=5d',\qquad a_{n+1}=\frac{15}{2}d',\qquad a_{n-1}\lt{}\frac52d'.

Последното означава, че

a_{n-1}

е равно на

d'

или на

2d'

, така че

a_{n-1}

дели

2d'

. Повтаряме същия аргумент още веднъж. Нека

d''=\gcd(a_{n-2},a_{n-1}).

Тогава

d''\gt{}a_{n-3}

. Понеже

d''

дели

a_{n-1}

, а

a_{n-1}

дели

2d'

, можем да запишем

2d'=m'd''

с цяло

m'

. От

d''\le a_{n-2}\lt{}d'

следва

m'\ge3

. Освен това

a_{n-2}\lt{}d'=\frac12m'd'',

\qquad a_{n+1}=\frac{15}{2}d'=\frac{15}{4}m'd''.

Ако

m'\ge5

, то

a_{n+1}=\frac{15}{4}m'd''\ge\frac{75}{4}d''\gt{}

\frac{75}{4}a_{n-3}\ge\frac{75}{4}\cdot2^{n-3}\gt{}2^{n+1}.

Ако

3\le m'\le4

, тогава

a_{n-2}\lt{}2d''

, откъдето

a_{n-2}=d''

, и значи

a_{n+1}=\frac{15}{4}m'a_{n-2}\ge

\frac{45}{4}a_{n-2}\ge\frac{45}{4}\cdot2^{n-2}\gt{}2^{n+1}.

Така във всички случаи получаваме

a_{n+1}\ge2^{n+1}

. Индукцията е завършена.

Отвори задачатаMathNetISL 2008 N3Условие — източник

Задача N4

Пълен запис

Условие

Нека

n

е положително цяло число. Докажете, че числата

\binom{2^n-1}{0},\quad \binom{2^n-1}{1},\quad \binom{2^n-1}{2},

\quad\ldots,\quad \binom{2^n-1}{2^{n-1}-1}

са конгруентни по модул

2^n

на числата

1,3,5,\ldots,2^n-1

в някакъв ред.

Решение

Всички разглеждани биномиални коефициенти са нечетни. Следователно е достатъчно да докажем, че остатъците им по модул

2^n

са два по два различни. Първо ще използваме две сравнения. За всяко допустимо

k

имаме

\binom{2^n-1}{2k}+\binom{2^n-1}{2k+1}\equiv0\pmod{2^n}\tag{1}

и

\binom{2^n-1}{2k}\equiv(-1)^k\binom{2^{n-1}-1}{k}\pmod{2^n}.\tag{2}

Първото следва от тъждеството

\binom{2^n-1}{2k}+\binom{2^n-1}{2k+1}=

\binom{2^n}{2k+1}=\frac{2^n}{2k+1}\binom{2^n-1}{2k},

чиято дясна страна се дели на

2^n

, понеже

2k+1

е нечетно. За второто записваме

\begin{aligned} \binom{2^n-1}{2k} &=\prod_{j=1}^{2k}\frac{2^n-j}{j}\\ &=\prod_{i=1}^k\frac{2^n-(2i-1)}{2i-1}\cdot\prod_{i=1}^k\frac{2^{n-1}-i}{i}\\ &\equiv(-1)^k\binom{2^{n-1}-1}{k}\pmod{2^n}, \end{aligned}

защото всички знаменатели

2i-1

са обратими по модул

2^n

. Сега доказваме твърдението с индукция по

n

. Случаят

n=1

е очевиден. Нека твърдението е вярно за

n-1

и да преминем към

n

. Полагаме

a_k=\binom{2^{n-1}-1}{k},\qquad b_m=\binom{2^n-1}{m}.

По индукционното предположение числата

a_k

за

0\le k\lt{}2^{n-2}

са два по два различни по модул

2^{n-1}

. От (1) и (2) получаваме

b_{2k}\equiv(-1)^k a_k\equiv-b_{2k+1}\pmod{2^n}.\tag{3}

Освен това, като приложим (1) за

n-1

, имаме

a_{2i+1}\equiv-a_{2i}\pmod{2^{n-1}}.\tag{4}

Затова ако за някои

j,k\lt{}2^{n-2}

е изпълнено

a_k\equiv-a_j\pmod{2^{n-1}}

, то множеството

\{j,k\}

е от вида

\{2i,2i+1\}

. Наистина, по индукционното предположение всеки нечетен остатък има единствен представител сред числата

a_k

, а (4) вече посочва неговия противоположен остатък. Разделяме индексите

0,1,\ldots,2^{n-1}-1

на две множества:

M=\{m\mid m\equiv0\text{ или }3\pmod4\},

\qquad L=\{m\mid m\equiv1\text{ или }2\pmod4\}.

От (3) следва, че за всяко

m\in M

е вярно

b_m\equiv a_{\lfloor m/2\rfloor}\pmod{2^n}.\tag{5}

Следователно числата

b_m

с

m\in M

са два по два различни по модул

2^n

. Всеки индекс

l\in L

е сдвоен с единствен индекс

m\in M

така, че

\{l,m\}=\{2k,2k+1\}

за някое

k

; по (3) съответните остатъци са противоположни. Оттук и числата

b_l

с

l\in L

са два по два различни. Остава да изключим съвпадение между двете групи. Да допуснем, че

b_m\equiv b_l\pmod{2^n}

за някои

m\in M

и

l\in L

. Нека

m'\in M

е индексът, сдвоен с

l

, тоест

\{m',l\}=\{2k,2k+1\}

за някое

k

. Тогава по (3)

b_{m'}\equiv-b_l\equiv-b_m\pmod{2^n}.

Сега от (5) получаваме

a_{\lfloor m'/2\rfloor}\equiv-a_{\lfloor m/2\rfloor}\pmod{2^n},

а значи и по модул

2^{n-1}

. Според предходното наблюдение тези два индекса са

2i

и

2i+1

в някакъв ред. Следователно

a_{2i+1}\equiv-a_{2i}\pmod{2^n}.

Но това би означавало

\binom{2^{n-1}-1}{2i}+\binom{2^{n-1}-1}{2i+1}=\binom{2^{n-1}}{2i+1}\equiv

0\pmod{2^n}.

Последното е невъзможно, защото

\binom{2^{n-1}}{2i+1}=\frac{2^{n-1}}{2i+1}\binom{2^{n-1}-1}{2i}

се дели точно на

2^{n-1}

: знаменателят

2i+1

е нечетен, а биномиалният коефициент вдясно също е нечетен. Полученото противоречие показва, че всички

b_m

са различни по модул

2^n

. Индукцията е завършена, а с това и доказателството.

Отвори задачатаMathNetISL 2008 N4Условие — източник

Задача N5

Пълен запис

Условие

За всяко

n\in\mathbb N

нека

d(n)

означава броя на положителните делители на

n

. Да се намерят всички функции

f:\mathbb N\to\mathbb N

, за които: (i)

d(f(x))=x

за всяко

x\in\mathbb N

; (ii)

f(xy)

дели

(x-1)y^{xy-1}f(x)

за всички

x,y\in\mathbb N

.

Решение

Единственото решение е следното:

f(1)=1,

а ако

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

е разлагането на

n\gt{}1

на прости множители, то

f(n)=p_1^{p_1^{a_1}-1}p_2^{p_2^{a_2}-1}\cdots p_k^{p_k^{a_k}-1}.\tag{1}

Първо проверяваме, че тази функция работи. Броят на делителите на

f(n)

е

(p_1^{a_1})(p_2^{a_2})\cdots(p_k^{a_k})=n,

така че (i) е изпълнено. За (ii) нека

p

е прост делител на

xy

. Ако

p\mid x

и

p\nmid y

, нужната степен на

p

във

f(xy)

вече се съдържа във

f(x)

. Ако

p\mid y

, то, като означим с

v_p(m)

степента на

p

в

m

, степента на

p

в

y^{xy-1}

е поне

p^{v_p(xy)}-1

, понеже

xy\ge p^{v_p(xy)}

. Следователно всички прости степени във

f(xy)

делят дясната страна на (ii). Нека сега

f

е произволно решение. От (i) за

x=1

получаваме

d(f(1))=1

, следователно

f(1)=1

. Освен това

f(m)=f(n)

влече

m=d(f(m))=d(f(n))=n

; тоест

f

е инективна. Ще използваме формулата

d(q_1^{b_1}\cdots q_r^{b_r})=(b_1+1)\cdots(b_r+1).\tag{2}

Нека

p

е просто число. Понеже

d(f(p))=p

, от (2) следва, че

f(p)=q^{p-1}

за някакво просто число

q

. Ще докажем, че всъщност

f(p)=p^{p-1}\tag{3}

за всяко просто

p

. Първо нека

p

е нечетно и

f(p)=q^{p-1}

. Прилагаме (ii) за

(x,y)=(2,p)

и за

(x,y)=(p,2)

. Получаваме, че

f(2p)

дели едновременно

p^{2p-1}f(2)

и

(p-1)2^{2p-1}q^{p-1}.

Ако

q\ne p

, то

p

не дели второто число, така че най-големият общ делител на тези две числа дели простото число

f(2)

. Понеже

f(2p)\gt{}1

, следва

f(2p)=f(2)

, което противоречи на инективността. Значи

q=p

и (3) е доказано за всички нечетни прости

p

. За

p=2

използваме вече доказаното

f(3)=3^2

. От (ii) за

(x,y)=(2,3)

и

(x,y)=(3,2)

следва, че

f(6)

дели едновременно

3^5f(2)

и

2^6f(3)=2^6\cdot3^2.

Ако простото число

f(2)

беше нечетно, щяхме да получим

f(6)\mid9

, а тогава

d(f(6))

би било

1

,

2

или

3

, не

6

. Противоречие. Следователно

f(2)=2

, така че (3) е доказано и за

p=2

. Следваща стъпка: всеки прост делител на

f(n)

дели

n

. Нека

n\gt{}1

и нека

p

е най-малкият прост делител на

n

. В (ii) вземаме

x=p

и

y=n/p

. Тогава

f(n)\mid(p-1)y^{n-1}f(p)=(p-1)y^{n-1}p^{p-1}.

Пишем

f(n)=\ell P

, където

\ell

е взаимно просто с

n

, а всички прости делители на

P

делят

n

. Тогава

\ell

дели

(p-1)y^{n-1}p^{p-1}

и е взаимно просто с

y^{n-1}p^{p-1}

, следователно

\ell\mid p-1

. Значи

d(\ell)\le\ell\lt{}p.

От друга страна по (i)

n=d(f(n))=d(\ell)d(P),

защото

\ell

и

P

са взаимно прости. Така

d(\ell)

е делител на

n

, по-малък от най-малкия прост делител

p

на

n

, следователно

d(\ell)=1

и

\ell=1

. Твърдението е доказано. За степен на просто число вече получаваме формулата веднага. Ако

a\ge1

, то единственият прост делител на

f(p^a)

е

p

, така че

f(p^a)=p^b

. От (i) следва

p^a=d(f(p^a))=b+1,

тоест

f(p^a)=p^{p^a-1}.\tag{4}

Накрая нека

n=p_1^{a_1}\cdots p_k^{a_k}

. От доказаното за простите делители имаме

f(n)=p_1^{b_1}\cdots p_k^{b_k}.

За фиксирано

i

прилагаме (ii) с

x=p_i^{a_i}

и

y=n/x

. Тогава

f(n)

дели

(p_i^{a_i}-1)y^{n-1}f(p_i^{a_i}).

Факторът

p_i^{b_i}

е взаимно прост с

(p_i^{a_i}-1)y^{n-1}

, затова от (4) получаваме

b_i\le p_i^{a_i}-1.

Сега по (i)

p_1^{a_1}\cdots p_k^{a_k}=n=d(f(n))=(b_1+1)\cdots(b_k+1)\le

p_1^{a_1}\cdots p_k^{a_k}.

Всички неравенства са равенства, следователно

b_i=p_i^{a_i}-1

за всяко

i

. Това е точно формулата (1), а доказателството е завършено.

Отвори задачатаMathNetISL 2008 N5Условие — източник

2008

11-12

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие