Контролно за национален отбор за БОМ

Задача 1

Пълен запис

Условие

Съществува ли множество

A \supset\{1, 2, \ldots, 2004\}

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

Решение

Решение. Съществува. Нека

a_0=1, a_i=2004! a_0 a_1 \ldots a_{i-1}-1, i \geq 1

и

A_i=\left\{2, 3, \ldots, 2004, a_0, a_1, \ldots, a_i\right\}, i \geq 0

. Тогава

\begin{gathered} \left(\prod_{a \in A_{i-1}} a-\sum_{a \in A_{i-1}} a^2\right)-\left(\prod_{a \in A_i} a-\sum_{a \in A_i} a^2\right)-1= \\ a_i^2-1-\left(a_i-1\right) \prod_{a \in A_{i-1}}=\left(a_i-1\right)\left(a_i+1-2004! a_0 a_1 \ldots a_{i-1}\right)=0 \end{gathered}

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

\prod_{a \in A_n} a=\sum_{a \in A_n} a^2

за

n=\prod_{a \in A_0} a-\sum_{a \in A_0} a^2

.

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

Задача 2

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

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

Задача 3

Пълен запис

Условие

Нека

A=\{1, 2, \ldots, n\}, n \geq 4

. За всяка функция

f: A \rightarrow A

и всяко

a \in A

дефинираме

f_{1}(a)=f(a), f_{i+1}(a)=f\left(f_{i}(a)\right), i \geq 1

. Да се намери броят на функциите

f: A \rightarrow A

, за които

f_{n-2}

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

f_{n-3}

не е константа.

Решение

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

G

с върхове елементите на

A

, в който е прекарано ориентирано ребро

x y

точно когато

f(x)=y

. Трябва да преброим графите

G

, за които:

(*)

не съществуват цикли с дължина, по-голяма от 1;

(*)

съществува верига

a_{2} \ldots a_{n}

с дължина

n-2

и не съществува верига с дължина

n-1

;

(*)

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

a_{1} a_{j}, 3 \leq j \leq n;

(*)

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

a_{n} a_{n}

. Веригата може да бъде избрана по

n

! начина, а реброто, което не е от неяпо

n-2

начина. Да забележим, че графите, за които това ребро е

a_{1} a_{3}

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

\binom{n}{2}(n-2)

!. Следователно отговорът на задачата е

n!(n-2)-\binom{n}{2}(n-2)\neq{}\frac{n!(2 n-5)}{2}

.

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

Задача 4

Пълен запис

Условие

Нека

A_{1} A_{2} \ldots A_{n}

е изпъкнал многоъгълник и

p_{i}

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

A_{i} A_{i+1}, 1 \leq i \leq n\left(A_{n+1} \equiv A_{1}\right)

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

\sum_{i=1}^{n} \frac{\left|A_{i} A_{i+1}\right|}{p_{i}}=4

, то многоъгълникът е правоъгълник.

Решение

Понеже даденият многоъгълник

A

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

2 p_{i}

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

A_{i} A_{i+1}

. Разглеждаме векторите

\overrightarrow{A_{1} A_{2}}, \overrightarrow{A_{2} A_{3}}, \ldots, \overrightarrow{A_{n} A_{1}}

и техните противоположни. От края на вектора

\overrightarrow{A_{1} A_{2}}

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

\vec{A}_{1} A_{2}

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

\overrightarrow{A_{i} A_{i+1}}

). За нанесения вектор правим същото и т. н. Получаваме изпъкнала фигура

B=B_{1} B_{2} \ldots B_{2 n}

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

B

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

O

. Нека

q_{i}

е проекцията на

B

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

B_{i} B_{i+1}

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

q_{i} \times \operatorname{dist}\left(B_{i} B_{i+1}, B_{i+n} B_{i+n+1}\right)

, съдържащ

B

, заключаваме, че

\frac{\left|B_{i} B_{i+1}\right|}{q_{i}} \leq 4 \frac{S_{\triangle B_{i} B_{i+1} O}}{S_{B}}

Оттук

\sum_{i=1}^{n} \frac{\left|A_{i} A_{i+1}\right|}{p_{i}}=\sum_{i=1}^{2 n} \frac{\left|B_{i} B_{i+1}\right|}{q_{i}} \leq 4,

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

B

образуват правоъгълник, т. е.

A

е правоъгълник.

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

Задача 5

Пълен запис

Условие

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

p(x)

и

q(x)

, всеки от които има по

m \geq 2

ненулеви коефициента. Да се намери минималният възможен брой ненулеви коефициенти на полинома

f(u, v)=p(u) q(v)- p(v) q(u)

.

Решение

Полиномите

p(x)=x^{m-1}+x^{m-2}+\cdots+x+1

и

q(x)=x^{m-1}+x^{m-2}+\cdots+ x+a, a \neq 1

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

2 m-2

(имаме

f(u, v)=(a-1)\left(u^{m-1}+u^{m-2}+\cdots+u\right)+(1-a)\left(v^{m-1}+v^{m-2}+\cdots+v\right)

). Ще докажем с индукция по

m

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

2 m-2

. Ако в

p(x)

или

q(x)

участва степен, която не се среща в другия, то ненулевите коефициенти в

f(u, v)

са поне

2 m

. Затова оттук нататък ще считаме, че в

p(x)

и

q(x)

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

p(x)

и

q(x)

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

f(u, v)

. При

m=2

имаме

p(x)=a x^{n}+b x^{k}

и

q(x)=c x^{n}+d x^{k}

, като

a d-b c \neq

0. Тогава

f(u, v)=(a d-b c) u^{n} v^{k}+(b c-a d) u^{k} v^{n}

има точно два ненулеви коефициента. При

m=3

нека

p(x)=x^{k}+a x^{n}+b x^{\ell}

и

q(x)=x^{k}+c x^{n}+d x^{\ell}

, като

a d-b c \neq 0

. Тогава

f(u, v)=(a d-b c) u^{\ell} v^{k}+(b c-a d) u^{\ell} v^{n}+(c-a) u^{k} v^{n}+ (a-c) u^{n} v^{k}+(d-b) u^{k} v^{\ell}+(b-d) u^{\ell} v^{k}

. Първите два коефициента са ненулеви, а тъй като равенствата

a=c

и

b=d

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

m \geq 4

и

p(x)=p_{1}(x)+a x^{n}+b x^{k}

и

q(x)=q_{1}(x)+c x^{n}+d x^{k}

, като

a d-b c \neq 0

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

p_{1}(x)

и

q_{1}(x)

имат по

m-2 \geq 2

ненулеви коефициента. Тогава

f(u, v)=f_{1}(u, v)+f_{2}(u, v)+f_{3}(u, v),

където

f_{1}(u, v)=p_{1}(u) q_{1}(v)-p_{1}(v) q_{1}(u), f_{2}(u, v)=\left(a u^{n}+b u^{k}\right) q_{1}(v)+\left(c v^{n}+\right. \left. d v^{k}\right) p_{1}(u)-\left(a v^{n}+b v^{k}\right) q_{1}(u)-\left(c u^{n}+d u^{k}\right) p_{1}(v)

и

f_{3}(u, v)=(a d-b c) u^{n} v^{k}+ (b c-a d) u^{k} v^{n}

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

p_{1}(x)

и

q_{1}(x)

са непропорционални, по индукционно предположение

f_{1}(u, v)

има поне

2(m-2)-2=2 m-6

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

f_{2}(u, v)

има поне 2 ненулеви коефициента, а

f_{3}(u, v)

има два ненулеви коефициента. Ако

p_{1}(x)=\alpha q_{1}(x), \alpha \neq 0

, получаваме

f_{2}(u, v)=

q_{1}(v)\left[(a-c \alpha) u^{n}+(b-d \alpha) u^{k}\right]

+q_{1}(u)\left[(c \alpha-a) v^{n}+(d \alpha-b) v^{k}\right].

Тъй като равенствата

a-c \alpha=0

и

b-d \alpha=0

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

f_{2}(u, v)

има поне

2(m-2)

ненулеви коефициента (два пъти повече от тези на

q_{1}(x)

). Заедно с двата ненулеви коефициента на

f_{3}(u, v)

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

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

Задача 6

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

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

Задача 7

Пълен запис

Условие

Нека

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

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

\left|A_{i} \cap A_{i+1}\right|\gt{}\frac{n-2}{n-1}\left|A_{i+1}\right|

за всяко

i=1, 2, \ldots, n\left(A_{n+1} \equiv A_{1}\right)

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

Решение

Можем да смятаме, че

A_{1}

е множеството с максимална мощност. Означаваме

A_{i} \cap A_{i+1}=B_{i}, i=1, 2, \ldots, n

. Тъй като

A_{n} \supset B_{n-1} \cup B_{n}

, получаваме

\begin{aligned} \left|A_{n}\right| & \geq\left|B_{n-1} \cup B_{n}\right|=\left|B_{n-1}\right|+\left|B_{n}\right|-\left|B_{n-1} \cap B_{n}\right| \\ & \gt{}\frac{n-2}{n-1}\left|A_{n}\right|+\frac{n-2}{n-1}\left|A_{1}\right|-\left|B_{n-1} \cap B_{n}\right| \end{aligned}

Оттук

\left|B_{n-1} \cap B_{n}\right|\gt{}\frac{n-2}{n-1}\left|A_{1}\right|-\frac{1}{n-1}\left|A_{n}\right| \geq \frac{n-3}{n-1}\left|A_{1}\right|

, т. е.

\mid A_{n-1} \cap A_{n} \cap \left. A_{1}\left|\gt{}\frac{n-3}{n-1}\right| A_{1} \right\rvert\,

. По-нататък, ако

C=A_{n-1} \cap A_{n} \cap A_{1}, A_{n-1} \supset C \cup B_{n-2}

и аналогично

\begin{gathered} \left|A_{n-1}\right| \geq\left|B_{n-2} \cup C\right|=\left|B_{n-2}\right|+|C|-\left|B_{n-2} \cap C\right| \\ \gt{}\frac{n-2}{n-1}\left|A_{n-1}\right|+\frac{n-3}{n-1}\left|A_{1}\right|-\left|B_{n-2} \cap C\right|. \end{gathered}

Оттук

\left|B_{n-2} \cap C\right|\gt{}\frac{n-3}{n-1}\left|A_{1}\right|-\frac{1}{n-1}\left|A_{n-1}\right| \geq \frac{n-4}{n-1}\left|A_{1}\right|

, т. е.

\left|A_{n-2} \cap A_{n-1} \cap A_{n} \cap A_{1}\right|\gt{}\frac{n-4}{n-1}\left|A_{1}\right|.

Индуктивно получаваме

\left|A_{n-k} \cap A_{n-k+1} \cap \cdots \cap A_{n-1} \cap A_{n} \cap A_{1}\right|\gt{}\frac{n-k-2}{n-1}\left|A_{1}\right|

за

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

и в частност,

\left|A_{2} \cap A_{3} \cap \cdots \cap A_{n-1} \cap A_{n} \cap A_{1}\right|\gt{}0

.

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

Задача 8

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

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

2004

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

9

Условие

Условие

Условие

Условие

Условие

Условие

Условие

Условие