SOM

Контролни по области

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

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

По година По клас

Избран клас

9

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

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

somnt2020-9-1: има placeholder текст
somgeo2020-9-2: има placeholder текст
somcomb2019-9-1: има placeholder текст
somalg2018-9-1: има placeholder текст
somnt2018-9-1: има placeholder текст
somcomb2018-9-2: има placeholder текст
somalg2018-9-3: има placeholder текст
somcomb2018-9-3: има placeholder текст
somcomb2017-9-1: има placeholder текст
somalg2016-9-1: има placeholder текст
somalg2016-9-2: има placeholder текст
somcomb2016-9-2: има placeholder текст
somcomb2016-9-3: има placeholder текст
somnt2015-9-1: има placeholder текст

2015 · Алгебра

3 задачи

Задача 1

Пълен запис

Условие

Нека

a, b, c, d

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

a b c d=1

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

\frac{1+a b}{1+a}+\frac{1+b c}{1+b}+\frac{1+c d}{1+c}+\frac{1+d a}{1+d} \geq 4

Решение

Имаме

\begin{gathered} \frac{1+a b}{1+a}+\frac{1+c d}{1+c}=\frac{1+a b}{1+a}+\frac{1+a b}{a b(1+c)} \geq \frac{4(1+a b)}{1+a+a b+a b c} \\ \frac{1+b c}{1+b}+\frac{1+d a}{1+d}=\frac{1+b c}{1+b}+\frac{1+b c}{b c(1+d)} \geq \\ \geq \frac{4(1+b c)}{1+b+b c+b c d}=\frac{4 a(1+b c)}{1+a+a b+a b c} \end{gathered}

Събираме горните неравенства и получаваме исканото неравенство.

Отвори задачатаБаза на maths.bgsomalg2015-9-1

Задача 2

Пълен запис

Условие

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

p(x)

с цели коефициенти, за който

p(\sqrt[3]{\vphantom{x^2}3}+\sqrt[3]{\vphantom{x^2}9})=3+\sqrt[3]{\vphantom{x^2}3}

Решение

Лесно се доказва, че ако

a

b

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

a \sqrt[3]{\vphantom{x^2}3}+b \sqrt[3]{\vphantom{x^2}9}

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

a=b=0

. От този факт с директна проверка следва, че не съществува полином с цели коефициенти и степен по-малка от три, който изпълнява даденото равенство. (Да отбележим, че единственият полином

p(x)

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

p(x)=\frac{x^{2}-x}{2}

.) Да допуснем, че полиномът

p(x)

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

\alpha=\sqrt[3]{\vphantom{x^2}3}+\sqrt[3]{\vphantom{x^2}9}

е корен на полинома

s(x)=x^{3}-9 x-12

. Нека

p(x)=s(x) q(x)+r(x)

, където

q(x)

r(x)

са полиноми с цели коефициенти и

r(x)=0

или

\operatorname{deg} r(x) \leq 2

. Тъй като

r(\alpha)=p(\alpha)=3+\sqrt[3]{\vphantom{x^2}3}

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

Отвори задачатаБаза на maths.bgsomalg2015-9-2

Задача 3

Пълен запис

Условие

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

f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}

такива, че

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

за произволни

x, y\gt{}0

Решение

Ако допуснем, че

f(y)\gt{}1

за някое

y\gt{}0

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

x=\frac{y}{f(y)-1}

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

f(y)=1

. И така,

f\lt{}1

. Оттук и условието следва, че

f

е намаляваща функция. Нека сега

f(y)=1

за някое

y\gt{}0

. Тогава

f(x+y)=f(x)

за всяко

x\gt{}0

и монотонноста на

f

показва, че

f=1

. Остава да разгледаме случая, когато

f(y)\lt{}1

за всяко

y\gt{}0

. Тогава

f

е строго намаляваща функция и значи е инективна. Сега от равенствата

\begin{gathered} f(y) f(x f(y))=f(x+y)=f(x f(y)+y+x(1-f(y)) \\ =f(x f(y)) f((y+x(1-f(y)) f(f(x f(y))) \end{gathered}

следва, че

y=(y+x(1-f(y)) f(x f(y))

. Като положим

y=1, x f(1)=z

c= 1-\frac{1}{f(1)}

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

f(z)=\frac{1}{1+c z}

. И така,

f(x)=\frac{1}{1+c x}(c\gt{}0)

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

Отвори задачатаБаза на maths.bgsomalg2015-9-3

2015 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

Даден е остроъгълният

\triangle A B C

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

O

. Нека

H_{A}, H_{B}

H_{C}

са ортоцентровете съответно на

\triangle B O C, \triangle A O C

\triangle A O B

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

O

е ортоцентърът на

\triangle H_{A} H_{B} H_{C}

, то

\triangle A B C

е равностранен.

Решение

Решение. Точка

O

е ортоцентър на

\triangle H_A H_B H_C

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

H_C O \perp H_A H_B

. От друга страна, точка

H_C

е ортоцентър на

\triangle A O B

, откъдето

H_C O \perp A B

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

H_A H_B \| A B

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

H_B

H_A

са ортоцентровете съответно на

\triangle A O C

\triangle B O C

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

H_B A \perp O C

H_A B \perp O C

. Тогава

H_A B \| H_B A

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

H_A B A H_B

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

H_A B=H_B A

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

\angle B H_A C=180^{\circ}-2 \alpha

\triangle B H_A C

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

\triangle B O C

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

H_A B=\frac{B C}{2 \cos \alpha}

. Аналогично

H_B A=\frac{A C}{2 \cos \beta}

. Така получихме, че от

H_A B=H_B A

следва, че

\frac{B C}{2 \cos \alpha}=\frac{A C}{2 \cos \beta}

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

\sin \alpha \cos \beta=\cos \alpha \sin \beta

. Това означава, че

\sin (\alpha-\beta)=0

или

A C=B C

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

A C=A B

Отвори задачатаБаза на maths.bgsomgeo2015-9-1

Задача 2

Пълен запис

Условие

Даден е остроъгълният

\triangle A B C

с ортоцентър

H

. Ъглополовящите на

\angle A B H

\angle A C H

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

E

. Нека

C E \cap A B= F

. Нека

A E

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

\triangle B E F

за втори път в точката

G

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

A G. B C \geq C G. A B

Решение

Решение. Нека

B E \cap A C=D

. Нека

\angle B A C=\alpha

. Тогава

\angle B F C=\angle B D C=45^{\circ}+\frac{\alpha}{2}

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

B F D C

е вписан и оттук

A C. A D=A B. A F=A E. A G

. Тогава и четириъгълникът

D E G C

е вписан и оттук

\angle E G C+\angle E G B=\angle A D E+\angle A F E

, откъдето следва, че

\angle B G C=90^{\circ}+\alpha

. Построяваме такава точка

M

, че

\triangle B A C \sim \triangle B G M

. Тогава

\angle C G M=90^{\circ}

. Имаме

\frac{A B}{B G}=\frac{B C}{B M}

\angle A B G=\angle C B M

и оттук

\triangle A B G \sim \triangle C B M

. Тогава

C M=\frac{A G. B C}{A B}

, но от

\angle C G M=90^{\circ}

следва

C G \leq C M

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

Отвори задачатаБаза на maths.bgsomgeo2015-9-2

Задача 3

Пълен запис

Условие

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

A B C D

, описан около окръжност с център

I

. Точката

P

е такава, че

\angle A P C

\angle B P D

имат обща вътрешна ъглополовяща

l

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

I

лежи върху

l

Решение

G3. Нека

M

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

A B, B C, C D

D A

(това е пресечната точка на описаните окръжности на четирите триъгълника, образувани от тези прави). Ще докажем първо, че

M

притежава описаното в задачата свойство, т. е., че

\angle A M C

\angle B M D

имат обща вътрешна ъглополовяща. Нека

Q

R

са такива, че

\triangle M I Q \sim \triangle M C B

\triangle M I R \sim \triangle M A B

, като подобията са еднопосочни. Тогава

\triangle M D A \sim \triangle M I Q \sim \triangle M C B

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

\triangle B Q A \sim \triangle C I D

. Оттук,

\angle B Q A+\angle A I B=\angle C I D+\angle A I B=180^{\circ}, A I B Q

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

A B C D

. Аналогично, същото е вярно и за

I C R B

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

M I C R B \sim M A I B Q

, откъдето

\triangle M I C \sim \triangle M A I

\angle C M I=\angle I M A

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

\triangle M D I \sim \triangle M I B

\angle D M I=\angle I M B

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

P

притежава описаното свойство и

M P C^{\prime} I^{\prime} A^{\prime} \sim M D C I A

. Понеже

\angle A P C

\angle B P D

имат обща вътрешна ъглополовяща и

\triangle C P D \sim \triangle B A^{\prime} A

, имаме

\angle B P A=\angle C P D=\angle B A^{\prime} A

, откъдето

B A P A^{\prime}

е вписан. Аналогично,

B C P C^{\prime}

също е вписан. Понеже

B I

е ъглополовяща и четириъгълниците

B A P A^{\prime}

B C P C^{\prime}

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

\begin{aligned} \angle I B P & =\frac{1}{2}(\angle A B P+\angle C B P)=\frac{1}{2}\left(\angle A A^{\prime} P+\angle C C^{\prime} P\right) \\ & =\frac{1}{2}\left(\angle A A^{\prime} M-\angle P A^{\prime} M+\angle C C^{\prime} M-\angle P C^{\prime} M\right). \end{aligned}

Разделяме тази сума на части и ги преобразуваме поотделно. Понеже

\triangle A A^{\prime} M \sim \triangle C C^{\prime} M \sim \triangle I I^{\prime} M

, то

\begin{gathered} \frac{1}{2}\left(\angle A A^{\prime} M+\angle C C^{\prime} M\right)= \\ =\frac{1}{2}\left(\angle I I^{\prime} M+\angle I I^{\prime} M\right)=\angle I I^{\prime} M. \end{gathered}

Понеже

B I

е ъглополовяща, то

\begin{gathered} \frac{1}{2}\left(\angle P A^{\prime} M+\angle P C^{\prime} M\right)= \\ =\frac{1}{2}(\angle A B M+\angle C B M)=\angle I B M=\angle P I^{\prime} M. \end{gathered}

И така,

\angle I B P=\angle I I^{\prime} M-\angle P I^{\prime} M=\angle I I^{\prime} P

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

B I P I^{\prime}

е вписан. Оттук

\angle B P I=\angle B I^{\prime} I

. От друга страна, от доказаното по-горе за точката

M

имаме, че

\triangle M P I^{\prime} \sim \triangle M D I \sim \triangle M I B

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

M D I P \sim M I B I^{\prime}

\angle I P D=\angle B I^{\prime} I

. По този начин,

\angle B P I=\angle I P D

, което и трябваше да се докаже.

Отвори задачатаБаза на maths.bgsomgeo2015-9-3

2015 · Комбинаторика

3 задачи

Задача 1

Пълен запис

Условие

Дадени са 2015 кофи с еднаква вместимост от

v

литра. На един ход Иван разпределя 1 литър вода в дадените кофи, а Петър може да изпразни произволни 2014 от кофите. Да се намерят всички стойности на

v

, за които Иван може да напълни догоре някоя кофа за краен брой ходове.

Решение

Ще решим задачата за

k

кофи. Да означим с

a_{i}

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

i

-ия ход. Ясно е, че

a_{1}=\frac{1}{k}\lt{}\frac{1}{k-1}

. Ако

a_{n-1}\lt{}\frac{1}{k-1}

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

\frac{1+a_{n-1}}{k}

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

a_{n}=\frac{1+a_{n-1}}{k}\lt{}\frac{1+\frac{1}{k-1}}{k}=\frac{1}{k-1}.

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

a_{n}=\frac{1+a_{n-1}}{k}

, т. е.

k a_{n}-a_{n-1}=1

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

k a_{n-1}- a_{n-2}=1

получаваме

k a_{n}-(k+1) a_{n}+a_{n-2}=0.

Корените на характеристичното уравнение

x^{2}-(k+1) x+1=0

са

x_{1}=1

x_{2}=\frac{1}{k}

, откъдето

a_{n}=c_{1}+\frac{c_{2}}{k^{n}}

за някакви константи

c_{1}

c_{2}

. От

a_{1}=\frac{1}{k}

a_{2}=\frac{1+\frac{1}{k}}{k}=\frac{k+1}{k^{2}}

намираме

c_{1}=\frac{1}{k-1}

c_{2}=-\frac{1}{k-1}

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

a_{n}=\frac{1}{k-1}-\frac{1}{(k-1) k^{n}}

откъдето

\lim _{n \rightarrow \infty} a_{n}=\frac{1}{k-1}

. Ако

\frac{1}{k-1}+1 \leq v

, то

a_{n}+1\lt{}\frac{1}{k-1}+1 \leq v

, т. е. Иван не може да напълни никоя кофа. Ако

\frac{1}{k-1}+1=\frac{k}{k-1}\gt{}v

, то за

\epsilon=\frac{1}{k-1}+1-v\gt{}0

съществува

n

, за което

\frac{1}{k-1}-a_{n}\lt{}\epsilon=\frac{1}{k-1}+1-v

. Оттук

a_{n}+1\gt{}v

, т. е. една кофа може да се напълни догоре. При

k=2015

търсените стойности са

v\lt{}\frac{2015}{2014}

Отвори задачатаБаза на maths.bgsomcomb2015-9-1

Задача 2

Пълен запис

Условие

За всяка редица

u

от нули и единици с дължина 5 с

D(u)

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

u

. Множеството

A

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

u, v \in A

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

D(u)

D(v)

нямат общи елементи. Да се намери

\max |A|

Решение

Множеството

A=\{00000, 11111, 11000, 00011, 10101, 01110\}

е съставено от 6 редици, като директно се проверява, че при

u, v \in A

имаме

D(u) \cap D(v)=\emptyset

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

\max |A| \geq 6

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

A

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

x \in\{0, 1\}

, ако

x x x x \notin D(u)

за всяко

u \in A

, то към

A

можем да добавим

x x x x x

. Ако

x x x x \in D(u)

за някое

u \in A

, то можем да заместим

u

с редицата

\operatorname{xx} x x x

. Следователно без ограничение

00000, 11111 \in A

. Всяка от останалите поне 5 редици ще има две нули и три единици или три нули и две единици. Поне три от редиците имат равен първи член (нека без ограничение това е

0)

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

x

0, u_2, u_3, u_4, x, \quad 0, u_2, u_3, u_4, x

Ако

x=0

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

u_2, u_3, u_4

v_2, v_3, v_4

(във всяка от

u_2, u_3, u_4

v_2, v_3, v_4

има най-много по една нула) и получаваме 0110. Ако

x=1

, директно се проверява, че единствените възможности са 01101 и 00011 или 00111 и 01001. И в двата случая директна проверка за третата редица с първи член 0 показва, че не се получава множество с търсеното свойство. Следователно търсената максимална стойност е 6.

Отвори задачатаБаза на maths.bgsomcomb2015-9-2

Задача 3

Пълен запис

Условие

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

p

-ъгълник

M

, където

p

е просто число. Оцветяване на част от диагоналите и страните на

M

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

Решение

Ще докажем, че едно оцветяване е интересно, ако в графа, образуван от върховете на

p

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

p

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

z, z^{2}, \ldots, z^{p}=1

. Съществуването на посока върху всяко оцветено ребро е еквивалентно на съществуване на линейна комбинация на върховете, която е равна на 0. Тъй като всеки вектор дава един коефициент 1 и един коефициент -1, то сборът от коефициентите на тази линейна комбинация е 0. Следователно

f(z)=a_{0}+a_{1} z+\cdots+a_{p-1} z^{p-1}

като

a_{0}+a_{1}+\cdots+a_{p-1}=0

. Полиномът

g(z)=1+z+z^{2}+\cdots+z^{p-1}

е минималният полином на

z

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

f(z)

дели

g(z)

. Но

f(z)

g(z)

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

g(z)=t f(z)

, за някоя константа

t

. Ако

f(z)

не е нулевият полином, то това е невъзможно тъй като

g(1)=p

, а

f(1)=0

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

f(z)=0

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

G

p

върха, с поне едно ребро и всички върхове на който са от четна степен. Този брой е равен на броя на графите с

p-1

върха (от всеки граф с

p-1

върха с добавяне на връх, свързан с всички върхове с нечетна степен се получава граф от търсения вид с

p

върха, а от всеки граф

G

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

p-1

върха). Тъй като в граф с

p-1

върха има

\binom{p-1}{2}

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

p-1

върха и поне едно ребро са точно

2^{\left(\frac{p-1}{2}\right)}-1

Отвори задачатаБаза на maths.bgsomcomb2015-9-3

2015 · Теория на числата

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomnt2015-9-1

Задача 2

Пълен запис

Условие

Ще решим следната по-обща задача. Дадени са естествени числа

m \geq 3

s \geq 2

, като

s

не се дели на

2^{\left[\frac{m+1}{2}\right]}

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

k

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

n

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

n 2^{k}-2^{m}+1

е точна

s

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

k

сравнението

x^{s} \equiv 1-2^{m} \left(\bmod 2^{k}\right)

има

Решение

x_{k}

. При

k \leq m

това е очевидноможем да вземем

x_{1}= x_{2}=\cdots=x_{m}=1

. Ако

x_{k}

е при някое

k \geq m

, ще конструираме x_{k+1}

за

k+1

. Ако

x_{k}^{s} \equiv 1-2^{m}\left(\bmod 2^{k+1}\right)

, полагаме

x_{k+1}=x_{k}

. Ако

x_{k}^{s} \not \equiv 1-2^{m}\left(\bmod 2^{k+1}\right)

, то

x_{k}^{s} \equiv 1-2^{m}+2^{k}\left(\bmod 2^{k+1}\right)

. Нека

s=2^{a} b

, където

b

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

a \leq\left[\frac{m+1}{2}\right]-1

, т. е.

a+1 \leq \frac{m+1}{2} \Longleftrightarrow 2 a+1 \leq m

. Тогава полагаме

x_{k+1}=x_{k}+2^{k-a}

. Имаме последователно

\begin{aligned} x_{k+1}^{s} & =\left(x_{k}+2^{k-a}\right)^{s} \equiv x_{k}^{s}+s x_{k}^{s-1} 2^{k-a} \\ & \equiv 1-2^{m}+2^{k}\left(1+b x_{k}^{s-1}\right) \equiv 1-2^{m}\left(\bmod 2^{k+1}\right) \end{aligned}

(използвахме, че

2(k-a) \geq k+1 \Longleftrightarrow k \geq 2 a+1

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

k \geq m \geq 2 a+1

и че числата

b

x_{k}

са нечетни).

Отвори задачатаБаза на maths.bgsomnt2015-9-2

Задача 3

Пълен запис

Условие

Дадени са редица

Y=\left(y_{1}, y_{2}, \ldots, y_{n-t}\right)

от нули и единици, където

n, t \in \mathbb{N}, 1 \leq t \leq n-1

, и цяло число

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

. Редицата

X=\left(x_{1}, x_{2}, \ldots, x_{n}\right.

), също от нули и единици, се нарича суперредица на

Y

, ако

Y

може да бъде получена от

X

с премахване на

t

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

X=\left(x_{1}, x_{2}, \ldots, x_{n}\right)

на

Y

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

x_{1}+2 x_{2}+\cdots+n x_{n} \equiv a \quad(\bmod n+1)

Решение

Първо ще докажем, че всяка редица

Y

с дължина

n-1

може да бъде допълнена по единствен начин до нейна суперредица

X

с дължина

n

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

s \in\{0, 1\}

и нека

p

е позицията на

s

X

, т. е.

x_{p}=s

. Да означим с

L_{0}

броят на нулите и с

L_{1}

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

x_{p}

X

и аналогично нека

R_{0}

(съответно

R_{1}

) е броят на нулите (единиците) отдясно на

x_{p}

X

. Очевидно имаме

p=1+L_{0}+L_{1}

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

w

е теглото (т. е. броят на единиците) на

Y

, то

w=L_{1}+R_{1}

. Нека

S=\sum_{i} i x_{i}(\bmod n+1)

S^{\prime}=\sum_{i} i y_{i}(\bmod n+1)

. Ако

s=0

, имаме

S-S^{\prime} \quad(\bmod n+1)=R_{1} \leq w,

а ако

s=1

, то

S-S^{\prime}(\bmod n+1)=p+R_{1}=1+L_{0}+L_{1}+R_{1}=1+L_{0}+w\gt{}w.

Тъй като

S \equiv a(\bmod n+1)

, разликата отляво е известна. Ако тя не надминава

w

, трябва да сме добавили 0, т. е.

x_{p}=0

, в противен случай

x_{p}=1

. В първия случай намираме еднозначно

R_{1}

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

L_{0}

и това определя позицията

p

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

X

като добавим 0 отляво на

R_{1}

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

Y

, или 1 отдясно на

L_{0}

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

Y

с дължина

n-1

. Лесно се вижда, че този брой е

\sum_{i=0}^{t-1}\binom{n-1}{i}

Отвори задачатаБаза на maths.bgsomnt2015-9-3

2016 · Алгебра

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomalg2016-9-1

Задача 2

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomalg2016-9-2

Задача 3

Пълен запис

Условие

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

f: \mathbb{R} \rightarrow \mathbb{R}

такива, че

f(x+y) \geq(y+1) f(x) \quad \forall x, y \in \mathbb{R}

Решение

Имаме, че

f(z) \geq 0. f(z+1)=0

f\left(\frac{k+1}{n} x\right) \geq\left(1+\frac{x}{n}\right) f\left(\frac{k x}{n}\right)

. Като умножим тези неравенства при

k=0, 1, \ldots, n-1

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

f(x) \geq\left(1+\frac{x}{n}\right)^{n} f(0)

. Аналогично, като умножим неравенствата

f\left(\frac{k x}{n}\right) \geq\left(1-\frac{x}{n}\right) f\left(\frac{k+1}{n} x\right)

при

k=0, 1, \ldots, n-1

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

f(0) \geq\left(1-\frac{x}{n}\right)^{n} f(x)

. Тъй като

\left(1 \pm \frac{x}{n}\right)^{n} \rightarrow e^{ \pm x}

, следва, че

f(x)=f(0) e^{x}

. Обратно, неравенството

e^{y} \geq 1+y

показва че за всяко

c \geq 0

функцията

f(x)=c e^{x}

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

Отвори задачатаБаза на maths.bgsomalg2016-9-3

2016 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

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

A B C D

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

F

. Нека правите

A B

C D

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

P

, а точка

M

е от лъча

P D^{\rightarrow}

, такава, че

P A \cdot A B=P M. C D

. Ако

N

е симетричната точка на

M

относно

P

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

P F \| A N

Решение

Решение. Нека правата

P F

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

A M

в точка

Q

. Означаваме с

h_{1}

h_{2}

разстоянията от точка

F

към правите

A P

D P

съответно. От

\triangle D C F \sim \triangle A B F

имаме

\frac{P M}{P A}=\frac{A B}{C D}=\frac{h_{1}}{h_{2}} \Rightarrow P M \cdot h_{2}=

P A \cdot h_{1} \Rightarrow S_{P M F}=S_{P A F} \Rightarrow M Q=M A.

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

P Q

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

\triangle A N M

, т. е.

P F \| A N

Отвори задачатаБаза на maths.bgsomgeo2016-9-1

Задача 2

Пълен запис

Условие

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

A B C D

, в който

\angle D A C =\angle A B C

\angle D C A=\angle A C B

. Точка

N

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

A B

и е такава, че

\angle N C B=\angle A B D

. Нека

M

е средата на

B D

. Правите

A M

B C

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

P

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

P N \perp A B

Решение

Решение. Нека

\angle A C B=\gamma

. Означаваме с

K

L

средите на

A D

A B

съответно. Имаме, че

\triangle D A C \sim \triangle A B C

и значи

C K

C L

са съответни медиани в тях. Следователно

\angle A K C=\angle B L C

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

A K C L

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

\triangle A B D

следва, че

\angle A B D=\angle A L K=\angle A C K=\angle B C L

, т. е.

N \equiv L

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

\triangle A N M

. От една страна

\angle A N M=180^{\circ}-\angle B A D=\angle A C B,

а от друга,

\frac{A N}{M N}=\frac{A B}{A D}=\frac{B C}{A C}

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

\triangle A N M \sim \triangle B C A

, т. е.

\angle B A P=\angle A B C

, откъдето следва, че

\triangle A B P

е равнобедрен. В този равнобедрен триъгълник

N

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

P N \perp A B

Отвори задачатаБаза на maths.bgsomgeo2016-9-2

Задача 3

Пълен запис

Условие

Даден е

\triangle A B C

, който е вписан в окръжност

k

с център

O

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

\triangle A B C

, т. е. окръжностите, които се допират вътрешно до

k

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

I O

, където

I

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

\triangle A B C

окръжност.

Решение

Решение. Нека

\omega

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

\omega_{A}, \omega_{B}

\omega_{C}

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

\triangle A B C

. Ще използваме означенията за точките от фигурата по-долу. Да разгледаме хомотетия

h

, която изпраща вписаната в описаната за

\triangle A B C

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

A T_{A}, B T_{B}

C T_{C}

се пресичат в центъра

T

на хомотетията

h

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

T, I

O

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

Q_{A}

Q_{C}

относно

k

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

T

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

Q_{A} Q_{C}

е полярата на точката

T

относно

k

. Остава да съобразим, че относно

k, P_{C}

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

\rho\left(\omega_{A}, \omega_{B}\right)

, а

P_{A}

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

\rho\left(\omega_{B}, \omega_{C}\right)

. Тогава

P_{A} P_{C}

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

P

на

\omega_{A}, \omega_{B}

\omega_{C}

относно

k

. Необходимо е да докажем, че

P_{A} P_{C} \| Q_{A} Q_{C}

. Но

\frac{T_{B} Q_{A}}{Q_{A} P_{A}}=\frac{T_{B} X_{B}}{X_{B} M_{A}}=\frac{T_{B} Y_{B}}{Y_{B} M_{C}}=\frac{T_{B} Q_{C}}{Q_{C} P_{C}}

с което доказателството е завършено. C1. Съществуват два независими едноцветни триъгълника

T_{1}=X_{1} X_{2} X_{3}

T_{2}=Y_{1} Y_{2} Y_{3}

(защо?). Нека

X_{1} X_{2} X_{3}

е червен, а

Y_{1} Y_{2} Y_{3}

- син. Ребрата между останалите пет върха не образуват едноцветен триъгълник (ако има такъв задачата би била решена) и следователно подграфът, индуциран от тези върхове се разбива на два едноцветни цикъла:

Z_{1} Z_{2} Z_{3} Z_{4} Z_{5} Z_{1}

- червен и

Z_{1} Z_{3} Z_{5} Z_{2} Z_{4} Z_{1}

- син. В подграфа, породен от

Y_{i}, Z_{1}, \ldots, Z_{5}, i=1, 2, 3

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

X_{i}, i=1, 2, 3

, образува с два от върховете

Z_{1}, \ldots, Z_{5}

червен триъгълник. Ако съществува монохроматичен триъгълник от вида

X_{i} Y_{j} Y_{k}

или

X_{i} X_{j} Y_{k}

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

Y_{j}

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

X_{i}

излиза не повече от едно синьо ребро. Това е противоречие, тъй като имаме девет ребра от вида

X_{i} Y_{j}

Отвори задачатаБаза на maths.bgsomgeo2016-9-3

2016 · Комбинаторика

3 задачи

Задача 1

Пълен запис

Условие

Ребрата на пълния граф с 11 върха са оцветени в червено и синьо. Да се докаже, че съществуват два независими (без общи върхове) едноцветни триъгълника, които са с един и същи цвят (и двата червени или и двата сини).

Решение

Съществуват два независими едноцветни триъгълника

T_{1}=X_{1} X_{2} X_{3}

T_{2}=Y_{1} Y_{2} Y_{3}

(защо?). Нека

X_{1} X_{2} X_{3}

е червен, а

Y_{1} Y_{2} Y_{3}

Z_{1} Z_{2} Z_{3} Z_{4} Z_{5} Z_{1}

- червен и

Z_{1} Z_{3} Z_{5} Z_{2} Z_{4} Z_{1}

- син. В подграфа, породен от

Y_{i}, Z_{1}, \ldots, Z_{5}, i=1, 2, 3

X_{i}, i=1, 2, 3

, образува с два от върховете

Z_{1}, \ldots, Z_{5}

червен триъгълник. Ако съществува монохроматичен триъгълник от вида

X_{i} Y_{j} Y_{k}

или

X_{i} X_{j} Y_{k}

Y_{j}

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

X_{i}

излиза не повече от едно синьо ребро. Това е противоречие, тъй като имаме девет ребра от вида

X_{i} Y_{j}

Отвори задачатаБаза на maths.bgsomcomb2016-9-1

Задача 2

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2016-9-2

Задача 3

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2016-9-3

2016 · Теория на числата

3 задачи

Задача 1

Пълен запис

Условие

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

a, b, c

d

са такива, че

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

Да се докаже, че числото

a c+b d

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

4

Решение

Решение. Да означим

f(x, y, z)=x^{2}+2 y^{2}+4 z^{2}+y z

. За всяко

a \in\{1, 2, \ldots, 30\}

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

f(x, y, z)=a

за някои цели

x, y

z

(това става най-лесно ако се разгледа първо

2 y^{2}+4 z^{2}+y z

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

f(x, y, z)=31

за някои цели

x, y

z

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

16 x^{2}+(8 z+y)^{2}=31\left(16-y^{2}\right)

което е невъзможно за цели

x, y

z

. Действително, 31 трябва да дели

x

8 z+y

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

31^{2}

, тогава

y=4, x=8 z+y=0

и т. н. Забележка. Горното решение е по-лесната част от решението на следната задача: Да се намери

\max \min \{a \in \mathbb{N}: a

не се представя като

f(x, y, z)\}

, където минимизирането се извършва по всички положително дефинитни квадратични форми на три цели променливи с цели коефициенти. Оказва се, че търсеният max min e точно 31, като квадратичната форма

x^{2}+2 y^{2}+4 z^{2}+y z

е единствената (с точност до еквивалентност), за която се достига равенство.

Отвори задачатаБаза на maths.bgsomnt2016-9-1

Задача 2

Пълен запис

Условие

Редицата от естествени числа

a_{1}, a_{2}, \ldots

удовлетворява връзката

a_{n+3}=a_{n+2} a_{n+1} a_{n}+1

за всяко естествено

n

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

n

, за които

a_{n}-43

е нечетно съставно число.

Решение

Ще решим следната по-обща задача. Дадени са естествени числа

m \geq 3

s \geq 2

, като

s

не се дели на

2^{\left[\frac{m+1}{2}\right]}

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

k

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

n

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

n 2^{k}-2^{m}+1

е точна

s

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

k

сравнението

x^{s} \equiv 1-2^{m} \left(\bmod 2^{k}\right)

има решение

x_{k}

. При

k \leq m

това е очевидноможем да вземем

x_{1}= x_{2}=\cdots=x_{m}=1

. Ако

x_{k}

е решение при някое

k \geq m

, ще конструираме решение

x_{k+1}

за

k+1

. Ако

x_{k}^{s} \equiv 1-2^{m}\left(\bmod 2^{k+1}\right)

, полагаме

x_{k+1}=x_{k}

. Ако

x_{k}^{s} \not \equiv 1-2^{m}\left(\bmod 2^{k+1}\right)

, то

x_{k}^{s} \equiv 1-2^{m}+2^{k}\left(\bmod 2^{k+1}\right)

. Нека

s=2^{a} b

, където

b

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

a \leq\left[\frac{m+1}{2}\right]-1

, т. е.

a+1 \leq \frac{m+1}{2} \Longleftrightarrow 2 a+1 \leq m

. Тогава полагаме

x_{k+1}=x_{k}+2^{k-a}

. Имаме последователно

\begin{aligned} x_{k+1}^{s} & =\left(x_{k}+2^{k-a}\right)^{s} \equiv x_{k}^{s}+s x_{k}^{s-1} 2^{k-a} \\ & \equiv 1-2^{m}+2^{k}\left(1+b x_{k}^{s-1}\right) \equiv 1-2^{m}\left(\bmod 2^{k+1}\right) \end{aligned}

(използвахме, че

2(k-a) \geq k+1 \Longleftrightarrow k \geq 2 a+1

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

k \geq m \geq 2 a+1

и че числата

b

x_{k}

са нечетни).

Отвори задачатаБаза на maths.bgsomnt2016-9-2

Задача 3

Пълен запис

Условие

Нека

a_{1}=1\lt{}a_{2}\lt{}a_{3}\lt{}\cdots\lt{}a_{n}\lt{}\cdots

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

i=1, 2, \ldots

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

A_{i}=\left\{k \in \mathbb{N}: k\lt{}a_{i+1}\right.

k

се дели на

\left. a_{i}\right\}

. Да се опишат тези редици

a_{i}

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

A_{i}

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

Решение

Решение. Първо ще докажем, че всяка редица

Y

с дължина

n-1

може да бъде допълнена по единствен начин до нейна суперредица

X

с дължина

n

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

s \in\{0, 1\}

и нека

p

е позицията на

s

X

, т. е.

x_{p}=s

. Да означим с

L_{0}

броят на нулите и с

L_{1}

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

x_{p}

X

и аналогично нека

R_{0}

(съответно

R_{1}

) е броят на нулите (единиците) отдясно на

x_{p}

X

. Очевидно имаме

p=1+L_{0}+L_{1}

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

w

е теглото (т. е. броят на единиците) на

Y

, то

w=L_{1}+R_{1}

. Нека

S=\sum_{i} i x_{i}(\bmod n+1)

S^{\prime}=\sum_{i} i y_{i}(\bmod n+1)

. Ако

s=0

, имаме

S-S^{\prime} \quad(\bmod n+1)=R_{1} \leq w,

а ако

s=1

, то

S-S^{\prime}(\bmod n+1)=p+R_{1}=1+L_{0}+L_{1}+R_{1}=1+L_{0}+w\gt{}w.

Тъй като

S \equiv a(\bmod n+1)

, разликата отляво е известна. Ако тя не надминава

w

, трябва да сме добавили 0, т. е.

x_{p}=0

, в противен случай

x_{p}=1

. В първия случай намираме еднозначно

R_{1}

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

L_{0}

и това определя позицията

p

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

X

като добавим 0 отляво на

R_{1}

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

Y

, или 1 отдясно на

L_{0}

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

Y

с дължина

n-1

. Лесно се вижда, че този брой е

\sum_{i=0}^{t-1}\binom{n-1}{i}

Отвори задачатаБаза на maths.bgsomnt2016-9-3

2017 · Алгебра

3 задачи

Задача 1

Пълен запис

Условие

Нека

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

е такава редица, че

a_{0}=\frac{1}{2}

a_{k+1}=a_{k}+\frac{a_{k}^{2}}{n}, \quad k=0, 1, \ldots, n

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

a_{n}\lt{}1\lt{}a_{n+1}

Решение

Имаме, че

\frac{1}{a_{k}}-\frac{1}{a_{k+1}}=\frac{1}{n+a_{k}}\lt{}\frac{1}{n}

и като сумираме при

k=0, \ldots n-1

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

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

, т. е.

a_{n}\lt{}1

. Тогава

\frac{1}{a_{k}}-\frac{1}{a_{k+1}}\gt{}\frac{1}{n+1}

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

\frac{1}{a_{0}}-\frac{1}{a_{n}}\gt{}\frac{n}{n+1}

, т. е.

a_{n}\gt{}\frac{n+1}{n+2}

. Оттук

a_{n+1}\gt{}\frac{n+1}{n+2}+\frac{(n+1)^{2}}{n(n+2)^{2}}=1+\frac{1}{n(n+2)^{2}}

Забележка. Във връзка с тази задача на читателите сигурно ще е интересно да видят и статията на проф. Николов в този брой.

Отвори задачатаБаза на maths.bgsomalg2017-9-1

Задача 2

Пълен запис

Условие

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

\alpha, \beta

\gamma

са ъгли в триъгълник, то

\frac{1}{3-2 \cos \alpha}+\frac{1}{3-2 \cos \beta}+\frac{1}{3-2 \cos \gamma} \geq \frac{3}{2}.

Решение

След полагането

x=2 \sin \frac{\alpha}{2}, y=2 \sin \frac{\beta}{2}, z=2 \sin \frac{\alpha}{2}

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

x, y, z\gt{}0

и (1)

x^{2}+y^{2}+z^{2}+x y z=4

, то

\frac{1}{1+x^{2}}+\frac{1}{1+y^{2}}+\frac{1}{1+z^{2}} \geq \frac{3}{2}

което е екивалентно на (2)

x^{2}+y^{2}+z^{2}+3 \geq x^{2} y^{2}+y^{2} z^{2}+z^{2} x^{2}+3 x^{2} y^{2} z^{2}

. Като използваме, че

x^{2} y^{2}+y^{2} z^{2}+z^{2} x^{2} \leq \frac{\left(x^{2}+y^{2}+z^{2}\right)}{3}

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

7-x y z \geq \frac{(4-x y z)^{2}}{3}+3 x^{2} y^{2} z^{2}

, което се преобразува до неравенството

(x y z-1)(2 x y z+1) \leq 0

. Остава да съобразим, че от

x^{2}+y^{2}+z^{2} \geq 3 \sqrt[3]{\vphantom{x^2}(x y z)^{2}}

и (1) следва, че

0\lt{}x y z \leq 1

Отвори задачатаБаза на maths.bgsomalg2017-9-2

Задача 3

Пълен запис

Условие

Нека

f

е полином с реални коефициенти и степен

n \geq 1

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

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

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

\sum_{i=0}^{n} a_{i} x^{2^{i}}

се дели на

f(x)

Решение

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

0 \leq i \leq n

имаме, че

x^{2^{i}}=q_{i}(x) f(x)+r_{i}(x)

, където

\operatorname{deg} r_{i} \leq n-1

. Тъй като всеки

n+1

вектора в

\mathbb{R}^{n}

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

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

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

\sum_{i=0}^{n} a_{i} r_{i}(x)=0

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

\sum_{i=0}^{n} a_{i} x^{2^{i}}=f(x) \sum_{i=0}^{n} a_{i} q_{i}(x)

Отвори задачатаБаза на maths.bgsomalg2017-9-3

2017 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

Даден е равнобедрен

\triangle A B C

(

A C=B C

), вписан в окръжност

k

. Нека

X

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

A B

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

k_{1}

k_{2}

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

A B

, до отсечката

C X

и вътрешно до

k

. Ако означим техните радиуси с

r_{1}

r_{2}

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

r_{1}+r_{2} \leq 2 r

където

r

е радиусът на вписаната в

\triangle A B C

окръжност.

Решение

Нека окръжността

k_{1}

е с център

I_{1}

и се допира до

A X

C X

в точките

P_{1}

Q_{1}

съответно, окръжността

k_{2}

е с център

I_{2}

и се допира до

B X

C X

в точките

P_{2}

Q_{2}

съответно, а вписаната в

\triangle A B C

окръжност е с център

I

и се допира до

A B

в точка

P

. От теоремата на Виктор-Тебо следва, че

I

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

I_{1} I_{2}

и нещо повече,

I

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

P_{1} Q_{1}

P_{2} Q_{2}

(Защо?). Без ограничение на общността нека

\angle A X C \leq 90^{\circ}

. Тогава

\frac{I_{1} I}{I I_{2}}=\frac{P_{1} P}{P P_{2}}=\operatorname{tg} \frac{\angle A X C}{2} \leq 1

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

M

на

I_{1} I_{2}

е между

I

I_{2}

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

A C= B C

, т. е.

r_{1} \geq r_{2}

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

M

до

A B

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

I

до

A B

, т. е.

\frac{r_{1}+r_{2}}{2} \leq r

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

r_{1}+r_{2}

се достига, когато

X

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

C

и допирната точка на външновписаната окръжност към страната

A B

A B

Отвори задачатаБаза на maths.bgsomgeo2017-9-1

Задача 2

Пълен запис

Условие

Даден е

\triangle A B C

. Нека

M

N

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

A C

B C

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

M N

образът

\omega^{\prime}

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

\triangle M N C

окръжност

\omega

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

A B

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

M

N

, окръжността

\omega

се допира до фиксирана окръжност.

Решение

Нека

T

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

\omega^{\prime}

A B

, а

P

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

\triangle A M T

\triangle B N T

. Без ограничение на общността нека

P

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

\triangle A B C

. Тогава

\angle M P N=360^{\circ}-\angle M P T-\angle N P T=

\alpha+\beta=180^{\circ}-\gamma,

т. е.

P \in \omega

(

P

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

\angle A P B=\angle A M T+\angle B N T=\gamma+\angle M T N=2 \gamma

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

\triangle A B P

окръжност се допира до

\omega

в точка

P

. Но

\begin{aligned} \angle M P A+\angle N P B & =\angle M T A+\angle N T B=180^{\circ}-\gamma= \\ & =(\angle M N P+\angle N M P)+(\angle A B P+\angle B A P), \end{aligned}

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

\triangle A B P

Отвори задачатаБаза на maths.bgsomgeo2017-9-2

Задача 3

Пълен запис

Условие

Даден е

\triangle A B C

и точка

T

върху страната

A B

. Да означим с

N

M

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

\triangle A T C

окръжност към страната

A C

със страната

A C

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

A T

. Съответно с

L

K

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

\triangle B T C

окръжност към страната

B C

със страната

B C

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

B T

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

M N

K L

, средата

X

на

C T

и центърът

I

на вписаната в

\triangle A B C

окръжност

k

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

T

съвпада с допирната точка на

k

A B

Решение

Нека

O_{1}

O_{2}

са центровете на разглежданите външновписани окръжности за

\triangle A T C

\triangle B T C

съответно,

P

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

M N

O_{1} T

, а

Q

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

K L

O_{2} T

. Точките

O_{1}, C, N

P

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

O_{2}, C, L

Q

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

\angle O_{1} P C=\angle O_{1} N C=90^{\circ}

\angle O_{2} Q C=\angle O_{2} L C=90^{\circ}

. Но

\angle O_{1} T O_{2}=90^{\circ}

, т. е.

P T Q C

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

X

на

C T

е среда и на

P Q

, и нещо повече,

P Q \| A B

(Защо?). Нека точките

D

E

от правата

P Q

са такива, че

M A D P

B K Q E

са успоредници. От теоремата на Щайнер за трапеца

M K Q P

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

M N

K L, X

I

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

X, I

и средата

Y

на

M K

лежат на една права, но отново от теоремата на Щайнер за трапеца

A B D E

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

Y

е среда на

A B

, т. е.

M A=B K

. Остава да съобразим, че

M A=B K

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

T

съвпада с допирната точка на вписаната в

\triangle A B C

окръжност с

A B

Отвори задачатаБаза на maths.bgsomgeo2017-9-3

2017 · Комбинаторика

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2017-9-1

Задача 2

Пълен запис

Условие

Даден е ориентиран граф

G

. Да се докаже, че ориентацията на някои (възможно нула) от ребрата на

G

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

H

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

H

няма цикли. (2) Най-дългият път между произволни два върха в

H

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

G

Решение

Да разгледаме всички подграфи на

G

, в които няма цикли. От всички такива графи да изберем граф

X

, който има най-много ребра. Да образуваме граф

H

, който се получава от

G

по следния начин: На ребрата от

X

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

X

променяме посоката. Ще докажем, че

H

изпълнява двете условия на задачата. (1) Тъй като в

X

няма цикли, то можем да номерираме върховете на

X

(а значи и на

G

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

X

свързва връх с по-малък номер с връх с по-голям номер. От максималността на

X

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

G

, което не е от

X

участва в цикъл с ребрата на

X

, т. е. свързва връх с по-голям номер с връх с по-малък номер. Но в

H

всички ребра от

G

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

X

са с променена посока. Това означава, че в

H

всяко ребро свързва връх с по-малък номер с връх с по-голям номер, т. е. в

G_{1}

няма цикли. (2) Да разгледаме път между два върха

a

b

H

. Нека този път включва ребро

x-y

от

G

с променена посока. Тъй като

y-x

участва в цикъл с ребра от

X

, то реброто

x-y

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

X

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

a

b

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

H

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

X

, а значи и само по ребра на

G

. От тук следва, че най-дългият път между произволни два върха в

H

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

G

Отвори задачатаБаза на maths.bgsomcomb2017-9-2

Задача 3

Пълен запис

Условие

Всички клетки на таблица

m \times n

, където

m

n

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

1 \times 2

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

1 \times 3

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

m \times n

Решение

Да номерираме редовете и стълбовете на таблицата съответно с числата от 1 до

m

и от 1 до

n

. Без ограничение нека празното квадратче е в клетка (

1; 1

). При всеки ход една от координатите на празното квадратче се променя с 2. Това означава, че празното квадратче може да заема само клетки с две нечетни координати. При това всяко домино може да заема само две положения. Да оцветим в зелено клетките с две нечетни координати. Да разгледаме множеството

A

от клетки, до които може да се стигне от клетката (

1; 1

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

A

по следния начин: За всеки правоъгълник

1 \times 3

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

a; b

) и (

p; q

) от контура на голямата таблица. Понеже

a+b

p+q

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

1 \times 3

, от който е получена тази червена клетка (в противен случай двете крайни клетки в правоъгълника

1 \times 3

ще бъдат от

A

). Това означава, че целият път от

(a; b)

до

(p; q)

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

A

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

Отвори задачатаБаза на maths.bgsomcomb2017-9-3

2017 · Теория на числата

3 задачи

Задача 1

Пълен запис

Условие

Да се реши в цели числа уравнението

2^{m}-37 n^{2}=19.

Решение

След умножение на двете страни по 4 уравнението може да се запише във вида

2\left(2^{m+1}-1\right)=37\left((2 n)^{2}+2\right).

Тъй като показателят на 2 по модул 37 е 36, то

36 \mid m+1

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

7=2^{3}-1 \mid 2^{m+1}-1

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

7 \nmid(2 n)^{2}+2

за никое

n \in \mathbb{Z}

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

Отвори задачатаБаза на maths.bgsomnt2017-9-1

Задача 2

Пълен запис

Условие

Нека

p

q

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

q\gt{}p

A_{k}=k^{p-1}+k^{p-2}+\cdots+k+1 \text{за} k \in\{1, 2, \ldots, q-1\}.

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

q

на числото

A_{1} A_{2} \ldots A_{q-1}

Решение

Ако

q \equiv 1(\bmod p)

, то

k^{p}-1 \mid k^{q-1}-1

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

x^{p} \equiv 1(\bmod q)

има решения в множеството

\{2, 3, \ldots, q-1\}

. Следователно в този случай

A_{1} A_{2} \ldots A_{q-1} \equiv 0(\bmod q)

. Нека

q \not \equiv 1(\bmod p)

. Тогава

k^{p} \equiv 1(\bmod q)

за

k \in\{2, 3, \ldots, q-1\}

е невъзможно (Защо?). Ако

k_{1}^{p} \equiv k_{2}^{p}(\bmod q)

за някои

k_{1}, k_{2} \in\{2, 3, \ldots, q-1\}, k_{1} \neq k_{2}

. Тогава

\left(k_{1} k_{2}^{-1}\right)^{p} \equiv 1(\bmod q)

, откъдето

k_{1} k_{2}^{-1} \equiv 1(\bmod q)

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

k_{2}^{-1}=k_{1}^{-1}

, т. е.

k_{2}=k_{1}

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

k^{p}-1, k \in\{2, 3, \ldots, q-1\}

, пробягват множеството

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

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

(k-1)^{-1}, k \in\{2, 3, \ldots, q-1\}

. Тогава

A_{2} A_{3} \ldots A_{q-1} \equiv

\prod_{k=2}^{q-1}\left(k^{p}-1\right) \prod_{k=2}^{q-1}(k-1)^{-1} \equiv 1 \quad

(\bmod q)

(използвахме теоремата на Уилсън), откъдето окончателно получаваме

A_{1} A_{2} \ldots A_{q-1} \equiv p(\bmod q)

Отвори задачатаБаза на maths.bgsomnt2017-9-2

Задача 3

Пълен запис

Условие

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

n

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

p\gt{}n

означаваме с

f_{p}(n)

броя на числата от множеството

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

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

p

. Естественото число

n

се нарича cnoкойно по отношение на квадратичните остатъи, и (споко), ако за всяко просто число

p\gt{}n

имаме

f_{p}(n) \geq \frac{n}{2}

. Да се определи дали 100 е споко.

Решение

Ще докажем, че 100 не е спокойно по отношение на квадратичните остатъци. За целта е достатъчно да докажем, че

f_{p}(100) \leq 49

за някое просто

p\gt{}100

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

p

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

[101, p-1]

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

[1, p-1]

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

[1, 100]

са по-малко от половината, т. е.

f_{p}(100) \leq 49

и значи 100 не е споко. Числото

p=109

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

102, 104, 105, 106

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

\left(102=50^{2}, 104=39^{2}, 105=43^{2}, 106=18^{2}, 108=33^{2}(\bmod 109)\right)

Отвори задачатаБаза на maths.bgsomnt2017-9-3

2018 · Алгебра

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomalg2018-9-1

Задача 2

Пълен запис

Условие

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

n

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

\sum_{i=1}^{n} \frac{1}{i^{2}+i+1}\lt{}\frac{4}{5}.

Решение

По индукция следва, че сумата не надминава

\frac{4}{5}-\frac{n+1}{(n+1)^{2}+2 / 7}

. Забележка.

\sum_{k=1}^{\infty} \frac{1}{k^{2}+k+1}=0, 7981 \ldots

Отвори задачатаБаза на maths.bgsomalg2018-9-2

Задача 3

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomalg2018-9-3

2018 · Комбинаторика

3 задачи

Задача 1

Пълен запис

Условие

По колко начина числата

1, 2, \ldots, 2 n

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

2 \times n

, така че числата във всеки ред (отляво надясно) и във всеки стълб (отгоре надолу) да са в нарастващ ред.

Решение

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

1, 2, \ldots, k

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

k

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

k

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

k

. Вярно е и обратното: ако в

1, 2, \ldots, k

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

k

е по-малко от

k

. Следователно редицата от 0 и 1 е с дължина

2 n

и изпълнява следното свойство: Във всяка частична редица

1, 2, \ldots, k

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

\frac{1}{n+1}\binom{2 n}{n}.

Отвори задачатаБаза на maths.bgsomcomb2018-9-1

Задача 2

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2018-9-2

Задача 3

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2018-9-3

2018 · Теория на числата

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomnt2018-9-1

Задача 2

Пълен запис

Условие

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

n \geq 2

, за които числото

\left(n^{2}\right)!-n^{2}

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

a

b

, за които

|a-b|\lt{}n

Решение

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

\left(n^{2}\right)!-n^{2}=a(a+x)

, където

x\lt{}n

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

\left(n^{2}\right)!-\left(n^{2}-x^{2}\right)=a^{2}+a x+x^{2}

Нека

n \geq 3

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

\left(n^{2}\right)!

има кратен на 3, който е различен от

n^{2}-x^{2}

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

\left(n^{2}-x^{2}\right)(3 k-1)=a^{2}+a x+x^{2}

, където

k

е естествено число. Тогава лявата страна има прост делител

p

от вида

3 s-1

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

p \mid a

p \mid x

(защото

a^{2}+a x+x^{2} \equiv 0(\bmod p)

дава

a^{3} \equiv x^{3}(\bmod p)

, откъдето при

(a, p)=(x, p)=1

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

a x^{-1}

по модул

p

дели

(3, p-1)=1

, т. е

a \equiv x(\bmod p)

и значи

p \mid 3 a^{2}

, противоречие). Може да изберем простото число

p

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

3 k-1

да е нечетна. Сега е ясно, че степента на

p

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

3 k-1

и значи е нечетна и в

n^{2}-x^{2}

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

x

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

p

отдясно е по-малка). Следователно

n=2

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

(4!)^{2}-2^{2}=20=4 \cdot 5

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

Отвори задачатаБаза на maths.bgsomnt2018-9-2

Задача 3

Пълен запис

Условие

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

k

съществуват безбройно много естествени числа

n

, за които

n \mid 2^{n+k}-1

Решение

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

k

съществува

n

, за което

n \mid 2^{n+k}-1

k+n \geq 7

. Наистина, при

k \geq 6

работа върши тривиалното

n=1

, а при

k \leq 5

ще посочим двойките

(k, n)=(1, 15), (2, 7), (3, 5), (4, 31), (5, 3).

Нека

k

е фиксирано и

n \in \mathbb{N}

е такова, че

n+k \geq 7

n \mid 2^{n+k}-1

. Ще конструираме

n_{1}\gt{}n

, което дели

2^{n_{1}+k}-1

. От теоремата на Жигмонди следва, че съществува просто число

p

, което дели

2^{n+k}-1

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

2^{i}-1

за

i\lt{}n+k

. Това означава, че показателят на 2 по модул

p

е равен на

n+k

, откъдето

n+k \mid p-1

. Тогава

p n+k=(p-1) n+n+k

се дели на

n+k

и имаме

2^{n+k}-1 \mid 2^{p n+k}-1

. Оттук

p

n

делят

2^{n+k}-1

и са взаимнопрости, защото

p\gt{}n+k\gt{}n

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

p n \mid 2^{p n+k}-1

, т. е.

n_{1}=p n\gt{}n

има исканото свойство.

Отвори задачатаБаза на maths.bgsomnt2018-9-3

2019 · Алгебра

3 задачи

Задача 1

Пълен запис

Условие

Нека

f(x)=x^{2}+a x+1, f_{1}(x)=f(x), f_{n+1}(x)=f\left(f_{n}(x)\right)

n \geq 1

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

a

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

f_{a}(x)=0

има поне един реален корен.

Решение

Лесно се вижда, че при

a=1

a=2

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

f(x)=b

има реално решение при

b \geq 1-\frac{a^{2}}{4}

и в този случай

x_{1}=\frac{-a+\sqrt{\vphantom{x^2}a^{2}+4 b-4}}{2} \geq-\frac{a}{2}

. Нека

a=3

. Тогава уравнението

f(x)=0

има корен

x_{1}=\frac{-3+\sqrt{\vphantom{x^2}5}}{2}

, уравнението

f(x)=x_{1}

има реален корен

x_{2}=\frac{-3+\sqrt{\vphantom{x^2}5+4 x_{1}}}{2} \geq 1-\frac{9}{4}

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

f(x)=x_{2}

има реален корен

x_{3}

. Тогава

f_{3}\left(x_{3}\right)=f_{2}\left(f\left(x_{3}\right)\right)=

f_{2}\left(x_{2}\right)=f\left(f\left(x_{2}\right)\right)=f\left(x_{1}\right)=0.

Нека сега

a \geq 4

. Тогава уравнението

f(x)=0

има реален корен

x_{1}=\frac{-a+\sqrt{\vphantom{x^2}a^{2}-4}}{2} \geq-\frac{a}{2}\gt{}1-\frac{a^{2}}{4}

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

x_{1}, x_{2}, \ldots, x_{a}

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

f(x)=x_{k}

има решение

x_{k+1}

при

k=1, 2, \ldots, a-1

. Тогава

f_{a}\left(x_{a}\right)=f_{a-1}\left(f\left(x_{a}\right)\right)=f_{a-1}\left(x_{a-1}\right)=\cdots=f\left(x_{1}\right)=0

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

a

са всички

a \geq 3

Отвори задачатаБаза на maths.bgsomalg2019-9-1

Задача 2

Пълен запис

Условие

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

\left\{a_{k}\right\}

, за която

a_{1}=1

a_{k}=a_{k-1}+a_{[k / 2]}

при

k\gt{}1

. Възможно ли е някой член на тази редица да се дели на 4?

Решение

Първи начин. Ако

n

е нечетно, то

a_{n}

също е нечетно. Действително,

a_{2 k+1}=a_{2 k}+a_{k}=a_{2 k-1}+2 a_{k}

показва, че

a_{2 k-1}

a_{2 k+1}

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

a_{1}

е нечетно. Ще докажем по индукция, че

a_{4 k} \equiv a_{k}(\bmod 4)

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

\begin{aligned} a_{4 k+4} & =a_{4 k+3}+a_{2 k+2}=a_{4 k+2}+2 a_{2 k+1}+a_{k+1}=a_{4 k+1}+3 a_{2 k+1}+a_{k+1}= \\ & =a_{4 k}+3 a_{2 k+1}+a_{2 k}+a_{k+1}=a_{4 k}+4 a_{2 k+1}+a_{k+1}-a_{k} \end{aligned}

откъдето

a_{4(k+1)}-a_{k+1} \equiv a_{4 k}-a_{k}(\bmod 4)

. Сега ще докажем, че ако

n \equiv 2(\bmod 4)

, то

a_{n} \equiv 2(\bmod 4)

. Имаме последователно

\begin{aligned} a_{4 k+2} & =a_{4 k+1}+a_{2 k+1}=a_{4 k}+a_{2 k}+a_{2 k+1}= \\ & =a_{4 k}-a_{k}+2 a_{2 k+1} \equiv 2 a_{2 k+1} \quad(\bmod 4) \end{aligned}

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

a_{2 k+1}

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

a_{n}

е този от тях с най-малък индекс. Тогава от горното следва, че

n

се дели на 4. Но сега

a_{n / 4}

също се дели на 4, противоречие с избора на

n

. Втори начин. Нека

n=2^{k} m

, където

m

е нечетно число. Тогава с индукция по

n

се доказва, че: (1) ако

k

е нечетно, то

a_{n} \equiv 2(\bmod 4)

; (2) ако

k

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

n

съдържа

s(n)

цифри, то

a_{n} \equiv 2 s(n)-1(\bmod 4)

Отвори задачатаБаза на maths.bgsomalg2019-9-2

Задача 3

Пълен запис

Условие

Нека е медицентърът на

\triangle A B C

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

\sin \angle M B C+\sin \angle M C A+\sin \angle M A B \leq \frac{3}{2}

Решение

Нека

D

е петата на перпендикуляра от

M

към

B C

. Тъй като

S_{A M B}=S_{B M C}=S_{C M A}

, то

M D=\frac{h_{a}}{3}

, където

h_{a}

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

A

. Понеже

B M=\frac{2 m_{b}}{3}

, където

m_{b}

е дължината на медианата през

B

, то

\sin \angle M B C=\frac{h_{a}}{2 m_{b}}

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

\frac{h_{a}}{m_{b}}+\frac{h_{b}}{m_{c}}+\frac{h_{c}}{m_{a}} \leq 3.

От неравенството на Коши-Буняковски-Шварц следва, че

\left(\frac{h_{a}}{m_{b}}+\frac{h_{b}}{m_{c}}+\frac{h_{c}}{m_{a}}\right)^{2} \leq

\left(h_{a}^{2}+h_{b}^{2}+h_{c}^{2}\right)\left(\frac{1}{m_{a}^{2}}+\frac{1}{m_{b}^{2}}+\frac{1}{m_{c}^{2}}\right)=: X.

Значи е достатъчно да докажем, че

X \leq 9

. Нека

(x, y, z)=\left(a^{2}, b^{2}, c^{2}\right)

. Да отбележим, че

h_{a}^{2}+h_{b}^{2}+h_{c}^{2}=4 S_{A B C}^{2} \cdot \frac{x y+y z+z x}{x y z}

\begin{aligned} & =\frac{\left(2(x y+y z+z x)-x^{2}-y^{2}-z^{2}\right)(x y+y z+z x)}{4 x y z} \\ \frac{1}{m_{a}^{2}}+\frac{1}{m_{b}^{2}}+ & \frac{1}{m_{c}^{2}}=\frac{36(x y+y z+z x)}{(2 x+2 y-z)(2 y+2 z-x)(2 z+2 x-y)} \end{aligned}

Тогава

X \leq 9

е еквивалентно на

\begin{gathered} x y z(2 x+2 y-z)(2 y+2 z-x)(2 z+2 x-y)+\left(x^{2}+y^{2}+z^{2}\right)(x y+y z+z x)^{2} \\ \geq 2(x y+y z+z x)^{3} \end{gathered}

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

(x-y)^{2}(y-z)^{2}(z-x)^{2} \geq 0

, което е очевидно.

Отвори задачатаБаза на maths.bgsomalg2019-9-3

2019 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

Даден е успоредник

A B C D

. Права

\ell

през

C

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

A D

A B

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

P

Q

(

D

е между

A

P, B

е между

A

Q

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

M

, такава, че когато

\ell

се мени,

M C

е ъглополовяща на

\angle P M Q

Решение

Нека

M

е симетричната точка на

C

относно

B D

. Тогава

D B M A

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

\angle A D M=\angle A B M

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

\frac{M B}{B Q}=\frac{B C}{B Q}=\frac{D P}{D C}=\frac{D P}{D M}

т. е.

\triangle M B Q \sim \triangle M D P

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

\frac{M P}{M Q}=\frac{D P}{B M}=\frac{D P}{B C}=\frac{P C}{Q C}

, т. е.

M C

е ъглополовяща на

\angle P M Q

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

Отвори задачатаБаза на maths.bgsomgeo2019-9-1

Задача 2

Пълен запис

Условие

Даден е

\triangle A B C

, вписан в окръжност

k

с център

O

. Нека

P

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

\triangle A B C

, различна от

O

. Правите

A P, B P

C P

пресичат

k

за втори път в точките

A_{1}, B_{1}

C_{1}

съответно. Нека

A_{2}, B_{2}

C_{2}

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

A_{1}, B_{1}

C_{1}

относно правата

O P

. Да означим с

\ell_{a}

правата през средата на

B C

, успоредна на

A A_{2}

. По аналогичен начин се дефинират правите

\ell_{b}

\ell_{c}

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

\ell_{a}, \ell_{b}

\ell_{c}

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

Решение

Достатъчно е да докажем, че

A A_{2}, B B_{2}

C C_{2}

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

\ell_{a}, \ell_{b}

\ell_{c}

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

\triangle A B C

и коефициент

-1 / 2

. Да забележим, че

\angle A O A_{2}=\angle A P A_{2}

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

\triangle O A A_{2}

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

P

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

k

, то образът на описаната около

\triangle O A A_{2}

окръжност е правата

A A_{2}

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

A A_{2}

минава през образа

P^{\prime}

на

P

при тази инверсия. Аналогично

B B_{2}

C C_{2}

ще минават през

P^{\prime}

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

Отвори задачатаБаза на maths.bgsomgeo2019-9-2

Задача 3

Пълен запис

Условие

Даден е

\triangle A B C

, вписан в окръжност

k

и нека

X

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

A B

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

\omega_{1}

\omega_{2}

с центрове

U_{1}

U_{2}

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

A B

, до отсечката

C X

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

k

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

S

на отсечката

U_{1} U_{2}

Решение

Нека

O

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

k

за

\triangle A B C, I

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

\ell

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

A B

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

k

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

C

както е изобразено на чертежа. Забелязваме, че

U_{1}

U_{2}

се намират на едно и също разстояние както от

O

, така и от правата

\ell

, т. е. при движението на

X

по

A B

описват парабола с фокус

O

и директриса

\ell

. От друга страна, от теоремата на Виктор Тебо следва, че

U_{1} U_{2}

минава през центъра

I

на вписаната в

\triangle A B C

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

X

. Остава да съобразим, че при това положение средата

S

на

U_{1} U_{2}

също описва парабола (в случая на окръжност този факт е очевиден, но се оказва валиден и в общия случай на коника). Тази парабола е отново с директриса, успоредна на

A B

(нейната ос на симетрия минава през средата на

O I

и е перпендикулярна на

A B

), минава през

I

, а краищата и

S_{1}

S_{2}

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

A

B

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

\triangle A B C

. Това са граничните случаи, когато

X \equiv A

X \equiv B

съответно.

Отвори задачатаБаза на maths.bgsomgeo2019-9-3

2019 · Комбинаторика

6 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomcomb2019-9-1

Задача 1b

Пълен запис

Условие

Във футболен турнир участват 6 отбора, които играят по веднъж всеки срещу всеки. За победа, равенство и загуба се присъждат съответно 3, 1 и 0 точки. Оказало се, че в крайното класиране разликата между всеки два съседни отбора е 2 точки. Колко победи има четвъртият в класирането?

Решение

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

s, s+2, \ldots, s+10

, а

T

е сумата им, т. е.

T=6 s+30

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

d

. Тогава

T=2 d+3(15-d)=45-d

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

T

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

T \in\{30, 36, 42\}

. Ако

T=30

, то

d=15

, т. е. всички срещи са завършили наравно, което е невъзможно. Ако

T=36

, то

d=9

s=1

. Отборът с 1 точка е завършил наравно един мач и е изгубил останалите четири, а отборът с 3 точки е изгубил поне два мача. Освен това отборът победител е спечелил поне 3 срещи, което означава, че поне една от тях е срещу отборите от второ до четвърто място. Получихме общо

4+2+1=7

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

d=9

. При

T=42

имаме

d=3

s=2

. Тогава отборите са спечелили съответно по

2, 1, 0, 2, 1, 0

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

Отвори задачатаБаза на maths.bgsomcomb2019-9-1b

Задача 2

Пълен запис

Условие

Едно естествено число

A

ще наричаме

k

-специално, ако е произведение на

k

различни прости числа. (Ненаредена) двойка естествени числа (

d_{1}, d_{2}

) наричаме

\kappa л а с{ }{ }^{\text{нескa}}

, ако частното на по-голямото към по-малкото е просто число. Да се намерят всички естествени числа

n

със следното свойство: за всяко 2019-специално

A

класическите (ненаредени) двойки от делители на числото

A^{n}

могат да се разбият на непресичащи се множества

\left\{S_{i}\right\}_{i=1}^{k}

от по 2019 елемента, така че за всяко

i

има делител

d_{i}

на

A^{n}

, който да е част от всички двойки в

S_{i}

. Например,

n=1

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

k=2

, защото за всяко

A=p_{1} p_{2}

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

4: \left\{\left(1, p_{1}\right), \left(1, p_{2}\right), \left(p_{1}, A\right), \left(p_{2}, A\right)\right\}

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

Решение

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

n

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

A=p_{1} \ldots p_{2019}

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

n

. Всички делители на

A^{n}

са от вида

p_{1}^{\alpha_{1}} \ldots p_{2019}^{\alpha_{2019}}, \alpha_{i} \in\{0, 1, \ldots, n\} \forall i

и може да ги илюстрираме като точки в 2019 -мерното пространство с целочислени координати

\left(\alpha_{1}, \ldots, \alpha_{2019}\right)

. Така отъждествихме множеството от делителите на

A^{n}

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

[0, n]^{2019}

. Два делителя образуват класическа двойка тогава и само тогава, когато отговарят на съседни точки в решетката, т. е. класическите двойки се отъждествяват с ребрата на решетката. От своя страна, условията върху разбиването на множеството от класическите двойки делители е еквивалентно на разбиване на ребрата на решетката в непресичащи се конструкции от по 2019 две по две перпендикулярни ребра с общо начало (т. е. локална координатна система в целочислена точка от мрежата). Остава да фиксираме началните точки на тези локални координатни системи и да определим ориентацията на координатните оси. Да оцветим в червено всички целочислени точки, за които

\alpha_{1}+\cdots+\alpha_{2019} \equiv 0(\bmod n+1)

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

B=\left(\beta_{1}, \ldots, \beta_{2019}\right)

. Върху всяка от координатните оси през

B

лежат по точно

n+1

точки от решетката (включая

B

), като за всеки две съседни точки разликата от сумите от координатите им е точно 1. Следователно, тези суми образуват пълна система от остатъци по модул

n+1

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

Отвори задачатаБаза на maths.bgsomcomb2019-9-2

Задача 2b

Пълен запис

Условие

Дадени са 1000 топки от 40 различни цвята, по 25 от всеки цвят. Да се намери минималното

n

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

n

поредни топки от поне 20 различни цвята.

Решение

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

18 \cdot 25+2=452

поредни топки. Ще докажем, че 452 топки са и достатъчни. Да разгледаме произволно разположение и множеството от всички „дъги“ от точки, при които имаме точно 20 цвята (това множество не е празно!). Нека

A

е "дъга" с 20 цвята и минимална дължина и първата топка от

A

е бяла. Ако в

A

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

A

. По същия начин се вижда, че последната топка (която не е бяла) също е уникална. Следователно имаме по една топка от два различни цвята и най-много

18 \cdot 25=450

топки от други цветове между тях, общо най-много 452.

Отвори задачатаБаза на maths.bgsomcomb2019-9-2b

Задача 3

Пълен запис

Условие

При подготовката на математическия бой към COM, проф. Бойваленков си бе поставил амбициозна задача. Той искаше да състави най-различни проекто-отбори за състезанието измежду поканените 43 ученици така, че:

(*)

Всеки проекто-отбор да е съставен от поне трима ученици.

(*)

Всеки два проекто-отбора да имат точно един общ участник.

(*)

Независимо кои двама ученици дойдат първи за състезанието, да могат да са съотборници. Възможно ли е това? Ако е възможно, да се даде пример.

Решение

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

\mathrm{c}\left\{c_{1}, \ldots, c_{43}\right\}

, а проекто-отборите с

\left\{T_{1}, T_{2}, \ldots\right\}

. Първо ще докажем, че е необходимо броят проекто-отбори да е 43, като всеки от тези отбори трябва да включва точно 7 ученика, а всеки ученик участва в точно 7 различни проекто-отбора. Разглеждаме произволен отбор

T

и произволен ученик

c \notin T

, който не е част от отбора. Да означим броя участници в

T

k \geq 3

. Тогава всеки отбор

T^{\prime}

, за който

c \in T^{\prime}

, има по точно един общ участник с

T

, като различните отбори имат различен общ участник (заради условие 2 ) и всеки различен участник в

T

е в общ отбор с

c

(заради условие 3). Следователно

c

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

k

раз- лични отбора и всеки отбор, в който

c

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

k

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

c^{\prime} \in T

от отбора

T

и да разгледаме единствения отбор

T^{\prime \prime}

, за който

\left\{c, c^{\prime}\right\} \in T^{\prime \prime}

. От условие 1 следва, че съществува и трети ученик

c^{\prime \prime} \notin\left\{c, c^{\prime}\right\}, c^{\prime \prime} \in T^{\prime \prime}

. Имаме, че

c^{\prime \prime} \notin T

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

k \geq 3

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

T^{\prime \prime \prime}

такъв, че

c^{\prime \prime} \in T^{\prime \prime \prime}

\left\{c, c^{\prime}\right\} \notin T^{\prime \prime \prime}

. От

c \notin T^{\prime \prime \prime}

следва, че

\left|T^{\prime \prime \prime}\right|=k

, а от

c^{\prime} \notin T^{\prime \prime \prime}

следва, че

c^{\prime}

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

k

различни отбора. Но

c^{\prime}

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

T

и значи всички участници в този отбор участват в по

k

отбора. Получихме, че всички ученици участват в точно

k

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

k

участници. Оттук следва, че броят ученици е равен на броя отбори, т. е. трябва да се съставят 43 отбора. Но ние имаме броя отбори като функция на

k

, защото от условие 2 следва че всички отбори имат по точно един общ участник с

T

и значи

k(k-1)+1=43

, т. е.

k=7

. Конструираме матрицата

\left\{A_{i j}\right\}

по следния начин:

A_{i j}= \begin{cases}1, & c_{i} \in T_{j} \\ 0, & c_{i} \notin T_{j}\end{cases}

От доказаното дотук получаваме, че

A

е с размери

43 \times 43

и условия

1-3

са еквивалентни на

(*)

\sum_{k=1}^{43} A_{k i}=\sum_{k=1}^{43} A_{i k}=7, \forall i=1, 2, \ldots, 43

(*)

\sum_{k=1}^{43} A_{k i} A_{k j}=\sum_{k=1}^{43} A_{i k} A_{j k}= \begin{cases}1, & i \neq j; \\ 7, & i=j.\end{cases}

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

x_{1}, x_{2}, \ldots, x_{43}

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

\left\{z_{i}\right\}_{1}^{43}

посредством:

z_{i}: =\sum_{k=1}^{43} A_{k i} x_{k}.

Всяко от тези числа е сума на 7 от хиксовете, в частност е тяхна линейна комбинация. Директно се проверява, че

\begin{aligned} \sum_{k=1}^{43} z_{k}^{2} & =\sum_{k}\left(\sum_{i, j} A_{i k} A_{j k} x_{i} x_{j}\right)=\sum_{i, j}\left(\sum_{k} A_{i k} A_{j k}\right) x_{i} x_{j} \\ & =6 \sum_{k} x_{k}^{2}+\underbrace{\left(\sum_{k} x_{k}\right)^{2}}_{: =s^{2}}. \end{aligned}

Ясно е, че

s

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

6 x_{44}^{2}

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

\left\{y_{i}\right\}_{1}^{44}

посредством

\begin{aligned} y_{4 i+1} &: =x_{4 i+1}-2 x_{4 i+2}-x_{4 i+3} \\ y_{4 i+2} &: =2 x_{4 i+1}+x_{4 i+2}+x_{4 i+4} \\ y_{4 i+3} &: =x_{4 i+1}+x_{4 i+3}-2 x_{4 i+4} \\ y_{4 i+4} &: =-x_{4 i+2}+2 x_{4 i+3}+x_{4 i+4} \end{aligned}

за всяко

i=0, 1, \ldots, 10

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

6 \sum_{k} x_{k}^{2}=\sum_{k} y_{k}^{2}

и значи

\sum_{k=1}^{43} z_{k}^{2}+6 x_{44}^{2}=\sum_{k=1}^{44} y_{k}^{2}+s^{2}

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

x_{1}, x_{2}, \ldots, x_{44}

. Остава да съобразим, че при подходящ избор на числата

x_{1}, \ldots, x_{43}

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

Y

, такова че

Y^{2}=\sum_{k=1}^{44} y_{k}^{2}-\sum_{k=1}^{43} z_{k}^{2}

. Ще илюстрираме само първата стъпка. Без ограничени на общността, с точност до преномериране на редовете и стълбовете на

A

, можем да считаме,

A_{11}=1

и значи

z_{1}=x_{1}+A_{21} x_{2}+\ldots

Тъй като

y_{1}=x_{1}-2 x_{2}-x_{3}

, ако изберем

x_{1}: =

-\frac{\left(A_{21}-2\right) x_{2}+\left(A_{31}-1\right) x_{3}+A_{41} x_{4}+\cdots+A_{43, 1} x_{43}}{2}

си гарантираме

y_{1}+z_{1}=0

и значи

y_{1}^{2}=z_{1}^{2}

. Останалите

y_{2}, \ldots, y_{44}

z_{2}, \ldots, z_{43}

са линейни комбинации на

x_{2}, \ldots, x_{44}

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

i

да фиксираме

x_{i}

да е подходящо избрана линейна комбинация с рационални коефициенти на

x_{i+1}, \ldots, x_{44}

, така че да съществуват двойка

j, k

със свойството

y_{j} \pm z_{k}=0

, което води до

y_{j}^{2}=z_{k}^{2}

. Така, стигнахме до тъждеството

6 x_{44}^{2}=Y^{2}+s^{2},

където

Y

s

са рационални числа, функции на

x_{44}

, а

x_{44}

е произволно рационално. Нека сега вземем

x_{44}=1, Y=A / B, s=C / D

, където

A, B, C, D

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

u, v, w

, такива че

6 w^{2}=u^{2}+v^{2},

което е невъзможно и по модул 2 и по модул 3. Следователно, такава матрица

A

не съществува! Забележка: Втората част от решението е доказателство, че не съществува крайна проективна равнина от ред 6. Това следва и директно от теоремата на Брук-Райзър, тъй като

6 \equiv 2(\bmod 4)

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

Отвори задачатаБаза на maths.bgsomcomb2019-9-3

Задача 3b

Пълен запис

Условие

Нека

A

е множество от функции

f: \mathbb{R} \rightarrow \mathbb{R}

със следното свойство: за всеки две функции

f_{1}, f_{2} \in A

съществува функция

f_{3} \in A

, такава, че

f_{1}\left(f_{2}(y)-x\right)+2 x=f_{3}(x+y)

за всички

x, y \in \mathbb{R}

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

f(x-f(x))=0

за всяка функция

f \in A

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

x

Решение

Полагането

x=0

дава

f_{1}\left(f_{2}(y)\right)=f_{3}(y)

за всяко

y

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

f_{1}

f_{2}

функция е тяхната композиция. Сега полагаме

x=-y

и получаваме

f_{1}\left(f_{2}(y)+y\right)-2 y=f_{3}(0)=f_{1}\left(f_{2}(0)\right)

. Това важи и за двойката функции (

f_{3}, f_{2}

), т. е.

f_{3}\left(f_{2}(y)+y\right)-2 y=f_{3}\left(f_{2}(0)\right)

. Връщайки се към двойката (

f_{1}, f_{2}

), полагаме

x=f_{2}(y)

и получаваме

f_{1}(0)+2 f_{2}(y)=f_{3}\left(f_{2}(y)+y\right)=2 y+f_{3}\left(f_{2}(0)\right)

. Оттук следва, че

f_{2}(y)=y+a

, където

2 a=f_{3}\left(f_{2}(0)\right)-f_{1}(0)

, т. е.

a

е константа и

f_{2}

е линейна функция. Последното важи за всяка функция

f \in A

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

f(x-f(x))=f(x-(x+a))=f(-a)=0.

Отвори задачатаБаза на maths.bgsomcomb2019-9-3b

2019 · Теория на числата

8 задачи

Задача 1

Пълен запис

Условие

Нека

\operatorname{gcd}\left(x_{1}, \ldots, x_{n}\right)

означава най-големия общ делител на естествените числа

x_{1}, \ldots, x_{n}

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

\operatorname{gcd}\left(\binom{n-1}{k-1}, \binom{n}{k+1}, \binom{n+1}{k}\right)=\operatorname{gcd}\left(\binom{n-1}{k}, \binom{n+1}{k+1}, \binom{n}{k-1}\right)

. Тук

\binom{n}{k}=\frac{n!}{k!(n-k)!}

Решение

Ясно е, че

\begin{array}{r} \operatorname{gcd}\left(\binom{n-1}{k-1}, \binom{n}{k+1}, \binom{n+1}{k}\right)=\operatorname{gcd}\left(\binom{n}{k} \frac{k}{n}, \binom{n}{k} \frac{n-k}{k+1}, \binom{n}{k} \frac{n+1}{n+1-k}\right), \cr \operatorname{gcd}\left(\binom{n-1}{k}, \binom{n+1}{k+1}, \binom{n}{k-1}\right)=\operatorname{gcd}\left(\binom{n}{k} \frac{n-k}{n}, \binom{n}{k} \frac{n+1}{k+1}, \binom{n}{k} \frac{k}{n+1-k}\right). \end{array}

Нека

p

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

a

- естествено число. С

\lambda_{p}(a)

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

p

, която дели

a

. Трябва да докажем, че най-високата степен на

p

, която дели лявата страна на исканото равенство е равна на най-високата степен на

p

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

\begin{array}{r} \min \left(\lambda_{p}(k)-\lambda_{p}(n), \lambda_{p}(n-k)-\lambda_{p}(k+1), \lambda_{p}(n+1)-\lambda_{p}(n+1-k)\right)= \tag{1}\cr \min \left(\lambda_{p}(n-k)-\lambda_{p}(n), \lambda_{p}(n+1)-\lambda_{p}(k+1), \lambda_{p}(k)-\lambda_{p}(n+1-k)\right). \end{array}

Ако положим

\left. x_{1}=\lambda_{p}(k)-\lambda_{p}(n), y_{1}=\lambda_{p}(n-k)-\lambda_{p}(k+1), z_{1}=\lambda_{p}(n+1)-\lambda_{p}(n+1-k)\right)

x_{2}=\min \left(\lambda_{p}(n-k)-\lambda_{p}(n), y_{2}=\lambda_{p}(n+1)-\lambda_{p}(k+1), z_{2}=\lambda_{p}(k)-\lambda_{p}(n+1-k)\right.

, равенство (1) е еквивалентно на

\min \left(x_{1}, y_{1}, z_{1}\right)=\min \left(x_{2}, y_{2}, z_{2}\right), \tag{2}

като при това

x_{1}+y_{1}+z_{1}=x_{2}+y_{2}+z_{2}. \tag{3}

Очевидно е, че ако

\lambda_{p}(a) \leq \lambda_{p}(b)

, то

\lambda_{p}(a)=\lambda_{p}(|a \pm b|)

. Оттук, ако

\lambda_{p}(k) \leq \lambda_{p}(n)

, то

\lambda_{p}(k)=\lambda_{p}(n-k)

x_{1}=x_{2}

. Ако

\lambda_{p}(k)\gt{}\lambda_{p}(n)

, то

\lambda_{p}(n-k)=\lambda_{p}(n)

x_{1}\gt{}0, x_{2}=0

, т. е.

\min \left(x_{1}, x_{2}\right)=0

. Така доказахме, че имаме

x_{1}=x_{2}

или

\min \left(x_{1}, x_{2}\right)=0

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

y_{1}=y_{2}

или

\min \left(y_{1}, y_{2}\right)=0

, както и че

z_{1}=z_{2}

или

\min \left(z_{1}, z_{2}\right)=0

. Нека

x_{1}=x_{2}

y_{1}=y_{2}

. Тогава от (3) следва

z_{1}=z_{2}

и (2) е очевидно. Ако

x_{1}=x_{2}, y_{1} \neq y_{2}, z_{1} \neq z_{2}

, то без ограничение на общността

y_{1}\gt{}y_{2}=0, z_{1}\lt{}z_{2}=0

. Сега минимумът е 0 или

x_{1}=x_{2}

и (2) е очевидно. Накрая при

x_{1} \neq x_{2}, y_{1} \neq y_{2}, z_{1} \neq z_{2}

от (3) отново получаваме

\min \left(x_{1}, y_{1}, z_{1}\right)=\min \left(x_{2}, y_{2}, z_{2}\right)=0.

Отвори задачатаБаза на maths.bgsomnt2019-9-1

Задача 2

Пълен запис

Условие

Дадени са естествени числа

m

n

, за които

m \leq \frac{n^{2}}{4}

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

m

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

n

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

m

дели

n!

Решение

Достатъчно е да докажем, че ако

p^{k} \mid m

, то

p^{k} \mid n!

. Ако

k=1

, то

p \mid m

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

p \leq n

, което означава, че

p \mid n!

. При

k\gt{}1

от

p^{k} \leq m \leq \frac{n^{2}}{4}

получаваме

n \geq 2 \sqrt{\vphantom{x^2}p^{k}}

. Ако

n \geq k p

, то поне

k

от числата

1, 2, \ldots, n

се делят на

p

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

p^{k} \mid n!

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

2 \sqrt{\vphantom{x^2}p^{k}} \geq k p

или еквивалентно

p^{\frac{k-2}{2}} \geq \frac{k}{2} \tag{1}

При

k=2

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

k \geq 4

имаме

p^{\frac{k-2}{2}} \geq 2^{\frac{k-2}{2}} \geq \frac{k}{2}

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

k=3

неравенство (1) е вярно при

p\gt{}2

, а при

p=2

получаваме

m \geq 8

, откъдето

n\gt{}5

n!

се дели на 8.

Отвори задачатаБаза на maths.bgsomnt2019-9-2

Задача 3

Пълен запис

Условие

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

m

, за които

2^{m}+1

дели

5^{m}-1

Решение

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

m

с исканото свойство. Ако

m

е нечетно, то

3\left|2^{m}+1\right| 5^{m}-1

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

n=2 k

k

е нечетно, то

5\left|2^{m}+1\right| 5^{m}-1

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

m=2^{n} t

, където

n \geq 2

t

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

t

е нечетно, и нека

F_{n}=2^{2^{n}}+1

n

-тото число на Ферма. Тогава

F_{n} \equiv 2(\bmod 5)

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

p

, което дели

F_{n}

и за което

p \equiv \pm 2 (\bmod 5)

. Ясно е, че

p\left|F_{n}\right| 2^{2^{n}} t+1=2^{m}+1 \mid 5^{m}-1

. Известно е (и се доказва лесно с разглеждане на показателя на 2 по модул

p

), че

p \equiv 1\left(\bmod 2^{n+1}\right)

; нека

p=2^{n+1} q+1

, където

q

е естествено число. От

p \equiv \pm 2(\bmod 5)

следва, че

p

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

p

. Тогава по критерия на Ойлер имаме

5^{(p-1) / 2} \equiv-1(\bmod p)

, т. е.

5^{2^{n} q} \equiv-1 (\bmod p)

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

5^{m q}=5^{2^{n} q t} \equiv(-1)^{t}=-1(\bmod p)

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

5^{m} \equiv 1(\bmod p)

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

Отвори задачатаБаза на maths.bgsomnt2019-9-3

Задача 4

Пълен запис

Условие

Нека

a_{1} \leq a_{2} \leq \cdots\lt{}a_{100}

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

a_{1}+a_{2}+\cdots+a_{100}\gt{}0

100\left(a_{1}^{2}+a_{2}^{2}+\cdots+a_{100}^{2}\right)=

2\left(a_{1}+a_{2}+\cdots+a_{100}\right)^{2}.

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

a_{51}\gt{}0

Решение

Ще наричаме

\left(a_{1}, \ldots, a_{100}\right)

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

a_{1}+\cdots+a_{100}=50

. Нека

1\lt{}\ell\lt{}100

е индекс, за който

a_{1} \leq \cdots \leq a_{\ell} \leq 0\lt{} a_{\ell+1} \leq \cdots \leq a_{100}

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

\ell\gt{}50

. Да означим

X: =a_{\ell+1}+\cdots+a_{100}

Y: =-\left(a_{1}+\cdots+a_{\ell}\right)

. Ясно е, че

X

Y

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

2(X-Y)=100\gt{}0

. С помощта на неравенството на Коши-Буняковски имаме

\begin{aligned} 50=\frac{1}{50} \cdot\left(\frac{50}{2}\right)^{2} & =\frac{1}{50}\left(a_{1}+\cdots+a_{100}\right)^{2} \\ & =\left(\left(-a_{1}\right)^{2}+\cdots+\left(-a_{\ell}\right)^{2}\right)+\left(a_{\ell+1}^{2}+\cdots+a_{100}^{2}\right) \\ & \geq \frac{Y^{2}}{\ell}+\frac{X^{2}}{100-\ell}. \end{aligned}

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

\frac{X^{2}}{100-\ell}+\frac{Y^{2}}{\ell} \geq \frac{2\left(X^{2}+Y^{2}\right)}{100}.

Действително, ако е вярно обратното, то

X^{2}\left(\frac{1}{100-\ell}-\frac{2}{100}\right) \leq Y^{2}\left(\frac{2}{100}-\frac{1}{\ell}\right)

откъдето

1 \leq \frac{X^{2}}{Y^{2}} \leq \frac{100-\ell}{\ell}

(съкратихме на

2 \ell-100\gt{}0

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

2 \ell \leq 100

, противоречие. Сега

(X-Y)^{2}=50^{2} \geq X^{2}+Y^{2}

, откъдето

X Y \leq 0

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

Отвори задачатаБаза на maths.bgsomnt2019-9-4

Задача 5

Пълен запис

Условие

Нека

k\gt{}1

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

S_{k}

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

n, a, b

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

n

е нечетно, (

a, b

)

=1, a+b=k

n \mid a^{n}+b^{n}

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

k

, за които

S_{k}

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

Решение

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

S_{k}

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

k

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

k

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

p

. Нека

n=p^{\ell}

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

\ell

. От лемата за повишаване на експонентата имаме

v_{p}\left(a^{n}+b^{n}\right)=v_{p}\left(a^{p^{\ell}}+b^{p^{\ell}}\right)=

v_{p}(a+b)+v_{p}(n)=v_{p}(k)+\ell \geq

1+\ell.

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

n \mid a^{n}+b^{n}

, което означава, че

\left(p^{\ell}, a, b\right) \in S_{k}

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

S_{k}

е безкрайно. Нека сега

k=2^{m}

. Нека

n\gt{}1

е фиксирано и

p

е най-малкият му прост делител. Ако

p

дели

b

, то

p

дели и

a

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

(a, b)=1

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

(p, b)=1

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

c

, такова, че

b c \equiv 1 (\bmod p)

. Тогава от

a^{n}+b^{n} \equiv 0(\bmod p)

следва, че

(a c)^{n} \equiv-1(\bmod p)

. Нека

d

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

a c

по модул

p

. Тогава

d \mid 2 n

d \mid p-1

, т. е.

d \mid(2 n, p-1)

. Последното, заедно с избора на

p

дава

d \in\{1, 2\}

. Ако

d=1

, то

-1 \equiv(a c)^{n} \equiv 1(\bmod p) \Longrightarrow p=2

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

d=2

, то

p \mid(a c)^{2}-1

, откъдето

a c \equiv-1(\bmod p)

. Последното след умножение с

c

води до

p \mid a+b=k

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

k

е степен на 2. Следователно

n=1

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

S_{k}

е крайно.

Отвори задачатаБаза на maths.bgsomnt2019-9-5

Задача 6

Пълен запис

Условие

На дъската са написани числата

1, 2, \ldots, 100

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

a

b

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

a^{2} b^{2}+3

a^{2}+b^{2}+2

. Възможно ли е последното число на дъската да е точна степен (по-голяма от първа)?

Решение

Тъй като

a^{2} b^{2}+3

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

a

b

не се делят на 3, то

a^{2} b^{2}+3

също не се дели на 3 и в този случай четността не се променя. Ако

a

b

се делят на 3, то

a^{2}+b^{2}+2

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

a

b

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

a^{2} b^{2}+3

се дели на 3 и четността се запазва.

Отвори задачатаБаза на maths.bgsomnt2019-9-6

Задача 7

Пълен запис

Условие

Даден е правоъгълен

\triangle A B C, \angle C=90^{\circ}

, в който

D

е средата на

A C

, а

E

е петата на перпендикуляра от

C

към

B D

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

C

към окръжността, описана около

\triangle A E C

, е перпендикулярна на

A B

Решение

Нека

S

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

A B

. Тъй като

\triangle B C D \sim \triangle C E D

, имаме

\frac{D C}{D B}=\frac{D E}{D C}

, откъдето

\frac{D A}{D B}=\frac{D E}{D A}.

Последното и общият

\angle B D A

дават подобието

\triangle A D E \sim \triangle B D A

. Тогава

\angle A B D=\angle E A D=\angle E C S

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

B C E S

е вписан и сега

\angle B S C=\angle B E C=90^{\circ}

Отвори задачатаБаза на maths.bgsomnt2019-9-7

Задача 8

Пълен запис

Условие

Даден е остроъгълен

\triangle A B C

. Нека

D

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

A

, а точките

E

F, E \neq F

, върху

A D

са такива, че

A E=B E

A F=C F

. Точка

T \neq D

е такава, че

\angle B T E=\angle C T F=90^{\circ}

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

T A^{2}=T C \cdot T B

Решение

Нека

M

n

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

A B

A C

. Тогава точките

B, D, T

M

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

B E

, а точките

C

N, T, D

F

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

C D

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

A M T N

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

\triangle T B A \sim \triangle T A C

. Имаме

\angle N T C=\angle N F C=90^{\circ}-\angle F C N

. Тъй като

\angle F C N=\angle C A F

, получаваме

\angle N T C=90^{\circ}-\angle C A F=\angle A C B

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

\angle A C T=\angle N C T=180^{\circ}-\angle N T C-\angle C N T=180^{\circ}-\angle A C B-\angle C N T =\angle C N M-\angle C N T=\angle M N T=\angle B A T

(използвахме, че

M N

е успоредно на

B C

A M T N

е вписан). Аналогично се вижда, че

\angle A B T=\angle C A T

Отвори задачатаБаза на maths.bgsomnt2019-9-8

2020 · Алгебра

3 задачи

Задача 1

Пълен запис

Условие

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

a\gt{}1

не е цяло число, то редицата с общ член

a_{n}=\left[a^{n+1}\right]-a\left[a^{n}\right](n \in \mathbb{N})

не е периодична.

Решение

Първи начин. Да допуснем, че редицата има период

p

. Тъй като

a\left(\left[a^{k p+1}\right]-[a]\right)=\left[a^{k p+2}\right]-\left[a^{2}\right]\gt{}0

за някое

k

, то (1)

a \in \mathbb{Q}

. За

b=a^{p} \in \mathbb{Q}

имаме, че

\sum_{i=0}^{p-1} a^{p-1-i} a_{n p+i}=

\sum_{i=0}^{p-1} a^{p-1-i}\left(\left[a^{n p+i+1}\right]-a\left[a^{n p+i}\right]\right)=

\sum_{i=1}^{p} a^{p-i}\left[a^{n p+i}\right]-\sum_{i=0}^{p-1} a^{p-i}\left[a^{n p+i}\right]=

\left[b^{n+1}\right]-b\left[b^{n}\right]=: b_{n}

и значи (2)

b_{n+1}=b_{n}

. Тогава за

c_{n}=\left[b^{n+1}\right]-\left[b^{n}\right]

следва, че

c_{n+1}=b c_{n}

, откъдето (3)

c_{n+1}=b^{n} c_{1}

, Ако

c_{1}=0

, то

\left[b^{n}\right]=[b]

за всяко

n

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

\mathrm{c} b\gt{}1

. Ако

c_{1} \neq 0

, то

b^{n} c_{1} \in \mathbb{Z}

за всяко

n

, т. е.

b \in \mathbb{Z}

- отново противоречие. Втори начин. (Ст. Герджиков) Да допуснем противното, т. е. че съществуват естествено число, такова, че

a_{n+p}=a_{n}

за всяко

n \geq 1

. Нека

b_{n}=\left[a^{n}\right]

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

n

имаме, че

b_{n+p+1}-a b_{n+p}=a_{n+p}=a_{n}=b_{n+1}-a b_{n}

Така получаваме, че редицата

\left\{b_{n}\right\}_{n=1}^{\infty}

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

t^{p+1}-a t^{p}-t+a=0

Това уравнение очевидно има корени

t_{0}=a

t_{j}=\xi^{j}

, където

\xi=\cos \frac{2 \pi}{p}+i \sin \frac{2 \pi}{p}

p

-ти корен на единицата. Тъй като

a\gt{}1

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

b_{n}

има вида

b_{n}=A a^{n}+\sum_{j=1}^{p} c_{j} \xi^{j n}

Да отбележим, че

b_{n}=\left[a^{n}\right] \rightarrow \infty

при

n \rightarrow \infty

, защото

a\gt{}1

. Тъй като

|\xi|=1

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

A \neq 0

. Сега, тъй като

\xi^{p}=1

, то

b_{n+p}-b_{n}=

A\left(a^{n+p}-a^{n}\right)+\sum_{j=1}^{p} c_{j}\left[\xi^{j n}-\xi^{j(n+p)}\right]=

A\left(a^{n+p}-a^{n}\right),

От

a\gt{}1

A \neq 0

следва, че дясната страна не е 0 и оттук

\frac{b_{n+2 p}-b_{n+p}}{b_{n+p}-b_{n}}=a^{p} \text{е рационално.}

Нека

a^{p}=\frac{r}{s}

, където

r\gt{}s

са взаимнопрости цели числа. Тогава

b_{n p+p}-b_{n p}=A a^{n p}\left(a^{p}-1\right)=\frac{A r^{n}(r-s)}{s^{n+1}}

и тъй като

(r, s)=1

A(r-s) \neq 0

не зависи от

n

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

n

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

b_{n p+p}-b_{n p}

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

n

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

\left\{a_{n}\right\}_{n=1}^{\infty}

не е периодична.

Отвори задачатаБаза на maths.bgsomalg2020-9-1

Задача 2

Пълен запис

Условие

Нека

F

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

A \neq B

F(A) \neq F(B)

, то правите

A B

F(A) F(B)

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

F

е равнина.

Решение

На всяка точка

A

съпоставяме вектора

a=\overrightarrow{O A}

и полагаме

f(a)= F(A), g(a)=f(a)-f(0)

. Понеже

(a-b)(g(a)-g(b))=0

, то (1)

a g(a)=0

(при

b=0

) и тогава (2)

a g(b)=-b g(a)

. Оттук (

\alpha, \beta \in \mathbb{R}

)

c(g(\alpha a+\beta b)-\alpha g(a)-\beta g(b))=

-(\alpha a+\beta b) g(c)+\alpha a g(c)+\beta b g(c)=0

за всяко

c

и значи

g

е линейно изображение. Нека

\left\{e_{1}, e_{2}, e_{3}\right\}

е ортогонален базис. От (1) и (2) намираме, че

g\left(e_{1}\right)=p_{3} e_{2}-p_{2} e_{3}, \quad g\left(e_{2}\right)=p_{1} e_{3}-p_{3} e_{1},

\quad g\left(e_{3}\right)=p_{2} e_{1}-p_{1} e_{2}

Тогава лесно следва, че образът на

g

е равнината

p_{1} x_{1}+p_{2} x_{2}+p_{3} x_{3}=0

. Забележка. От решението може да се извлече, че

F

е композиция на ортогонална проекция върху равнина

\pi

и въртяща хомотетия на

90^{\circ}

\pi

Отвори задачатаБаза на maths.bgsomalg2020-9-2

Задача 3

Пълен запис

Условие

Възможно ли е сумата от реципрочните на няколко две по две различни естествени числа, всяко от които няма две еднакви съседни цифри в десетичния си запис, да е по-голяма от: а) 10; б) 30?

Решение

Да означим с

S_{i}

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

i

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

S_{i}

участват

9^{i}

числа и значи

S_{i}\gt{}9^{i} / 10^{i}

. Понеже

S_{1}\gt{}2

, то

T_{n}: =\sum_{i=1}^{n} S_{n}\gt{}2+\sum_{i=2}^{n} \frac{9^{i}}{10^{i}}=\frac{101}{10}

и следователно отговорът на а) е „да“. От друга страна, всяко добро

i

-цифрено число

a

поражда 9 добри

(i+1)

-цифрени числа от вида

10 a+b(0 \leq b \leq 9)

и значи

S_{i+1}\lt{}9 S_{i} / 10

. Понеже

S_{1}\lt{}3

, то

T_{n}\lt{}S_{1} \sum_{i=0}^{n-1} \frac{9^{i}}{10^{i}}\lt{}30

и следователно отговорът на б) е „не”.

Отвори задачатаБаза на maths.bgsomalg2020-9-3

2020 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

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

k

, точка

M

, вътрешна за

k

и права

\ell

, която се допира до

k

. Да се построят с линийка и пергел точки

A

B

върху

\ell

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

A

B

към

k

(различни от

\ell)

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

C

, то

M

е медицентър за

\triangle A B C

Решение

(Анализ) Нека окръжността

k

е с център

I

, радиус

r

и се допира до

\ell

в точка

P

. Ако

\triangle A B C

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

A

B

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

P

. Да означим с

Q

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

P

k

и нека лъчът

C Q^{\rightarrow}

пресича

\ell

в точка

R

. Добре известен факт е, че

R

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

\triangle A B C

окръжност към страната

A B

, т. е. средата

S

на

A B

се явява и среда на

P R

. Ако означим с

N

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

\triangle A B C

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

N \in Q R

, а от друга,

N \in I M \rightarrow

I M: M N=1: 2

(Защо?). (Построение) Последователно построяваме: (1) точка

I

, център на

k

; (2) точка

P

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

k

\ell

; (3) точка

Q

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

P

k

; (4) точка

N

, като

N \in I M^{\rightarrow}

I M: M N=1: 2

; (5) точка

R

, като

R=Q N^{\rightarrow} \cap \ell

; (6) точка

S

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

P R

; (7) точка

C

, като

C \in S M^{\rightarrow}

S M: M C=1: 2

; (8) точките

A

B

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

C

към

k

\ell

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

k

е вписана в

\triangle A B C, C S

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

M

в отношение

2: 1

, т. е.

M

е медицентър за

\triangle A B C

. (Извод) Задачата има решение тогава и само тогава, когато точка

N

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

\ell

и окръжността

k

, т. е. за разстоянието

d

от

M

до

\ell

е изпълнено

d\gt{}2 r / 3

. В този случай решението е единствено.

Отвори задачатаБаза на maths.bgsomgeo2020-9-1

Задача 2

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomgeo2020-9-2

Задача 3

Пълен запис

Условие

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

A B C D

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

O

, такава че

A O

C O

са ъглополовящи на

\angle B A D

\angle B C D

съответно. Върху отсечките

A O

C O

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

M

N

, такива че

\angle M B N=\frac{1}{2} \angle A B C

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

A B C D

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

\angle M N B=\angle D N O

Решение

Ако означим с

I

J

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

\triangle A B D

\triangle C B D

съответно, то

\angle I B J=\frac{1}{2} \angle A B C=\angle M B N

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

M \in A I

, или

N \in C J

. Без ограничение на общността нека

M \in A I

и да построим окръжността

k

с център

M

, която се допира до

A D

A B

в точките

X

Y

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

B

D

към

k

я допират в точките

R

T

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

L

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

A D

A B

в точките

P

Q

съответно. Тогава

B L-D L=B R-D T=B Y-D X=B A-D A

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

A B C D

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

L B C D

е описан. Но

\angle L B N=\angle M B N-\angle M B L=

\frac{1}{2}(\angle A B C-\angle A B L)=\frac{1}{2} \angle L B C

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

N

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

\triangle B E C

, където

E

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

B P

C D

. Ако означим с

F

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

\triangle P D E

окръжност, то точките

E, F

N

, както и точките

M

P

F

лежат на една права. Тогава

L B C D

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

\Leftrightarrow \quad D N

е ъглополовяща на

\angle L D C

\Leftrightarrow \quad \angle M D N=\frac{1}{2} \angle A D C

(защото

M D

е ъглополовяща на

\angle A D Q

)

\Leftrightarrow \quad

четириъгълникът

M N D F

е вписан

\left(\angle M F N=\frac{1}{2} \angle A D C\right)

\Leftrightarrow \quad \angle M N D+\angle M F D=180^{\circ}

\Leftrightarrow \quad \angle M N D+\angle B N C=180^{\circ}\left(\angle B N C=90^{\circ}+\frac{1}{2} \angle B E C=\angle P F D\right)

\Leftrightarrow \quad \angle M N D=\angle O N B

\Leftrightarrow \quad \angle M N B=\angle D N O

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

Отвори задачатаБаза на maths.bgsomgeo2020-9-3

2020 · Комбинаторика

3 задачи

Задача 1

Пълен запис

Условие

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

A

n

елемента. Множествата

A_{1}

A_{2}, \ldots, A_{n}

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

A

и всяко от тях има по

k

елемента. Известно е, че всяко подмножество

X

на

A

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

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

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

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

се пресичат.

Решение

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

X

на

A

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

\binom{n}{2}

, а броят на подмножествата на

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

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

n\binom{k}{2}

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

n(n-1)= n k(k-1)

, откъдето

k(k-1)=n-1 \tag{*}

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

a \in A

и нека

A_{1}, A_{2}, \ldots, A_{t}

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

a

. Всяко множество

A_{i}, i=1, 2, \ldots, t

, съдържа

k-1

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

a

. Всички подмножества на

A

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

a

, са

n-1

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

t(k-1)=n-1

и от (*) следва, че

t=k

. Да разгледаме две произволни множества

\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}

\left\{b_{1}, b_{2}, \ldots\right.

\left. b_{k}\right\}

. Ще докажем, че те имат общ елемент. Това е вярно, ако

a_{1}=b_{j}

за някое

j

. Нека

a_{1} \neq b_{j}

за всяко

j

. Според доказаното по-горе има точко

k

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

a_{1}

. Всяка от двойките (

a_{1}, b_{j}

) се среща точно в едно от тези

k

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

b_{i}, b_{j}

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

\left\{b_{1}, b_{2}, \ldots, b_{k}\right\}

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

b_{j}

(има

k

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

a_{1}

(има

k

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

j

, за което

b_{j} \in\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}

Отвори задачатаБаза на maths.bgsomcomb2020-9-1

Задача 2

Пълен запис

Условие

Ребрата на пълния граф с

n

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

1, 2, \ldots, \frac{n(n-1)}{2}

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

n-1

(възможно с повтарящи се върхове), за който редицата от етикетите е нарастваща.

Решение

С всеки връх

x

свързваме число

w(x)=

дължината (брой ребра) на най-дългия път с нарастващи етикети, завършващ в

x

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

\sum_{x} w(x)=n(n-1)

. Тогава ще има път с дължина

n-1

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

w(x)

, които в началото са 0. Нека на

i

-тата стъпка добавяме реброто

e=x y

. Ако

w(x)=w(y)

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

w(x)

w(y)

се увеличават с 1. Ако

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

, то реброто удължава най-дългия път завършващ в

x

и имаме за новата стойност на

w(x): w(x)=w(y)+1

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

w(x)

се увеличава с 2, а

w(y)

остава същото. И в двата случая към сумата се добавя 2. Следователно след

n(n-1) / 2

стъпки ще имаме

\sum_{x} w(x)=n(n-1)

Отвори задачатаБаза на maths.bgsomcomb2020-9-2

Задача 3

Пълен запис

Условие

Нека

d

k\lt{}d

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

m=2^{k}

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

\sum_{i=1}^{m} \sum_{j=1}^{m} \sum_{S \subseteq A_{i} \triangle A_{j}}(-1)^{|S|-1}|S| \leq

k 2^{k}

когато

A_{1}, A_{2}, \ldots, A_{m} \subseteq\{1, 2, \ldots, d\}

. (Тук

B \triangle C=(B \backslash C) \cup(C \backslash B)

Решение

Ако

X

е множество с

d

елемента, то

\sum_{S \subseteq X}(-1)^{|S|-1}|S|=\left\{\begin{array}{l} 1, \text{ако} d=1 \cr 0 \text{иначе.} \end{array}\right.

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

d=0

или

d=1

, така че да допуснем, че

d\gt{}1

. Нека

x_{0} \in X

X^{\prime}=X \backslash\left\{x_{0}\right\}

. Тогава

\begin{aligned} \sum_{S \subseteq X}(-1)^{|S|-1}|S| & =\sum_{S \subseteq X^{\prime}}(-1)^{|S|-1}\left(|S|-\left|S \cup\left\{x_{0}\right\}\right|\right)= \\ & =\sum_{S \subseteq X^{\prime}}(-1)^{|S|}=(1-1)^{\left|X^{\prime}\right|}=0 \end{aligned}

защото

\left|X^{\prime}\right| \geq 1

. Нека

X=\left\{x_{1}, x_{2}, \ldots, x_{d}\right\}

. Съпоставяме на всяко множество

A_{i}

характеристичния вектор

v_{i} \in\{0, 1\}^{d}

на

A_{i}

, т. е.

v_{i}(j)=\left\{\begin{array}{l} 1, \text{ако} x_{j} \in A_{i} \cr 0, \text{ако} x_{j} \in A_{i} \end{array}\right.

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

T(V)=\left\{\left(v_{i}, v_{j}\right)| | v_{i}-v_{j} \mid=1, 1 \leq i, j \leq m\right\},

\text{където} V=\left\{v_{1}, v_{2}, \ldots, v_{m}\right\}.

Лема. Нека

v_{1}, v_{2}, \ldots, v_{m} \in\{0, 1\}^{d}

. Тогава

T\left(v_{1}, v_{2}, \ldots, v_{m}\right)

е максимално ако

v_{1}, v_{2}, \ldots, v_{m}

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

d

. За

d=1

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

d-1

към

d

. Нека

V=\left\{v_{1}, v_{2}, \ldots, v_{m}\right\}

максимизира

T(V)

d^{\prime} \leq d

е произволно. Нека

V_{0}\left(d^{\prime}\right)=\left\{v_{i} \mid v_{i}\left(d^{\prime}\right)=0\right\}

, а

V_{1}\left(d^{\prime}\right)=\left\{v_{i} \mid v_{i}\left(d^{\prime}\right)=1\right\}

. Тогава имаме, че

T(V) \leq

T\left(V_{0}\left(d^{\prime}\right)\right)+T\left(V_{1}\left(d^{\prime}\right)\right)

+2 \min \left(\left|V_{0}\left(d^{\prime}\right)\right|, \left|V_{1}\left(d^{\prime}\right)\right|\right)

където използвахме, че за всяко

v_{i} \in V_{0}\left(d^{\prime}\right)

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

v_{j} \in V_{1}\left(d^{\prime}\right)

, за което

\left|v_{i}-v_{j}\right|=1

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

d^{\prime}

. Да обърнем внимание, че ако

V_{0}\left(d^{\prime}\right)

V_{1}\left(d^{\prime}\right)

са сортирани лексикографски по всички координати с изключение на

d^{\prime}

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

T(V)=

T\left(V_{0}\left(d^{\prime}\right)\right)+T\left(V_{1}\left(d^{\prime}\right)\right)

+2 \min \left(\left|V_{0}\left(d^{\prime}\right)\right|, \left|V_{1}\left(d^{\prime}\right)\right|\right).

Така показахме, че ако

L_{0}\left(V, d^{\prime}\right)

са първите

\left|V_{0}\left(d^{\prime}\right)\right|

в лексикографската наредба вектори с

d^{\prime}

-координата нула, а

L_{1}\left(V, d^{\prime}\right)

са първите

\left|V_{0}\left(d^{\prime}\right)\right|

в лексикографската наредба вектори с

d^{\prime}

-координата нула, то

T(V)=T\left(L\left(V, d^{\prime}\right)\right),

\text{където} L\left(V, d^{\prime}\right)=L_{0}\left(V, d^{\prime}\right) \cup L_{1}\left(V, d^{\prime}\right).

Освен това е ясно, че лексикографски най-големите вектори в

L_{0}\left(V, d^{\prime}\right)

L_{1}\left(V, d^{\prime}\right)

не надминават лексикографски най-големите вектори в

V_{0}\left(d^{\prime}\right)

V_{1}\left(d^{\prime}\right)

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

L_{0}\left(V, d^{\prime}\right)=V_{0}\left(d^{\prime}\right)

L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right)

. От горните разсъждения може да смятаме, че за всяко

d^{\prime} \leq d

е в сила, че

L_{0}\left(V, d^{\prime}\right)=V_{0}\left(d^{\prime}\right) \text{и} L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right).

Сега да допуснем, че

y \notin V

и нека

v \in V

е лексикографски най-малко, за което

y \prec_{l e x} v

. Ако

y\left(d^{\prime}\right)=v\left(d^{\prime}\right)=j

, то очевидно

L_{j}\left(V, d^{\prime}\right) \neq V_{j}\left(d^{\prime}\right)

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

y\left(d^{\prime}\right) \neq v\left(d^{\prime}\right)

за всяко

d^{\prime} \leq d

. В частност

y(1)=0

v(1)=1

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

v\left(d^{\prime}\right)=1

за някое

d^{\prime}\gt{}1

, тогава тъй като

L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right)

, то

v=(1, 0, \ldots, 0) \in V

. Тъй като

y\left(d^{\prime}\right) \neq v\left(d^{\prime}\right)

за всяко

d^{\prime}

, то

y=(0, 1, \ldots, 1)

. Сега, ако отново има

v^{\prime} \in V

, за който

v^{\prime}(1)=1

v^{\prime}\left(d^{\prime}\right)=1

за някое

d^{\prime}\gt{}1

, то очевидно

L_{1}\left(V, d^{\prime}\right) \neq V_{1}\left(d^{\prime}\right)

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

V

не е сортирано лексикографски, то

V=\left\{\left(0, v^{\prime}\right) \mid v^{\prime} \in\{0, 1\}^{d-1}\right\} \backslash\{y\} \cup\{v\}.

Но сега е ясно, че

\left|v-\left(0, v^{\prime}\right)\right|\gt{}1

, за всяко

v^{\prime} \neq(0, 0, \ldots, 0)

, докато

\left|y-\left(0, v^{\prime}\right)\right|=1

за

d-1

стойности на

v^{\prime} \in\{0, 1\}^{d-1}

. За

d \geq 2

заключаваме, че

T(V) \leq T(V \backslash\{v\} \cup\{y\}).

Следователно наистина най-голямата стойност на

T(V)

се достига, когато

V

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

2^{k}

вектора от

\{0, 1\}

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

\{0\}^{d-k} \times\{0, 1\}^{k}

. За всеки вектор

v

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

k

вектора

u

, за които

|u-v|=1

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

T\left(\{0\}^{d-k} \times\{0, 1\}^{k}\right)=k 2^{k}=k 2^{k}.

Отвори задачатаБаза на maths.bgsomcomb2020-9-3

2020 · Теория на числата

3 задачи

Задача 1

Нужна е проверка

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgsomnt2020-9-1

Задача 2

Пълен запис

Условие

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

q

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

\alpha

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

p

, такова, че

\left|\alpha-\frac{p}{q}\right| \leq \frac{1}{q^{2}}

За фиксирано

\alpha \in \mathbb{R}

означаваме с

D_{\alpha}

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

\alpha

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

D_{\alpha}

съдържа всички числа от вида

2^{k}+1

, където

k \in \mathbb{N}

, то

D_{\alpha}=\mathbb{N}

Решение

Ще докажем, че числото

\alpha

е цяло, което очевидно води до

D_{\alpha}= \mathbb{N}

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

\alpha

е ирационално. Тогава за всяко

q \in D_{\alpha}

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

\{q \alpha\}

принадлежи на някой от интервалите (

0, 1 / q

) и (

1-1 / q, 1

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

r

е такова, че

2^{r}\gt{}\max \left(\frac{1}{\{\alpha\}}, \frac{1}{1-\{\alpha\}}\right)

Ако

0\lt{}\left\{\left(2^{r}+1\right) \alpha\right\}\lt{}1 /\left(2^{r}+1\right)

, то

\{\alpha\}\gt{}1 /\left(2^{r}+1\right)\gt{}

\left\{\left(2^{r}+1\right) \alpha\right\}=\left\{\left\{2^{r} \alpha\right\}+\{\alpha\}\right\}.

Това означава, че

1-\{\alpha\}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}+\frac{1}{2^{r}+1}

Ако пък

1\gt{}\left\{\left(2^{r}+1\right) \alpha\right\}\gt{}1-1 /\left(2^{r}+1\right)

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

1-\{\alpha\}-\frac{1}{2^{r}+1}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}

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

\left\{2^{r} \alpha\right\}+\{\alpha\}\lt{}2-1 /\left(2^{r}+1\right)

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

r

). Получихме, че за всички достатъчно големи

r

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

1-\{\alpha\}-\frac{1}{2^{r}+1}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}+\frac{1}{2^{r}+1}

Това лесно води до противоречие (с разглеждане поотделно на случаите

\{\alpha\}\lt{}1 / 2

\{\alpha\}\gt{}1 / 2

). Нека сега

\alpha=a / b

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

b \in \mathbb{N}, a \in \mathbb{Z}

(a, b)=1

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

q_{n}=2^{2^{n}}+1

съществува

p_{n} \in \mathbb{Z}

, такова, че

\left|\frac{a}{b}-\frac{p_{n}}{q_{n}}\right| \leq \frac{1}{q_{n}^{2}}

тоест

\left|a q_{n}-p_{n} b\right|\lt{}b / q_{n}

. Оттук при

q_{n}\gt{}b

заключаваме

a q_{n}=p_{n} b

, което води до

b \mid q_{n}

, за всяко

n\gt{}b

и тъй като

\left(q_{n}, q_{n+1}\right)=1

, заключаваме, че

b=1

, т. е.

\alpha

е цяло число.

Отвори задачатаБаза на maths.bgsomnt2020-9-2

Задача 3

Пълен запис

Условие

Нека

P

Q

са неконстантни полиноми с цели неотрицателни коефициенти и старши коефициент 1, а

k

е естествено число. Естествените числа

a_{1}, a_{2}, \ldots, a_{k}, a_{i} \geq 2

за

i=1, 2, \ldots, k

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

n

числото

\left(a_{1}^{P(n)}+Q(n)\right)\left(a_{2}^{P(n)}+Q(n)\right) \ldots\left(a_{k}^{P(n)}+Q(n)\right)

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

a_{1} a_{2} \ldots a_{k}

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

Решение

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

f

е неконстантен полином с цели коефициенти и нека

A

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

p

, за които

v_{p}(f(n))

е нечетно за някое

n \in \mathbb{N}

. Ако множеството

A

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

g

с цели коефициенти и константа

c

, такива, че

f=c g^{2}

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

f

е свободен от квадрати (т. е. не се дели на квадрат на полином с цели коефициенти). От условието следва, че множеството от простите числа, които делят точно в четни степени стойности на

f

, е безкрайно. Нека

p

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

p^{2 k} \| f(n)

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

n

k

. Да разгледаме

f\left(n+\ell p^{k+1}\right)

, където

\ell \in \mathbb{N}

. Лесно се вижда, че

f\left(n+\ell p^{k+1}\right) \equiv f(n)+\ell p^{k+1} f^{\prime}(n) \quad

\left(\bmod p^{2 k+2}\right)

Ако

\left(p, f^{\prime}(n)\right)=1

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

\ell f^{\prime}(n)+\frac{f(n)}{p^{k+1}} \equiv p^{k}\left(\bmod p^{k+1}\right)

има решение. Това означава, че съществува естествено число

n_{1}

, за което

p^{2 k+1} \| f\left(n_{1}\right)

, т. е.

p \in A

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

p

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

n

, такова, че

p \mid\left(f(n), f^{\prime}(n)\right)

. Сега от лемата на Безу за полиноми следва, че съществуват полиноми

u, v \in \mathbb{Z}[x]

, такива че

u f+v f^{\prime}=T

, където

T \in \mathbb{Z}[x]

е найголемият общ делител на

f

f^{\prime}

, като при това

T

не е константа. Нека

R

е неразложим делител на

T

и нека

z

е негов (комплексен) корен. Тъй като

z

е общ корен на

f

f^{\prime}

, то

z

е кратен корен на

f

. Тъй като

R

няма кратни корени (защото е неразложим), всеки негов корен е корен и на

f / R

, тоест

R^{2} \mid f

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

f

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

f=c g^{2}

за някои

c \in \mathbb{Z}

g \in \mathbb{Z}[x]

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

a_{1}, a_{2}, \ldots, a_{k}

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

c=P(1)\gt{}0

и да разгледаме полинома

g(x)=Q(x)+a_{1}^{c}

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

g(x)

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

p

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

n_{0}

, за което

v_{p}\left(g\left(n_{0}\right)\right)=2 k+1

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

p

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

n

, за което

n \equiv 1(\bmod p-1)

n \equiv n_{0} \left(\bmod p^{2 k+2}\right)

. Тогава

p^{2 k+1} \| g(n)=Q(n)+a_{1}^{P(n)}

. Последното означава, че

p \mid a_{i}^{P(n)}+Q(n)

за някое

i \neq 1

, откъдето

p \mid a_{1}^{c}-a_{i}^{c}

. Тъй като можем да изберем

p\gt{}\max \left\{\left|a_{1}^{c}-a_{i}^{c}\right|: i=2, 3, \ldots, k\right\}

, заключаваме, че

a_{1}^{c}=a_{i}^{c}

за някое

i \neq 1

, т. е.

a_{1}=a_{i}

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

Q(x)+a_{1}^{c}=R_{1}^{2}(x)

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

\mathrm{C} d=P(2)\gt{}P(1)=c

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

Q(x)+a_{1}^{d}=R_{2}^{2}(x)

е точен квадрат на неконстантен полином с цели коефициенти. Тогава

a_{1}^{c}-a_{1}^{d}=\left(R_{1}(x)-R_{2}(x)\right)\left(R_{1}(x)+R_{2}(x)\right),

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

R_{1} \equiv R_{2}

a_{1}^{c}=a_{1}^{d}

, т. е.

a_{1}=1

Отвори задачатаБаза на maths.bgsomnt2020-9-3

2023 · Алгебра

3 задачи

Задача 1

Пълен запис

Условие

Нека

n

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

f

g

с реални коефициенти от степен

n

n+1

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

(f(x))^{2}-f\left(x^{2}\right)=g(x)

за всички реални

x

Решение

Нека

f(x)=a_{0} x^{n}+a_{n-k} x^{k}+\ldots

, където

a_{n-k} x^{k}

е първият ненулев член, по-малък от старшия. Тогава

f(x)^{2}=a_{0}^{2} x^{2 n}+2 a_{0} a_{n-k} x^{n+k}+\ldots \quad

f\left(x^{2}\right)=a_{0} x^{2 n}+a_{n-k} x^{2 k}+\ldots.

Разликата на тези полиноми е от степен

2 n\gt{}n+1

, освен ако

a_{0}=1

(случаят

n=1

е разгледан по-долу). Следователно,

a_{0}=1

и следващият коефициент на

f(x)^{2}-f\left(x^{2}\right)

2 a_{n-k} x^{n+k}

, който трябва да бъде старши коефициент на

g(x)

, т. е.

k=1

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

f(x)=x^{n}+a x+b, a \neq 0

, и

g(x)

се определя еднозначно от това:

g(x)=2 a x^{n+1}+\left(a^{2}-a\right) x^{2}+2 a b x+b^{2}-b,

\quad a \neq 0, a, b \in \mathbb{R}.

Ако

n=1

, то

f(x)=a x+b, g(x)=\left(a^{2}-a\right) x^{2}+2 a b x+b^{2}-b

, следователно, за да бъдат това полиноми от степен съответно

1, 2, a \neq 0, a \neq 1, a, b \in \mathbb{R}

Отвори задачатаБаза на maths.bgsomalg2023-9-1

Задача 2

Пълен запис

Условие

Нека

a, b, c

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

\left(a^{7}-a^{4}+3\right)\left(b^{7}-b^{4}+3\right)\left(c^{7}-c^{4}+3\right) \geq(a+b+c)^{3}.

Решение

Наблюдаваме, че

x^{7}-x^{4}-x^{3}+1=\left(x^{4}-1\right)\left(x^{3}-1\right) \geq 0

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

x

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

a^{7}-a^{4}+3 \geq a^{3}+2

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

\left(a^{3}+1+1\right)\left(b^{3}+1+1\right)\left(c^{3}+1+1\right) \geq(a+b+c)^{3}.

Последното следва директно от неравенство на Хьолдер. Алтернативно, след разкриване на скобите в

\left(a^{3}+2\right)\left(b^{3}+2\right)\left(c^{3}+2\right) \geq(a+b+c)^{3}

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

\begin{aligned} a^{3}+b^{3} c^{3}+1 & \geq 3 a b c \\ a^{3} b^{3} c^{3}+1+1 & \geq 3 a b c \\ a^{3}+a^{3} b^{3}+1 & \geq 3 a^{2} b \\ a^{3}+a^{3} c^{3}+1 & \geq 3 a^{2} c \\ b^{3}+a^{3} b^{3}+1 & \geq 3 b^{2} a \\ c^{3}+a^{3} c^{3}+1 & \geq 3 c^{2} a \\ b^{3} c^{3}+b^{3}+1 & \geq 3 b^{2} c \\ b^{3}+c^{3}+c^{3} & \geq 3 c^{2} b \end{aligned}

Всяко от тези неравенства следва от СА-СГ.

Отвори задачатаБаза на maths.bgsomalg2023-9-2

Задача 3

Пълен запис

Условие

Нека

f

е полином с реални коефициенти от степен

n \geq 1

и старши коефициент 1 и нека

x_{0}\lt{}x_{1}\lt{}x_{2}\lt{}\cdots\lt{}x_{n}

са цели числа. a) Да се докаже, че

\sum_{k=0}^{n} \frac{\left|f\left(x_{k}\right)\right|}{\prod_{j \neq k}\left|x_{k}-x_{j}\right|} \geq 1

б) Да се докаже, че съществува

k

, за което

\left|f\left(x_{k}\right)\right| \geq \frac{n!}{2^{n}}

Решение

Формулата в

a

) предполага използване на интерполационната формула на Лагранж: за точките

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

и стойностите

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

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

\leq n

със стойност

c_{i}

в точката

x_{i}

, и той e

\sum_{k=0}^{n} c_{k} \prod_{j \neq k} \frac{x-x_{j}}{x_{k}-x_{j}}

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

f(x)=\sum_{k=0}^{n} f\left(x_{k}\right) \prod_{j \neq k} \frac{x-x_{j}}{x_{k}-x_{j}},

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

|f(x)| \leq

\sum_{k=0}^{n}\left|f\left(x_{k}\right)\right| \prod_{j \neq k} \frac{\left|x-x_{j}\right|}{\left|x_{k}-x_{j}\right|}

Разделяме на

x^{n}

и оставяме

x \rightarrow \infty

и така получаваме

a

) (тук е важно, че старшият коефициент е 1 ). За б), използваме факта, че

x_{j}

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

\prod_{j \neq k}\left|x_{k}-x_{j}\right| \geq k!(n-k)!

\sum_{k=0}^{n} \frac{\left|f\left(x_{k}\right)\right|}{k!(n-k)!} \geq 1

Знаем, че

\sum_{k=0}^{n} \frac{1}{k!(n-k)!}=

\frac{1}{n!} \sum_{0}^{n} \frac{n!}{k!(n-k)!}=\frac{2^{n}}{n!},

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

k

е вярно, че

\left|f\left(x_{k}\right)\right| \geq n!/ 2^{n}

Отвори задачатаБаза на maths.bgsomalg2023-9-3

2023 · Геометрия

3 задачи

Задача 1

Пълен запис

Условие

Даден е триъгълник

A B C

B C\gt{}A B\gt{}A C

. Нека точките

B_{1}

C_{1}

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

A C

A B

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

B B_{1}

C C_{1}

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

G

. Описаната около триъгълника

B B_{1} C

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

A B

за втори път в точката

X

, а описаната около триъгълника

B C_{1} C

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

B B_{1}

за втори път в точката

P

. Допирателната в

G

към описаната около триъгълника

B G C

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

C P

в точка

Y

. Описаната около триъгълника

G Y C

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

B G

за втори път в точката

Z

, а правите

B_{1} Y

X G

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

T

. Ако

\angle X C_{1} G=\angle X B_{1} G

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

\angle T C_{1} B=\angle T C Z

Решение

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

T

лежи на описаната около триъгълника

B B_{1} C

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

\angle B X T=\angle B B_{1} T

. Имаме

\angle C C_{1} X=\angle C P B_{1}

, както и

\angle C B_{1} P=\angle C X C_{1}

, откъдето следва, че

\triangle C P B_{1} \sim \triangle C C_{1} X

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

\angle C G Y=\angle G B C=\angle C C_{1} P

, което значи, че

C_{1} P \| G Y

. От Теорема на Талес следва, че

\frac{C_{1} G}{G C}=\frac{P Y}{Y C}

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

Y

G

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

\angle P B_{1} Y=\angle C_{1} X G

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

\angle B X T=\angle B B_{1} T

. Сега от условието имаме, че

\angle G C_{1} X=\angle G B_{1} X=\angle B T G

, тоест точките

B, C_{1}, G, T

лежат на една окръжност. От

\angle C G Y=\angle C B B_{1}=\angle C T B_{1}

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

T, G, C, Y, Z

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

\angle T C_{1} B=\angle T G Z=\angle T C Z

, което искахме да докажем.

Отвори задачатаБаза на maths.bgsomgeo2023-9-1

Задача 2

Пълен запис

Условие

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

A B C D

ъглите при върховете

A

C

са остри. Нека

B_{1}, B_{2}, B_{3}

са петите на перпендикулярите от

B

към

A D, A C

D C

, съответно, и нека

D_{1}, D_{2}, D_{3}

са петите на перпендикулярите от

D

към

A B, A C

B C

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

B_{1} B_{2} B_{3}

D_{1} D_{2} D_{3}

, се пресичат върху правата

A C

Решение

Нека точката

P

е такава, че

\angle P A C=\angle B A D, \angle P C A=\angle B C D

P

B

са в различни полуравнини спрямо

A C

. Нека също

P_{1}, P_{2}

P_{3}

са петите на перпендикулярите от

P

към

A D, A C

D C

, съответно. Имаме

\triangle C B B_{2} \sim \triangle C P P_{3}

\triangle C B B_{3} \sim \triangle C P P_{2}

, откъдето

\frac{C B_{2}}{C P_{3}}=\frac{C B}{C P}=\frac{C B_{3}}{C P_{2}}.

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

P_{2}, B_{2}, P_{3}

B_{3}

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

P_{2} B_{2}

P_{3} B_{3}

се пресичат в средата на

B P

, то тази среда

O

е център на тази окръжност. Аналогично

P_{2}, B_{2}, P_{1}

B_{1}

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

O

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

B_{1} B_{2} B_{3}

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

P_{2}

, която лежи на

A C

. Аналогично като повторим описаната конструкция за

D

спрямо

A B C

ще получим, че ако

Q

е аналогично дефинираната на

P

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

A C P

A C Q

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

A C

. Така аналогично дефинираната на

P_{2}

съвпада с

P_{2}

и лежи на окръжността около

D_{1} D_{2} D_{3}

, с което исканото е доказано.

Отвори задачатаБаза на maths.bgsomgeo2023-9-2

Задача 3

Пълен запис

Условие

Даден е разностранен триъгълник

A B C

. Произволна окръжност

\omega_{C}

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

C A

C B

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

P

Q

, като

A

е между

C

P, B

е между

C

Q

\omega_{C}

и триъгълника

A B C

нямат общи точки. Окръжността

\Omega_{C}

минава през

A

B

и се допира до

\omega_{C}

в точка

T_{C}

(като

\omega_{C}

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

\Omega_{C}

). Правите

P Q

A B

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

K_{C}

, а правата

K_{C} T_{C}

пресича

\omega_{C}

за втори път в точката

L_{C}

. Аналогично се дефинират точките

L_{A}

L_{B}

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

\omega_{A}, \omega_{B}

\omega_{C}

са независими една от друга). Да се докаже, че правите

A L_{A}

B L_{B}

C L_{C}

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

Решение

Ще докажем, че (независимо от избора на

\left.\omega_{C}\right) C L_{C}

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

C_{1}

на вписаната окръжност на

A B C

със страната

A B

. Тогава ще следва, че трите разглеждани прави се пресичат в точката на Жергон и задачата ще е решена. Нека

A T_{C}

B T_{C}

пресичат

\omega_{C}

за втори път в точките

X

Y

, съответно. Чрез хомотетията с център

T_{C}

, изпращаща

\omega_{C}

\Omega_{C}

(или разглеждане на общата допирателна и съображения с периферни ъгли), получаваме

X Y \| A B

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

C

, изпращаща вписаната окръжност на

A B C

\omega_{C}

, изпраща

C_{1}

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

\omega_{C}

е успоредна на

A B

, а оттук и на

X Y

- така тази точка е точно средата на дъгата

\widehat{X T_{C} Y}

(и искаме да се окаже, че е

L_{C}

). Следователно е достатъчно да докажем, че

T_{C} K_{C}

е външна ъглополовяща за

\angle X T_{C} Y=\angle A T_{C} B

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

\frac{A K_{C}}{K_{C} B}=\frac{A T_{C}}{B T_{C}}

. От теоремата на Менелай за триъгълника

C P Q

и правата

A B K_{C}

получаваме

\frac{C P}{P A} \cdot \frac{A K_{C}}{K_{C} B} \cdot \frac{B Q}{Q C}=1

и тъй като

C P=C Q

, то

\frac{A K_{C}}{K_{C} B}=\frac{A P}{B Q}.

От друга страна, чрез степените на точките

A

B

относно

\omega_{C}

получаваме

A P^{2}=A X \cdot A T_{C}

B Q^{2}=B Y \cdot B T_{C}

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

\frac{A P^{2}}{B Q^{2}}=\frac{A X}{B Y} \cdot \frac{A T_{C}}{B T_{C}}=\left(\frac{A T_{C}}{B T_{C}}\right)^{2}

(последното от теоремата на Талес). Така

\frac{A K_{C}}{K_{C} B}=\frac{A T_{C}}{B T_{C}}

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

Отвори задачатаБаза на maths.bgsomgeo2023-9-3

2023 · Комбинаторика

3 задачи

Задача 1

Пълен запис

Условие

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

Решение

Ще докажем, че Иван има печеливша стратегия. Да разгледаме произволни 121 от дадените точки и да ги означим с двойките (

a, b

), където

a

b

са числа от 1 до 11. Тъй като 11 е просто число, то за всеки две двойки

A\left(a_{1}, b_{1}\right)

B\left(a_{2}, b_{2}\right)

съществува най-много едно

k

, за което

a_{1}-a_{2} \equiv k\left(b_{1}-b_{2}\right)(\bmod 11)

. Когато

k

е цифра, Иван записва на отсечката

A B

цифрата

k

. Върху останалите отсечки Иван записва произволни цифри. Директно се проверява, че ако върху отсечките

A B

A C

е записана една и съща цифра, то върху отсечката

B C

е записана същата цифра. Също така, за всяка цифра точките се разделят на 11 групи от по 11 точки, като във всяка група върху всички отсечки е записана една и съща цифра. Петър записва на тези 121 точки 121 цифри и следователно някоя цифра

k

ще се среща 12 пъти. От принципа на Дирихле следва, че някои две от тези 12 точки ще са в една от 11 -те групи, на които се разделят дадените точки спрямо цвета

k

. Получаваме две точки, на които е записана една и съща цифра

k

и на отсечката между тях е записана същата цифра

k

, т. е. печели Иван.

Отвори задачатаБаза на maths.bgsomcomb2023-9-1

Задача 2

Пълен запис

Условие

За всяко непразно множество

A

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

S(A)

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

A

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

t

със следното свойство: За всяко естествено число

n

и всяко множество

M

от

n

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

M

може да се раздели на

n

непресичащи се групи, така че ако

P

Q

са множества от една и съща група, то

\frac{S(P)}{S(Q)} \leq t

Решение

Да допуснем, че съшествува константа

t\lt{}2

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

M=\left\{1, 2, 2^{2}, \ldots, 2^{n-1}\right\}

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

B=\left\{1, 2, 3, \ldots, 2^{n}-1\right\}

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

B

на

n

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

t

. Ясно е, че числата

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

трябва да са в различни групи. Нека

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

са групите, като

2^{k}, 0 \leq k \leq n-1

лежи в

B_{k}

. Нека някое множество

B_{k}

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

2^{k}

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

a

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

B_{k}

, то

a \leq 2^{k}

и отношението на най-голямото число в

B_{k}

a

е поне

\frac{a+2^{k}}{a}=1+\frac{2^{k}}{a} \geq 2,

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

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

числата са най-много

2^{0}+2^{1}+\cdots+2^{n-1}=2^{n}-1

. От друга страна този брой е точно

2^{n}-1

и следователно във всяко множество

B_{k}

има точно

2^{k}

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

a

B_{n-1}

и най-голямото число в

B_{n-1}

(което е поне

a+2^{n-1}-1

) е поне

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

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

t \geq 2-\frac{1}{2^{n-1}}

което е невъзможно, тъй като

t\lt{}2

. Нека

M=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}

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

\left. a_{1}\lt{}a_{2}\lt{}\cdots\lt{}a_{n}\right\}

. Нека

S_{0}=0, S_{i}=a_{1}+\cdots+a_{i}

за

i=1, 2, \ldots, n

. Ако

\sigma

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

M

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

i

, за което

S_{i-1}\lt{}\sigma \leq S_{i} \tag{1}

Разбиваме множеството от сумите на подмножества

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

, където в

c_{i}

са всички суми, удовлетворяващи (1). Ще докажем, че ако

\sigma \in c_{i}

, то

\frac{S_{i}}{2}\lt{}\sigma \leq S_{i}

. Тъй като

\sigma\gt{}S_{i-1}=a_{1}+\cdots+a_{i-1}

, то

\sigma

съдържа поне едно събираемо

a_{k}

за което

k \geq i

. Тогава

S_{i}-\sigma\lt{}S_{i}-S_{i-1}=a_{i} \leq a_{k} \leq \sigma

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

\sigma\gt{}\frac{1}{2} S_{i}

. Но

\sigma \leq S_{i}

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

Отвори задачатаБаза на maths.bgsomcomb2023-9-2

Задача 3

Пълен запис

Условие

В галактика има

N

планети, като някои от тях са свързани с двупосочни авиолинии. Броят на линиите е

N-1

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

1, 2, \ldots, N-1

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

A

S(A)

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

B \neq A

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

A

или за които съществува път от

A

до

B

, като номерата на авиолиниите по този път са в нарастващ ред. Да се намери най-малката стойност на

N

, за която е възможно

S(A) \geq 2023

за всяка планета

A

Решение

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

N

графът е дърво с

N-1

ребра. В противен случай ще има свързана компонента, за която броят на ребрата е по-малък от броя на върховете (т. е. тази свързана компонента е дърво), което е противоречие с минималността на

N

. С индукция по

k

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

S(A) \geq k

, то

N \geq 2^{k}

. При

k=1

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

k

да разгледаме такова

N

, за което в съответното дърво

G

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

S(A) \geq k+1

. Да премахнем реброто с най-голям номер. Тогава

G

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

A

от едната компонента в

S(A)

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

S(A) \geq k

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

2^{k}

планети. Общо планетите са

2^{k+1}

. Пример при

k=1

се дава с

2^{1}=2

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

2^{k}

планети и

S(A)=k

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

2^{k}

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

2^{k+1}

планети и

S(A)=k+1

. Задачите са предложени от: Милен ИвановА1, А2, А3; Кристиян Василев - G1; Александър Иванов - G2, G3, C2, C3; Емил Колев C1, Данила Черкашин (идея Георгий Струков и Сергей Сотников) - NT1, Александър Иванов и Сергей Берлов - NT2, Навид Сафаей - NT3.

Отвори задачатаБаза на maths.bgsomcomb2023-9-3

2023 · Теория на числата

3 задачи

Задача 1

Пълен запис

Условие

Дадени са полиномите

f(x)=x^{2}+2 x+3

g(x)=5 x^{2}+2

. Разрешено ни е за започнем с произволно цяло число

x

, да го заместим с

f(x), g(x)

или

x-2023

и т. н. (на всяка стъпка заместваме текущото число

y

f(y), g(y)

или

y-2023

). Съществува ли начално число

x

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

Решение

ОтговорНе! Да разгледаме ситуацията по модул

17^{2}

. Тъй като

f=(x+1)^{2}+2

g=5 x^{2}+2

, от

f

или

g \equiv 2(\bmod 17)

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

f

или

g \equiv 2\left(\bmod 17^{2}\right)

. Операцията

x-2023

не променя остатъка по модул

17^{2}

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

17^{2}

. Забележка. Лесно се вижда, че чрез

f

отместваме с 2 квадратичните остатъци по модули 7 и 17, а чрез

g

правим същото с квадратичните неостатъци по тези модули (защото 5 е квадратичен неостатък по модул 7 и 17). Следователно можем да получим всички остатъци по модули 7 и 17.

Отвори задачатаБаза на maths.bgsomnt2023-9-1

Задача 2

Пълен запис

Условие

Редицата

\left(a_{n}\right)_{n=1}^{\infty}

е дефинирана чрез равенствата

a_{1}=2, \quad a_{n+1}=a_{1} a_{2} \cdot \ldots \cdot a_{n}+1

за всяко

n \geq 1

. Естествените числа

x_{1}, x_{2}, \ldots, x_{2023}

са по-големи от 1,

X=x_{1}+x_{2}+\cdots+x_{2023}

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

x_{i}-1 \mid X

за всяко

1 \leq i \leq 2023

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

X \leq 2023\left(a_{2024}-1\right)

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

Решение

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

\left(a_{n}\right)_{n=1}^{\infty}

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

b_{1} \leq b_{2} \leq \cdots \leq b_{n}

са такива естествени числа, че

\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots+\frac{1}{b_{n}}\lt{}1

. Тогава

\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots+\frac{1}{b_{n}} \leq \frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}

Доказателство. Да отбележим, че

\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=\frac{A_{n}-1}{A_{n}},

където

A_{n}=a_{1} \cdots a_{n}

. Ще проведем индукция по

n

, като базата

n=1

е очевидна. Да означим

\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=C_{n}

\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots \frac{1}{b_{n}}=B_{n}

и да фиксираме

n \geq 2

. Да допуснем, че исканото не е изпълнено, т. е.

B_{i} \leq C_{i}

за всяко

i \leq n-1

, но

B_{n}\gt{}C_{n}

. Прилагайки двукратно сумиране по Абел, получаваме

\begin{aligned} \sum_{i=1}^{n} \frac{b_{i}}{a_{i}} & =C_{1}\left(b_{1}-b_{2}\right)+C_{2}\left(b_{2}-b_{3}\right)+\cdots+C_{n-1}\left(b_{n-1}-b_{n}\right)+C_{n} \cdot b_{n} \\ & \lt{}B_{1}\left(b_{1}-b_{2}\right)+B_{2}\left(b_{2}-b_{3}\right)+\ldots B_{n-1}\left(b_{n-1}-b_{n}\right)+B_{n} \cdot b_{n}=n \end{aligned}

\sum_{i=1}^{n} \frac{b_{i}}{a_{i}} \geq n \sqrt[n]{\vphantom{x^2}\frac{b_{1} \ldots b_{n}}{a_{1} \ldots a_{n}}}

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

b_{1} b_{2} \ldots b_{n}\lt{}a_{1} a_{2} \ldots a_{n}

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

\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots+\frac{1}{b_{n}} \leq

\frac{b_{1} b_{2} \ldots b_{n}-1}{b_{1} b_{2} \ldots b_{n}}\lt{}\frac{a_{1} a_{2} a_{n}-1}{a_{1} a_{2} \ldots a_{n}}

с което лемата е доказана. Обратно в задачата, да положим

d_{i}=\frac{X}{x_{i}-1}

за

i=1, 2, \ldots, 2023

. Тогава

\begin{aligned} & \frac{X}{d_{1}}+\frac{X}{d_{2}}+\ldots+\frac{X}{d_{2023}}=X-2023 \\ & \frac{1}{d_{1}}+\frac{1}{d_{2}}+\ldots+\frac{1}{d_{2023}}=1-\frac{2023}{X}\lt{}1 \end{aligned}

От лемата следва, че

1-\frac{2023}{X} \leq 1-\frac{1}{A}

където

A=a_{1} a_{2} \ldots a_{2023}

. Оттук

X \leq 2023 a_{1} a_{2} \ldots a_{2023}=2023\left(a_{2024}-1\right)

Равенство се достига тогава и само тогава, когато

d_{i}=a_{i}

, т. е. при

x_{i}=\frac{2023\left(a_{2024}-1\right)}{a_{i}}+1; \quad i=1, 2, \ldots, 2023.

Отвори задачатаБаза на maths.bgsomnt2023-9-2

Задача 3

Пълен запис

Условие

Нека

p

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

\operatorname{Crad}_{p}(n)

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

n

, различни от

p

. Нека

c \neq 0

е цяло число и

f: \mathbb{N} \rightarrow \mathbb{N}

е мултипликативна функция със свойството

\operatorname{rad}_{p}(n) \mid f(n+1)-c

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

n

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

f(n)=n^{r}

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

r

Решение

Да фиксираме естествени числа

a

b

и нека

q\gt{}\max (a, b, |c|, \mid c f(a b)- f(a) f(b) \mid), q \neq p

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

r, s, x, y \mathrm{p}

такива, че

a x=1+r q, b y=1+s q

x, y

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

\operatorname{gcd}(x, a b)=\operatorname{gcd}(y, a b x)=1

. Можем да запишем

a b x y=q T+1

, където

T=r+s+q r s

. Тогава

f(a) f(x)=f(a x)=f(1+q r) \equiv c(\bmod q)

. По-нататък,

f(b) f(y)=f(b y)=f(1+s q) \equiv c \quad(\bmod q)

Накрая,

f(a b) f(x) f(y)=f(a b x y)=f(q T+1) \equiv c(\bmod q)

. От избора на

q

следва, че

f(x) f(y)

не се дели на

q

. Тогава

f(a) f(b) \equiv c f(a b) \quad(\bmod q)

Нещо повече, от избора на

q

следва, че

c f(a b)=f(a) f(b)

. Полагайки

a=b=1

, получаваме

c=1

, т. е. функцията

f

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

f(a b)=f(a) f(b)

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

a

b

. Нека

N

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

q

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

f(N)

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

q \mid p N

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

\operatorname{gcd}(q, N p)=1

). Тогава съществуват естествени числа

x

y

, за които

N x=q y+1

. Тъй като

q \neq p

, получаваме

0 \equiv f(N) f(x)=f(N x)=f(1+q y) \equiv 1 \quad(\bmod q)

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

r

можем да запишем

f(r)=r^{\alpha_{r}} p^{\beta_{p}}

. В частност,

f(p)=p^{\alpha}

. Сега за естествени числа

n

s

имаме

f\left(n p^{2 s}\right)=f\left(1+\left(n p^{2 s}-1\right)\right) \equiv 1 \quad

\left(\bmod \operatorname{rad}_{p}\left(n p^{2 s}-1\right)\right)

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

n^{\alpha} f\left(n p^{2 s}\right)=n^{\alpha} f(n) p^{2 s \alpha}=f(n)\left(m p^{2 s}\right)^{\alpha} \equiv

f(n) \quad

\left(\bmod \operatorname{rad}_{p}\left(n p^{2 s}-1\right)\right).

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

s

имаме, че

\operatorname{rad}_{p}\left(n p^{2 s}-1\right)

дели

f(n)-n^{\alpha}

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

x_{s}=n p^{2 s}-1

е безкрайно, можем да изберем подходящо

s

, за което

f(n)=n^{\alpha}

Отвори задачатаБаза на maths.bgsomnt2023-9-3