IMO Shortlisted Problems

Задача A2

Пълен запис

Условие

Разгледайте функциите

f:\mathbb N\to\mathbb N

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

f(m+n)\ge f(m)+f(f(n))-1

за всички

m,n\in\mathbb N

. Намерете всички възможни стойности на

f(2007)

. Тук

\mathbb N

означава множеството на положителните цели числа.

Решение

Отговорът е всяко цяло число от

1

до

2008

. Нека

f:\mathbb N\to\mathbb N

удовлетворява условието. Ако

m\gt{}n

, тогава

f(m)=f(n+(m-n))\ge

f(n)+f(f(m-n))-1\ge f(n),

понеже

f

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

f

е ненамаляваща. Функцията

f\equiv1

очевидно работи. Нека занапред

f

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

1

и нека

a

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

f(a)\gt{}1

. Тогава

f(b)\ge f(a)\gt{}1

за всяко

b\ge a

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

f(n)\gt{}n

за някое

n

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

f(f(n))=f((f(n)-n)+n)\ge

f(f(n)-n)+f(f(n))-1,

така че

f(f(n)-n)\le1

. Значи

f(n)-n\lt{}a

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

f(n)-n

има най-голяма стойност; нека тя е

c

, и нека

f(k)-k=c\ge1

. Тогава, използвайки максималността на

c

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

2k+c\ge f(2k)=f(k+k)\ge f(k)+f(f(k))-1\ge

f(k)+f(k)-1=2k+(2c-1).

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

c\le1

, а оттук

f(n)\le n+1

за всяко

n

. В частност

f(2007)\le2008

. Остава да покажем, че всички стойности от

1

до

2008

се реализират. За

j=1,2,\ldots,2007

дефинираме

f_j(n)=\max\{1,n+j-2007\}.

Тогава

f_j(2007)=j

. Функцията

f_j

е ненамаляваща и

f_j(n)\le n

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

f_j(f_j(n))\le f_j(n)\le n

. Ако

f_j(m)=1

, то

f_j(m+n)\ge f_j(n)\ge

f_j(f_j(n))=f_j(m)+f_j(f_j(n))-1.

Ако

f_j(m)\gt{}1

, тогава

f_j(m)+f_j(f_j(n))-1\le

(m+j-2007)+n=f_j(m+n).

Значи тези функции удовлетворяват условието. За стойността

2008

използваме функцията

f_{2008}(n)=\begin{cases}n, & 2007\nmid n,\\ n+1, & 2007\mid n.\end{cases}

Тогава

f_{2008}(2007)=2008

, а за всяко

n

имаме

n\le f_{2008}(n)\le n+1

и също

f_{2008}(f_{2008}(n))\le n+1

. Ако

2007\mid m+n

, то

f_{2008}(m+n)=m+n+1=(m+1)+(n+1)-1\ge

f_{2008}(m)+f_{2008}(f_{2008}(n))-1.

Ако

2007\nmid m+n

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

m,n

не се дели на

2007

. В първия случай

f_{2008}(m)=m

, а във втория

f_{2008}(f_{2008}(n))=f_{2008}(n)=n

. И в двата случая

f_{2008}(m)+f_{2008}(f_{2008}(n))-1\le

m+n=f_{2008}(m+n).

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

1,2,\ldots,2008

.

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

Задача A3

Пълен запис

Условие

Нека

n

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

x

и

y

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

x^n+y^n=1

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

\left(\sum_{k=1}^n\frac{1+x^{2k}}{1+x^{4k}}\right)\left(\sum_{k=1}^n\frac{1+y^{2k}}{1+y^{4k}}\right)\lt{}

\frac1{(1-x)(1-y)}.

Решение

За всяко реално

t\in(0,1)

имаме

\frac{1+t^2}{1+t^4}=\frac1t-\frac{(1-t)(1-t^3)}{t(1+t^4)}\lt{}\frac1t.

Замествайки

t=x^k

и

t=y^k

, получаваме

0\lt{}\sum_{k=1}^n\frac{1+x^{2k}}{1+x^{4k}}\lt{}

\sum_{k=1}^n\frac1{x^k}=\frac{1-x^n}{x^n(1-x)}

и

0\lt{}\sum_{k=1}^n\frac{1+y^{2k}}{1+y^{4k}}\lt{}

\sum_{k=1}^n\frac1{y^k}=\frac{1-y^n}{y^n(1-y)}.

Понеже

1-y^n=x^n

и

1-x^n=y^n

, следва

\frac{1-x^n}{x^n(1-x)}=\frac{y^n}{x^n(1-x)},

\qquad \frac{1-y^n}{y^n(1-y)}=\frac{x^n}{y^n(1-y)}.

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

\left(\sum_{k=1}^n\frac{1+x^{2k}}{1+x^{4k}}\right)\left(\sum_{k=1}^n\frac{1+y^{2k}}{1+y^{4k}}\right)\lt{}

\frac{y^n}{x^n(1-x)}\cdot\frac{x^n}{y^n(1-y)}=\frac1{(1-x)(1-y)},

както трябваше.

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

Задача A4

Пълен запис

Условие

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

f:\mathbb R^+\to\mathbb R^+

, такива че

f(x+f(y))=f(x+y)+f(y)

за всички

x,y\in\mathbb R^+

. Тук

\mathbb R^+

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

Решение

Отговорът е

f(x)=2x.

Първо ще докажем, че

f(y)\gt{}y

за всяко

y\in\mathbb R^+

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

f(x+f(y))=f(x+y)+f(y)\gt{}f(x+y),

така че

f(y)\ne y

. Ако

f(y)\lt{}y

за някое

y

, то при

x=y-f(y)\gt{}0

получаваме

f(y)=f((y-f(y))+f(y))=

f((y-f(y))+y)+f(y)\gt{}

f(y),

противоречие. Значи

f(y)\gt{}y

за всяко

y\gt{}0

. Дефинираме

g(x)=f(x)-x

. Тогава

g(x)\gt{}0

и

f(x)=x+g(x)

. Ако положим

t=x+y

, уравнението се превръща в

g(t+g(y))=g(t)+y\qquad\text{за всички }t\gt{}y\gt{}0.\tag{1}

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

g

е инективна. Ако

g(y_1)=g(y_2)

, то за всяко

t\gt{}\max\{y_1,y_2\}

от (1) имаме

g(t)+y_1=g(t+g(y_1))=g(t+g(y_2))=g(t)+y_2,

откъдето

y_1=y_2

. Нека

u,v\gt{}0

и

t\gt{}u+v

. Прилагайки (1) три пъти, получаваме

g(t+g(u)+g(v))=g(t+g(u))+v=

g(t)+u+v=g(t+g(u+v)).

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

g(u)+g(v)=g(u+v).\tag{2}

Понеже

g(v)\gt{}0

, равенството (2) показва и че

g

е строго растяща. Комбинирайки (1) и (2), получаваме

g(t)+y=g(t+g(y))=g(t)+g(g(y)),

тоест

g(g(y))=y.

Ако за някое

x

имаме

x\gt{}g(x)

, то от растежа на

g

следва

g(x)\gt{}g(g(x))=x

, невъзможно. Ако

x\lt{}g(x)

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

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

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

g(x)=x

за всяко

x\gt{}0

, а значи

f(x)=2x

. Проверката на

f(x)=2x

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

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

Задача A5

Пълен запис

Условие

Нека

c\gt{}2

и нека

a(1),a(2),\ldots

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

a(m+n)\le2a(m)+2a(n)\qquad\text{за всички }m,

n\ge1,\tag{1}

и

a(2^k)\le\frac1{(k+1)^c}\qquad\text{за всички }k\ge0.\tag{2}

Докажете, че редицата

a(n)

е ограничена.

Решение

За удобство дефинираме

a(0)=0

; тогава (1) остава вярно и за неотрицателни индекси. Лема. За произволни неотрицателни цели числа

n_1,\ldots,n_k

имаме

a\left(\sum_{i=1}^k n_i\right)\le\sum_{i=1}^k2^i a(n_i)\tag{3}

и

a\left(\sum_{i=1}^k n_i\right)\le2k\sum_{i=1}^k a(n_i).\tag{4}

Доказателство. Неравенството (3) се доказва с индукция по

k

. Базата

k=1

е ясна, а индукционната стъпка следва от

a\left(\sum_{i=1}^{k+1}n_i\right)\le2a(n_1)+2a\left(\sum_{i=1}^k n_{i+1}\right)\le

2a(n_1)+2\sum_{i=1}^k2^i a(n_{i+1})=

\sum_{i=1}^{k+1}2^i a(n_i).

За (4) първо по очевидна индукция по

d

получаваме

a\left(\sum_{i=1}^{2^d}n_i\right)\le2^d\sum_{i=1}^{2^d}a(n_i).

Ако

2^{d-1}\lt{}k\le2^d

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

a\left(\sum_{i=1}^k n_i\right)=a\left(\sum_{i=1}^k n_i+\sum_{i=k+1}^{2^d}0\right)\le

2^d\sum_{i=1}^k a(n_i)\le2k\sum_{i=1}^k a(n_i).

Лемата е доказана. Нека

0=M_0\lt{}M_1\lt{}M_2\lt{}\cdots

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

n

и записваме двоичното му представяне

n=\sum_{i=0}^d\varepsilon_i2^i,\qquad \varepsilon_i\in\{0,1\}.

Полагаме

\varepsilon_i=0

за

i\gt{}d

и избираме

f

така, че

M_f\gt{}d

. От (3), приложено към групите от индекси

M_{k-1}\le i\lt{}M_k

, следва

a(n)\le\sum_{k=1}^f2^k a\left(\sum_{M_{k-1}\le i\lt{}M_k}\varepsilon_i2^i\right).

В интервала

[M_{k-1},M_k)

има по-малко от

M_k-M_{k-1}+1

цели числа. Затова от (4) и (2) получаваме

\begin{aligned}a(n)&\le\sum_{k=1}^f2^k\cdot2(M_k-M_{k-1}+1)\sum_{M_{k-1}\le i\lt{}M_k}\varepsilon_i a(2^i)\\ &\le\sum_{k=1}^f2^k\cdot2(M_k-M_{k-1}+1)^2\max_{M_{k-1}\le i\lt{}M_k}a(2^i)\\ &\le\sum_{k=1}^f2^{k+1}(M_k+1)^2\cdot\frac1{(M_{k-1}+1)^c}\\ &=\sum_{k=1}^f\left(\frac{M_k+1}{M_{k-1}+1}\right)^2\frac{2^{k+1}}{(M_{k-1}+1)^{c-2}}.\end{aligned}

Избираме

M_k=4^{k/(c-2)}-1.

Тогава

a(n)\le

\sum_{k=1}^f4^{2/(c-2)}\frac{2^{k+1}}{\left(4^{(k-1)/(c-2)}\right)^{c-2}}=

8\cdot4^{2/(c-2)}\sum_{k=1}^f\left(\frac12\right)^k\lt{}

8\cdot4^{2/(c-2)}.

Оценката не зависи от

n

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

a(n)

е ограничена.

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

Задача A6

Пълен запис

Условие

Нека

a_1,a_2,\ldots,a_{100}

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

a_1^2+a_2^2+\cdots+a_{100}^2=1.

Докажете, че

a_1^2a_2+a_2^2a_3+\cdots+a_{100}^2a_1\lt{}\frac{12}{25}.

Решение

Нека

S=\sum_{k=1}^{100}a_k^2a_{k+1},

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

100

, тоест

a_{101}=a_1

и

a_{102}=a_2

. Имаме

3S=\sum_{k=1}^{100}a_{k+1}(a_k^2+2a_{k+1}a_{k+2}).

По неравенството на Коши-Шварц, а след това по AM-GM за

a_{k+1}^2

и

a_{k+2}^2

, получаваме

\begin{aligned} (3S)^2&\le\left(\sum_{k=1}^{100}a_{k+1}^2\right)\left(\sum_{k=1}^{100}(a_k^2+2a_{k+1}a_{k+2})^2\right)\\ &=\sum_{k=1}^{100}\left(a_k^4+4a_k^2a_{k+1}a_{k+2}+4a_{k+1}^2a_{k+2}^2\right)\\ &\le\sum_{k=1}^{100}\left(a_k^4+2a_k^2(a_{k+1}^2+a_{k+2}^2)+4a_{k+1}^2a_{k+2}^2\right)\\ &=\sum_{k=1}^{100}\left(a_k^4+6a_k^2a_{k+1}^2+2a_k^2a_{k+2}^2\right). \end{aligned}

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

\sum_{k=1}^{100}\left(a_k^4+2a_k^2a_{k+1}^2+2a_k^2a_{k+2}^2\right)\le

\left(\sum_{k=1}^{100}a_k^2\right)^2=1,

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

X=\sum_{i=1}^{50}a_{2i-1}^2\quad\text{и}\quad Y=\sum_{j=1}^{50}a_{2j}^2,

то

\sum_{k=1}^{100}a_k^2a_{k+1}^2\le XY,

понеже всеки съседен чифт има един нечетен и един четен индекс. Следователно

\begin{aligned} (3S)^2&\le1+4XY\le1+(X+Y)^2=2. \end{aligned}

Така

S\le\frac{\sqrt2}{3}\lt{}\frac{12}{25},

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

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

Задача C1

Пълен запис

Условие

Нека

n\gt{}1

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

a_1,a_2,\ldots,a_{n^2+n}

, удовлетворяващи следните условия: (a)

a_i\in\{0,1\}

за всяко

1\le i\le n^2+n

; (b)

a_{i+1}+a_{i+2}+\cdots+a_{i+n}\lt{}a_{i+n+1}+a_{i+n+2}+\cdots+a_{i+2n}

за всяко

0\le i\le n^2-n

.

Решение

Отговорът е единствената редица, която за

1\le u\le n

и

0\le v\le n

се задава с

a_{u+vn}=\begin{cases}0, & u+v\le n,\\ 1, & u+v\ge n+1.\end{cases}

Ще докажем това. За

0\le k\le \ell\le n^2+n

означаваме

S(k,\ell]=a_{k+1}+a_{k+2}+\cdots+a_\ell,

като при

k=\ell

сумата е

0

. Условието (b) се записва като

S(i,i+n]\lt{}S(i+n,i+2n]\qquad(0\le i\le n^2-n).

От тези неравенства за

i=0,n,2n,\ldots,n^2-n

получаваме

0\le S(0,n]\lt{}S(n,2n]\lt{}\cdots\lt{}S(n^2,n^2+n]\le n.

Това са

n+1

различни цели числа между

0

и

n

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

S(vn,(v+1)n]=v\qquad(0\le v\le n).

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

n

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

u

с

0\le u\le n

и разглеждаме веригата

S(u,u+n]\lt{}S(u+n,u+2n]\lt{}

\cdots\lt{}S(u+(n-1)n,u+n^2].

В нея има

n

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

\{0,1,\ldots,n\}

. Нека

m

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

S(0,n^2+n]=0+1+\cdots+n.

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

S(0,n^2+n]=

S(0,u]+\sum_{v=0}^{n-1}S(u+vn,u+(v+1)n]

+S(u+n^2,n^2+n].

Понеже първите

u

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

n-u

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

S(0,u]=0

и

S(u+n^2,n^2+n]=n-u

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

0+1+\cdots+n=(0+1+\cdots+n-m)+(n-u),

тоест

m=n-u

. Значи за

0\le u\le n

и

0\le v\le n-1

е вярно

S(u+vn,u+(v+1)n]=\begin{cases}v, & v\le n-u-1,\\ v+1, & v\ge n-u.\end{cases}

Сега възстановяваме редицата. За

1\le u\le n

и

1\le t\le n

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

\begin{aligned}a_{u+tn}-a_{u+(t-1)n}&=S(u+(t-1)n,u+tn]\\ &\quad-S((u-1)+(t-1)n,(u-1)+tn]\\ &=\begin{cases}0, & t\le n-u,\\ 1, & t=n-u+1,\\ 0, & t\ge n-u+2.\end{cases} \end{aligned}

Тъй като

a_u=0

, при сумиране по

t

получаваме точно горната формула. Тя веднага показва, че всички членове са

0

или

1

. Остава да проверим (b). За фиксирано

u

последните стойности са строго растящи при нарастване на

v

. Всяко неравенство от (b) е едно от неравенствата в такава верига, според остатъка на

i

при деление на

n

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

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

Задача C3

Пълен запис

Условие

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

n

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

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

могат да бъдат оцветени в червено и синьо така, че в

S\times S\times S

да има точно

2007

наредени тройки

(x,y,z)

със следните две свойства: (i)

x,y,z

са в един и същи цвят; (ii)

x+y+z

се дели на

n

.

Решение

Отговорът е

n=69\quad\text{или}\quad n=84.

Нека

R

и

B

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

|R|=r

и

|B|=b

. Ще преброим наредените тройки

(x,y,z)

, за които

n\mid x+y+z

. За всяка двойка

(x,y)\in S\times S

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

z\in S

, за което

n\mid x+y+z

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

n^2

. Да преброим двуцветните делящи се тройки. Ако

(x,y,z)

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

(x,y),(y,z),(z,x)

точно една принадлежи на

R\times B

. Обратно, за всяка двойка

(x,y)\in R\times B

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

z

с

n\mid x+y+z

трите тройки

(x,y,z),(y,z,x),(z,x,y)

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

x\ne y

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

3rb

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

n^2-3rb=(r+b)^2-3rb=r^2-rb+b^2.

Трябва да решим

r^2-rb+b^2=2007.

От

9\mid2007

и

r^2-rb+b^2=(r+b)^2-3rb

следва първо

3\mid r+b

, а после

3\mid rb

; оттук

3\mid r

и

3\mid b

. Полагаме

r=3s

,

b=3c

и без ограничение приемаме

s\ge c

. Тогава

s^2-sc+c^2=223.

Освен това

892=4(s^2-sc+c^2)=(2c-s)^2+3s^2\ge3s^2,

а от

s\ge c

имаме и

s^2\ge s^2-sc+c^2=223

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

15\le s\le17

. Ако

s=15

, то

c(15-c)=15^2-223=2

, което е невъзможно. Ако

s=16

, то

c(16-c)=33

, отново невъзможно. При

s=17

получаваме

c(17-c)=66

, откъдето

c=6

или

c=11

. Така, с евентуална размяна на цветовете,

(r,b)=(51,18)\quad\text{или}\quad(r,b)=(51,33),

и съответно

n=69

или

n=84

. И двете стойности на

n

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

r

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

b

в синьо за съответната двойка

(r,b)

. Доказаното броене показва, че тогава едноцветните делящи се тройки са точно

2007

.

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

Задача C4

Пълен запис

Условие

Нека

A_0=(a_1,\ldots,a_n)

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

k\ge0

от редицата

A_k=(x_1,\ldots,x_n)

построяваме нова редица

A_{k+1}

по следния начин. 1. Избираме разбиване

\{1,\ldots,n\}=I\cup J

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

\left|\sum_{i\in I}x_i-\sum_{j\in J}x_j\right|

има най-малка възможна стойност. Допускаме

I

или

J

да е празно множество; тогава съответната сума е

0

. Ако има няколко такива разбивания, избираме едно произволно. 2. Полагаме

A_{k+1}=(y_1,\ldots,y_n)

, където

y_i=x_i+1

за

i\in I

и

y_i=x_i-1

за

i\in J

. Докажете, че за някое

k

редицата

A_k

съдържа елемент

x

, за който

|x|\ge n/2

.

Решение

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

(x_1,\ldots,x_n)

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

|x_i|\lt{}a

, то съществува разбиване

\{1,2,\ldots,n\}=I\cup J

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

\left|\sum_{i\in I}x_i-\sum_{j\in J}x_j\right|\lt{}a.

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

n

. За

n=1

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

n-1

. Избираме разбиване

I'\cup J'

на

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

, за което

\left|\sum_{i\in I'}x_i-\sum_{j\in J'}x_j\right|\lt{}a.

Без ограничение нека първата сума е поне втората. Ако

x_n\ge0

, поставяме

n

в

J'

; ако

x_n\lt{}0

, поставяме

n

в

I'

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

|x_n|

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

(-a,a)

. Лемата е доказана. Да се върнем към задачата. Допускаме противното: за всяко

k

всички членове на

A_k

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

(-n/2,n/2)

. Ако

A_k=(b_1,\ldots,b_n)

, то всяко

b_i-a_i

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

1

. Интервал с дължина

n

съдържа най-много

n

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

b_i

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

n

възможни стойности. Следователно има най-много

n^n

различни редици

A_k

, така че някои две от тях съвпадат:

A_p=A_q

за

p\lt{}q

. Нека

S_k

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

A_k

. Разглеждаме една стъпка от

A_k=(x_1,\ldots,x_n)

към

A_{k+1}=(y_1,\ldots,y_n)

и нека

I,J

е избраното разбиване. По лемата съществува разбиване с разлика по абсолютна стойност по-малка от

n/2

; понеже нашето разбиване минимизира тази стойност, за него също е вярно

\left|\sum_{i\in I}x_i-\sum_{j\in J}x_j\right|\lt{}\frac n2.

Тогава

\begin{aligned}S_{k+1}-S_k&=\sum_{i\in I}\big((x_i+1)^2-x_i^2\big)+\sum_{j\in J}\big((x_j-1)^2-x_j^2\big)\\ &=n+2\left(\sum_{i\in I}x_i-\sum_{j\in J}x_j\right)\gt{}0. \end{aligned}

Значи

S_k

строго нараства при всяка стъпка. Това е невъзможно по цикъла

A_p,A_{p+1},\ldots,A_q

, защото

A_p=A_q

би дало

S_p=S_q

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

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

Задача C7

Пълен запис

Условие

Нека

\alpha\lt{}\frac{3-\sqrt{\vphantom{x^2}5}}{2}

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

n

и

p\gt{}\alpha\cdot2^n

, за които могат да се изберат

2p

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

S_1,\ldots,S_p,T_1,\ldots,T_p

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

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

така, че

S_i\cap T_j\ne\varnothing

за всички

1\le i,j\le p

.

Решение

Нека

k

и

m

са положителни цели числа, които ще изберем по-късно, и нека

n=km

. Разбиваме множеството

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

на

k

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

A_1,\ldots,A_k

, всяко с по

m

елемента. Дефинираме

\begin{aligned}\mathcal S&=\{S\subset\{1,2,\ldots,n\}: S\cap A_i\ne\varnothing\text{ за всяко }i\},\\ \mathcal T_1&=\{T\subset\{1,2,\ldots,n\}: A_i\subset T\text{ за някое }i\},\qquad \mathcal T=\mathcal T_1\setminus\mathcal S. \end{aligned}

Ако

S\in\mathcal S

и

T\in\mathcal T

, то за някое

i

имаме

A_i\subset T

, а същевременно

S\cap A_i\ne\varnothing

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

S\cap T\ne\varnothing

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

k

и

m

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

|\mathcal S|\gt{}\alpha\cdot2^n\quad\text{и}\quad |\mathcal T|\gt{}\alpha\cdot2^n.

Тогава вземаме

p=\min\{|\mathcal S|,|\mathcal T|\}

и избираме по

p

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

\mathcal S

и

\mathcal T

са непресичащи се фамилии. Броим. За всяко

i

сечението

S\cap A_i

може да бъде всяко непразно подмножество на

A_i

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

|\mathcal S|=(2^m-1)^k.

Ако едно множество не съдържа изцяло никое от

A_i

, то за всяко

i

има

2^m-1

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

A_i

. Значи

|\mathcal T_1|=2^{km}-(2^m-1)^k.

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

\mathcal S\setminus\mathcal T_1

имат с всяко

A_i

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

|\mathcal S\setminus\mathcal T_1|=(2^m-2)^k.

От тези три преброявания получаваме

|\mathcal T|=2^{km}-2(2^m-1)^k+(2^m-2)^k.

Нека

\delta=\frac{3-\sqrt{\vphantom{x^2}5}}{2}

и изберем

k=\left\lfloor2^m\log\frac1\delta\right\rfloor.

Когато

m\to\infty

, имаме

k/2^m\to\log(1/\delta)

, откъдето

\frac{|\mathcal S|}{2^{km}}=\left(1-\frac1{2^m}\right)^k\longrightarrow \delta

и от формулата за

|\mathcal T|

\frac{|\mathcal T|}{2^{km}}\longrightarrow1-2\delta+\delta^2.

Понеже

\delta

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

\delta^2-3\delta+1=0

, имаме

1-2\delta+\delta^2=\delta

. Следователно и двете отношения клонят към

\delta

. Тъй като

\alpha\lt{}\delta

, за достатъчно голямо

m

получаваме

|\mathcal S|\gt{}\alpha\cdot2^{km}\quad\text{и}\quad |\mathcal T|\gt{}\alpha\cdot2^{km}.

Но

n=km

, така че това е точно нужното неравенство.

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

Задача N1

Пълен запис

Условие

Намерете всички двойки

(k,n)

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

7^k-3^n

дели

k^4+n^2

.

Решение

Отговорът е

(k,n)=(2,4)

. Нека двойката

(k,n)

удовлетворява условието. Понеже

7^k-3^n

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

k^4+n^2

също е четно, откъдето

k

и

n

са с еднаква четност. Ако и двете са нечетни, тогава

k^4+n^2\equiv1+1=2\pmod4,

докато

7^k-3^n\equiv7-3\equiv0\pmod4,

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

k

и

n

са четни. Нека

k=2a

и

n=2b

. Тогава

7^k-3^n=7^{2a}-3^{2b}=\frac{7^a-3^b}{2}\cdot2(7^a+3^b),

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

2(7^a+3^b)

дели

7^k-3^n

, а

7^k-3^n

дели

k^4+n^2=2(8a^4+2b^2).

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

7^a+3^b\le8a^4+2b^2.\tag{1}

Ще използваме следните оценки:

8a^4\lt{}7^a

за

a\ge4

,

2b^2\lt{}3^b

за

b\ge1

и

2b^2+9\le3^b

за

b\ge3

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

8\cdot4^4=2048\lt{}7^4=2401,\qquad 2\lt{}3,

2\cdot2^2=8\lt{}3^2=9,\qquad 2\cdot3^2+9=3^3=27.

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

a\ge4

и

b\ge3

, то

8(a+1)^4=8a^4\left(\frac{a+1}{a}\right)^4\lt{}7^a\left(\frac54\right)^4\lt{}7^{a+1}

и

2(b+1)^2+9\lt{}(2b^2+9)\left(\frac{b+1}{b}\right)^2\le

3^b\left(\frac43\right)^2\lt{}3^{b+1},

което завършва индукцията. Ако

a\ge4

, получаваме

7^a+3^b\gt{}8a^4+2b^2

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

a\le3

. 1) Нека

a=1

. Тогава

k=2

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

8+2b^2\ge7+3^b

, тоест

2b^2+1\ge3^b

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

b\le2

. Ако

b=1

, то

n=2

и

\frac{k^4+n^2}{7^k-3^n}=\frac{2^4+2^2}{7^2-3^2}=\frac12,

което не е цяло число. Ако

b=2

, то

n=4

и

\frac{k^4+n^2}{7^k-3^n}=\frac{2^4+4^2}{7^2-3^4}=-1,

така че

(2,4)

е решение. 2) Нека

a=2

. Тогава

k=4

и

256+4b^2\ge |7^4-3^{2b}|=|49-3^b|(49+3^b).

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

22

, при

b=3

, затова

128+2b^2\ge11(49+3^b),

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

3^b\gt{}2b^2

. 3) Нека

a=3

. Тогава

k=6

и

1296+4b^2\ge |7^6-3^{2b}|=|343-3^b|(343+3^b).

Аналогично

|343-3^b|\ge100

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

324+b^2\ge25(343+3^b),

което отново е невъзможно. Следователно единственото решение е

(k,n)=(2,4)

.

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

Задача N2

Пълен запис

Условие

Нека

b,n\gt{}1

са цели числа. Да предположим, че за всяко цяло число

k\gt{}1

съществува цяло число

a_k

, такова че

b-a_k^n

се дели на

k

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

b=A^n

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

A

.

Решение

Нека разлагането на

b

на прости множители е

b=p_1^{\alpha_1}\cdots p_s^{\alpha_s},

където

p_1,\ldots,p_s

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

\alpha_i

се дели на

n

; тогава можем да вземем

A=p_1^{\alpha_1/n}\cdots p_s^{\alpha_s/n}.

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

k=b^2

. Тогава

b-a_k^n

се дели на

b^2

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

i

се дели и на

p_i^{2\alpha_i}

. Значи

a_k^n\equiv b\equiv0\pmod{p_i^{\alpha_i}},

но

a_k^n\equiv b\not\equiv0\pmod{p_i^{\alpha_i+1}}.

Това означава, че най-голямата степен на

p_i

, която дели

a_k^n

, е точно

p_i^{\alpha_i}

. Понеже

a_k^n

е пълна

n

-та степен, показателят

\alpha_i

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

n

. Това е вярно за всяко

i

, откъдето следва твърдението.

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

Задача N3

Пълен запис

Условие

Нека

X

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

10000

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

47

. Докажете, че съществува

2007

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

Y

на

X

, такова че

a-b+c-d+e

не се дели на

47

за никакви

a,b,c,d,e\in Y

.

Решение

Да наречем множество

M

от цели числа добро, ако

47\nmid a-b+c-d+e

за всички

a,b,c,d,e\in M

. Разглеждаме множеството

J=\{-9,-7,-5,-3,-1,1,3,5,7,9\}.

То е добро. Наистина за произволни

a,b,c,d,e\in J

числото

a-b+c-d+e

е нечетно и

-45=(-9)-9+(-9)-9+(-9)\le

a-b+c-d+e\le 9-(-9)+9-(-9)+9=45.

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

-45

до

45

няма нечетно число, което се дели на

47

. За всяко

k=1,2,\ldots,46

дефинираме

A_k=\{x\in X\mid \text{съществува }j\in J\text{ с }kx\equiv j\pmod{47}\}.

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

A_k

е добро. Ако някое

A_k

не е добро, то за някои

a,b,c,d,e\in A_k

имаме

47\mid a-b+c-d+e.

Умножавайки по

k

, получаваме

47\mid ka-kb+kc-kd+ke.

Но по дефиниция остатъците на

ka,kb,kc,kd,ke

по модул

47

съвпадат с елементи на

J

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

J

не е добро. Противоречие. Остава да намерим

k

, за което

|A_k|\ge2007

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

x\in X

принадлежи на точно

10

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

A_k

: понеже

47\nmid x

, умножението по

x

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

47

, а

J

има

10

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

\sum_{k=1}^{46}|A_k|=10|X|=100000.

От принципа на Дирихле за някое

k

имаме

|A_k|\ge\frac{100000}{46}\gt{}2173\gt{}2007.

Вземаме произволни

2007

елемента от това добро множество

A_k

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

Y

.

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

Задача N4

Пълен запис

Условие

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

k\ge2

докажете, че

2^{3k}

дели числото

\binom{2^{k+1}}{2^k}-\binom{2^k}{2^{k-1}},

но

2^{3k+1}

не го дели.

Решение

Използваме означенията

(2n-1)!\neq{}1\cdot3\cdots(2n-1),

\qquad (2n)!\neq{}2\cdot4\cdots(2n)=2^n n!.

Тогава

(2n)\neq{}2^n n!(2n-1)!!

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

n

имаме

\binom{4n}{2n}=\frac{(4n)!}{(2n)!^2}=\frac{2^{2n}}{(2n)!}(4n-1)!!

и

\binom{2n}{n}=\frac1{(2n)!}\left(\frac{(2n)!}{n!}\right)^2=

\frac{2^{2n}}{(2n)!}(2n-1)!!^2.

Затова разглежданата разлика е

\frac{2^{2^k}(2^k-1)!!}{(2^k)!}\left((2^k+1)(2^k+3)\cdots(2^k+2^k-1)-(2^k-1)(2^k-3)\cdots(2^k-2^k+1)\right).\tag{1}

Ще намерим точния показател на

2

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

v_2((2^r)!)=2^r-1

. Базата

r=1

е ясна, а ако

(2^r)\neq{}2^{2^r-1}(2d+1)

, то

(2^{r+1})\neq{}2^{2^r}(2^r)!(2^{r+1}-1)!\neq{}

2^{2^{r+1}-1}(2q+1)

за някое цяло

q

. Следователно показателят на

2

в първия множител на (1) е

2^k-(2^k-1)=1.

Вторият множител е стойността при

x=2^k

на полинома

P(x)=

(x+1)(x+3)\cdots(x+2^k-1)

-(x-1)(x-3)\cdots(x-2^k+1).

Понеже

k\ge2

, имаме

P(-x)=-P(x)

, така че

P

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

P(x)=x^3Q(x)+cx

с полином

Q

с цели коефициенти. Намираме показателя на

2

в

c

. Коефициентът пред

x

е

\begin{aligned}c&=2(2^k-1)!!\sum_{i=1}^{2^{k-1}}\frac1{2i-1}\\&=(2^k-1)!!\sum_{i=1}^{2^{k-1}}\left(\frac1{2i-1}+\frac1{2^k-2i+1}\right)\\&=2^k\sum_{i=1}^{2^{k-1}}\frac{(2^k-1)!!}{(2i-1)(2^k-2i+1)}=2^kS.\end{aligned}

За всяко

i

нека

a_{2i-1}

е обратният остатък на

2i-1

по модул

2^k

. Когато

2i-1

пробягва всички нечетни остатъци, същото прави и

a_{2i-1}

. Затова

\begin{aligned}S&\equiv-\sum_{i=1}^{2^{k-1}}\frac{(2^k-1)!!}{(2i-1)^2}\equiv-(2^k-1)!!\sum_{i=1}^{2^{k-1}}(2i-1)^2\\&=-(2^k-1)!!\frac{2^{k-1}(2^{2k}-1)}3\pmod{2^k}. \end{aligned}

Оттук точният показател на

2

в

S

е

k-1

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

c=2^{2k-1}(2t+1)

за някое цяло

t

. Накрая

P(2^k)=2^{3k}Q(2^k)+2^k c=

2^{3k}Q(2^k)+2^{3k-1}(2t+1),

така че

P(2^k)

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

2^{3k-1}

. Заедно с първия множител в (1) получаваме точен показател

1+(3k-1)=3k

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

2^{3k}

, но не и на

2^{3k+1}

.

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

Задача N5

Пълен запис

Условие

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

f:\mathbb N\to\mathbb N

, такива че за всички

m,n\in\mathbb N

и всяко просто число

p

числото

f(m+n)

се дели на

p

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

f(m)+f(n)

се дели на

p

. Тук

\mathbb N

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

Решение

Отговорът е

f(n)=n

. Нека

f:\mathbb N\to\mathbb N

удовлетворява условието. Лема. За всяко просто число

p

и всички

x,y\in\mathbb N

имаме

x\equiv y\pmod p\quad\Longleftrightarrow\quad f(x)\equiv f(y)\pmod p.

Освен това

p\mid f(x)

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

p\mid x

. Доказателство. Фиксираме просто число

p

. Понеже

f

е сюрективна, съществува

x

, за което

p\mid f(x)

. Нека

d=\min\{x\in\mathbb N:p\mid f(x)\}.

С индукция по

r

получаваме

p\mid f(rd)

за всяко

r\in\mathbb N

: ако

p\mid f(rd)

и

p\mid f(d)

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

p\mid f(rd+d)

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

x

, за което

d\nmid x

, но

p\mid f(x)

. Нека

y

е най-малкото такова число. Тогава

y\gt{}d

, числото

y-d

е положително и не се дели на

d

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

p\nmid f(y-d)

по минималността на

y

. Но

p\mid f(d)

и

p\mid f(d+(y-d))=f(y)

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

p\mid f(x)\quad\Longleftrightarrow\quad d\mid x.\tag{1}

Нека

x\equiv y\pmod d

. Имаме

p\mid f(x+(2xd-x))=f(2xd)

. Също

d\mid y+(2xd-x)

, така че

p\mid f(y+(2xd-x))

. По условието

p\mid f(x)+f(2xd-x),\qquad p\mid f(y)+f(2xd-x),

откъдето

f(x)\equiv f(y)\pmod p

. Обратно, ако

f(x)\equiv f(y)\pmod p

, то от

p\mid f(x)+f(2xd-x)

следва

p\mid f(y)+f(2xd-x)

. По условието

p\mid f(y+(2xd-x))

, а от (1) получаваме

0\equiv y+2xd-x\equiv y-x\pmod d.

Така доказахме

x\equiv y\pmod d\quad\Longleftrightarrow\quad f(x)\equiv f(y)\pmod p.\tag{2}

Остава да покажем, че

d=p

. Числата

1,2,\ldots,d

имат различни остатъци по модул

d

, следователно по (2) числата

f(1),f(2),\ldots,f(d)

имат различни остатъци по модул

p

, откъдето

p\ge d

. От сюрективността на

f

съществуват

x_1,\ldots,x_p

, за които

f(x_i)=i

. По (2) тези

x_i

имат различни остатъци по модул

d

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

d\ge p

. Значи

d=p

, а (1) и (2) дават лемата. Сега доказваме

f(n)=n

с индукция по

n

. За

n=1

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

f(1)

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

f(1)=1

. Нека

n\gt{}1

и

k=f(n)

. Има просто число

q\mid n

, така че по лемата

q\mid k

и

k\gt{}1

. Ако

k\gt{}n

, то

k-n+1\gt{}1

и има просто

p\mid k-n+1

. Тогава

k\equiv n-1\pmod p

. По индукционното предположение

f(n-1)=n-1

, така че

f(n)\equiv f(n-1)\pmod p

. Лемата дава

n\equiv n-1\pmod p

, невъзможно. Ако

k\lt{}n

, тогава

f(k-1)=k-1

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

p\mid n-k+1

, откъдето

n\equiv k-1\pmod p

. По лемата

k=f(n)\equiv f(k-1)=k-1\pmod p,

също невъзможно. Остава само

k=n

, тоест

f(n)=n

. Функцията

f(n)=n

очевидно удовлетворява условието.

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

Задача N6

Пълен запис

Условие

Нека

k

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

(4k^2-1)^2

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

8kn-1

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

k

е четно.

Решение

Ще използваме следната лема. Лема. За произволни положителни цели числа

x,y

числото

4xy-1

дели

(4x^2-1)^2

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

x=y

. Доказателство. Ако

x=y

, твърдението е очевидно. За обратната посока ще докажем, че няма лоши двойки

(x,y)

, където

4xy-1

дели

(4x^2-1)^2

, но

x\ne y

. Свойство 1. Ако

(x,y)

е лоша двойка и

x\lt{}y

, тогава съществува положително цяло

z\lt{}x

, за което

(x,z)

също е лоша двойка. Нека

r=\frac{(4x^2-1)^2}{4xy-1}.

Тогава

r=-r(-1)\equiv-r(4xy-1)=-(4x^2-1)^2\equiv-1\pmod{4x},

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

r=4xz-1

за някое положително цяло

z

. От

x\lt{}y

получаваме

4xz-1=\frac{(4x^2-1)^2}{4xy-1}\lt{}4x^2-1,

така че

z\lt{}x

. По построение

4xz-1

дели

(4x^2-1)^2

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

(x,z)

е лоша двойка. Свойство 2. Ако

(x,y)

е лоша двойка, тогава

(y,x)

също е лоша двойка. Понеже

1\equiv(4xy)^2\pmod{4xy-1}

, имаме

(4y^2-1)^2\equiv

(4y^2-(4xy)^2)^2=16y^4(4x^2-1)^2\equiv0\pmod{4xy-1}.

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

4xy-1

дели и

(4y^2-1)^2

. Ако съществува лоша двойка, избираме такава

(x,y)

, за която

2x+y

е минимално. Ако

x\lt{}y

, свойство 1 дава лоша двойка

(x,z)

с

z\lt{}y

, така че

2x+z\lt{}2x+y

. Ако

y\lt{}x

, свойство 2 дава лоша двойка

(y,x)

, а

2y+x\lt{}2x+y

. И двете са противоречия. Лемата е доказана. Прилагаме лемата с

x=k

и

y=2n

. Числото

8kn-1

дели

(4k^2-1)^2

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

k=2n

. Затова такова

n

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

k

, а при четно

k

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

n=k/2

.

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

Задача N7

Пълен запис

Условие

За просто число

p

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

n

нека

\nu_p(n)

означава показателя на

p

в разлагането на

n!

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

d

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

\{p_1,\ldots,p_k\}

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

n

, за които

d\mid\nu_{p_i}(n)

за всички

1\le i\le k

.

Решение

За просто

p

и положително цяло

n

нека

\operatorname{ord}_p(n)

е показателят на

p

в

n

. Тогава

\nu_p(n)=\operatorname{ord}_p(n!)=\sum_{i=1}^n\operatorname{ord}_p(i).

Лема. Нека

p

е просто число,

q

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

r

и

s

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

p^s\gt{}r

. Тогава

\nu_p(qp^s+r)=\nu_p(qp^s)+\nu_p(r).

Доказателство. За

0\lt{}i\lt{}p^s

имаме

\operatorname{ord}_p(qp^s+i)=\operatorname{ord}_p(i)

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

e=\operatorname{ord}_p(i)

, то

e\lt{}s

, така че

qp^s+i

се дели на

p^e

, но не и на

p^{e+1}

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

\nu_p(qp^s+r)=

\sum_{i=1}^{qp^s}\operatorname{ord}_p(i)+\sum_{i=qp^s+1}^{qp^s+r}\operatorname{ord}_p(i)=

\nu_p(qp^s)+\nu_p(r).

Лемата е доказана. За цяло число

a

да означим с

\overline a

остатъка му по модул

d

. Събирането на остатъци също е по модул

d

. За положително цяло

n

нека

f(n)=(f_1(n),\ldots,f_k(n)),

\qquad f_i(n)=\overline{\nu_{p_i}(n)}.

Дефинираме редица

n_1=1,\qquad n_{\ell+1}=(p_1p_2\cdots p_k)^{n_\ell}.

Твърдим, че за всички

\ell_1\lt{}\ell_2\lt{}\cdots\lt{}\ell_m

е изпълнено

f(n_{\ell_1}+n_{\ell_2}+\cdots+n_{\ell_m})=

f(n_{\ell_1})+f(n_{\ell_2})+\cdots+f(n_{\ell_m}),

\tag{1}

където събирането на

k

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

m

, като случаят

m=1

е ясен. За

m\gt{}1

по построение

p_i^{n_{\ell_1}}

дели

n_{\ell_2}+\cdots+n_{\ell_m}

и

p_i^{n_{\ell_1}}\gt{}n_{\ell_1}

. Прилагаме лемата с

p=p_i

,

s=r=n_{\ell_1}

и

qp^s=n_{\ell_2}+\cdots+n_{\ell_m}

. Получаваме

f_i(n_{\ell_1}+\cdots+n_{\ell_m})=

f_i(n_{\ell_1})+f_i(n_{\ell_2}+\cdots+n_{\ell_m})

за всяко

i

, а индукционното предположение дава (1). Сега разглеждаме стойностите

f(n_1),f(n_2),\ldots

. Те са крайно много възможни, следователно съществува безкрайна редица индекси

\ell_1\lt{}\ell_2\lt{}\cdots

, за които

f(n_{\ell_1})=f(n_{\ell_2})=\cdots.

Тогава за всяко

m

от (1) следва

f(n_{\ell_{m+1}}+n_{\ell_{m+2}}+\cdots+n_{\ell_{m+d}})=

d\cdot f(n_{\ell_1})=(\overline0,\ldots,\overline0).

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

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

2007

11-12

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие