IFYM

Български фестивал на младите математици

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

11 години2 класаИма видими липси

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

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

2014

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

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

f-ifym2014-8-1: има placeholder текст
d4-ifym2014-8-2: има placeholder текст
f-ifym2014-8-4: има placeholder текст
d2-ifym2014-10-3: има placeholder текст
f-ifym2014-10-3: има placeholder текст
f-ifym2014-10-4: има placeholder текст
d2-ifym2014-10-5: има placeholder текст
d2-ifym2014-10-6: има placeholder текст
d1-ifym2014-10-7: има placeholder текст
d3-ifym2014-10-8: има placeholder текст

8 · Ден 1

8 задачи

Задача 1

Пълен запис

Условие

Всяко от четирите числа

a, a+1, a+2

a+3

има точно 6 положителни делители. Съществуват точно 20 различни естествени числа, всяко от които е делител на поне едно от тези числа, като едно от тези 20 числа е 27. Намерете всички възможни стойности на

a

. (Числата 1 и

n

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

n

Решение

Отговор: 242. Числото 1 е общ делител и на четирите числа. Числото 2 е също общ делител на

a

a+2

или на

a+1

a+3

. Това означава, че измежду всички

4 \cdot 6=24

делители на

a, a+1, a+2

a+3

числото 1 броено 4 пъти, а числото 2 е броено 2 пъти. Тогава различните делители на

a, a+1, a+2

a+3

са най-много

4 \cdot 6-3-1=20

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

a+1

или

a+2

. От условието следва, че това число се дели на 27 и има шест различни делители. Ако това число има прост делител, различен от 3, то броят на делителите му е поне 8. Следователно това число е

3^{5}=243

, откъдето намираме

a+1=243

или

a+2=243

. Понеже 241 е просто число (и има само два делителя), вторият случай не води до Остава

a=242

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

242, 243, 244

и 245 изпълняват условието на задачата.

Отвори задачатаБаза на maths.bgd1-ifym2014-8-1

Задача 2

Пълен запис

Условие

Дадени са 26 тежести с тегла съответно

1, 2, 3, \ldots, 26

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

1, 2, 4, 8, 16

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

2, 7, 8, 15, 25

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

7+8=15

.) Намерете добро множество с 6 тежести и докажете, че не съществува добро множество със 7 тежести.

Решение

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

1, 5, 10, 23, 25, 26

образуват добро множество. Да допуснем, че има добро множество със 7 тежести. Сборът на четирите най-големи числа е

23+24+25+26=98

, като поради

23+26=24+25

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

1, 2, 3

или 4 елемента ще бъде число от 1 до 97. Имаме 7 единични подмножества, 21 подмножества с 2 елемента, 35 подмножества с 3 елемента и 35 подмножества с 4 елемента т. е. общо

7+21+35+35=98\gt{}97

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

Отвори задачатаБаза на maths.bgd1-ifym2014-8-2

Задача 3

Пълен запис

Условие

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

2014 \times 1

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

Решение

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

n

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

n \geq 1

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

n=1

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

n \leq k

и да разгледаме таблица с

n=k+1

пула. Нека върху дъската има

t

черни пула. Ако

t

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

\leq k

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

t-2

(ако съседния на махнатия пул е бил черен) или

t

(ако съседния на махнатия пул е бил бял) и според индукционното допускане можем да премахнем всички пулове. Ако

t

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

Отвори задачатаБаза на maths.bgd1-ifym2014-8-3

Задача 4

Пълен запис

Условие

Определете най-малката възможна стойност на

a+b+c+d

, ако

a, b, c, d

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

\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}=\frac{9}{14}

Решение

Отговор: 25. От условието и от неравенството между средното аритметично и средното хармонично

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

получаваме

a+b+c+d \geq \frac{4^{2}.14}{9}=24 \frac{8}{9}

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

a+b+c+d \geq 25

, като при

(a; b; c; d)=(6; 6; 6; 7)

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

a+b+c+d=25

Отвори задачатаБаза на maths.bgd1-ifym2014-8-4

Задача 5

Пълен запис

Условие

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

p, q

r

, за които

p+q\lt{}111

\frac{p+q}{r}=p-q+r

Да се намери най-голямата стойност на произведението

p q r

Решение

Отговор: 2014. Понеже

p+q

p-q

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

r

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

\frac{p+q}{r}

ще има четността на

p+q

, а

p-q+r

ще има четността на

p+q+1

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

r=2

и получаваме

p=3 q-4

. Сега от

p+q\lt{}111

намираме

4 q-4\lt{}111

или

q\lt{}29

и значи

q=2, 3, 5, 7, 11, 13, 17, 19

или 23. При

q=23

получаваме

p=65

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

q=19

намираме

p=53

- просто число. Търсеният максимум е

2 \cdot 19 \cdot 53=2014

Отвори задачатаБаза на maths.bgd1-ifym2014-8-5

Задача 6

Пълен запис

Условие

Някои от върховете на правилен 2014 -ъгълник

A

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

A

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

Решение

Ще докажем, че върховете на

A

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

\left\lceil\frac{2014}{3}\right\rceil=672

са оцветени в един цвят.

Отвори задачатаБаза на maths.bgd1-ifym2014-8-6

Задача 7

Пълен запис

Условие

Точка

M

е среда на страната

A B

на триъгълник

A B C

. Правата

C M

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

\triangle A B C

в точка

P

, а точката

Q

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

P

спрямо

M

. Правата

B Q

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

A C

в точка

R

. Ако

C R M B

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

\angle B R C

Решение

Отговор:

90^{\circ}

. Понеже

M

е среда на

A B

P Q

, то

A P B Q

е успоредник. Тогава

\angle P B M=\angle Q A B

. Тъй като

\angle R C M=\angle R B M

\angle A C P=\angle A B P

, то

\angle Q B A= \angle P B M=\angle Q A B

. В

\triangle A B Q

имаме, че

Q B=Q A

M

е среда на

A B

, откъдето

R M \perp A B

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

\angle B R C=\angle B M C=90^{\circ}

Отвори задачатаБаза на maths.bgd1-ifym2014-8-7

Задача 8

Пълен запис

Условие

\triangle A B C

е построена ъглополовящата

A P, (P \in B C)

. Точката

M

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

A P

, а точката

N

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

M

спрямо средата на

B C

. Правата

C N

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

A B

в точка

E

(

B

е между

A

E

), а правата

B N

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

A C

в точка

D(C

е между

A

D)

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

C D=B E

Решение

Понеже

M B N C

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

M B \| N E

, откъдето

S_{M B E}=S_{M B N}= \frac{1}{2} S_{M B N C}

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

M C \| B D

имаме

S_{M C D}=S_{M B C}=\frac{1}{2} S_{M B N C}

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

S_{M B E}=S_{M C D}

и понеже

M

е точка от ъглополовящата, получаваме

B E=C D

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

8 · Ден 2

8 задачи

Задача 1

Пълен запис

Условие

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

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

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

n \geq 1

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

a_{n+1} \leq a_{1}+\cdots+a_{n}

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

Решение

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

t \leq a_{1}+\cdots+a_{n}

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

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

. При

t=1

имаме

1=a_{1}

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

t \leq a_{1}+\cdots+a_{n}

. Да изберем число

k

, за което

a_{1}+\cdots+a_{n}\lt{}k \leq a_{1}+\cdots+a_{n}+a_{n+1}

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

0 \leq a_{1}+\cdots+a_{n}-a_{n+1}\lt{}k-a_{n+1}\lt{}a_{1}+\cdots+a_{n}

и числото

t=k-a_{n+1}

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

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

. Тогава

k=t+a_{n+1}

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

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

Отвори задачатаБаза на maths.bgd2-ifym2014-8-1

Задача 2

Пълен запис

Условие

Държава има

n

града, някои свързани с двупосочни авиолинии. Има

r\gt{}2014

маршрути между градове, включващи не повече от 1 прекачване (посоката на движение е важна). Намерете най-малкото възможно

n

и най-малкото възможно

r

за това

n

Решение

Ако град е свързан с

m

други града, той е краен пункт за

m

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

m(m-1)

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

n-1

13 \cdot 122\lt{}2014

, така че

n \geq 14

. Нека

n=14

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

r

е четно:

r \geq 2016

. Можем да получим

r=2016=14 \cdot 122

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

Отвори задачатаБаза на maths.bgd2-ifym2014-8-2

Задача 3

Пълен запис

Условие

Точката

D

е среда на дъгата

A C B

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

\triangle A B C

. Окръжност през точките

D

C

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

C A

C B

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

M

N

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

A M=B N

Решение

Разглеждаме

\triangle B N D

A M D

. Имаме:

(*)

\angle N B D=\angle C B D=\angle C A D=\angle M A D

(*)

A D=B D

(*)

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

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

A M=B N

Отвори задачатаБаза на maths.bgd2-ifym2014-8-3

Задача 4

Пълен запис

Условие

Нека

a, b, c

са дължините на страните на триъгълник. Да се докажат неравенствата:

\sqrt{\vphantom{x^2}2}(a+b+c) \leq

\sqrt{\vphantom{x^2}a^{2}+b^{2}}+\sqrt{\vphantom{x^2}b^{2}+c^{2}}+\sqrt{\vphantom{x^2}c^{2}+a^{2}}\lt{}

\sqrt{\vphantom{x^2}3}(a+b+c).

Решение

Имаме

a+b \leq \sqrt{\vphantom{x^2}2\left(a^{2}+b^{2}\right)} \Rightarrow \sqrt{\vphantom{x^2}a^{2}+b^{2}} \geq \frac{a+b}{\sqrt{\vphantom{x^2}2}}

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

|a-b|\lt{}c \Rightarrow

(a-b)^{2}\lt{}c^{2} \Leftrightarrow a^{2}+b^{2}\lt{}c^{2}+2 a b \Rightarrow \sqrt{\vphantom{x^2}a^{2}+b^{2}}+\sqrt{\vphantom{x^2}b^{2}+c^{2}}+\sqrt{\vphantom{x^2}c^{2}+a^{2}}\lt{}\sqrt{\vphantom{x^2}c^{2}+2 a b}+\sqrt{\vphantom{x^2}b^{2}+2 c a}+ \sqrt{\vphantom{x^2}a^{2}+2 b c} \leq \sqrt{\vphantom{x^2}3\left(\left(c^{2}+2 a b\right)+\left(b^{2}+2 c a\right)+\left(a^{2}+2 b c\right)\right)}=\sqrt{\vphantom{x^2}3}(a+b+c)

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

Отвори задачатаБаза на maths.bgd2-ifym2014-8-4

Задача 5

Пълен запис

Условие

Намерете всички

a, b, c \in \mathbb{N}

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

4^{a}+2^{b}+1=c^{2}

b\lt{}2 a

Решение

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

2^{b}\left(2^{2 a-b}+1\right)=(c-1)(c+1)

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

a, b, c

. Понеже е изпълнено

2^{b-1} \mid c-1

или

2^{b-1} \mid c+1 \Rightarrow 2^{b-1} \leq c+1

2^{b} \leq 2 c+2 \Rightarrow 2^{2 a-b}+1 \geq \frac{c-1}{2} \geq \frac{2^{b-1}}{2}-1 \Rightarrow 2^{2 a-b}+1 \geq \frac{2^{b-1}}{2}-1 \Rightarrow 2^{2 a-b-1}+1 \geq 2^{b-3}

. Допускаме, че

b \geq a+2

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

1 \geq 2^{2 a-b-1}\left(2^{(b-3)-(2 a-b-1)}-1\right)=2^{2 a-b-1}\left(2^{2 b-2 a-2}-1\right) \geq 3

, противоречие

\Rightarrow b \leq a+1

. Допускаме, че

b\lt{}a+1

. Тогава

\left(2^{a}\right)^{2}\lt{}4^{a}+2^{b}+1\lt{}\left(2^{a}+1\right)^{2}

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

4 a+2 b+1

е т. кв. по условие. Оттук

b=a+1

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

(a; b; c)=\left(a; a+1; 2^{a}+1\right), a \in N

Отвори задачатаБаза на maths.bgd2-ifym2014-8-5

Задача 6

Пълен запис

Условие

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

m

означаваме с

\tau(m)

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

m

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

n

, за които от

d \mid n, d \in \mathbb{N}

, следва

\tau(d) \mid \tau(n)

Решение

Отговор: Всички естествени числа, които са свободни от квадрати. Ако

n=p_{1} \ldots p_{k}

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

\tau(n)=2^{k}

. Всеки делител

d

на

n

има вида

p_{i_{1}} \ldots p_{i_{t}}

, където

\left\{i_{1}, \ldots, i_{t}\right\} \subseteq\{1, \ldots, k\}

. Тогава

\tau(d)=2^{i_{t}} \mid \tau(n)=2^{k}

. Нека

n

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

p^{t} \| n, p

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

t \geq 2

. Тогава

d=\frac{n}{p}

е делител на

n

, за който

\tau(d)

не дели

\tau(n)

(Докажете!).

Отвори задачатаБаза на maths.bgd2-ifym2014-8-6

Задача 7

Пълен запис

Условие

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

Решение

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

A

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

(*)

Когато за първи път някой читател (нека това е читател

B

) я напуска.

(*)

Когато влиза последният читател (нека това е читател

C

). Тъй като

B

си тръгва най-рано, то

A

е дошъл след напускането на

B

, аналогично

C

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

A

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

C

. Оттук заключваме, че измежду тройката

A, B

C

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

Отвори задачатаБаза на maths.bgd2-ifym2014-8-7

Задача 8

Пълен запис

Условие

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

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

на числата

1, 2, \ldots, 25

, за които всяко от числата

a_{1}, a_{1}+a_{2}, a_{1}+a_{2}+a_{3}, \ldots, a_{1}+a_{2}+\cdots+a_{25}

не се дели на 3.

Решение

Измежду числата

1, 2, \ldots, 25

имаме 9, които дават остатък 1 при деление на 3, 8, който дават остатък 2 и 8, които се делят на 3. Първо ще наредим числата, които не се делят на 3. Ако първото число е 2, то редицатаще бъде

2, 2, 1, 2, 1, 2, \ldots, 2, 1

и двойките са винаги повече. Следователно първото число е 1 и редицата с дължина 17 е

1, 1, 2, 1, 2, 1, 2, 1, 2, 1, \ldots, 1, 2

. Сега остава да поставим 8 -те нули (съответстващи на числата, които се делят на 3), като не може да имаме нула на първо място, а на всяко от останалите 17 места може да имаме произволен брой нули. Това означава, че търсим броя на решенията на

a_{1}+a_{2}+\cdots+a_{17}=8

, при

a_{i} \geq 0

. Този брой е

\binom{24}{16}

. Всяка редица от 0, 1 и 2 съответства на

8!.8!.9

! редици от числата

1, 2, \ldots, 25

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

\frac{24!.8!.9!}{16!}

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

8 · Ден 3

8 задачи

Задача 1

Пълен запис

Условие

Съществува ли безкрайно множество

A

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

A

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

Решение

Отговор: Съществува. Нека

p_{1}=2, p_{2}=3, p_{3}, \ldots

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

A=

\left\{a_{1}=p_{1}, a_{2}=p_{1}^{2}. p_{2}, \ldots, a_{n}=p_{1}^{2}, p_{2}^{2} \ldots p_{n-1}^{2} p_{n}, \ldots\right\}.

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

S

на числа от

A

и нека

a_{k}

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

S

се дели на

p_{k}

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

p_{k}^{2}

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

Отвори задачатаБаза на maths.bgd3-ifym2014-8-1

Задача 2

Пълен запис

Условие

Във вътрешността на триъгълник

A B C

, за който

\angle A B C=45^{\circ}

е избрана точка

D

така, че

\angle B A D=\angle B C D=45^{\circ}

. Ако

B D=6 \mathrm{~cm}

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

A D C B

Решение

Отговор:

18 \mathbf{c m}^{2}

. Нека

P

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

A D

B C

. Тогава

\triangle A P B

\triangle C D P

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

S_{A P B}=\frac{1}{2} B P^{2}

S_{C D P}=\frac{1}{2} D P^{2}

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

S_{A D C B}=S_{A P B}+S_{C D P}=\frac{1}{2} B P^{2}+\frac{1}{2} D P^{2}=\frac{1}{2} B D^{2},

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

\triangle B D P

. При

B D=6 \mathrm{~cm}

получаваме

S_{A D C B}=18 \mathrm{~cm}^{2}

Отвори задачатаБаза на maths.bgd3-ifym2014-8-2

Задача 3

Пълен запис

Условие

Четири деца си поделили

n

мъниста, където

n

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

n

Решение

Отговор: 432. Възможните бройки са

x+x+x+x=4 x

(възможно точно когато

n

се дели на 4 );

x+x+2 x+2 x=6 x

(точно когато

n

се дели на 6 );

x+2 x+2 x+2 x=7 x

(точно когато

n

се дели на 7 );

x+2 x+4 x+4 x=11 x

(точно когато

n

се дели на 11). Сред трицифрените числа има

900: 4=225

кратни на

4, 900: 6=150

кратни на 6,

(1001-105): 7=128

кратни на 7 и

(1001-110): 11=81

кратни на 11. Сред тях има

900: 12=75

кратни на 4 и

6, (1008-112): 28=32

кратни на 4 и

7; (1012-132): 44=20

кратни на 4 и

11; (1008-126): 42=21

кратни на 6 и

7; (1056-132): 66=14

кратни на 6 и

11; (1001-154): 77=11

кратни на 7 и

11; (1008-168): 84=10

кратни на 4, 6 и 7;

(1056-132): 132=7

кратни на 4, 6 и

11; 3

кратни на 4, 7 и

11(308, 616, 924); 2

кратни на 6, 7 и

11(462, 924)

и 1 кратно на

4, 6, 7, 11(924)

. Според принципа за включване и изключване, отговорът е

225+150+128+81-75-32-20-21-14-11+10+7+3+2-1=432

Отвори задачатаБаза на maths.bgd3-ifym2014-8-3

Задача 4

Пълен запис

Условие

Нека

n

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

a

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

2 n^{2}

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

n^{2}+a

не може да е точен квадрат.\

Решение

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

n^{2}+a=x^{2}

за някое

x \in N

. По условие

2 n^{2}=k a, k \in N

и тогава имаме

x^{2}=n^{2}+\frac{2 n^{2}}{k} \Longleftrightarrow\left(\frac{k x}{n}\right)^{2}=k^{2}+2 k

. Квадратът на рационалното число

\frac{k x}{n}

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

\frac{k x}{n}

е цяло число. Оттук

k^{2}+2 k

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

k^{2}\lt{}k^{2}+2 k\lt{}(k+1)^{2}

Отвори задачатаБаза на maths.bgd3-ifym2014-8-4

Задача 5

Пълен запис

Условие

Дадени са

n

монети, наредени по окръжност. (

n \geq 5

) В началото всички са ези. Имаме право на следните операции:

(*)

Избираме монета и ако тя е ези, обръщаме двата и съседа.

(*)

Избираме монета и ако тя е тура, обръщаме двата и съседа през едно (т. е. обръщаме тези две монети, които са съседи на съседите й). За кои

n

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

Решение

Нека означим монетите с

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

(*)

Случай:

n=4 k+2

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

a_{1}, a_{3}, a_{5}, \ldots, a_{4 k+1}

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

Отвори задачатаБаза на maths.bgd3-ifym2014-8-5

Задача 6

Пълен запис

Условие

По колко начина можем да подредим в кръг

x

жени и

y

мъже,

1 \leq y \leq x

, така че всеки мъж да е между две жени?

Решение

След като поставим първата жена (Ева), останалите жени могат да се разположат по

(x-1)

! начина. За всяка жена, започвайки от Ева надясно, да запишем номера на мъжа вдясно от нея, а ако такъв няма, да запишем *. Така разположението е кодирано с

y

различни числа и

x-y

звездички. Броят на тези кодове е

x!: (x-y)!

. Отговор:

\frac{(x-1)! x!}{(x-y)!}

Отвори задачатаБаза на maths.bgd3-ifym2014-8-6

Задача 7

Пълен запис

Условие

В редицата

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

числото

a_{n+1}

, (

n \geq 2

) е остатъкът на

a_{n}+a_{n-1}+1

при деление с 3. Ако

a_{93}=a_{1}

, то намерете

a_{1}

Решение

Всички остатъци в то са при деление на 3. Остатъкът на дадено число зависи само от остатъците на предишните две. Ако две поредни числа дават остатък 2, то това важи за всички числа в редицата. Редицата

1, 2, 1, 1, 0, 2, 0, 0, 1, 2, \ldots

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

2, 2, 2, \ldots

И в двата случая имаме

a_{n+8}=a_{n} \forall n

, а

a_{n+4}=a_{n}

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

a_{n+4}=2

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

2; a_{93}

a_{1}

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

Отвори задачатаБаза на maths.bgd3-ifym2014-8-7

Задача 8

Пълен запис

Условие

Върху страните

A C

B C

на триъгълник

A B C

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

B_{1}

A_{1}

. Ако

A A_{1}

B B_{1}

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

X

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

S_{X A_{1} B_{1}}\lt{}S_{A B X}; \quad

б)

S_{X A_{1} B_{1}}\lt{}S_{C B_{1} A_{1}}

Решение

а) Тъй като височината от

B

към

A C

е по-голяма от височината от

A_{1}

към

A C

, то

S_{A B B_{1}}\gt{}S_{A A_{1} B_{1}}

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

S_{A X B_{1}}

, получаваме исканото неравенство. б) Ако прекараме права през

B_{1}

, успоредна на

X A_{1}

и права през

A_{1}

, успоредна на

X B_{1}

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

y_{1}

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

\triangle B_{1} A_{1} C

. Понеже

\triangle B_{1} A_{1} Y \equiv \triangle A_{1} B_{1} Y_{1}

S_{B_{1} A_{1} Y_{1}}\lt{}S_{B_{1} A_{1} C}

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

S_{X A_{1} B_{1}}\lt{}S_{C B_{1} A_{1}}

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

8 · Ден 4

8 задачи

Задача 1

Пълен запис

Условие

Нека

m

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

p, q

r

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

r \equiv 5(\bmod 8)

. Да се намерят

m

q

, ако

2^{m} p^{2}+1=q^{r}

Решение

Отговор:

m=1, q=3

. От представянето

2^{m} p^{2}=(q-1)\left(q^{r-1}+q^{r-2}+\cdots+q+1\right)

и факта, че вторият множител отдясно е нечетен и по-голям от 1, следва, че

q-1=2^{m}

или

q-1=2^{m} p

. Случай 1. Ако

q-1=2^{m} p

, то

2^{m} p^{2}=\left(2^{m} p+1\right)^{r} \geq\left(2^{m} p+1\right)^{3}\gt{}2^{3 m} p^{3}

което е противоречие. Случай 2. Ако

q-1=2^{m}

, то

2^{m} p^{2}=\left(2^{m}+1\right)^{r}-1=2^{2 m} A+r \cdot 2^{m}

където

A

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

p^{2}=2^{m} A+r

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

m \geq 2

(противоречие по модул 8 ). При

m=1

получаваме

q=3

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

r=5

p=11

Отвори задачатаБаза на maths.bgd4-ifym2014-8-1

Задача 2

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd4-ifym2014-8-2

Задача 3

Пълен запис

Условие

На дъската е записано числото 1. Ако на дъската присъства числото

x

, то е разрешено там да се напишат още числата

3 x+2, 5 x-3

x-7

. Колко са трицифрените естествени числа, които никога не могат да се появят на дъската?

Решение

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

(*)

ако

3 x+2 \equiv 6(\bmod 7)

, то

3 x \equiv 4 \equiv 18(\bmod 7), x \equiv 6(\bmod 7)

;

(*)

ако

5 x-3 \equiv 6(\bmod 7)

, то

5 x \equiv 9 \equiv 30(\bmod 7), x \equiv 6(\bmod 7)

;

(*)

ако

x-7 \equiv 6(\bmod 7)

, то

x \equiv 6(\bmod 7)

. Ще покажем, че всяко друго трицифрено число може да се получи. Достатъчно е да покажем, че всяко от числата от 994 до 999 може да се получи, понеже всяко трицифрено число, което не дава остатък 6 при деление на 7, може да се получи от тези с многократно прилагане на последното правило. И така:

999 \leftarrow 1006 \leftarrow 1013 \leftarrow 337 \leftarrow 68 \leftarrow 22 \leftarrow 5 \leftarrow 1; 998 \leftarrow 332 \leftarrow 67 \leftarrow 14 \leftarrow 4 \leftarrow 11 \leftarrow 3 \leftarrow 10 \leftarrow 17 \leftarrow 5 \leftarrow 1; 997 \leftarrow 200 \leftarrow 66 \leftarrow 73 \leftarrow 80 \leftarrow 26 \leftarrow 8 \leftarrow 2 \leftarrow 1; 996 \leftarrow 1003 \leftarrow 1010 \leftarrow 336 \leftarrow 343 \leftarrow 350 \leftarrow 116 \leftarrow 38 \leftarrow 12 \leftarrow 3 \leftarrow 10 \leftarrow 17 \leftarrow 5 \leftarrow 1; 995 \leftarrow 331 \leftarrow 338 \leftarrow 112 \leftarrow 23 \leftarrow 7 \leftarrow 2 \leftarrow 1

. Трицифрените числа, които дават остатък 6 при деление на 7, са

(1000-104): 7=128

Отвори задачатаБаза на maths.bgd4-ifym2014-8-3

Задача 4

Пълен запис

Условие

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

A B

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

A B C

е избрана точка

M

. Точка

N

е външна за

\triangle A B C

\triangle A M N

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

A C

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

B N

в точка

D

, а правата

C M

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

A N

в точка

K

. Да се намери

\angle A D K

Решение

Отговор:

60^{\circ}

. Имаме

\triangle C A M \cong \triangle B A N

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

60^{\circ}

), откъдето

\angle A C K=\angle A B D

. Сега

\triangle C A K \cong \triangle B A D

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

A D=A K

и понеже

\angle D A K=60^{\circ}

, то

\triangle A D K

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

Отвори задачатаБаза на maths.bgd4-ifym2014-8-4

Задача 5

Пълен запис

Условие

Квадрат

31 \times 31

е разбит на квадрати

3 \times 3

5 \times 5

, както и на

n \geq 0

квадрати с по-малък размер. Определете най-малката възможна стойност на

n

и видовете квадрати от по-малък размер при нея.

Решение

Номерираме редовете и записваме -2 в полетата от

3, 6, 9, \ldots, 30

ред и 1 в останалите полета. Сборът на всички числа е 31, сборът в квадратите

3 \times 3

5 \times 5

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

2 \times 2

е 4 или -2, а сборът в квадратите

1 \times 1

е 1 или -2. Това сочи, че

n \geq 1

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

1 \times 1

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

1 \times 1

в центъра; остатъка разрязваме на 4 правоъгълника

15 \times 16

, всеки от които се състои от два

15 \times 3

и два

15 \times 5

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

3 \times 3

5 \times 5

Отвори задачатаБаза на maths.bgd4-ifym2014-8-5

Задача 6

Пълен запис

Условие

Всяка поредица от главни български букви ще наричаме дума. Ще казваме, че една дума е кротка, ако в нея не се среща РР (т. е. две съседни букви Р). Нека

A

е броят кротки думи с дължина 2014. Определете последната цифра на

A

Решение

Нека

a_{n}

е броят кротки думи с дължина

n

. Явно

a_{1}=30

a_{2}=899

(има

30 \cdot 30=900

комбинации, от които трябва да се махне РР). При

k\gt{}2

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

k-1

букви, или от P, следвана от не-Р, следвани от кротка дума с

k-2

букви. Така

a_{k}=29\left(a_{k-1}+a_{k-2}\right)

. Оттук

a_{3} \equiv 1

(

\bmod 10), a_{4} \equiv 0(\bmod 10), a_{5} \equiv 9(\bmod 10)

. Последните цифри на

a_{k}

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

a_{k-1}

a_{k-2}

) и понеже в редицата от последни цифри е

0, 9, 1, 0

, 9,... се срещат две поредни, които повтарят по-ранни две поредни, нататък редицата е периодична с период 3. От

2014 \equiv 1(\bmod 3)

следва

a_{2014} \equiv 9(\bmod 10)

Отвори задачатаБаза на maths.bgd4-ifym2014-8-6

Задача 7

Пълен запис

Условие

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

x, y

z

числата (

x- y)^{5}+(y-z)^{5}+(z-x)^{5}

(x-y)(y-z)(z-x)

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

Решение

Нека

a=x-y, b=y-z

c=z-x

. Имаме

a+b+c=0

(като

a, b, c \neq 0

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

a^{5}+b^{5}+c^{5}

a b c

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

a \geq b \geq c

. Тогава

a\gt{}0, c\lt{}0

и:

(*)

При

b\gt{}0

, то

a b c\lt{}0

a^{5}+b^{5}+c^{5}\lt{}(a+b)^{5}+c^{5}=(-c)^{5}+c^{5}=0

(*)

При

b\lt{}0

имаме

a b c\gt{}0

a^{5}+b^{5}+c^{5}\gt{}a^{5}+(b+c)^{5}=a^{5}+(-a)^{5}=0

Отвори задачатаБаза на maths.bgd4-ifym2014-8-7

Задача 8

Пълен запис

Условие

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

x

y

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

x^{2}+x=y^{3}-y

y^{2}+y=x^{3}-x

Решение

Отговор:

(0, 0), (0, -1), (-1, 0), (-1, -1), (2, 2)

. Записваме двете равенства във вида:

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

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

. Когато някое от

x

y

е равно на 0, 1 или -1 се разглеждат директно и се получават решенията

(0, 0), (0, -1), (-1, 0), (-1, -1)

. В противен случай (когато

x, y \neq 0, 1, -1

) намираме (

x-1

)(

y-1

)

=1

, откъдето

y=\frac{x}{x-1}

y+1=\frac{2 x-1}{x-1}

. След заместване в

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

получаваме

x^{4}-2 x^{3}=0

, откъдето

x=2

. Оттук

y=2

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

8 · Финал

8 задачи

Задача 1

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgf-ifym2014-8-1

Задача 2

Пълен запис

Условие

Страните

B C

A D

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

A B C D

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

O

. Ако

C D=A O, B C=O D

C A

е ъглополовяща на ъгъл

B C D

. Да се намери ъгъл

A B C

Решение

Отговор:

126^{\circ}

. От

B C \| A D

следва

\angle B C O=\angle C A D

, откъдето

\triangle A C D

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

A O=C D=A D

\triangle A O D

е също равнобедрен. Тогава

\angle A D O=\angle A O D

и отново от

B C \| A D

намираме

\angle C B O=\angle C O B

и значи

C B=C O

. Тогава

D O=O C=B C

\triangle C O D

е равнобедрен. Ако

\angle B C O=\alpha

, то

\angle C B O= \angle C O B=2 \angle O C D=2 \alpha

и от

\triangle C O B

намираме

\alpha=36^{\circ}

. Тогава

\triangle B C D

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

A D=C D=B D

, т. е.

\triangle A B D

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

\angle A B D=\frac{180^{\circ}-72^{\circ}}{2}=54^{\circ}

, откъдето

\angle A B C=54^{\circ}+72^{\circ}=126^{\circ}

Отвори задачатаБаза на maths.bgf-ifym2014-8-2

Задача 3

Пълен запис

Условие

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

n\gt{}3

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

Решение

Нека

A

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

B_{1}, B_{2}, \ldots, B_{k}

B_{i}

за

1 \leq i \leq k

познава

n_{i}\gt{}1

делегати. Ако

k=1

, то задачата е решена и нека сега

k \geq 2

. Всеки двама от

B_{1}, B_{2}, \ldots, B_{k}

имат общ познат

A

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

n_{1}, n_{2}, \ldots, n_{k}

са две по две различни. От друга страна, от избора на

A

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

[1, k]

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

1, 2, \ldots, k

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

n_{i}=1

за някое

i

, с което задачата е решена.

Отвори задачатаБаза на maths.bgf-ifym2014-8-3

Задача 4

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgf-ifym2014-8-4

Задача 5

Пълен запис

Условие

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

n

F(n)

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

n

. (Например

F(42)=1 \cdot 2 \cdot 3 \cdot 6 \cdot 7 \cdot 14 \cdot 21 \cdot 42

.) Да се намери най-малкото естествено число

k

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

n

, за което

F(n)=2014 n^{k}

Решение

Отговор: 3. Имаме

F(2014)=F(2 \cdot 13 \cdot 79)=

1 \cdot 2 \cdot 13 \cdot 79.(2 \cdot 13) \cdot(2 \cdot 79) \cdot(13 \cdot 79) \cdot(2 \cdot 13 \cdot 79)=

2^{4}.13^{4}.79^{4}=2014^{4}

което означава, че

F(2014)=2014 \cdot 2014^{3}

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

k \leq 3

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

k=1

или 2 съществува

n

, за което

F(n)=2014 n^{k}=2 \cdot 13 \cdot 79. n^{k}

. Тогава 2, 13 и 79 са делители на

n

и нека

2^{\alpha}

е най-високата степен на 2, която дели

n

. Степента на 2 в

F(n)=2014. n^{k}

1+k \alpha

. Числата

2^{\alpha}, 13 \cdot 2^{\alpha}, 79 \cdot 2^{\alpha}

13 \cdot 79 \cdot 2^{\alpha}

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

n

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

F(n)

се дели на

2^{4 \alpha}

, което означава, че

4 \alpha \leq 1+k \alpha

, т. е.

(4-k) \alpha \leq 1

Отвори задачатаБаза на maths.bgf-ifym2014-8-5

Задача 6

Пълен запис

Условие

Колко пъти се среща цифрата 5 в числото:

1+10+19+28+37+\cdots+10^{2014}?

Решение

В сбора

1+10+\cdots+10^{n}

имаме

\frac{10^{n}-1}{9}+1

събираеми. Тогава

1+10+\cdots+10^{n}=\left(\frac{10^{n}-1}{9}+1\right) \frac{10^{n}+1}{2}

Тъй като

\frac{10^{n}-1}{9}+1=\underbrace{11 \ldots 1}_{n-1} 2

, то

\frac{\frac{10^{n}-1}{9}+1}{2}=\underbrace{55 \ldots 5}_{n-2} 6

е число с

n-2

цифри 5 и една цифра 6. Трябва да намерим броя на цифрите 5 в числото

\underbrace{55 \ldots 5}_{n-2} 6\left(10^{n}+1\right)

. Понеже последните

n

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

\underbrace{55 \ldots 5}_{n-2} 6 \cdot 10^{n}

са нули, то търсеното число е

\underbrace{55 \ldots 5}_{n-2} 60 \underbrace{55 \ldots 5}_{n-2} 6

и петиците са

2.(n-2)

. При

n=2014

получаваме 4024.

Отвори задачатаБаза на maths.bgf-ifym2014-8-6

Задача 7

Пълен запис

Условие

Едно число

n

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

a\lt{}b\lt{}c

, за които

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

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

n

, за които

1 \leq n \leq 2014

Решение

Отговор: 2014. От равенството

(3 n+2)^{2}+(4 n)^{2}-(5 n+1)^{2}=2 n+3

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

\geq 9

(при

n=-1, 0, 2

не е изпълнено условието

a\lt{}b\lt{}c

) е квадратно. тъй като

1=4^{2}+7^{2}-8^{2}, 3=4^{2}+6^{2}-7^{2}, 5=4^{2}+5^{2}-6^{2}

7=10^{2}+14^{2}-17^{2}

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

(3 n)^{2}+(4 n-1)^{2}-(5 n-1)^{2}=2 n

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

\geq 4

(при

n=1

имаме

a=b)

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

2=5^{2}+11^{2}-12^{2}

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

Отвори задачатаБаза на maths.bgf-ifym2014-8-7

Задача 8

Пълен запис

Условие

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

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

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

a_{n+3}=5 a_{n+2}^{6}-4 a_{n+1}^{3}+a_{n}^{2}, \forall n \geq 1

\left\{a_{1}, a_{2}, a_{3}\right\}=\{2013, 2014, 2015\}

. Възможно ли е някой от членовете на редицата да бъде точна шеста степен на цяло число?

Решение

Отговор: Не!. Достатъчно е да докажем, че нито един член на редицата не е сравним с 0 или 1 по модул 7. От зададените начални условия следва, че

a_{1}, a_{2}

a_{3}

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

a_{n+2}, a_{n+1}

a_{n}

също имат исканото свойство. Тогава

a_{n+2}^{6} \equiv 1(\bmod 7)

a_{n+1}^{3} \equiv \pm 1(\bmod 7)

a_{n}^{2} \equiv 1, 2, 4(\bmod 7)

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

a_{n+3} \equiv 0, 1(\bmod 7)

е невъзможно.

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

10 · Ден 1

8 задачи

Задача 1

Пълен запис

Условие

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

a, b, c \in\left[\frac{1}{3}, 3\right]

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

\frac{a}{a+b}+\frac{b}{b+c}+\frac{c}{c+a} \geq \frac{7}{5}

Решение

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

c=\max \{a, b, c\}

, като от

a, b, c \in\left[\frac{1}{3}, 3\right]

следва

\frac{c}{9} \leq a \leq c

. При

s=\frac{b}{b+c}-\frac{7}{5}

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

(s+1) a^{2}+(s b+s c+2 c) a+(s+1) b c \geq 0 \tag{1}

При

s+1 \leq 0

е достатъчно да проверим верността на (1) при

a=\frac{c}{9}

a=c

. При

a=\frac{c}{9}

имаме:

\frac{a}{a+b}+\frac{b}{b+c}+\frac{c}{c+a}=\frac{c}{9 b+c}+\frac{b}{b+c}+\frac{c}{c+a}=

\frac{7}{5}+\frac{(3 b-c)^{2}}{2(9 b+c)(b+c)}

а при

a=c

имаме

\frac{a}{a+b}+\frac{b}{b+c}+\frac{c}{c+a}=\frac{3}{2}

При

s+1\gt{}0

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

s b+s c+2 c \geq 0

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

a=\frac{c}{9}

Отвори задачатаБаза на maths.bgd1-ifym2014-10-1

Задача 2

Пълен запис

Условие

Да се намери най-малкото естествено число

n

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

1=d_{1}\lt{}d_{2}\lt{}d_{3}\lt{}d_{4}\lt{}d_{5}\lt{}d_{6}\lt{}\cdots

, за които

d_{3}+d_{4}=d_{5}+6

d_{4}+d_{5}=d_{6}+7

Решение

Отговор: 494. От

d_{3}+d_{4}=d_{5}+6

следва, че измежду числата

d_{3}

d_{4}

d_{5}

има поне едно четно. Това означава, че

d_{2}=2

. Ако 4 дели

n

, то

d_{3}=3

или 4 и тогава

d_{4}=d_{5}+\left(6-d_{3}\right)\gt{}d_{5}

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

d_{3}

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

n

2 d_{3}

. Понеже измежду числата

d_{3}, d_{4}

d_{5}

има поне едно четно, то

d_{4}=2 d_{3}

или

d_{5}=2 d_{3}

. Ако

d_{4}=2 d_{3}

, то

d_{5}=3 d_{3}-6

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

n

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

d_{3} \neq 3

. Остава

d_{5}=2 d_{3}

, откъдето

d_{4}=d_{3}+6

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

d_{6}=3 d_{3}-1

, т. е.

d_{6}

е четно число. Тъй като

d_{4}=d_{3}+6

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

n

2 d_{4}

, откъдето

2 d_{4}=d_{6}

, т. е.

2\left(d_{3}+6\right)=2 d_{4}=d_{6}=3 d_{3}-1

От горното равенство намираме

d_{3}=13

и тогава

d_{4}=19, d_{5}=26

d_{6}=38

. Търсеното число е

2 \cdot 13 \cdot 19=494

Отвори задачатаБаза на maths.bgd1-ifym2014-10-2

Задача 3

Пълен запис

Условие

В остроъгълен

\triangle A B C

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

A H_{a}

B H_{b}

и точка

M

е средата на страната

A B

. Около

\triangle A M H_{a}

\triangle B M H_{b}

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

P

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

P

лежи на описаната около \triangle

A B C

окръжност.

Решение

Нека

X

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

k_{A M H_{a}}

k_{A B C}

. Тогава

\angle A X H_{a}=\angle B M H_{a}= 180^{\circ}-2 \beta

\angle A X C=180^{\circ}-\beta

, откъдето

H_{a} X C=\left(180^{\circ}-\beta\right)-\left(180^{\circ}-2 \beta\right)=\beta

. Тъй като

\angle H_{a} H_{b} C=\beta

, то

X

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

k_{A B C}

k_{H_{a} H_{b} C}

. Нека

Y

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

k_{B M H_{b}}

k_{A B C}

. Тогава

\angle A Y B=\gamma

\angle H_{b} Y B= \angle A M H_{b}=180^{\circ}-2 \alpha

, откъдето

\angle A Y H_{b}=\angle A Y B-\angle H_{b} Y B=\gamma-\left(180^{\circ}-2 \alpha\right)=\alpha-\beta

. От

\angle A Y C=180^{\circ}-\beta

сега намираме

\angle H_{b} Y C=180^{\circ}-\beta-(\alpha-\beta)=180^{\circ}-\alpha

. Тъй като

\angle H_{b} H_{a} C=\alpha

, то

H_{b} H_{a} C Y

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

Y

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

k_{A B C}

k_{H_{a} H_{b} C}

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

X \equiv Y \equiv P

P

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

\triangle A B C

окръжност.

Отвори задачатаБаза на maths.bgd1-ifym2014-10-3

Задача 4

Пълен запис

Условие

Един квадрат със страна 1 е оцветен в три цвята. Koe е най-голямото реално число

\alpha

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

\alpha

Решение

Отговор:

\sqrt{\vphantom{x^2}\frac{65}{64}}

. Разгледайте следните случаи: (1) два противоположни върха на квадрата са оцветени в един и същи цвят; (2) всеки два противоположни върха на квадрата са оцветени в различни цветове; (2 \cdot 1) за цвета

c

няма връх, оцветен в този цвят. Без загуба на общност, нека върховете

A

B

са бели, а

C

D

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

M, M \in A D, A M: M D=1: 3

; и

N, N \in B C, B N: N C=1: 1

. (2 \cdot 2) за всеки цвят има връх, оцветен в този цвят. Без загуба на общност, нека върховете

A

B

са бели,

C

е зелен и

D

е червен. Разгледайте точките

M, M \in A D

A M: M D=1: 7; N, N \in B C, B N: N C=1: 7

; и

P, P \in C D, C P: P D=1: 1

Отвори задачатаБаза на maths.bgd1-ifym2014-10-4

Задача 5

Пълен запис

Условие

Нека

f(x)

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

a

b

такива, че

f(a)

f(b)

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

x

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

f(x)

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

Решение

Нека

a

b

са такива, че

(f(a), f(b))=1

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

c \in Z

, за което

c \equiv a(\bmod f(b)), c \equiv b(\bmod (a))

. Оттук

f(c) \equiv f(a) (\bmod f(b))

f(c) \equiv f(b)(\bmod f(a))

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

(f(a), f(c))=1

(f(c), f(b))=1

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

d \in Z

, за което

d \equiv a(\bmod f(c)), d \equiv b(\bmod f(a)), d \equiv c (\bmod f(b))

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

Отвори задачатаБаза на maths.bgd1-ifym2014-10-5

Задача 6

Пълен запис

Условие

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

x_{i} \geq 0, i=1, 2, \ldots, n, n \geq 3

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

\begin{aligned} & \sum_{i=1}^{n} \frac{x_{i}}{x_{i+1}+x_{i+2}} \geq \frac{n}{2} \\ & \sum_{i=1}^{n} \frac{x_{i}}{x_{i-1}+x_{i-2}} \geq \frac{n}{2} \end{aligned}

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

1, 2, \ldots, n

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

n

, т. е.

x_{0}=x_{n}, x_{-1}=x_{n-1}

x_{n+1}=x_{1}

x_{n+2}=x_{2}

Решение

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

\sum_{i=1}^{n} \frac{x_{i}+x_{i+3}}{x_{i+1}+x_{i+2}} \geq n

. Имаме

\begin{aligned} \sum_{i=1}^{n} \frac{x_{i}+x_{i+3}}{x_{i+1}+x_{i+2}} & =\sum_{i=1}^{n}\left(\frac{x_{i}+x_{i+3}+x_{i+1}+x_{i+2}}{x_{i+1}+x_{i+2}}-1\right)= \\ & =\sum_{i=1}^{n} \frac{x_{i}+x_{i+1}}{x_{i+1}+x_{i+2}}+\sum_{i=1}^{n} \frac{x_{i+2}+x_{i+3}}{x_{i+1}+x_{i+2}}-n= \\ & =\sum_{i=1}^{n} \frac{x_{i}+x_{i+1}}{x_{i+1}+x_{i+2}}+\sum_{i=1}^{n} \frac{x_{i+2}+x_{i+1}}{x_{i+1}+x_{i}}-n \geq n \end{aligned}

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

Отвори задачатаБаза на maths.bgd1-ifym2014-10-6

Задача 7

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd1-ifym2014-10-7

Задача 8

Пълен запис

Условие

В клас с

n

ученика в продължение на

k

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

k

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

\frac{n(n-3)}{6} \leq k \leq \frac{n(n-1)}{6}.

Решение

Да номерираме учениците с числата от 1 до

n

. Тъй като във всяка тройка

\{a, b, c\}

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

\{a, b\}, \{a, c\}

\{b, c\}

, то

3 k \leq\binom{ n}{2}

, откъдето

k \leq \frac{n(n-1)}{6}

. От друга страна тройките

\{a, b, c\}

, за които

a+b+c

се дели на

n

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

\{x, y, z\}

, за която

x+y+z

се дели на

n

. За избор на

x

имаме

n

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

y

поне

n-3

възможности (

y

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

x

z=n-x-y

или

z=2 n-x-y

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

x

y

). Това означава, че броят на различните тройки

\{a, b, c\}

, за които

a+b+c

се дели на

n

е поне

\frac{n(n-3)}{6}

, т. е.

k \geq \frac{n(n-3)}{6}

Отвори задачатаБаза на maths.bgd1-ifym2014-10-8

10 · Ден 2

8 задачи

Задача 1

Пълен запис

Условие

Всяка от клетките на таблица

2014 \times 2014

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

2 \times 2

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

3 \times 3

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

Решение

Да запишем 1 във всяка черна клетка и 0 във всяка бяла. Разглеждаме квадрат

3 \times 3

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

2 \times 2

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

4 \times 4

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

a+e+h

d+e+h

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

a=b

. Тъй като

e+h

g+f

са с еднаква четност (защото

e+h+g+f

е четно) и

a+e+h

g+f+b

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

a=b

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

a=b=c=d

и от

2014 \equiv 1(\bmod 3)

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

\begin{array}{|l|l|l|l|} \hline a & & & b \cr \hline & e & f & \cr \hline & g & h & \cr \hline e & & & d \cr \hline \end{array}

клетки на таблицата са едноцветни.

Отвори задачатаБаза на maths.bgd2-ifym2014-10-1

Задача 2

Пълен запис

Условие

Точката с координати (

p^{m}, q^{n}

), където

p

q

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

m

n

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

r

, където

r

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

r

Решение

Отговор: 5. От условието следва, че

p^{2 m}+q^{2 n}=r^{2}

. Случай 1. Ако

r=2 t

е четно, то

p

q

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

4 t^{2}=p^{2 m}+q^{2 n} \equiv 2(\bmod 4)

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

p=q=2

2^{2 m}+2^{2 n}=4 t^{2} \Longleftrightarrow 2^{2 n-2}\left(2^{2 m-2 n}-1\right)=t^{2}

(без ограничение на общността

m \geq n

). Оттук

2^{2(m-n)}-1

е точен квадрат, което е невъзможно. Случай 2. Ако

r

е нечетно, то

p

q

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

p=2

. Получаваме

2^{2 m}=r^{2}-q^{2 n}=\left(r-q^{n}\right)\left(r+q^{n}\right)

, откъдето

r-q^{n}=2^{u}, r+q^{n}=2^{v}, u+v=2 m

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

q^{n}=2^{u-1}-2^{v-1}

, което означава, че

v=1, u=2 m-1

и значи

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

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

2^{m-1}-1=1

, откъдето

m=2, q=3

n=1

r=5

Отвори задачатаБаза на maths.bgd2-ifym2014-10-2

Задача 3

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd2-ifym2014-10-3

Задача 4

Пълен запис

Условие

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

P, Q \in R[x]

, такива че:

P(2)=2, Q(x)

няма отрицателни корени,

(x-2) P\left(x^{2}-1\right) Q(x+1)=P(x) Q\left(x^{2}\right)+Q(x+1)

Решение

Полагаме

x=2. \Rightarrow P(2) Q(4)+Q(3)=0 \Rightarrow 2 Q(4)+Q(3)=0 \Rightarrow \exists a: Q(a)=0

3 \leq a \leq 4

Нека

b \geq 3

Q(b)=0

. Полагаме

x=b-1 \Rightarrow P(b-1) Q\left((b-1)^{2}\right)=0

. Допускаме, че

P(b-1)=0

и полагаме

x=-\sqrt{\vphantom{x^2}b} \Rightarrow Q(1-\sqrt{\vphantom{x^2}b})=0

, което е противоречие с условието

Q

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

\Rightarrow Q\left((b-1)^{2}\right)=0 \Rightarrow(b-1)^{2}

е корен на

Q

и освен това

(b-1)^{2}\gt{}b

, защото

b \geq 3

. \Rightarrow Можем да конструираме безкрайна растяща редица

\left\{c_{i}\right\}_{i=1}^{\infty}

от корени на

Q(x)

по следния начин:

c_{1}=a c_{i+1}=\left(c_{i}-1\right)^{2}

, за

i \geq 1 \Rightarrow Q\left(c_{i}\right)=0, \forall i \Rightarrow Q(x) \equiv 0

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

Отвори задачатаБаза на maths.bgd2-ifym2014-10-4

Задача 5

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd2-ifym2014-10-5

Задача 6

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd2-ifym2014-10-6

Задача 7

Пълен запис

Условие

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

A B C D

ъглите при върховете

A

C

са равни и ъглополовящата на ъгъла при върха

B

минава през средата на страната

C D

. Ако

C D= 3 A D

, да се намери отношението

\frac{A B}{B C}

Решение

Отговор:

\frac{5}{3}

. Нека

M

е средата на

D C

E

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

C

спрямо

B M

. Тъй като

B M

е ъглополовяща на

\angle A B C

, то

E \in A B

. Имаме

M D=M C

(по условие) и

M C= M E

(от симетрията), откъдето

\triangle D E C

е правоъгълен. От

B M \perp E C

сега намираме

B M \| E D

. Освен това

\angle B E M=\angle B C M=\angle B A D

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

A D \| E M

. Триъгълниците

B E M

E A D

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

\frac{E M}{A D}=\frac{C M}{A D}=\frac{\frac{C D}{2}}{A D}=\frac{3}{2}

B E=\frac{3}{2} A E, A B=\frac{5}{2} A E

, откъдето

\frac{A B}{B C}=\frac{A B}{B E}=\frac{5}{3}

Отвори задачатаБаза на maths.bgd2-ifym2014-10-7

Задача 8

Пълен запис

Условие

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

n\gt{}2

от добра таблица

n \times n

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

n

реда и

n-1

стълба също да е добра.

Решение

Да допуснем противното Ако съществува стълб

k

такъв, че за всеки два реда съществува стълб

m \neq k

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

k

и задачата е решена. Обратно, за всеки стълб съществуват 2 реда, такива че числата в пресечните клетки с него са от различна четност, а в пресечните клетки с всеки друг стълб са от еднкава четност. Разглеждаме граф с върхове редовете на нашата таблица. За всеки стълб избираме двата реда, изпълняващи горното условие и ги свързваме. Така получаваме неориентиран граф с

n

върха и

n

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

n\gt{}3

върха и поне

n

ребра има цикъл

C=h_{1}, h_{2}, \ldots h_{k}, h_{1}

. Сега за

h_{1}, h_{2}

по дефиниция съществува стълб

k

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

m \neq k

са от еднаква. Разсъждавайки аналогично за останалите двойки последователни ребра на

C

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

k

в редове

h_{2}, h_{3}, \ldots, h_{k}, h_{1}

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

k

Отвори задачатаБаза на maths.bgd2-ifym2014-10-8

10 · Ден 3

8 задачи

Задача 1

Пълен запис

Условие

През центъра

O

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

\triangle A B C

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

l

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

C A

в точка

N

и страната

B C

в точка

M

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

A M, B N

M N

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

M N

на всички построени триъгълници (когато правата

l

се мени) е една и съща.

Решение

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

A B C D

с основа

\triangle A B C

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

M N

през центъра

O

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

\triangle D M N

с височина

D O

- височината на тетраедъра. Очевидно

\triangle M N D

е търсения триъгълник, защото

D M=A M

D N=B N

Отвори задачатаБаза на maths.bgd3-ifym2014-10-1

Задача 2

Пълен запис

Условие

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

a_{0}=a_{1}=1, a_{n+1}=14 a_{n}-a_{n-1}

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

2 a_{n}-1

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

Решение

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

t^{2}-14 t+1=0

има корени

7 \pm 4 \sqrt{\vphantom{x^2}3}=\left(2 \pm \sqrt{\vphantom{x^2}3}^{2}\right.

. Ако разгледаме редицата

b_{0}=-1, b_{1}=1, b_{n+1}=4 b_{n}-b_{n-1}

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

2 a_{n}-1=b_{n}^{2}

Отвори задачатаБаза на maths.bgd3-ifym2014-10-2

Задача 3

Пълен запис

Условие

Граф

G

с 2014 върха не съдържа триъгълник. Ако множеството от степените на върховете на

G

\{1, 2, \ldots, k\}

, да се намери най-голямата възможна стойност на

k

Решение

Отговор: 1342. Да допуснем, че

k \geq 1343

и нека

A

е връх от степен

k

. Да разгледаме връх

B

, от степен поне 672. Ако

A

B

са свързани, от

1342+671=2013\gt{}2012

следва, че

A

B

са свързани с един и същи връх, т. е. има триъгълник, противоречие. Получихме, че всички 671 върха със степени

672, 673, \ldots 1342

не са свързани с

A

. Но тогава върховете в графа са поне

1+1343+671\gt{}2014

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

k \leq 1342

. Пример на граф със степени

\{1, 2, \ldots, 1342\}

е следния: Върховете са

A_{i}, i=1, 2 \ldots, 672

B_{j}, j=1, 2, \ldots, 1342

. Връх

A_{i}

е свързан с

B_{i}, B_{i+1}, \ldots, B_{1342}

. Степента на

A_{i}

при

i= 1, 2 \ldots, 672

1343-i

, а степента на

B_{j}

за

j=1, 2, \ldots, 671

j

Отвори задачатаБаза на maths.bgd3-ifym2014-10-3

Задача 4

Пълен запис

Условие

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

x, y, z

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

\frac{x}{y+z}+\frac{25 y}{z+x}+\frac{4 z}{x+y}\gt{}2

Решение

Имаме

\begin{aligned} \frac{x}{y+z}+\frac{25 y}{z+x}+\frac{4 z}{x+y} & =(x+y+z)\left(\frac{1}{y+z}+\frac{25}{z+x}+\frac{4}{x+y}\right)-(1+25+4)= \\ & =\frac{1}{2}((y+z)+(z+x)+(x+y))\left(\frac{1}{y+z}+\frac{25}{z+x}+\frac{4}{x+y}\right)-30 \geq \\ & \geq \frac{1}{2}(1+5+2)^{2}-30=2 \end{aligned}

Равенство имаме при

(y+z)^{2}=\frac{(z+x)^{2}}{25}=\frac{(x+y)^{2}}{4} \Leftrightarrow y+z=\frac{z+x}{5}=\frac{x+y}{2}

, или

(x, y, z)= (-3 t, t, -2 t)

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

Отвори задачатаБаза на maths.bgd3-ifym2014-10-4

Задача 5

Пълен запис

Условие

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

\triangle A B C

. Нека

P

Q

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

A B

, така че

P

е между

A

Q

. Нека

H_{1}

H_{2}

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

A

към

C P

C Q

. Нека

H_{3}

H_{4}

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

B

към

C P

C Q

. Нека

H_{3} H_{4} \cap B C=X

H_{1} H_{2} \cap A C=Y

, като

X

е след

B

, а

Y

е след

A

. Ако

X Y \| A B

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

C P

C Q

са изогонални, спрямо

\triangle A B C

Решение

Нека

\angle A C B=\gamma, \angle A C P=\varphi, \angle B C Q=\psi

\Rightarrow \angle C X H_{4}=90^{\circ}+\varphi-\psi-\gamma, \angle B H_{4} X=\gamma-\varphi, \angle C Y H_{1}=90^{\circ}-\varphi+\psi-\gamma, \angle A H_{1} Y=\gamma-\psi

. От синусови теореми за

\triangle B X H_{4}, \triangle B C H_{4}, \triangle A Y H_{1}, \triangle A C H_{1}

имаме:

\begin{gathered} \frac{1}{\sin (\gamma-\varphi)} \cdot \frac{\cos (\gamma+\psi-\varphi)}{\sin \psi}=\frac{C B}{B X}=\frac{C A}{A Y}=\frac{1}{\sin (\gamma-\psi)} \cdot \frac{\cos (\gamma-\psi+\varphi)}{\sin \varphi} \\ \Rightarrow \frac{\cos (\gamma+(\varphi-\psi))}{\cos (\gamma-(\varphi-\psi))}=\frac{\sin (\gamma-\psi)}{\sin \psi} \cdot \frac{\sin \varphi}{\sin (\gamma-\varphi)} \\ \Rightarrow \frac{\cos \gamma \cot (\varphi-\psi)-\sin \gamma}{\cos \gamma \cot (\varphi-\psi)+\sin \gamma}=\frac{\sin \gamma \cot \psi-\cos \gamma}{\sin \gamma \cot \varphi-\cos \gamma} \\ \Rightarrow \frac{\cos \gamma \frac{\cot \varphi \cot \psi+1}{\cot \psi-\cot \varphi}-\sin \gamma}{\cos \gamma \frac{\cot \varphi \cot \psi+1}{\cot \psi-\cot \varphi}+\sin \gamma}=\frac{\sin \gamma \cot \psi-\cos \gamma}{\sin \gamma \cot \varphi-\cos \gamma} \\ \Rightarrow \sin \gamma(\cot \varphi-\cot \psi)(\cos \gamma \cot \varphi \cot \psi+\cot \varphi \sin \gamma+\cot \psi \sin \gamma-\cos \gamma)=0 \\ \sin \gamma\gt{}0 \Rightarrow(\cot \varphi-\cot \psi)(\cos \gamma \cot \varphi \cot \psi+\cot \varphi \sin \gamma+\cot \psi \sin \gamma-\cos \gamma)=0 \end{gathered}

Ако

\cot \varphi-\cot \psi=0

, то

\varphi=\psi

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

\begin{gathered} \cos \gamma \cot \varphi \cot \psi+\cot \varphi \sin \gamma+\cot \psi \sin \gamma-\cos \gamma=0 \\ \Rightarrow \frac{\cos \gamma}{\sin \gamma}=\frac{\cot \psi+\cot \varphi}{1-\cot \psi \cot \varphi} \\ \Rightarrow \operatorname{tg}\left(90^{\circ}-\gamma\right)=\operatorname{tg}\left(180^{\circ}-\varphi-\psi\right) \end{gathered}

но

\operatorname{tg}\left(90^{\circ}-\gamma\right)\gt{}0

, а

\operatorname{tg}\left(180^{\circ}-\varphi-\psi\right)\lt{}0

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

Отвори задачатаБаза на maths.bgd3-ifym2014-10-5

Задача 6

Пълен запис

Условие

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

A

B

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

a \in A

b \in B

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

A

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

B

и всеки елемент на

B

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

A

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

a_{1}, a_{2} \in A

b_{1}, b_{2} \in B

такива, че двойките (

a_{1}, b_{1}

) и (

a_{2}, b_{2}

) са задружни, но (

a_{1}, b_{2}

) и (

a_{2}, b_{1}

) не са.

Решение

Да означим с

a_{1}

елементът на

A

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

B

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

B

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

b_{2} \in B

, който не е задружен с

a_{1}

. Освен това всеки елемент на

B

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

A

и нека

a_{2} \in A

е задружен с

b_{2}

(очевидно

a_{2} \neq a_{1}

). Ще докажем, че съществува

b_{1} \in B

такъв, че

a_{1}

е задружен с него, но

a_{2}

не е. Наистина, иначе всеки елемент задружен с

a_{1}

ще е задружен и с

a_{2}

, понеже

b_{2}

е задружен с

a_{2}

, но

a_{2}

не е с

b_{1}

, то излиза че

a_{2}

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

a_{1}

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

a_{1}

. В такъв случай съществува

b_{1} \in B

, който е задружен с

a_{1}

, но не и с

a_{2}

и така избраните двойки (

a_{1}, b_{1}

) и (

a_{2}, b_{2}

) изпълняват условието на задачата.

Отвори задачатаБаза на maths.bgd3-ifym2014-10-6

Задача 7

Пълен запис

Условие

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

f: N \rightarrow N

, за които

f(f(n)+m)=n+f(m+2014)

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

m, n

Решение

Полагайки

m=f(1)

получаваме

f(f(n)+f(1))=n+f(f(1)+2014)=n+ 1+f(4028)=f(f(n+1)+2014)

. Оттук след добавяне на

m

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

f(f(f(n)+f(1))+m)=f(f(f(n+1)+2014)+m) \rightarrow f(n)+f(1)+f(m+2014)= f(n+1)+2014+f(m+2014) \rightarrow f(n+1)-f(n)=f(1)-2014=a \rightarrow f(n)=\operatorname{sum}_{k=1}^{n-1}(f(k+1)- f(k))+f(1)=a n+2014

. След заместване в условието стигаме до

a^{2} n+2014 a+a m+2014= n+a(m+2014)+2014

и ако

a=-1

, то

f(n)=-n+2014\lt{}0

при

n \geq 2015

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

a=1

f(n)=n+2014

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

Отвори задачатаБаза на maths.bgd3-ifym2014-10-7

Задача 8

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgd3-ifym2014-10-8

10 · Ден 4

8 задачи

Задача 1

Пълен запис

Условие

Да се намерят всички двойки естествени числа (

m, n

), за които

m \mid 2^{\varphi(n)}+1

n \mid 2^{\varphi(m)}+1

Решение

Очевидно

m

n

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

\varphi(m)=2^{m_{0}} m_{1}

\varphi(n)=2^{n_{0}} n_{1}

, където

m_{0}

n_{0}

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

m_{1}

n_{1}

са нечетни естествени числа. Без ограничение на общността можем да считаме, че

m_{0} \geq n_{0}

. Нека

k=2^{k_{0}} k_{1}

е показателят на 2 по модул

n

(тук

k_{0}

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

k_{1}

е нечетно естествено число. От

k \mid \varphi(n)

следва, че

k_{0} \leq n_{0}

. От

2^{\varphi(m)} \equiv-1(\bmod n)

следва, че

2^{2 \varphi(m)} \equiv 1(\bmod n)

и значи

k \mid 2 \varphi(m)

, т. е.

2^{k_{0}} k_{1} \mid 2^{m_{0}+1} m_{1}

. Освен това

n

не дели

2^{\varphi(m)}-1

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

k

не дели

\varphi(m)

, т. е.

2^{k_{0}} k_{1}

не дели

2^{m_{0}} m_{1}

. Това може да се случи само ако

k_{0}=m_{0}+1

. Получихме

m_{0} \geq n_{0} \geq k_{0}=m_{0}+1

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

m

n

е равно на 1 и вече лесно получаваме решенията

(1, 1), (1, 3)

(3, 1)

Отвори задачатаБаза на maths.bgd4-ifym2014-10-1

Задача 2

Пълен запис

Условие

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

n

, за което

n \cdot 2^{2^{2014}}-81-n

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

Решение

Отговор: Да. За всяко

k \in N

имаме

A=3 \prod_{l=1}^{k-1}\left(2^{2^{l}}+1\right)

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

2^{2^{i}}+1

за

1 \leq i \leq k-1

са две по две взаимнопрости (Защо?). Тогава от Китайската теорема за остатъците съществува естетвено число

c

, за което

c \equiv 2^{2^{l-1}}\left(\bmod 2^{2^{l}}+1\right), l \in[1, k-1]

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

c^{2}+1 \equiv 2^{2^{l}}+1 \equiv 0\left(\bmod 2^{2^{l}}+1\right)

A

дели

3\left(c^{2}+1\right)

и значи

A

дели

81 c^{2}+81

. Тогава

81 c^{2}+81=n A

, или

(9 c)^{2}=n A-81

, с което търсеният отговор е „Да“.

Отвори задачатаБаза на maths.bgd4-ifym2014-10-2

Задача 3

Пълен запис

Условие

Всяка поредица от главни български букви ще наричаме дума. Ще казваме, че една дума е кротка, ако в нея не се среща РР (т. е. две съседни букви Р). Запишете в явен вид функцията

f(n)

, чиято стойност е броят кротки думи с дължина

n

Решение

Явно

f(0)=1

f(1)=30

(и

f(2)=899

: наистина има

30 \cdot 30=900

комбинации, от които трябва да се махне РВ). При

k\gt{}2

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

k-1

букви, или от P, следвана от не- P, следвани от кротка дума с

k-2

букви. Така

f(k)=29(f(k-1)+f(k-2))

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

z^{2}-29 z-29=0

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

z_{1, 2}=\frac{29 \pm \sqrt{\vphantom{x^2}957}}{2}

, така че търсим

f(n)=A z_{1}^{n}+B z_{2}^{n}

. Понеже

f(0)=1=A+B, B=1-A, f(1)=30= A z_{1}+(1-A) z_{2}=A \sqrt{\vphantom{x^2}957}+\frac{29-\sqrt{\vphantom{x^2}957}}{2}

, получаваме

A=\frac{1}{2}+\frac{31}{2 \sqrt{\vphantom{x^2}957}}, B=\frac{1}{2}-\frac{31}{2 \sqrt{\vphantom{x^2}957}}

. Остава да заместим

z_{1, 2}, A

B

f(n)

Отвори задачатаБаза на maths.bgd4-ifym2014-10-3

Задача 4

Пълен запис

Условие

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

A B C

, (

\angle A C B=90^{\circ}

). Точките

P

Q

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

B C

и точките

R

S

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

C A

са такива, че

\angle B A P=\angle P A Q=\angle Q A C

\angle A B S=\angle S B R=\angle R B C

. Ака

T

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

A P

B S

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

120^{\circ}\lt{}\angle R T B\lt{}150^{\circ}

Решение

Нека

\angle B A P=\alpha, \angle A B S=\beta

A Q \cap B R=H

. Тогава

\alpha+\beta=30^{\circ}

T

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

\triangle A B H

. Тогава

\angle A H B=180^{\circ}-2(\alpha+\beta)=120^{\circ}

H T

е ъглополовяща на

\angle A H B

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

\angle R H T=\angle A H T=\angle T H B=\angle B H Q=60^{\circ}

, откъдето

\triangle A R H \cong \triangle A T H

\triangle B Q H \cong \triangle B T H

\angle R T H=30^{\circ}

. Получаваме

\angle R T B=\angle R T H+\angle H T B=30^{\circ}+\angle H Q B=

30^{\circ}+\angle 90^{\circ}+\alpha=120^{\circ}+\alpha.

Тъй като

0\lt{}\alpha\lt{}30^{\circ}

, получаваме

120^{\circ}\lt{}\angle R T B\lt{}150^{\circ}

Отвори задачатаБаза на maths.bgd4-ifym2014-10-4

Задача 5

Пълен запис

Условие

Реалната функция

f

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

x

f(0)=0

. При това

f(9+x)=f(9-x)

f(x-10)=f(-x-10)

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

x

. Колко най-малко нули може да има

f

в интервала

[0; 2014]

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

f

да бъде непрекъсната?

Решение

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

f(18)=f(9+9)=f(9-9)=f(0)=0

; също за всяко реално

x

имаме

f(x)=f(9+(x-9))=f(9-(x-9))=f(18-x)=f((28-x)-10)= f((x-28)-10)=f(x-38)

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

k

е в сила

f(38 k)=0

(в дадения интервал има 54 такива числа) и

f(18+38 k)=0

(в дадения интервал има 53 такива числа). Можем да построим непрекъсната функция, която в

[0; 2014]

има само тези

54+53=107

числа за нули:

f(x)=x

за

x \in[-10; 9], f(x)=18-x

за

x \in[9; 28]

и по-нататък

f

се продължава 38 -периодично. И така, отговорът е 107 и не зависи от изискването

f

да е непрекъсната (впрочем не е трудно

f

да бъде направена дори аналитична).

Отвори задачатаБаза на maths.bgd4-ifym2014-10-5

Задача 6

Пълен запис

Условие

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

n

съществува кръг, който съдържа точно

n

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

Решение

Отговор: Да. Да разгледаме кръг с център (

\sqrt{\vphantom{x^2}2}, \sqrt{\vphantom{x^2}3}

) и радиус

r

, менящ се от 0 до

\infty

. Понеже за всяка стойност на

r

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

r

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

Отвори задачатаБаза на maths.bgd4-ifym2014-10-6

Задача 7

Пълен запис

Условие

На международна конференция има 4 официални езика. Всеки двама от участниците могат да говорят на един от тях. Докажете, че поне

60 \%

от участниците говорят на един и същи език.

Решение

Ако има участник, който говори само на един от езиците, то твърдението е очевидно. Нека с

X

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

Y

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

\mathrm{C} A, B, C

D

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

A B

C D; A C

B D

;

A D

B C

нямат общи елементи. Имаме освен това:

(*)|A|+|B|+|C|+|D| \geq 3|Y|+2|X| \text{.}

Без ограничение можем да приемем, че

X=A B+A C+B C

, или

X=A B+A C+A D

. Ако например

|D| \leq|Y|

, то от (\textit{) получаваме

|A|+|B|+|C| \geq 2|Y|+2|X|=2 n

, където с

n

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

\max |A|, |B|, |C| \geq \frac{2}{3} n

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

|A| \geq|X|=n-|Y|

. Ако сега

|A| \geq 0, 6 n

, всичко е ясно. Ако

|A|\lt{}0, 6 n

, то

|Y| \geq 0, 4 n

и от (}) ще получим

|A|+|B|+|C|+|D| \geq 3+2|X|=2 n+|Y| \geq 2, 4 n.

Отвори задачатаБаза на maths.bgd4-ifym2014-10-7

Задача 8

Пълен запис

Условие

Дадена е реална константа

c\gt{}1

. За редицата

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

имаме:

a_{1}=1, a_{2}=2

a_{m n}=a_{m} a_{n}

a_{m+n} \leq c\left(a_{m}+a_{n}\right)

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

a_{n}=n

Решение

Ако

a_{p}=q\gt{}p

, за някое

p

, имаме

\left. a_{p^{k}}\right)=q^{k}, k\gt{}0

. От друга страна имаме

a_{n}\lt{}c n

и при

n=p^{k}

ще получим

q^{k} \leq c p^{k}

, или

(q / p)^{k}\lt{}1

за всяко

k

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

a_{n} \leq n

за всяко

n

. Нека сега

a_{p}=q\lt{}p

за някое

p

и нека

p

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

p

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

k

толкова голямо, че

q^{k}\lt{}1 / c p^{k}-1

. Да изберем

n=p^{k}

m

такова, че

2^{m} \equiv 1(\bmod n)

. Нека

2^{m}=n t+1

. Тогава

2^{m}=a_{2^{m}}= a_{n t+1} \leq c\left(a_{n} t+1\right)=c\left(a_{n} a_{t}+1\right) \leq c\left(t a_{n}+1\right)\lt{}c(t 1 / c n-t+1) \leq t n=2^{m}-1

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

Отвори задачатаБаза на maths.bgd4-ifym2014-10-8

10 · Финал

8 задачи

Задача 1

Пълен запис

Условие

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

3 \times 4

или

4 \times 3

съдържа точно 8 бели квадратчета. По колко начина може да се направи това оцветяване?

Решение

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

3 \times 1

или

1 \times 3

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

3 \times 4

4 \times 3

, които имат общ квадрат

3 \times 3

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

A, B, C

е равен на броя на черните квадратчета измежду

D, E, F

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

E

F

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

A, B, C

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

A, B, C

и две над нея има поне по едно черно квадратче. Намерихме правоъгълник

4 \times 3

, в който има поне 6 черни квадратчета, противоречие. Ако

D

F

са черни, то същия

4 \times 3

правоъгълник съдържа поне 5 черни квадратчета. Ако над черно

D

има три бели, то в трите клетки до

D

няма черно и в правоъгълника

3 \times 4

, с долен десен ъгъл

D

ще има две черни съседни или през едно. Това означава, че всеки правоъгълник

3 \times 1

или

1 \times 3

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

3 \times 1

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

Отвори задачатаБаза на maths.bgf-ifym2014-10-1

Задача 2

Пълен запис

Условие

Върху квадратен тричлен Поли може да извършва следните действия:

(*)

Смяна на местата на старшия и свободния коефициент;

(*)

Заместване на

x

x-m

, където

m

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

6 x^{2}+2 x+1996

тя да получи

25 x^{2}+5 x+2014

с краен брой прилагания на операции от горния вид?

Решение

Отговор: Не!. Разглеждаме квадратния тричлен

f(x)=a x^{2}+b x+c

. При прилагане на разрешените операции

f(x)

добива съответно вида

g_{1}(x)=c x^{2}+b x+a

или

g_{2}(x)=a(x-m)^{2}+b(x-m)+c=a x^{2}+(b-2 m a) x+a m^{2}-b m+c

. Да забележим, че дискриминантата на

f(x)

D=b^{2}-4 a c

, а тези на

g_{1}(x)

g_{2}(x)

съответно

D_{1}=b^{2}-4 c a=D

D_{2}=(b-2 m a)^{2}-4 a\left(a m^{2}-b m+c\right)=b^{2}-4 a c=D

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

6 x^{2}+2 x+1996

е -47900, а тази на

25 x^{2}+5 x+2014

е -201375, то отговорът на задачата е не.

Отвори задачатаБаза на maths.bgf-ifym2014-10-2

Задача 3

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgf-ifym2014-10-3

Задача 4

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

Условие

BLANK BLANK BLANK

Решение

BLANK BLANK BLANK

Отвори задачатаБаза на maths.bgf-ifym2014-10-4

Задача 5

Пълен запис

Условие

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

\triangle A B C(a\gt{}b)

. Точка

D

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

C

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

A. O

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

\triangle A B C

окръжност.

M

е средата на

A C

. Нека

K

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

O

относно точка

M

. Нека

E \in B C

E O \perp A B. F \in M K

е такава, че

F K=O E

K

лежи между

F

M

. Нека

B D

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

\triangle A B C

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

P

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

A P \perp C F

Решение

Нека

A P \cap C F=Q

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

A M Q F

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

\angle Q F M=\angle Q A M

, но

\angle Q A M= \angle P B C \Rightarrow

достатъчно е да докажем, че

\angle C F M=\angle C B D

. Нека

\angle C A B=\alpha

\angle A B C=\beta, \angle A C B=\gamma, \angle C F O=\varphi

\angle C B D=\psi, C O=R

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

\varphi=\psi

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

\triangle A D C

\triangle C B D

\begin{gathered} C D=b \operatorname{tg} \frac{\alpha}{2}, \quad \frac{\sin \left(90^{\circ}-\beta+\psi\right)}{\sin \psi}=\frac{B C}{C D} \\ \frac{\cos (\beta-\psi)}{\sin \psi}=\frac{\sin \alpha}{\sin \beta \operatorname{tg} \frac{\alpha}{2}}=\frac{2 \cos ^{2} \frac{\alpha}{2}}{\sin \beta} \Rightarrow \cos \beta \cot \psi+\sin \beta=\frac{2 \cos ^{2} \frac{\alpha}{2}}{\sin \beta} \\ \Rightarrow \cot \psi=\frac{\cos \alpha+1-\sin ^{2} \beta}{\sin \beta \cos \beta} \end{gathered}

От синусова теорема за

\triangle C O E \Rightarrow E O=\frac{R \cos \alpha}{\cos \beta}

. Имаме, че

O M=M K=R \cos \beta

\begin{gathered} \Rightarrow F M=R \cos \beta+\frac{R \cos \alpha}{\cos \beta} \\ \Rightarrow \cot \varphi=\frac{F M}{M C}=\frac{R\left(\cos \beta+\frac{\cos \alpha}{\cos \beta}\right)}{R \sin \beta}= \\ =\frac{\cos \beta}{\sin \beta}+\frac{\cos \alpha}{\sin \beta \cos \beta}=\frac{\cos ^{2} \beta+\cos \alpha}{\sin \beta \cos \beta}= \end{gathered}

\begin{gathered} =\frac{\cos \alpha+1-\sin ^{2} \beta}{\sin \beta \cos \beta}=\cot \psi \\ \Rightarrow \cot \varphi=\cot \psi, 0^{\circ} \leq \varphi \leq 180^{\circ}, 0^{\circ} \leq \psi \leq 180^{\circ} \\ \Rightarrow \varphi=\psi, \end{gathered}

което трябваше да докажем.

Отвори задачатаБаза на maths.bgf-ifym2014-10-5

Задача 6

Пълен запис

Условие

Разполагаме с 19 ъгълчета (квадрат

2 \times 2

без едно единично квадратче) и неограничен брой квадрати

2 \times 2

. Да се намери най-голямото нечетно число

n

за което квадрат

n \times n

може да бъде покрит с дадените фигури.

Решение

Отговор: 9. Ще докажем, че при покриване на квадрат

(2 k-1) \times(2 k-1)

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

2 \times 2

са ни необходими поне

4 k-1

ъгълчета. Нека квадрат

(2 k-1) \times(2 k-1)

е покрит с

x

ъгълчета и

y

квадрати

2 \times 2

. Тогава

3 x+4 y=(2 k-1)^{2}

. Да оцветим клетките

(i, j)

(това е клетката, която се намира в

i

-ия ред и

j

-ия стълб), за които

i

j

са нечетни числа. Имаме точно

k^{2}

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

2 \times 2

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

x+y \geq k^{2}

. Тогава

y \geq k^{2}-x

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

(2 k-1)^{2}=3 x+4 y \geq 3 x+4\left(k^{2}-x\right)=4 k^{2}-x

откъдето

x \geq 4 k-1

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

n \geq 11=2 \cdot 6-1

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

n \times n

ще са необходими поне

4 \cdot 6-1=23

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

n \leq 9

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

n=9

Отвори задачатаБаза на maths.bgf-ifym2014-10-6

Задача 7

Пълен запис

Условие

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

Решение

Да означим състезателите с

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

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

A_{1}

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

A_{2}

), то

A_{1}

A_{2}

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

A_{1}

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

A_{2}

A_{3}

), то общия приятел на

A_{1}

A_{2}

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

A_{3}

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

A_{2}

A_{3}

са приятели. Тогава

A_{2}

A_{3}

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

A_{4}, \ldots, A_{12}

. Това означава, че някой от

A_{4}, \ldots, A_{12}

(без ограничение нека това е

A_{4}

) не е познат с

A_{2}

A_{3}

. Сега

A_{1}

A_{4}

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

A_{1}

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

A_{2}, A_{3}

A_{4}

. Ако между

A_{2}, A_{3}

A_{4}

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

A_{2}

A_{3}

), то

A_{1}

A_{4}

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

A_{2}, A_{3}

A_{4}

има поне две двойки приятели. Всеки от

A_{2}, A_{3}

A_{4}

има най-много 4 приятели, общо най-много 12 приятели. Това означава, че приятелите на

A_{2}, A_{3}

A_{4}

измежду 8 -те състезатели

A_{5}, \ldots, A_{12}

са най-много

12-3-2 \cdot 2=5

( 12 приятели без трите приятелства с

A_{1}

и без двете двойки приятелства измежду

A_{2}, A_{3}

A_{4}

, всяка от които се брой по два пъти). Следователно някой от

A_{5}, \ldots, A_{12}

(нека това е

A_{5}

) не е приятел с

A_{2}, A_{3}

A_{4}

и тогава

A_{1}

A_{5}

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

A_{1}

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

A_{1}

са

A_{2}, A_{3}, A_{4}

A_{5}

. Ако измежду

A_{2}, A_{3}, A_{4}

A_{5}

има три двойки приятели, то приятелите на

A_{2}, A_{3}, A_{4}

A_{5}

измежду 7 -те състезатели

A_{6}, \ldots, A_{12}

са най-много

4 \cdot 4-4-3 \cdot 2=6

. Това означава, че измежду

A_{6}, \ldots, A_{12}

има състезател (нека това е

A_{6}

), който не е приятел с

A_{2}, A_{3}, A_{4}

A_{5}

и тогава

A_{1}

A_{6}

нямат общ приятел. Следователно измежду

A_{2}, A_{3}, A_{4}

A_{5}

има най-много две двойки познати и понеже всеки от

A_{2}, A_{3}, A_{4}

A_{5}

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

A_{2}

A_{3}

, както

A_{4}

A_{5} \diamond

. Всеки от

A_{2}, A_{3}, A_{4}

A_{5}

има по двама приятели измежду

A_{6}, \ldots, A_{12}

и всеки от

A_{6}, \ldots, A_{12}

трябва да има приятел измежду

A_{2}, A_{3}, A_{4}

A_{5}

. Тогава точно един от

A_{6}, \ldots, A_{12}

(нека това е

A_{6}

) има двама приятели измежду

A_{2}, A_{3}, A_{4}

A_{5}

. Ако

A_{6}

е приятел с

A_{2}

A_{3}

съответно

A_{4}

A_{5}

), получаваме противоречие с Лемата, приложена за

A_{2}

(съответно

A_{4}

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

A_{2}, A_{3}, A_{4}

A_{5}

са:

A_{2}

е приятел с

A_{6}

A_{7}; A_{3}

е приятел с

A_{8}

A_{9}; A_{4}

е приятел с

A_{9}

A_{10}

A_{5}

е приятел с

A_{11} 6

A_{12}

. Общият приятел на

A_{4}

A_{6}

и на

A_{4}

A_{7}

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

A_{10}

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

A_{10}

е приятел с

A_{6}

и с

A_{7}

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

A_{6}

Отвори задачатаБаза на maths.bgf-ifym2014-10-7

Задача 8

Пълен запис

Условие

Няколко монети са разделени първо в 200 групи, а след това в 300 групи. Една монета е специална, ако при второто разделяне е била в група с по-малко монети отколкото при първото разделяне. Да се намери минималния брой специални монети.

Решение

Отговор: 101. Ако разделим 200 \cdot 101 монети първо в 200 групи от по 101 монети, а след това една от тези групи разделим на 101 групи от по една монета, ще получим второ разделяне на 300 групи и ще имаме точно 101 специални монети. Нека

x_{1} \leq x_{2} \leq \cdots \leq x_{200}

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

y_{1} \leq y_{2} \leq \cdots \leq y_{200}

е броят на монетите в тези групи. Тъй като

x_{1}+x_{2}+\cdots+x_{200}\gt{}y_{1}+y_{2}+\cdots+y_{200},

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

j

, за който

x_{1} \leq y_{1}, \ldots, x_{j-1} \leq y_{j-1}, x_{j}\gt{}y_{j}

Монетите от всяка група

y_{i}

за

1 \leq i \leq j

не са специални и следователно при първото разделяне те са били в група с брой монети

\leq y_{i}

. Но всички групи

x_{k}

за

k \geq j

имат повече монети от всяка група

y_{i}

за

1 \leq i \leq j

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

y_{1}, y_{2}, \ldots, y_{j}

са измежду монетите от

x_{1}, x_{2}, \ldots, x_{j-1}

. Тогава

y_{1}+y_{2}+\cdots+y_{j} \leq x_{1}+x_{2}+\cdots+x_{j-1}

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

x_{1} \leq y_{1}, \ldots, x_{j-1} \leq y_{j-1}, y_{j}\gt{}0

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

Отвори задачатаБаза на maths.bgf-ifym2014-10-8