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

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

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

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

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

2020

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

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

  • somnt2020-9-1: има placeholder текст
  • somgeo2020-9-2: има placeholder текст

9 · Алгебра

3 задачи

Задача 1

Пълен запис
Условие
Да се докаже, че ако a>1a\gt{}1 не е цяло число, то редицата с общ член an=[an+1]−a[an](n∈N)a_{n}=\left[a^{n+1}\right]-a\left[a^{n}\right](n \in \mathbb{N}) не е периодична.
РешениеПърви начин. Да допуснем, че редицата има период pp. Тъй като a([akp+1]−[a])=[akp+2]−[a2]>0a\left(\left[a^{k p+1}\right]-[a]\right)=\left[a^{k p+2}\right]-\left[a^{2}\right]\gt{}0 за някое kk, то (1) a∈Qa \in \mathbb{Q}. За b=ap∈Qb=a^{p} \in \mathbb{Q} имаме, че∑i=0p−1ap−1−ianp+i=\sum_{i=0}^{p-1} a^{p-1-i} a_{n p+i}=∑i=0p−1ap−1−i([anp+i+1]−a[anp+i])=\sum_{i=0}^{p-1} a^{p-1-i}\left(\left[a^{n p+i+1}\right]-a\left[a^{n p+i}\right]\right)=∑i=1pap−i[anp+i]−∑i=0p−1ap−i[anp+i]=\sum_{i=1}^{p} a^{p-i}\left[a^{n p+i}\right]-\sum_{i=0}^{p-1} a^{p-i}\left[a^{n p+i}\right]=[bn+1]−b[bn]=:bn\left[b^{n+1}\right]-b\left[b^{n}\right]=: b_{n}и значи (2) bn+1=bnb_{n+1}=b_{n}. Тогава за cn=[bn+1]−[bn]c_{n}=\left[b^{n+1}\right]-\left[b^{n}\right] следва, че cn+1=bcnc_{n+1}=b c_{n}, откъдето (3) cn+1=bnc1c_{n+1}=b^{n} c_{1}, Ако c1=0c_{1}=0, то [bn]=[b]\left[b^{n}\right]=[b] за всяко nn, което е противоречие cb>1\mathrm{c} b\gt{}1. Ако c1≠0c_{1} \neq 0, то bnc1∈Zb^{n} c_{1} \in \mathbb{Z} за всяко nn, т. е. b∈Zb \in \mathbb{Z} - отново противоречие. Втори начин. (Ст. Герджиков) Да допуснем противното, т. е. че съществуват естествено число, такова, че an+p=ana_{n+p}=a_{n} за всяко n≥1n \geq 1. Нека bn=[an]b_{n}=\left[a^{n}\right]. Тогава за всяко nn имаме, чеbn+p+1−abn+p=an+p=an=bn+1−abnb_{n+p+1}-a b_{n+p}=a_{n+p}=a_{n}=b_{n+1}-a b_{n}Така получаваме, че редицата {bn}n=1∞\left\{b_{n}\right\}_{n=1}^{\infty} е линейна рекурентна редица с характеристично уравнениеtp+1−atp−t+a=0t^{p+1}-a t^{p}-t+a=0Това уравнение очевидно има корени t0=at_{0}=a и tj=ξjt_{j}=\xi^{j}, къдетоξ=cos⁡2πp+isin⁡2πp\xi=\cos \frac{2 \pi}{p}+i \sin \frac{2 \pi}{p}е pp-ти корен на единицата. Тъй като a>1a\gt{}1, то всички тези корени са различни и общият член на редицата bnb_{n} има видаbn=Aan+∑j=1pcjξjnb_{n}=A a^{n}+\sum_{j=1}^{p} c_{j} \xi^{j n}Да отбележим, че bn=[an]→∞b_{n}=\left[a^{n}\right] \rightarrow \infty при n→∞n \rightarrow \infty, защото a>1a\gt{}1. Тъй като ∣ξ∣=1|\xi|=1, това означава, че A≠0A \neq 0. Сега, тъй като ξp=1\xi^{p}=1, тоbn+p−bn=b_{n+p}-b_{n}=A(an+p−an)+∑j=1pcj[ξjn−ξj(n+p)]=A\left(a^{n+p}-a^{n}\right)+\sum_{j=1}^{p} c_{j}\left[\xi^{j n}-\xi^{j(n+p)}\right]=A(an+p−an),A\left(a^{n+p}-a^{n}\right),От a>1a\gt{}1 и A≠0A \neq 0 следва, че дясната страна не е 0 и оттукbn+2p−bn+pbn+p−bn=apе рационално.\frac{b_{n+2 p}-b_{n+p}}{b_{n+p}-b_{n}}=a^{p} \text{е рационално.}Нека ap=rsa^{p}=\frac{r}{s}, където r>sr\gt{}s са взаимнопрости цели числа. Тогаваbnp+p−bnp=Aanp(ap−1)=Arn(r−s)sn+1b_{n p+p}-b_{n p}=A a^{n p}\left(a^{p}-1\right)=\frac{A r^{n}(r-s)}{s^{n+1}}и тъй като (r,s)=1(r, s)=1 и A(r−s)≠0A(r-s) \neq 0 не зависи от nn, то при достатъчно големи nn дясната страна не може да е цяло число. Но bnp+p−bnpb_{n p+p}-b_{n p} е цяло, като разлика на две цели за всяко nn. Това е противоречие. Следователно редицата {an}n=1∞\left\{a_{n}\right\}_{n=1}^{\infty} не е периодична.
Отвори задачатаБаза на maths.bgsomalg2020-9-1

Задача 2

Пълен запис
Условие
Нека FF е такова непостоянно изображение на тримерното пространство в себе си, че ако A≠BA \neq B и F(A)≠F(B)F(A) \neq F(B), то правите ABA B и F(A)F(B)F(A) F(B) са перпендикулярни. Да се докаже, че образът на FF е равнина.
РешениеНа всяка точка AA съпоставяме вектора a=OA→a=\overrightarrow{O A} и полагаме f(a)=F(A),g(a)=f(a)−f(0)f(a)= F(A), g(a)=f(a)-f(0). Понеже (a−b)(g(a)−g(b))=0(a-b)(g(a)-g(b))=0, то (1) ag(a)=0a g(a)=0 (при b=0b=0 ) и тогава (2) ag(b)=−bg(a)a g(b)=-b g(a). Оттук ( α,β∈R\alpha, \beta \in \mathbb{R} )c(g(αa+βb)−αg(a)−βg(b))=c(g(\alpha a+\beta b)-\alpha g(a)-\beta g(b))=−(αa+βb)g(c)+αag(c)+βbg(c)=0-(\alpha a+\beta b) g(c)+\alpha a g(c)+\beta b g(c)=0за всяко cc и значи gg е линейно изображение. Нека {e1,e2,e3}\left\{e_{1}, e_{2}, e_{3}\right\} е ортогонален базис. От (1) и (2) намираме, чеg(e1)=p3e2−p2e3,g(e2)=p1e3−p3e1,g\left(e_{1}\right)=p_{3} e_{2}-p_{2} e_{3}, \quad g\left(e_{2}\right)=p_{1} e_{3}-p_{3} e_{1},g(e3)=p2e1−p1e2 \quad g\left(e_{3}\right)=p_{2} e_{1}-p_{1} e_{2}Тогава лесно следва, че образът на gg е равнината p1x1+p2x2+p3x3=0p_{1} x_{1}+p_{2} x_{2}+p_{3} x_{3}=0. Забележка. От решението може да се извлече, че FF е композиция на ортогонална проекция върху равнина π\pi и въртяща хомотетия на 90∘90^{\circ} в π\pi.
Отвори задачатаБаза на maths.bgsomalg2020-9-2

Задача 3

Пълен запис
Условие
Възможно ли е сумата от реципрочните на няколко две по две различни естествени числа, всяко от които няма две еднакви съседни цифри в десетичния си запис, да е по-голяма от: а) 10; б) 30?
РешениеДа означим с SiS_{i} сумата от реципрочните на добрите ii-цифрени числа, т. е. тези, които изпълняват условието. В SiS_{i} участват 9i9^{i} числа и значи Si>9i/10iS_{i}\gt{}9^{i} / 10^{i}. Понеже S1>2S_{1}\gt{}2, тоTn:=∑i=1nSn>2+∑i=2n9i10i=10110T_{n}: =\sum_{i=1}^{n} S_{n}\gt{}2+\sum_{i=2}^{n} \frac{9^{i}}{10^{i}}=\frac{101}{10}и следователно отговорът на а) е „да“. От друга страна, всяко добро ii-цифрено число aa поражда 9 добри (i+1)(i+1)-цифрени числа от вида 10a+b(0≤b≤9)10 a+b(0 \leq b \leq 9) и значи Si+1<9Si/10S_{i+1}\lt{}9 S_{i} / 10. Понеже S1<3S_{1}\lt{}3, тоTn<S1∑i=0n−19i10i<30T_{n}\lt{}S_{1} \sum_{i=0}^{n-1} \frac{9^{i}}{10^{i}}\lt{}30и следователно отговорът на б) е „не”.
Отвори задачатаБаза на maths.bgsomalg2020-9-3

9 · Геометрия

3 задачи

Задача 1

Пълен запис
Условие
В равнината е дадена окръжност kk, точка MM, вътрешна за kk и права ℓ\ell, която се допира до kk. Да се построят с линийка и пергел точки AA и BB върху ℓ\ell, такива че ако допирателните от AA и BB към kk (различни от ℓ)\ell) се пресичат в точка CC, то MM е медицентър за △ABC\triangle A B C.
Решение(Анализ) Нека окръжността kk е с център II, радиус rr и се допира до ℓ\ell в точка PP. Ако △ABC\triangle A B C изпълнява условието на задачата, то AA и BB са от различни страни на PP. Да означим с QQ диаметрално противоположната точка на PP в kk и нека лъчът CQ→C Q^{\rightarrow} пресича ℓ\ell в точка RR. Добре известен факт е, че RR се явява допирна точка на външновписаната за △ABC\triangle A B C окръжност към страната ABA B, т. е. средата SS на ABA B се явява и среда на PRP R. Ако означим с NN точката на Нагел за △ABC\triangle A B C, то от една страна N∈QRN \in Q R, а от друга, N∈IM→N \in I M \rightarrow и IM:MN=1:2I M: M N=1: 2 (Защо?). (Построение) Последователно построяваме: (1) точка II, център на kk; (2) точка PP, допирна точка на kk с ℓ\ell; (3) точка QQ, диаметрално противоположната на PP в kk; (4) точка NN, като N∈IM→N \in I M^{\rightarrow} и IM:MN=1:2I M: M N=1: 2; (5) точка RR, като R=QN→∩ℓR=Q N^{\rightarrow} \cap \ell; (6) точка SS, като среда на PRP R; (7) точка CC, като C∈SM→C \in S M^{\rightarrow} и SM:MC=1:2S M: M C=1: 2; (8) точките AA и BB, като пресечни точки на допирателните от CC към kk c ℓ\ell. (Доказателство) От построението следва, че окръжността kk е вписана в △ABC,CS\triangle A B C, C S е медиана, която се дели от MM в отношение 2:12: 1, т. е. MM е медицентър за △ABC\triangle A B C. (Извод) Задачата има решение тогава и само тогава, когато точка NN лежи в полуравнината, определена от ℓ\ell и окръжността kk, т. е. за разстоянието dd от MM до ℓ\ell е изпълнено d>2r/3d\gt{}2 r / 3. В този случай решението е единствено.
Отвори задачатаБаза на maths.bgsomgeo2020-9-1

Задача 2

Нужна е проверка
Условие
BLANK BLANK BLANK
РешениеBLANK BLANK BLANK
Отвори задачатаБаза на maths.bgsomgeo2020-9-2

Задача 3

Пълен запис
Условие
Даден е изпъкнал четириъгълник ABCDA B C D и вътрешна за него точка OO, такава че AOA O и COC O са ъглополовящи на ∠BAD\angle B A D и ∠BCD\angle B C D съответно. Върху отсечките AOA O и COC O са избрани съответно точки MM и NN, такива че ∠MBN=12∠ABC\angle M B N=\frac{1}{2} \angle A B C. Да се докаже, че ABCDA B C D е описан четириъгълник тогава и само тогава, когато ∠MNB=∠DNO\angle M N B=\angle D N O.
РешениеАко означим с II и JJ центровете на вписаните окръжности в △ABD\triangle A B D и △CBD\triangle C B D съответно, то ∠IBJ=12∠ABC=∠MBN\angle I B J=\frac{1}{2} \angle A B C=\angle M B N и следователно или M∈AIM \in A I, или N∈CJN \in C J. Без ограничение на общността нека M∈AIM \in A I и да построим окръжността kk с център MM, която се допира до ADA D и ABA B в точките XX и YY съответно. Нека допирателните от BB и DD към kk я допират в точките RR и TT, пресичат се в точка LL и пресичат отсечките ADA D и ABA B в точките PP и QQ съответно. ТогаваBL−DL=BR−DT=BY−DX=BA−DAB L-D L=B R-D T=B Y-D X=B A-D Aи следователно ABCDA B C D е описан тогава и само тогава, когато LBCDL B C D е описан. Но∠LBN=∠MBN−∠MBL=\angle L B N=\angle M B N-\angle M B L=12(∠ABC−∠ABL)=12∠LBC\frac{1}{2}(\angle A B C-\angle A B L)=\frac{1}{2} \angle L B Cи следователно NN е центърът на вписаната окръжност в △BEC\triangle B E C, където EE е пресечната точка на правите BPB P и CDC D. Ако означим с FF центъра на вписаната в △PDE\triangle P D E окръжност, то точките E,FE, F и NN, както и точките MM, PP и FF лежат на една права. Тогава LBCDL B C D е описан четириъгълник ⇔DN\Leftrightarrow \quad D N е ъглополовяща на ∠LDC\angle L D C ⇔∠MDN=12∠ADC\Leftrightarrow \quad \angle M D N=\frac{1}{2} \angle A D C (защото MDM D е ъглополовяща на ∠ADQ\angle A D Q ) ⇔\Leftrightarrow \quad четириъгълникът MNDFM N D F е вписан (∠MFN=12∠ADC)\left(\angle M F N=\frac{1}{2} \angle A D C\right) ⇔∠MND+∠MFD=180∘\Leftrightarrow \quad \angle M N D+\angle M F D=180^{\circ} ⇔∠MND+∠BNC=180∘(∠BNC=90∘+12∠BEC=∠PFD)\Leftrightarrow \quad \angle M N D+\angle B N C=180^{\circ}\left(\angle B N C=90^{\circ}+\frac{1}{2} \angle B E C=\angle P F D\right) ⇔∠MND=∠ONB\Leftrightarrow \quad \angle M N D=\angle O N B ⇔∠MNB=∠DNO\Leftrightarrow \quad \angle M N B=\angle D N Oи доказателството е завършено.
Отвори задачатаБаза на maths.bgsomgeo2020-9-3

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

3 задачи

Задача 1

Пълен запис
Условие
Дадено е множество AA с nn елемента. Множествата A1A_{1}, A2,…,AnA_{2}, \ldots, A_{n} са подмножества на AA и всяко от тях има по kk елемента. Известно е, че всяко подмножество XX на AA с два елемента е подмножество на точно едно от множествата A1,A2,…,AnA_{1}, A_{2}, \ldots, A_{n}. Да се докаже, че всеки две от множествата A1,A2,…,AnA_{1}, A_{2}, \ldots, A_{n} се пресичат.
РешениеПодмножествата XX на AA с два елемента са (n2)\binom{n}{2}, а броят на подмножествата на A1,A2,…,AnA_{1}, A_{2}, \ldots, A_{n} с два елемента са n(k2)n\binom{k}{2}. Следователно n(n−1)=nk(k−1)n(n-1)= n k(k-1), откъдетоk(k−1)=n−1(*)k(k-1)=n-1 \tag{*}Да фиксираме елемент a∈Aa \in A и нека A1,A2,…,AtA_{1}, A_{2}, \ldots, A_{t} са множествата, които съдържат aa. Всяко множество Ai,i=1,2,…,tA_{i}, i=1, 2, \ldots, t, съдържа k−1k-1 множества с два елемента, единият от които е aa. Всички подмножества на AA с два елемента, единият от които е aa, са n−1n-1. Следователно t(k−1)=n−1t(k-1)=n-1 и от (*) следва, че t=kt=k. Да разгледаме две произволни множества {a1,a2,…,ak}\left\{a_{1}, a_{2}, \ldots, a_{k}\right\} и {b1,b2,…\left\{b_{1}, b_{2}, \ldots\right., bk}\left. b_{k}\right\}. Ще докажем, че те имат общ елемент. Това е вярно, ако a1=bja_{1}=b_{j} за някое jj. Нека a1≠bja_{1} \neq b_{j} за всяко jj. Според доказаното по-горе има точко kk множества, които съдържат a1a_{1}. Всяка от двойките ( a1,bja_{1}, b_{j} ) се среща точно в едно от тези kk множества. Освен това никои два елемента bi,bjb_{i}, b_{j} не се срещат в множество, различно от {b1,b2,…,bk}\left\{b_{1}, b_{2}, \ldots, b_{k}\right\}. Следователно всяко bjb_{j} (има kk такива елемента) се среща точно в едно от множествата, които съдържат a1a_{1} (има kk такива множества), откъдето следва, че съществува jj, за което bj∈{a1,a2,…,ak}b_{j} \in\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}.
Отвори задачатаБаза на maths.bgsomcomb2020-9-1

Задача 2

Пълен запис
Условие
Ребрата на пълния граф с nn върха са маркирани по произволен начин с числата 1,2,…,n(n−1)21, 2, \ldots, \frac{n(n-1)}{2}, като всяко ребро получава различно число. Да се докаже, че съществува път с дължина поне n−1n-1 (възможно с повтарящи се върхове), за който редицата от етикетите е нарастваща.
РешениеС всеки връх xx свързваме число w(x)=w(x)= дължината (брой ребра) на най-дългия път с нарастващи етикети, завършващ в xx. Ще докажем, че ∑xw(x)=n(n−1)\sum_{x} w(x)=n(n-1). Тогава ще има път с дължина n−1n-1, за който редицата от етикетите е нарастваща. Преглеждаме ребрата в нарастващ ред на номерата и следим как се изменят числата w(x)w(x), които в началото са 0. Нека на ii-тата стъпка добавяме реброто e=xye=x y. Ако w(x)=w(y)w(x)=w(y), то новите стойности на w(x)w(x) и w(y)w(y) се увеличават с 1. Ако w(x)<w(y)w(x)\lt{}w(y), то реброто удължава най-дългия път завършващ в xx и имаме за новата стойност на w(x):w(x)=w(y)+1w(x): w(x)=w(y)+1. Така получаваме, че w(x)w(x) се увеличава с 2, а w(y)w(y) остава същото. И в двата случая към сумата се добавя 2. Следователно след n(n−1)/2n(n-1) / 2 стъпки ще имаме ∑xw(x)=n(n−1)\sum_{x} w(x)=n(n-1).
Отвори задачатаБаза на maths.bgsomcomb2020-9-2

Задача 3

Пълен запис
Условие
Нека dd и k<dk\lt{}d са естествени числа, а m=2km=2^{k}. Да се докаже, че∑i=1m∑j=1m∑S⊆Ai△Aj(−1)∣S∣−1∣S∣≤\sum_{i=1}^{m} \sum_{j=1}^{m} \sum_{S \subseteq A_{i} \triangle A_{j}}(-1)^{|S|-1}|S| \leqk2k k 2^{k}когато A1,A2,…,Am⊆{1,2,…,d}A_{1}, A_{2}, \ldots, A_{m} \subseteq\{1, 2, \ldots, d\}. (Тук B△C=(B\C)∪(C\B)B \triangle C=(B \backslash C) \cup(C \backslash B).)
РешениеАко XX е множество с dd елемента, то∑S⊆X(−1)∣S∣−1∣S∣={1,акоd=10иначе.\sum_{S \subseteq X}(-1)^{|S|-1}|S|=\left\{\begin{array}{l} 1, \text{ако} d=1 \cr 0 \text{иначе.} \end{array}\right.Твърдението е очевидно ако d=0d=0 или d=1d=1, така че да допуснем, че d>1d\gt{}1. Нека x0∈Xx_{0} \in X и X′=X\{x0}X^{\prime}=X \backslash\left\{x_{0}\right\}. Тогава∑S⊆X(−1)∣S∣−1∣S∣=∑S⊆X′(−1)∣S∣−1(∣S∣−∣S∪{x0}∣)==∑S⊆X′(−1)∣S∣=(1−1)∣X′∣=0\begin{aligned} \sum_{S \subseteq X}(-1)^{|S|-1}|S| & =\sum_{S \subseteq X^{\prime}}(-1)^{|S|-1}\left(|S|-\left|S \cup\left\{x_{0}\right\}\right|\right)= \\ & =\sum_{S \subseteq X^{\prime}}(-1)^{|S|}=(1-1)^{\left|X^{\prime}\right|}=0 \end{aligned}защото ∣X′∣≥1\left|X^{\prime}\right| \geq 1. Нека X={x1,x2,…,xd}X=\left\{x_{1}, x_{2}, \ldots, x_{d}\right\}. Съпоставяме на всяко множество AiA_{i} характеристичния вектор vi∈{0,1}dv_{i} \in\{0, 1\}^{d} на AiA_{i}, т. е.vi(j)={1,акоxj∈Ai0,акоxj∈Aiv_{i}(j)=\left\{\begin{array}{l} 1, \text{ако} x_{j} \in A_{i} \cr 0, \text{ако} x_{j} \in A_{i} \end{array}\right.Така задачата се свежда до това, да намерим максимума наT(V)={(vi,vj)∣∣vi−vj∣=1,1≤i,j≤m},T(V)=\left\{\left(v_{i}, v_{j}\right)| | v_{i}-v_{j} \mid=1, 1 \leq i, j \leq m\right\},къдетоV={v1,v2,…,vm}. \text{където} V=\left\{v_{1}, v_{2}, \ldots, v_{m}\right\}.Лема. Нека v1,v2,…,vm∈{0,1}dv_{1}, v_{2}, \ldots, v_{m} \in\{0, 1\}^{d}. Тогава T(v1,v2,…,vm)T\left(v_{1}, v_{2}, \ldots, v_{m}\right) е максимално ако v1,v2,…,vmv_{1}, v_{2}, \ldots, v_{m} са подредени лексикографски. Доказателството на лемата ще направим с индукция по dd. За d=1d=1 всичко е ясно, така че преминаваме към индукционната стъпка от d−1d-1 към dd. Нека V={v1,v2,…,vm}V=\left\{v_{1}, v_{2}, \ldots, v_{m}\right\} максимизира T(V)T(V) и d′≤dd^{\prime} \leq d е произволно. Нека V0(d′)={vi∣vi(d′)=0}V_{0}\left(d^{\prime}\right)=\left\{v_{i} \mid v_{i}\left(d^{\prime}\right)=0\right\}, а V1(d′)={vi∣vi(d′)=1}V_{1}\left(d^{\prime}\right)=\left\{v_{i} \mid v_{i}\left(d^{\prime}\right)=1\right\}. Тогава имаме, чеT(V)≤T(V) \leqT(V0(d′))+T(V1(d′)) T\left(V_{0}\left(d^{\prime}\right)\right)+T\left(V_{1}\left(d^{\prime}\right)\right)+2min⁡(∣V0(d′)∣,∣V1(d′)∣)+2 \min \left(\left|V_{0}\left(d^{\prime}\right)\right|, \left|V_{1}\left(d^{\prime}\right)\right|\right)където използвахме, че за всяко vi∈V0(d′)v_{i} \in V_{0}\left(d^{\prime}\right) има най-много едно vj∈V1(d′)v_{j} \in V_{1}\left(d^{\prime}\right), за което ∣vi−vj∣=1\left|v_{i}-v_{j}\right|=1, защото двата вектора вече се различават на позиция d′d^{\prime}. Да обърнем внимание, че ако V0(d′)V_{0}\left(d^{\prime}\right) и V1(d′)V_{1}\left(d^{\prime}\right) са сортирани лексикографски по всички координати с изключение на d′d^{\prime}, то от индукционното предположение имаме, чеT(V)=T(V)=T(V0(d′))+T(V1(d′))T\left(V_{0}\left(d^{\prime}\right)\right)+T\left(V_{1}\left(d^{\prime}\right)\right)+2min⁡(∣V0(d′)∣,∣V1(d′)∣).+2 \min \left(\left|V_{0}\left(d^{\prime}\right)\right|, \left|V_{1}\left(d^{\prime}\right)\right|\right).Така показахме, че ако L0(V,d′)L_{0}\left(V, d^{\prime}\right) са първите ∣V0(d′)∣\left|V_{0}\left(d^{\prime}\right)\right| в лексикографската наредба вектори с d′d^{\prime}-координата нула, а L1(V,d′)L_{1}\left(V, d^{\prime}\right) са първите ∣V0(d′)∣\left|V_{0}\left(d^{\prime}\right)\right| в лексикографската наредба вектори с d′d^{\prime}-координата нула, тоT(V)=T(L(V,d′)),T(V)=T\left(L\left(V, d^{\prime}\right)\right),къдетоL(V,d′)=L0(V,d′)∪L1(V,d′). \text{където} L\left(V, d^{\prime}\right)=L_{0}\left(V, d^{\prime}\right) \cup L_{1}\left(V, d^{\prime}\right).Освен това е ясно, че лексикографски най-големите вектори в L0(V,d′)L_{0}\left(V, d^{\prime}\right) и L1(V,d′)L_{1}\left(V, d^{\prime}\right) не надминават лексикографски най-големите вектори в V0(d′)V_{0}\left(d^{\prime}\right) и V1(d′)V_{1}\left(d^{\prime}\right). От друга страна ако тези вектори съвпадат, то L0(V,d′)=V0(d′)L_{0}\left(V, d^{\prime}\right)=V_{0}\left(d^{\prime}\right) и L1(V,d′)=V1(d′)L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right). От горните разсъждения може да смятаме, че за всяко d′≤dd^{\prime} \leq d е в сила, чеL0(V,d′)=V0(d′)иL1(V,d′)=V1(d′).L_{0}\left(V, d^{\prime}\right)=V_{0}\left(d^{\prime}\right) \text{и} L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right).Сега да допуснем, че y∉Vy \notin V и нека v∈Vv \in V е лексикографски най-малко, за което y≺lexvy \prec_{l e x} v. Ако y(d′)=v(d′)=jy\left(d^{\prime}\right)=v\left(d^{\prime}\right)=j, то очевидно Lj(V,d′)≠Vj(d′)L_{j}\left(V, d^{\prime}\right) \neq V_{j}\left(d^{\prime}\right), което е противоречие. Следователно y(d′)≠v(d′)y\left(d^{\prime}\right) \neq v\left(d^{\prime}\right) за всяко d′≤dd^{\prime} \leq d. В частност y(1)=0y(1)=0 и v(1)=1v(1)=1. Да допуснем, че v(d′)=1v\left(d^{\prime}\right)=1 за някое d′>1d^{\prime}\gt{}1, тогава тъй като L1(V,d′)=V1(d′)L_{1}\left(V, d^{\prime}\right)=V_{1}\left(d^{\prime}\right), то v=(1,0,…,0)∈Vv=(1, 0, \ldots, 0) \in V. Тъй като y(d′)≠v(d′)y\left(d^{\prime}\right) \neq v\left(d^{\prime}\right) за всяко d′d^{\prime}, то y=(0,1,…,1)y=(0, 1, \ldots, 1). Сега, ако отново има v′∈Vv^{\prime} \in V, за който v′(1)=1v^{\prime}(1)=1 и v′(d′)=1v^{\prime}\left(d^{\prime}\right)=1 за някое d′>1d^{\prime}\gt{}1, то очевидно L1(V,d′)≠V1(d′)L_{1}\left(V, d^{\prime}\right) \neq V_{1}\left(d^{\prime}\right). Следователно, ако VV не е сортирано лексикографски, тоV={(0,v′)∣v′∈{0,1}d−1}\{y}∪{v}.V=\left\{\left(0, v^{\prime}\right) \mid v^{\prime} \in\{0, 1\}^{d-1}\right\} \backslash\{y\} \cup\{v\}.Но сега е ясно, че ∣v−(0,v′)∣>1\left|v-\left(0, v^{\prime}\right)\right|\gt{}1, за всяко v′≠(0,0,…,0)v^{\prime} \neq(0, 0, \ldots, 0), докато ∣y−(0,v′)∣=1\left|y-\left(0, v^{\prime}\right)\right|=1 за d−1d-1 стойности на v′∈{0,1}d−1v^{\prime} \in\{0, 1\}^{d-1}. За d≥2d \geq 2 заключаваме, чеT(V)≤T(V\{v}∪{y}).T(V) \leq T(V \backslash\{v\} \cup\{y\}).Следователно наистина най-голямата стойност на T(V)T(V) се достига, когато VV е лексикографски сортирано. Лесно се вижда, че ако 2k2^{k} вектора от {0,1}\{0, 1\} са лексикографски сортирани, то те дефинират точно множеството {0}d−k×{0,1}k\{0\}^{d-k} \times\{0, 1\}^{k}. За всеки вектор vv в това множество има точно kk вектора uu, за които ∣u−v∣=1|u-v|=1. СледователноT({0}d−k×{0,1}k)=k2k=k2k.T\left(\{0\}^{d-k} \times\{0, 1\}^{k}\right)=k 2^{k}=k 2^{k}.
Отвори задачатаБаза на maths.bgsomcomb2020-9-3

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

3 задачи

Задача 1

Нужна е проверка
Условие
BLANK BLANK BLANK
РешениеBLANK BLANK BLANK
Отвори задачатаБаза на maths.bgsomnt2020-9-1

Задача 2

Пълен запис
Условие
Ще казваме, че естественото число qq е добро за апроксимиране на реалното число α\alpha, ако съществува цяло число pp, такова, че∣α−pq∣≤1q2\left|\alpha-\frac{p}{q}\right| \leq \frac{1}{q^{2}}За фиксирано α∈R\alpha \in \mathbb{R} означаваме с DαD_{\alpha} множеството от всички естествени числа, които са добри за апроксимиране на α\alpha. Да се докаже, че ако DαD_{\alpha} съдържа всички числа от вида 2k+12^{k}+1, където k∈Nk \in \mathbb{N}, то Dα=ND_{\alpha}=\mathbb{N}.
РешениеЩе докажем, че числото α\alpha е цяло, което очевидно води до Dα=ND_{\alpha}= \mathbb{N}. Да допуснем първо, че α\alpha е ирационално. Тогава за всяко q∈Dαq \in D_{\alpha} от неравенствата в условието следва, че дробната част {qα}\{q \alpha\} принадлежи на някой от интервалите ( 0,1/q0, 1 / q ) и ( 1−1/q,11-1 / q, 1 ). Нека естественото число rr е такова, че2r>max⁡(1{α},11−{α})2^{r}\gt{}\max \left(\frac{1}{\{\alpha\}}, \frac{1}{1-\{\alpha\}}\right)Ако 0<{(2r+1)α}<1/(2r+1)0\lt{}\left\{\left(2^{r}+1\right) \alpha\right\}\lt{}1 /\left(2^{r}+1\right), то{α}>1/(2r+1)>\{\alpha\}\gt{}1 /\left(2^{r}+1\right)\gt{}{(2r+1)α}={{2rα}+{α}}.\left\{\left(2^{r}+1\right) \alpha\right\}=\left\{\left\{2^{r} \alpha\right\}+\{\alpha\}\right\}.Това означава, че1−{α}<{2rα}<1−{α}+12r+11-\{\alpha\}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}+\frac{1}{2^{r}+1}Ако пък 1>{(2r+1)α}>1−1/(2r+1)1\gt{}\left\{\left(2^{r}+1\right) \alpha\right\}\gt{}1-1 /\left(2^{r}+1\right), аналогично получаваме, че1−{α}−12r+1<{2rα}<1−{α}1-\{\alpha\}-\frac{1}{2^{r}+1}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}(използваме и неравенството {2rα}+{α}<2−1/(2r+1)\left\{2^{r} \alpha\right\}+\{\alpha\}\lt{}2-1 /\left(2^{r}+1\right), което следва от избора на rr ). Получихме, че за всички достатъчно големи rr е са изпълнени неравенствата1−{α}−12r+1<{2rα}<1−{α}+12r+11-\{\alpha\}-\frac{1}{2^{r}+1}\lt{}\left\{2^{r} \alpha\right\}\lt{}1-\{\alpha\}+\frac{1}{2^{r}+1}Това лесно води до противоречие (с разглеждане поотделно на случаите {α}<1/2\{\alpha\}\lt{}1 / 2 и {α}>1/2\{\alpha\}\gt{}1 / 2 ). Нека сега α=a/b\alpha=a / b е рационално число, b∈N,a∈Zb \in \mathbb{N}, a \in \mathbb{Z} и (a,b)=1(a, b)=1. Тогава неравенството в условието казва, че за всяко qn=22n+1q_{n}=2^{2^{n}}+1 съществува pn∈Zp_{n} \in \mathbb{Z}, такова, че∣ab−pnqn∣≤1qn2\left|\frac{a}{b}-\frac{p_{n}}{q_{n}}\right| \leq \frac{1}{q_{n}^{2}}тоест ∣aqn−pnb∣<b/qn\left|a q_{n}-p_{n} b\right|\lt{}b / q_{n}. Оттук при qn>bq_{n}\gt{}b заключаваме aqn=pnba q_{n}=p_{n} b, което води до b∣qnb \mid q_{n}, за всяко n>bn\gt{}b и тъй като (qn,qn+1)=1\left(q_{n}, q_{n+1}\right)=1, заключаваме, че b=1b=1, т. е. α\alpha е цяло число.
Отвори задачатаБаза на maths.bgsomnt2020-9-2

Задача 3

Пълен запис
Условие
Нека PP и QQ са неконстантни полиноми с цели неотрицателни коефициенти и старши коефициент 1, а kk е естествено число. Естествените числа a1,a2,…,ak,ai≥2a_{1}, a_{2}, \ldots, a_{k}, a_{i} \geq 2 за i=1,2,…,ki=1, 2, \ldots, k, са такива, че за всяко естествено число nn числото(a1P(n)+Q(n))(a2P(n)+Q(n))…(akP(n)+Q(n))\left(a_{1}^{P(n)}+Q(n)\right)\left(a_{2}^{P(n)}+Q(n)\right) \ldots\left(a_{k}^{P(n)}+Q(n)\right)е точен квадрат. Да се докаже, че числото a1a2…aka_{1} a_{2} \ldots a_{k} също е точен квадрат.
РешениеЩе използваме следната лема. Лема. Нека ff е неконстантен полином с цели коефициенти и нека AA е множеството от прости числа pp, за които vp(f(n))v_{p}(f(n)) е нечетно за някое n∈Nn \in \mathbb{N}. Ако множеството AA е крайно, то съществуват полином gg с цели коефициенти и константа cc, такива, че f=cg2f=c g^{2}. Доказателство. Можем да считаме, че полиномът ff е свободен от квадрати (т. е. не се дели на квадрат на полином с цели коефициенти). От условието следва, че множеството от простите числа, които делят точно в четни степени стойности на ff, е безкрайно. Нека pp е такова просто число и p2k∥f(n)p^{2 k} \| f(n) за някои естествени числа nn и kk. Да разгледаме f(n+ℓpk+1)f\left(n+\ell p^{k+1}\right), където ℓ∈N\ell \in \mathbb{N}. Лесно се вижда, чеf(n+ℓpk+1)≡f(n)+ℓpk+1f′(n)f\left(n+\ell p^{k+1}\right) \equiv f(n)+\ell p^{k+1} f^{\prime}(n) \quad( mod p2k+2)\left(\bmod p^{2 k+2}\right)Ако (p,f′(n))=1\left(p, f^{\prime}(n)\right)=1, то сравнението ℓf′(n)+f(n)pk+1≡pk( mod pk+1)\ell f^{\prime}(n)+\frac{f(n)}{p^{k+1}} \equiv p^{k}\left(\bmod p^{k+1}\right) има решение. Това означава, че съществува естествено число n1n_{1}, за което p2k+1∥f(n1)p^{2 k+1} \| f\left(n_{1}\right), т. е. p∈Ap \in A, което е противоречие. Следователно съществуват безбройно много прости числа pp, за които съществува естествено число nn, такова, че p∣(f(n),f′(n))p \mid\left(f(n), f^{\prime}(n)\right). Сега от лемата на Безу за полиноми следва, че съществуват полиноми u,v∈Z[x]u, v \in \mathbb{Z}[x], такива че uf+vf′=Tu f+v f^{\prime}=T, където T∈Z[x]T \in \mathbb{Z}[x] е найголемият общ делител на ff и f′f^{\prime}, като при това TT не е константа. Нека RR е неразложим делител на TT и нека zz е негов (комплексен) корен. Тъй като zz е общ корен на ff и f′f^{\prime}, то zz е кратен корен на ff. Тъй като RR няма кратни корени (защото е неразложим), всеки негов корен е корен и на f/Rf / R, тоест R2∣fR^{2} \mid f, което противоречи на избора на ff в началото. Следователно f=cg2f=c g^{2} за някои c∈Zc \in \mathbb{Z} и g∈Z[x]g \in \mathbb{Z}[x], с което лемата е доказана. Обратно към решението да отбележим първо, че можем да считаме, че числата a1,a2,…,aka_{1}, a_{2}, \ldots, a_{k} са две по две различни. Нека c=P(1)>0c=P(1)\gt{}0 и да разгледаме полинома g(x)=Q(x)+a1cg(x)=Q(x)+a_{1}^{c}. Да допуснем, че g(x)g(x) не е точен квадрат на полином с цели коефициенти. Тогава от горната лема и от лемата на Шур следва, че съществуват безбройно много прости числа pp, за които съществува естествено числа n0n_{0}, за което vp(g(n0))=2k+1v_{p}\left(g\left(n_{0}\right)\right)=2 k+1 е нечетно число. За всяко такова pp по Китайската теорема за остатъците можем да изберем естествено число nn, за което n≡1( mod p−1)n \equiv 1(\bmod p-1) и n≡n0( mod p2k+2)n \equiv n_{0} \left(\bmod p^{2 k+2}\right). Тогава p2k+1∥g(n)=Q(n)+a1P(n)p^{2 k+1} \| g(n)=Q(n)+a_{1}^{P(n)}. Последното означава, че p∣aiP(n)+Q(n)p \mid a_{i}^{P(n)}+Q(n) за някое i≠1i \neq 1, откъдето p∣a1c−aicp \mid a_{1}^{c}-a_{i}^{c}. Тъй като можем да изберем p>max⁡{∣a1c−aic∣:i=2,3,…,k}p\gt{}\max \left\{\left|a_{1}^{c}-a_{i}^{c}\right|: i=2, 3, \ldots, k\right\}, заключаваме, че a1c=aica_{1}^{c}=a_{i}^{c} за някое i≠1i \neq 1, т. е. a1=aia_{1}=a_{i}, противоречие. Нека Q(x)+a1c=R12(x)Q(x)+a_{1}^{c}=R_{1}^{2}(x) е точен квадрат на неконстантен полином с цели коефициенти. Cd=P(2)>P(1)=c\mathrm{C} d=P(2)\gt{}P(1)=c и разсъждения както по-горе заключаваме, че и Q(x)+a1d=R22(x)Q(x)+a_{1}^{d}=R_{2}^{2}(x) е точен квадрат на неконстантен полином с цели коефициенти. Тогаваa1c−a1d=(R1(x)−R2(x))(R1(x)+R2(x)),a_{1}^{c}-a_{1}^{d}=\left(R_{1}(x)-R_{2}(x)\right)\left(R_{1}(x)+R_{2}(x)\right),откъдето лесно следва, че R1≡R2R_{1} \equiv R_{2} и a1c=a1da_{1}^{c}=a_{1}^{d}, т. е. a1=1a_{1}=1.
Отвори задачатаБаза на maths.bgsomnt2020-9-3