maths.bgmaths.bg
Всички колекции
SOM

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

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

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

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

2023

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

9 · Алгебра

3 задачи

Задача 1

Пълен запис
Условие
Нека nn е естествено число. Да се намерят всички двойки ненулеви полиноми ff и gg с реални коефициенти от степен nn и n+1n+1 съответно, за които е изпълнено(f(x))2−f(x2)=g(x)(f(x))^{2}-f\left(x^{2}\right)=g(x)за всички реални xx.
РешениеНека f(x)=a0xn+an−kxk+…f(x)=a_{0} x^{n}+a_{n-k} x^{k}+\ldots, където an−kxka_{n-k} x^{k} е първият ненулев член, по-малък от старшия. Тогаваf(x)2=a02x2n+2a0an−kxn+k+…f(x)^{2}=a_{0}^{2} x^{2 n}+2 a_{0} a_{n-k} x^{n+k}+\ldots \quadf(x2)=a0x2n+an−kx2k+…. f\left(x^{2}\right)=a_{0} x^{2 n}+a_{n-k} x^{2 k}+\ldots.Разликата на тези полиноми е от степен 2n>n+12 n\gt{}n+1, освен ако a0=1a_{0}=1 (случаят n=1n=1 е разгледан по-долу). Следователно, a0=1a_{0}=1 и следващият коефициент на f(x)2−f(x2)f(x)^{2}-f\left(x^{2}\right) е 2an−kxn+k2 a_{n-k} x^{n+k}, който трябва да бъде старши коефициент на g(x)g(x), т. е. k=1k=1. Следователно, f(x)=xn+ax+b,a≠0f(x)=x^{n}+a x+b, a \neq 0, и g(x)g(x) се определя еднозначно от това:g(x)=2axn+1+(a2−a)x2+2abx+b2−b,g(x)=2 a x^{n+1}+\left(a^{2}-a\right) x^{2}+2 a b x+b^{2}-b,a≠0,a,b∈R. \quad a \neq 0, a, b \in \mathbb{R}.Ако n=1n=1, то f(x)=ax+b,g(x)=(a2−a)x2+2abx+b2−bf(x)=a x+b, g(x)=\left(a^{2}-a\right) x^{2}+2 a b x+b^{2}-b, следователно, за да бъдат това полиноми от степен съответно 1,2,a≠0,a≠1,a,b∈R1, 2, a \neq 0, a \neq 1, a, b \in \mathbb{R}.
Отвори задачатаБаза на maths.bgsomalg2023-9-1

Задача 2

Пълен запис
Условие
Нека a,b,ca, b, c са положителни реални числа. Да се докаже, че(a7−a4+3)(b7−b4+3)(c7−c4+3)≥(a+b+c)3.\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}.
РешениеНаблюдаваме, че x7−x4−x3+1=(x4−1)(x3−1)≥0x^{7}-x^{4}-x^{3}+1=\left(x^{4}-1\right)\left(x^{3}-1\right) \geq 0 за всяко положително xx, следователно a7−a4+3≥a3+2a^{7}-a^{4}+3 \geq a^{3}+2. Достатъчно е да докажем, че(a3+1+1)(b3+1+1)(c3+1+1)≥(a+b+c)3.\left(a^{3}+1+1\right)\left(b^{3}+1+1\right)\left(c^{3}+1+1\right) \geq(a+b+c)^{3}.Последното следва директно от неравенство на Хьолдер. Алтернативно, след разкриване на скобите в (a3+2)(b3+2)(c3+2)≥(a+b+c)3\left(a^{3}+2\right)\left(b^{3}+2\right)\left(c^{3}+2\right) \geq(a+b+c)^{3} получаваме неравенство, което следва от събиране на неравенствата:a3+b3c3+1≥3abca3b3c3+1+1≥3abca3+a3b3+1≥3a2ba3+a3c3+1≥3a2cb3+a3b3+1≥3b2ac3+a3c3+1≥3c2ab3c3+b3+1≥3b2cb3+c3+c3≥3c2b\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

Пълен запис
Условие
Нека ff е полином с реални коефициенти от степен n≥1n \geq 1 и старши коефициент 1 и нека x0<x1<x2<⋯<xnx_{0}\lt{}x_{1}\lt{}x_{2}\lt{}\cdots\lt{}x_{n} са цели числа. a) Да се докаже, че∑k=0n∣f(xk)∣∏j≠k∣xk−xj∣≥1\sum_{k=0}^{n} \frac{\left|f\left(x_{k}\right)\right|}{\prod_{j \neq k}\left|x_{k}-x_{j}\right|} \geq 1б) Да се докаже, че съществува kk, за което∣f(xk)∣≥n!2n\left|f\left(x_{k}\right)\right| \geq \frac{n!}{2^{n}}
РешениеФормулата в aa ) предполага използване на интерполационната формула на Лагранж: за точките x0,x1,…xnx_{0}, x_{1}, \ldots x_{n} и стойностите c0,c1,…cnc_{0}, c_{1}, \ldots c_{n} съществува единствен полином от степен ≤n\leq n със стойност cic_{i} в точката xix_{i}, и той e∑k=0nck∏j≠kx−xjxk−xj\sum_{k=0}^{n} c_{k} \prod_{j \neq k} \frac{x-x_{j}}{x_{k}-x_{j}}Следователно,f(x)=∑k=0nf(xk)∏j≠kx−xjxk−xj,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)∣≤|f(x)| \leq∑k=0n∣f(xk)∣∏j≠k∣x−xj∣∣xk−xj∣ \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|}Разделяме на xnx^{n} и оставяме x→∞x \rightarrow \infty и така получаваме aa ) (тук е важно, че старшият коефициент е 1 ). За б), използваме факта, че xjx_{j} са различни цели числа, следователно ∏j≠k∣xk−xj∣≥k!(n−k)!\prod_{j \neq k}\left|x_{k}-x_{j}\right| \geq k!(n-k)! и∑k=0n∣f(xk)∣k!(n−k)!≥1\sum_{k=0}^{n} \frac{\left|f\left(x_{k}\right)\right|}{k!(n-k)!} \geq 1Знаем, че∑k=0n1k!(n−k)!=\sum_{k=0}^{n} \frac{1}{k!(n-k)!}=1n!∑0nn!k!(n−k)!=2nn!,\frac{1}{n!} \sum_{0}^{n} \frac{n!}{k!(n-k)!}=\frac{2^{n}}{n!},следователно за поне едно kk е вярно, че ∣f(xk)∣≥n!/2n\left|f\left(x_{k}\right)\right| \geq n!/ 2^{n}.
Отвори задачатаБаза на maths.bgsomalg2023-9-3

9 · Геометрия

3 задачи

Задача 1

Пълен запис
Условие
Даден е триъгълник ABCA B C с BC>AB>ACB C\gt{}A B\gt{}A C. Нека точките B1B_{1} и C1C_{1} са на отсечките ACA C и ABA B съответно и отсечките BB1B B_{1} и CC1C C_{1} се пресичат в точка GG. Описаната около триъгълника BB1CB B_{1} C окръжност пресича отсечката ABA B за втори път в точката XX, а описаната около триъгълника BC1CB C_{1} C окръжност пресича отсечката BB1B B_{1} за втори път в точката PP. Допирателната в GG към описаната около триъгълника BGCB G C окръжност пресича отсечката CPC P в точка YY. Описаната около триъгълника GYCG Y C окръжност пресича отсечката BGB G за втори път в точката ZZ, а правите B1YB_{1} Y и XGX G се пресичат в точка TT. Ако ∠XC1G=∠XB1G\angle X C_{1} G=\angle X B_{1} G, то да се докаже, че ∠TC1B=∠TCZ\angle T C_{1} B=\angle T C Z.
РешениеПърво ще докажем, че (независимо от условието за равните ъгли) TT лежи на описаната около триъгълника BB1CB B_{1} C окръжностеквивалентно, ∠BXT=∠BB1T\angle B X T=\angle B B_{1} T. Имаме ∠CC1X=∠CPB1\angle C C_{1} X=\angle C P B_{1}, както и ∠CB1P=∠CXC1\angle C B_{1} P=\angle C X C_{1}, откъдето следва, че △CPB1∼△CC1X\triangle C P B_{1} \sim \triangle C C_{1} X. От друга страна ∠CGY=∠GBC=∠CC1P\angle C G Y=\angle G B C=\angle C C_{1} P, което значи, че C1P∥GYC_{1} P \| G Y. От Теорема на Талес следва, че C1GGC=PYYC\frac{C_{1} G}{G C}=\frac{P Y}{Y C}, следователно точките YY и GG са съответни елементи в подобните триъгълници. Така получаваме, че ∠PB1Y=∠C1XG\angle P B_{1} Y=\angle C_{1} X G, което е еквивалентно на ∠BXT=∠BB1T\angle B X T=\angle B B_{1} T. Сега от условието имаме, че ∠GC1X=∠GB1X=∠BTG\angle G C_{1} X=\angle G B_{1} X=\angle B T G, тоест точките B,C1,G,TB, C_{1}, G, T лежат на една окръжност. От ∠CGY=∠CBB1=∠CTB1\angle C G Y=\angle C B B_{1}=\angle C T B_{1} следва, че точките T,G,C,Y,ZT, G, C, Y, Z лежат на една окръжност. Сега от последните два вписани четириъгълника получаваме ∠TC1B=∠TGZ=∠TCZ\angle T C_{1} B=\angle T G Z=\angle T C Z, което искахме да докажем.
Отвори задачатаБаза на maths.bgsomgeo2023-9-1

Задача 2

Пълен запис
Условие
В изпъкналия четириъгълник ABCDA B C D ъглите при върховете AA и CC са остри. Нека B1,B2,B3B_{1}, B_{2}, B_{3} са петите на перпендикулярите от BB към AD,ACA D, A C и DCD C, съответно, и нека D1,D2,D3D_{1}, D_{2}, D_{3} са петите на перпендикулярите от DD към AB,ACA B, A C и BCB C, съответно. Да се докаже, че окръжностите, описани около триъгълниците B1B2B3B_{1} B_{2} B_{3} и D1D2D3D_{1} D_{2} D_{3}, се пресичат върху правата ACA C.
РешениеНека точката PP е такава, че ∠PAC=∠BAD,∠PCA=∠BCD\angle P A C=\angle B A D, \angle P C A=\angle B C D и PP и BB са в различни полуравнини спрямо ACA C. Нека също P1,P2P_{1}, P_{2} и P3P_{3} са петите на перпендикулярите от PP към AD,ACA D, A C и DCD C, съответно. Имаме △CBB2∼△CPP3\triangle C B B_{2} \sim \triangle C P P_{3} и △CBB3∼△CPP2\triangle C B B_{3} \sim \triangle C P P_{2}, откъдетоCB2CP3=CBCP=CB3CP2.\frac{C B_{2}}{C P_{3}}=\frac{C B}{C P}=\frac{C B_{3}}{C P_{2}}.Следователно точките P2,B2,P3P_{2}, B_{2}, P_{3} и B3B_{3} лежат на една окръжност и понеже симетралите на P2B2P_{2} B_{2} и P3B3P_{3} B_{3} се пресичат в средата на BPB P, то тази среда OO е център на тази окръжност. Аналогично P2,B2,P1P_{2}, B_{2}, P_{1} и B1B_{1} лежат на една окръжност със същия център OO, като всъщност тази и предишната окръжност съвпадат. В частност, описаната около триъгълника B1B2B3B_{1} B_{2} B_{3} окръжност минава през точката P2P_{2}, която лежи на ACA C. Аналогично като повторим описаната конструкция за DD спрямо ABCA B C ще получим, че ако QQ е аналогично дефинираната на PP точка, то описаните около триъгълниците ACPA C P и ACQA C Q окръжности са симетрични спрямо ACA C. Така аналогично дефинираната на P2P_{2} съвпада с P2P_{2} и лежи на окръжността около D1D2D3D_{1} D_{2} D_{3}, с което исканото е доказано.
Отвори задачатаБаза на maths.bgsomgeo2023-9-2

Задача 3

Пълен запис
Условие
Даден е разностранен триъгълник ABCA B C. Произволна окръжност ωC\omega_{C} се допира до правите CAC A и CBC B съответно в точките PP и QQ, като AA е между CC и P,BP, B е между CC и QQ и ωC\omega_{C} и триъгълника ABCA B C нямат общи точки. Окръжността ΩC\Omega_{C} минава през AA и BB и се допира до ωC\omega_{C} в точка TCT_{C} (като ωC\omega_{C} е във вътрешността на ΩC\Omega_{C} ). Правите PQP Q и ABA B се пресичат в точката KCK_{C}, а правата KCTCK_{C} T_{C} пресича ωC\omega_{C} за втори път в точката LCL_{C}. Аналогично се дефинират точките LAL_{A} и LBL_{B} (като произволните окръжности ωA,ωB\omega_{A}, \omega_{B} и ωC\omega_{C} са независими една от друга). Да се докаже, че правите ALAA L_{A}, BLBB L_{B} и CLCC L_{C} се пресичат в една точка.
РешениеЩе докажем, че (независимо от избора на ωC)CLC\left.\omega_{C}\right) C L_{C} минава през допирната точка C1C_{1} на вписаната окръжност на ABCA B C със страната ABA B. Тогава ще следва, че трите разглеждани прави се пресичат в точката на Жергон и задачата ще е решена. Нека ATCA T_{C} и BTCB T_{C} пресичат ωC\omega_{C} за втори път в точките XX и YY, съответно. Чрез хомотетията с център TCT_{C}, изпращаща ωC\omega_{C} в ΩC\Omega_{C} (или разглеждане на общата допирателна и съображения с периферни ъгли), получаваме XY∥ABX Y \| A B. Нататък, да забележим, че хомотетията с център CC, изпращаща вписаната окръжност на ABCA B C в ωC\omega_{C}, изпраща C1C_{1} в точка, чиято допирателна в ωC\omega_{C} е успоредна на ABA B, а оттук и на XYX Y - така тази точка е точно средата на дъгата XTCY^\widehat{X T_{C} Y} (и искаме да се окаже, че е LCL_{C} ). Следователно е достатъчно да докажем, че TCKCT_{C} K_{C} е външна ъглополовяща за ∠XTCY=∠ATCB\angle X T_{C} Y=\angle A T_{C} B, което е еквивалентно на AKCKCB=ATCBTC\frac{A K_{C}}{K_{C} B}=\frac{A T_{C}}{B T_{C}}. От теоремата на Менелай за триъгълника CPQC P Q и правата ABKCA B K_{C} получаваме CPPA⋅AKCKCB⋅BQQC=1\frac{C P}{P A} \cdot \frac{A K_{C}}{K_{C} B} \cdot \frac{B Q}{Q C}=1 и тъй като CP=CQC P=C Q, тоAKCKCB=APBQ.\frac{A K_{C}}{K_{C} B}=\frac{A P}{B Q}.От друга страна, чрез степените на точките AA и BB относно ωC\omega_{C} получаваме AP2=AX⋅ATCA P^{2}=A X \cdot A T_{C} и BQ2=BY⋅BTCB Q^{2}=B Y \cdot B T_{C} и следователноAP2BQ2=AXBY⋅ATCBTC=(ATCBTC)2\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}(последното от теоремата на Талес). Така AKCKCB=ATCBTC\frac{A K_{C}}{K_{C} B}=\frac{A T_{C}}{B T_{C}} и исканото следва.
Отвори задачатаБаза на maths.bgsomgeo2023-9-3

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

3 задачи

Задача 1

Пълен запис
Условие
В равнината са дадени 128 точки, всеки две от които са свързани с отсечка. Иван записва на всяка отсечка по една цифра, а след това Петър записва на всяка точка по една цифра. Ако има две точки на които е записана една и съща цифра и на отсечката между тях е записана същата цифра, печели Иван. В противен случай печели Петър. Да се определи кой има печеливша стратегия.
РешениеЩе докажем, че Иван има печеливша стратегия. Да разгледаме произволни 121 от дадените точки и да ги означим с двойките ( a,ba, b ), където aa и bb са числа от 1 до 11. Тъй като 11 е просто число, то за всеки две двойки A(a1,b1)A\left(a_{1}, b_{1}\right) и B(a2,b2)B\left(a_{2}, b_{2}\right) съществува най-много едно kk, за което a1−a2≡k(b1−b2)( mod 11)a_{1}-a_{2} \equiv k\left(b_{1}-b_{2}\right)(\bmod 11). Когато kk е цифра, Иван записва на отсечката ABA B цифрата kk. Върху останалите отсечки Иван записва произволни цифри. Директно се проверява, че ако върху отсечките ABA B и ACA C е записана една и съща цифра, то върху отсечката BCB C е записана същата цифра. Също така, за всяка цифра точките се разделят на 11 групи от по 11 точки, като във всяка група върху всички отсечки е записана една и съща цифра. Петър записва на тези 121 точки 121 цифри и следователно някоя цифра kk ще се среща 12 пъти. От принципа на Дирихле следва, че някои две от тези 12 точки ще са в една от 11 -те групи, на които се разделят дадените точки спрямо цвета kk. Получаваме две точки, на които е записана една и съща цифра kk и на отсечката между тях е записана същата цифра kk, т. е. печели Иван.
Отвори задачатаБаза на maths.bgsomcomb2023-9-1

Задача 2

Пълен запис
Условие
За всяко непразно множество AA от реални числа с S(A)S(A) означаваме сбора от елементите на AA. Да се намери най-малкото реално число tt със следното свойство: За всяко естествено число nn и всяко множество MM от nn положителни реални числа, множеството от всички непразни подмножества на MM може да се раздели на nn непресичащи се групи, така че ако PP и QQ са множества от една и съща група, то S(P)S(Q)≤t\frac{S(P)}{S(Q)} \leq t.
РешениеДа допуснем, че съшествува константа t<2t\lt{}2, която удовлетворява условието на задачата. Да разгледаме множеството M={1,2,22,…,2n−1}M=\left\{1, 2, 2^{2}, \ldots, 2^{n-1}\right\}. Сборът от числата на всички подмножества са точно двоичните представяния на числата от множеството B={1,2,3,…,2n−1}B=\left\{1, 2, 3, \ldots, 2^{n}-1\right\}. Да допуснем, че съществува разбиване на множеството BB на nn групи, така че отношението на всеки две числа в дадена група е по-малко от tt. Ясно е, че числата 1,2,22,…,2n−11, 2, 2^{2}, \ldots, 2^{n-1} трябва да са в различни групи. Нека B0,B1,…,Bn−1B_{0}, B_{1}, \ldots, B_{n-1} са групите, като 2k,0≤k≤n−12^{k}, 0 \leq k \leq n-1 лежи в BkB_{k}. Нека някое множество BkB_{k} съдържа повече от 2k2^{k} елемента. Ако aa е най-малкото число в BkB_{k}, то a≤2ka \leq 2^{k} и отношението на най-голямото число в BkB_{k} и aa е понеa+2ka=1+2ka≥2,\frac{a+2^{k}}{a}=1+\frac{2^{k}}{a} \geq 2,противоречие. Следователно общо във всички множества B0,B1,…,Bn−1B_{0}, B_{1}, \ldots, B_{n-1} числата са най-много 20+21+⋯+2n−1=2n−12^{0}+2^{1}+\cdots+2^{n-1}=2^{n}-1. От друга страна този брой е точно 2n−12^{n}-1 и следователно във всяко множество BkB_{k} има точно 2k2^{k} числа. Тогава отношението на най-малкото число aa в Bn−1B_{n-1} и най-голямото число в Bn−1B_{n-1} (което е поне a+2n−1−1a+2^{n-1}-1 ) е поне a+2n−1−1a=2−12n−1\frac{a+2^{n-1}-1}{a}=2-\frac{1}{2^{n-1}}. Следователноt≥2−12n−1t \geq 2-\frac{1}{2^{n-1}}което е невъзможно, тъй като t<2t\lt{}2. Нека M={a1,a2,…,an}M=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\} е произволно множество от положителни числа, за които a1<a2<⋯<an}\left. a_{1}\lt{}a_{2}\lt{}\cdots\lt{}a_{n}\right\}. Нека S0=0,Si=a1+⋯+aiS_{0}=0, S_{i}=a_{1}+\cdots+a_{i} за i=1,2,…,ni=1, 2, \ldots, n. Ако σ\sigma е сбор на елементи на подмножество на MM, то съществува ii, за коетоSi−1<σ≤Si(1)S_{i-1}\lt{}\sigma \leq S_{i} \tag{1}Разбиваме множеството от сумите на подмножества c1,c2,…,cnc_{1}, c_{2}, \ldots, c_{n}, където в cic_{i} са всички суми, удовлетворяващи (1). Ще докажем, че ако σ∈ci\sigma \in c_{i}, то Si2<σ≤Si\frac{S_{i}}{2}\lt{}\sigma \leq S_{i}. Тъй като σ>Si−1=a1+⋯+ai−1\sigma\gt{}S_{i-1}=a_{1}+\cdots+a_{i-1}, то σ\sigma съдържа поне едно събираемо aka_{k} за което k≥ik \geq i. Тогава Si−σ<Si−Si−1=ai≤ak≤σS_{i}-\sigma\lt{}S_{i}-S_{i-1}=a_{i} \leq a_{k} \leq \sigma и следователно σ>12Si\sigma\gt{}\frac{1}{2} S_{i}. Но σ≤Si\sigma \leq S_{i}, т. е. твърдението е доказано.
Отвори задачатаБаза на maths.bgsomcomb2023-9-2

Задача 3

Пълен запис
Условие
В галактика има NN планети, като някои от тях са свързани с двупосочни авиолинии. Броят на линиите е N−1N-1 и те са номерирани с числата 1,2,…,N−11, 2, \ldots, N-1 по произволен начин. За всяка планета AA с S(A)S(A) означаваме броя на планетите B≠AB \neq A, които са свързани директно с AA или за които съществува път от AA до BB, като номерата на авиолиниите по този път са в нарастващ ред. Да се намери най-малката стойност на NN, за която е възможно S(A)≥2023S(A) \geq 2023 за всяка планета AA.
РешениеОт условието е ясно, че за търсеното минимално NN графът е дърво с N−1N-1 ребра. В противен случай ще има свързана компонента, за която броят на ребрата е по-малък от броя на върховете (т. е. тази свързана компонента е дърво), което е противоречие с минималността на NN. С индукция по kk ще докажем, че ако за всяка планета S(A)≥kS(A) \geq k, то N≥2kN \geq 2^{k}. При k=1k=1 твърдението е очевидно. Ако твърдението е вярно за някое kk да разгледаме такова NN, за което в съответното дърво GG за всяка планета е вярно S(A)≥k+1S(A) \geq k+1. Да премахнем реброто с най-голям номер. Тогава GG се разпада на две дървета, като за всяка планета AA от едната компонента в S(A)S(A) влиза най-много една планета от другата компонента. Следователно във всяка компонента е изпълнено S(A)≥kS(A) \geq k и следователно във всяка от тях има поне 2k2^{k} планети. Общо планетите са 2k+12^{k+1}. Пример при k=1k=1 се дава с 21=22^{1}=2 планети. Нека имаме пример за дърво с 2k2^{k} планети и S(A)=kS(A)=k за всяка планета. Добавяме нови 2k2^{k} планети, всяка от които свързваме с точно една от старите, като номерираме новите ребра с най-малките номера. Получаваме пример с 2k+12^{k+1} планети и S(A)=k+1S(A)=k+1. Задачите са предложени от: Милен ИвановА1, А2, А3; Кристиян Василев - G1; Александър Иванов - G2, G3, C2, C3; Емил Колев C1, Данила Черкашин (идея Георгий Струков и Сергей Сотников) - NT1, Александър Иванов и Сергей Берлов - NT2, Навид Сафаей - NT3.
Отвори задачатаБаза на maths.bgsomcomb2023-9-3

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

3 задачи

Задача 1

Пълен запис
Условие
Дадени са полиномите f(x)=x2+2x+3f(x)=x^{2}+2 x+3 и g(x)=5x2+2g(x)=5 x^{2}+2. Разрешено ни е за започнем с произволно цяло число xx, да го заместим с f(x),g(x)f(x), g(x) или x−2023x-2023 и т. н. (на всяка стъпка заместваме текущото число yy с f(y),g(y)f(y), g(y) или y−2023y-2023 ). Съществува ли начално число xx, за което да е възможно получаването на кое да е естествено число след краен брой операции от описания вид?
РешениеОтговорНе! Да разгледаме ситуацията по модул 17217^{2}. Тъй като f=(x+1)2+2f=(x+1)^{2}+2 и g=5x2+2g=5 x^{2}+2, от ff или g≡2( mod 17)g \equiv 2(\bmod 17) следва, че съответно ff или g≡2( mod 172)g \equiv 2\left(\bmod 17^{2}\right). Операцията x−2023x-2023 не променя остатъка по модул 17217^{2}. Следователно е невъзможно да се получат числата, които са сравними с 19 по модул 17217^{2}. Забележка. Лесно се вижда, че чрез ff отместваме с 2 квадратичните остатъци по модули 7 и 17, а чрез gg правим същото с квадратичните неостатъци по тези модули (защото 5 е квадратичен неостатък по модул 7 и 17). Следователно можем да получим всички остатъци по модули 7 и 17.
Отвори задачатаБаза на maths.bgsomnt2023-9-1

Задача 2

Пълен запис
Условие
Редицата (an)n=1∞\left(a_{n}\right)_{n=1}^{\infty} е дефинирана чрез равенстватаa1=2,an+1=a1a2⋅…⋅an+1a_{1}=2, \quad a_{n+1}=a_{1} a_{2} \cdot \ldots \cdot a_{n}+1за всяко n≥1n \geq 1. Естествените числа x1,x2,…,x2023x_{1}, x_{2}, \ldots, x_{2023} са по-големи от 1, X=x1+x2+⋯+x2023X=x_{1}+x_{2}+\cdots+x_{2023} и са такива, чеxi−1∣Xx_{i}-1 \mid Xза всяко 1≤i≤20231 \leq i \leq 2023. Да се докаже, че X≤2023(a2024−1)X \leq 2023\left(a_{2024}-1\right) и да се определи кога се достига равенство.
РешениеЩе използваме следната лема. Лема. Нека (an)n=1∞\left(a_{n}\right)_{n=1}^{\infty} е редицата от условието и b1≤b2≤⋯≤bnb_{1} \leq b_{2} \leq \cdots \leq b_{n} са такива естествени числа, че 1b1+1b2+⋯+1bn<1\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots+\frac{1}{b_{n}}\lt{}1. Тогава1b1+1b2+⋯+1bn≤1a1+1a2+⋯+1an\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}}Доказателство. Да отбележим, че1a1+1a2+⋯+1an=An−1An,\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=\frac{A_{n}-1}{A_{n}},където An=a1⋯anA_{n}=a_{1} \cdots a_{n}. Ще проведем индукция по nn, като базата n=1n=1 е очевидна. Да означим 1a1+1a2+⋯+1an=Cn\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=C_{n} и 1b1+1b2+⋯1bn=Bn\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots \frac{1}{b_{n}}=B_{n} и да фиксираме n≥2n \geq 2. Да допуснем, че исканото не е изпълнено, т. е. Bi≤CiB_{i} \leq C_{i} за всяко i≤n−1i \leq n-1, но Bn>CnB_{n}\gt{}C_{n}. Прилагайки двукратно сумиране по Абел, получаваме∑i=1nbiai=C1(b1−b2)+C2(b2−b3)+⋯+Cn−1(bn−1−bn)+Cn⋅bn<B1(b1−b2)+B2(b2−b3)+…Bn−1(bn−1−bn)+Bn⋅bn=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}Ho∑i=1nbiai≥nx2b1…bna1…ann\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}}}от неравенството между средното аритметично и средното геометрично, откъдетоb1b2…bn<a1a2…anb_{1} b_{2} \ldots b_{n}\lt{}a_{1} a_{2} \ldots a_{n}Следователно1b1+1b2+⋯+1bn≤\frac{1}{b_{1}}+\frac{1}{b_{2}}+\cdots+\frac{1}{b_{n}} \leqb1b2…bn−1b1b2…bn<a1a2an−1a1a2…an \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}}с което лемата е доказана. Обратно в задачата, да положим di=Xxi−1d_{i}=\frac{X}{x_{i}-1} за i=1,2,…,2023i=1, 2, \ldots, 2023. ТогаваXd1+Xd2+…+Xd2023=X−20231d1+1d2+…+1d2023=1−2023X<1\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−2023X≤1−1A1-\frac{2023}{X} \leq 1-\frac{1}{A}където A=a1a2…a2023A=a_{1} a_{2} \ldots a_{2023}. ОттукX≤2023a1a2…a2023=2023(a2024−1)X \leq 2023 a_{1} a_{2} \ldots a_{2023}=2023\left(a_{2024}-1\right)Равенство се достига тогава и само тогава, когато di=aid_{i}=a_{i}, т. е. приxi=2023(a2024−1)ai+1;i=1,2,…,2023.x_{i}=\frac{2023\left(a_{2024}-1\right)}{a_{i}}+1; \quad i=1, 2, \ldots, 2023.
Отвори задачатаБаза на maths.bgsomnt2023-9-2

Задача 3

Пълен запис
Условие
Нека pp е фиксирано просто число. Crad⁡p(n)\operatorname{Crad}_{p}(n) означаваме произведението на всички различни прости делители на nn, различни от pp. Нека c≠0c \neq 0 е цяло число и f:N→Nf: \mathbb{N} \rightarrow \mathbb{N} е мултипликативна функция със свойствотоrad⁡p(n)∣f(n+1)−c\operatorname{rad}_{p}(n) \mid f(n+1)-cза всяко естествено число nn. Да се докаже, че f(n)=nrf(n)=n^{r} за някакво естествено число rr.
РешениеДа фиксираме естествени числа aa и bb и нека q>max⁡(a,b,∣c∣,∣cf(ab)−f(a)f(b)∣),q≠pq\gt{}\max (a, b, |c|, \mid c f(a b)- f(a) f(b) \mid), q \neq p е просто число. Съществуват естествени числа r,s,x,ypr, s, x, y \mathrm{p} такива, че ax=1+rq,by=1+sqa x=1+r q, b y=1+s q и x,yx, y са прости числа, като при това gcd⁡(x,ab)=gcd⁡(y,abx)=1\operatorname{gcd}(x, a b)=\operatorname{gcd}(y, a b x)=1. Можем да запишем abxy=qT+1a b x y=q T+1, където T=r+s+qrsT=r+s+q r s. Тогава f(a)f(x)=f(ax)=f(1+qr)≡c( mod q)f(a) f(x)=f(a x)=f(1+q r) \equiv c(\bmod q). По-нататък,f(b)f(y)=f(by)=f(1+sq)≡c( mod q)f(b) f(y)=f(b y)=f(1+s q) \equiv c \quad(\bmod q)Накрая, f(ab)f(x)f(y)=f(abxy)=f(qT+1)≡c( mod q)f(a b) f(x) f(y)=f(a b x y)=f(q T+1) \equiv c(\bmod q). От избора на qq следва, че f(x)f(y)f(x) f(y) не се дели на qq. Тогаваf(a)f(b)≡cf(ab)( mod q)f(a) f(b) \equiv c f(a b) \quad(\bmod q)Нещо повече, от избора на qq следва, че cf(ab)=f(a)f(b)c f(a b)=f(a) f(b). Полагайки a=b=1a=b=1, получаваме c=1c=1, т. е. функцията ff е напълно мултипликативна, f(ab)=f(a)f(b)f(a b)=f(a) f(b) за всички цели aa и bb. Нека NN е естествено число и qq е прост делител на f(N)f(N). Ще докажем, че q∣pNq \mid p N. Да допуснем противното (т. е. gcd⁡(q,Np)=1\operatorname{gcd}(q, N p)=1 ). Тогава съществуват естествени числа xx и yy, за които Nx=qy+1N x=q y+1. Тъй като q≠pq \neq p, получаваме0≡f(N)f(x)=f(Nx)=f(1+qy)≡1( mod q)0 \equiv f(N) f(x)=f(N x)=f(1+q y) \equiv 1 \quad(\bmod q)противоречие. Следователно за всяко просто число rr можем да запишем f(r)=rαrpβpf(r)=r^{\alpha_{r}} p^{\beta_{p}}. В частност, f(p)=pαf(p)=p^{\alpha}. Сега за естествени числа nn и ss имамеf(np2s)=f(1+(np2s−1))≡1f\left(n p^{2 s}\right)=f\left(1+\left(n p^{2 s}-1\right)\right) \equiv 1 \quad( mod rad⁡p(np2s−1))\left(\bmod \operatorname{rad}_{p}\left(n p^{2 s}-1\right)\right)От друга страна,nαf(np2s)=nαf(n)p2sα=f(n)(mp2s)α≡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} \equivf(n) f(n) \quad( mod rad⁡p(np2s−1)).\left(\bmod \operatorname{rad}_{p}\left(n p^{2 s}-1\right)\right).Следователно, за всяко ss имаме, че rad⁡p(np2s−1)\operatorname{rad}_{p}\left(n p^{2 s}-1\right) дели f(n)−nαf(n)-n^{\alpha}. Тъй като множеството от прости делители на xs=np2s−1x_{s}=n p^{2 s}-1 е безкрайно, можем да изберем подходящо ss, за което f(n)=nαf(n)=n^{\alpha}.
Отвори задачатаБаза на maths.bgsomnt2023-9-3