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

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

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

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

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

2015

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

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

  • somnt2015-9-1: има placeholder текст

9 · Алгебра

3 задачи

Задача 1

Пълен запис
Условие
Нека a,b,c,da, b, c, d са положителни числа, за които abcd=1a b c d=1. Да се докаже, че1+ab1+a+1+bc1+b+1+cd1+c+1+da1+d≥4\frac{1+a b}{1+a}+\frac{1+b c}{1+b}+\frac{1+c d}{1+c}+\frac{1+d a}{1+d} \geq 4
РешениеИмаме1+ab1+a+1+cd1+c=1+ab1+a+1+abab(1+c)≥4(1+ab)1+a+ab+abc1+bc1+b+1+da1+d=1+bc1+b+1+bcbc(1+d)≥≥4(1+bc)1+b+bc+bcd=4a(1+bc)1+a+ab+abc\begin{gathered} \frac{1+a b}{1+a}+\frac{1+c d}{1+c}=\frac{1+a b}{1+a}+\frac{1+a b}{a b(1+c)} \geq \frac{4(1+a b)}{1+a+a b+a b c} \\ \frac{1+b c}{1+b}+\frac{1+d a}{1+d}=\frac{1+b c}{1+b}+\frac{1+b c}{b c(1+d)} \geq \\ \geq \frac{4(1+b c)}{1+b+b c+b c d}=\frac{4 a(1+b c)}{1+a+a b+a b c} \end{gathered}Събираме горните неравенства и получаваме исканото неравенство.
Отвори задачатаБаза на maths.bgsomalg2015-9-1

Задача 2

Пълен запис
Условие
Да се докаже, че не съществува полином p(x)p(x) с цели коефициенти, за който p(x233+x293)=3+x233p(\sqrt[3]{\vphantom{x^2}3}+\sqrt[3]{\vphantom{x^2}9})=3+\sqrt[3]{\vphantom{x^2}3}.
РешениеЛесно се доказва, че ако aa и bb са рационални числа, за които ax233+bx293a \sqrt[3]{\vphantom{x^2}3}+b \sqrt[3]{\vphantom{x^2}9} е рационално число, то a=b=0a=b=0. От този факт с директна проверка следва, че не съществува полином с цели коефициенти и степен по-малка от три, който изпълнява даденото равенство. (Да отбележим, че единственият полином p(x)p(x) с рационални коефициенти и степен по-малка от три, който изпълнява даденото равенство, е p(x)=x2−x2p(x)=\frac{x^{2}-x}{2}.) Да допуснем, че полиномът p(x)p(x) изпълнява дадените условия и степента му е поне три. Ще използваме факта, че числото α=x233+x293\alpha=\sqrt[3]{\vphantom{x^2}3}+\sqrt[3]{\vphantom{x^2}9} е корен на полинома s(x)=x3−9x−12s(x)=x^{3}-9 x-12. Нека p(x)=s(x)q(x)+r(x)p(x)=s(x) q(x)+r(x), където q(x)q(x) и r(x)r(x) са полиноми с цели коефициенти и r(x)=0r(x)=0 или deg⁡r(x)≤2\operatorname{deg} r(x) \leq 2. Тъй като r(α)=p(α)=3+x233r(\alpha)=p(\alpha)=3+\sqrt[3]{\vphantom{x^2}3} стигаме до противоречие и твърдението е доказано.
Отвори задачатаБаза на maths.bgsomalg2015-9-2

Задача 3

Пълен запис
Условие
Да се намерят всички функции f:R+→R+f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}такива, че f(y)f(xf(y))=f(x+y)f(y) f(x f(y))=f(x+y) за произволни x,y>0x, y\gt{}0.
РешениеАко допуснем, че f(y)>1f(y)\gt{}1 за някое y>0y\gt{}0, то след полагането x=yf(y)−1x=\frac{y}{f(y)-1} в началното равенство достигаме до противоречието f(y)=1f(y)=1. И така, f<1f\lt{}1. Оттук и условието следва, че ff е намаляваща функция. Нека сега f(y)=1f(y)=1 за някое y>0y\gt{}0. Тогава f(x+y)=f(x)f(x+y)=f(x) за всяко x>0x\gt{}0 и монотонноста на ff показва, че f=1f=1. Остава да разгледаме случая, когато f(y)<1f(y)\lt{}1 за всяко y>0y\gt{}0. Тогава ff е строго намаляваща функция и значи е инективна. Сега от равенстватаf(y)f(xf(y))=f(x+y)=f(xf(y)+y+x(1−f(y))=f(xf(y))f((y+x(1−f(y))f(f(xf(y)))\begin{gathered} f(y) f(x f(y))=f(x+y)=f(x f(y)+y+x(1-f(y)) \\ =f(x f(y)) f((y+x(1-f(y)) f(f(x f(y))) \end{gathered}следва, че y=(y+x(1−f(y))f(xf(y))y=(y+x(1-f(y)) f(x f(y)). Като положим y=1,xf(1)=zy=1, x f(1)=z и c=1−1f(1)c= 1-\frac{1}{f(1)}, получаваме, че f(z)=11+czf(z)=\frac{1}{1+c z}. И така, f(x)=11+cx(c>0)f(x)=\frac{1}{1+c x}(c\gt{}0), като лесно се проверява, че тези функции изпълняват даденото условие.
Отвори задачатаБаза на maths.bgsomalg2015-9-3

9 · Геометрия

3 задачи

Задача 1

Пълен запис
Условие
Даден е остроъгълният △ABC\triangle A B C с център на описаната окръжност точка OO. Нека HA,HBH_{A}, H_{B} и HCH_{C} са ортоцентровете съответно на △BOC,△AOC\triangle B O C, \triangle A O C и △AOB\triangle A O B. Да се докаже, че ако точката OO е ортоцентърът на △HAHBHC\triangle H_{A} H_{B} H_{C}, то △ABC\triangle A B C е равностранен.
РешениеРешение. Точка OO е ортоцентър на △HAHBHC\triangle H_A H_B H_C, следователно HCO⊥HAHBH_C O \perp H_A H_B. От друга страна, точка HCH_C е ортоцентър на △AOB\triangle A O B, откъдето HCO⊥ABH_C O \perp A B. Следователно HAHB∥ABH_A H_B \| A B. По условие точките HBH_B и HAH_A са ортоцентровете съответно на △AOC\triangle A O C и △BOC\triangle B O C, откъдето получаваме, че HBA⊥OCH_B A \perp O C и HAB⊥OCH_A B \perp O C. Тогава HAB∥HBAH_A B \| H_B A. Следователно HABAHBH_A B A H_B е успоредник. Оттук получаваме, че HAB=HBAH_A B=H_B A. Лесно се вижда, че при стандартни означения за ъглите на триъгълника имаме ∠BHAC=180∘−2α\angle B H_A C=180^{\circ}-2 \alpha и △BHAC\triangle B H_A C е равнобедрен, защото △BOC\triangle B O C е такъв. Следователно HAB=BC2cos⁡αH_A B=\frac{B C}{2 \cos \alpha}. Аналогично HBA=AC2cos⁡βH_B A=\frac{A C}{2 \cos \beta}. Така получихме, че от HAB=HBAH_A B=H_B A следва, че BC2cos⁡α=AC2cos⁡β\frac{B C}{2 \cos \alpha}=\frac{A C}{2 \cos \beta}, а оттук получаваме sin⁡αcos⁡β=cos⁡αsin⁡β\sin \alpha \cos \beta=\cos \alpha \sin \beta. Това означава, че sin⁡(α−β)=0\sin (\alpha-\beta)=0 или AC=BCA C=B C. Аналогично получаваме, че AC=ABA C=A B.
Отвори задачатаБаза на maths.bgsomgeo2015-9-1

Задача 2

Пълен запис
Условие
Даден е остроъгълният △ABC\triangle A B C с ортоцентър HH. Ъглополовящите на ∠ABH\angle A B H и ∠ACH\angle A C H се пресичат в точката EE. Нека CE∩AB=FC E \cap A B= F. Нека AEA E пресича описаната окръжност около △BEF\triangle B E F за втори път в точката GG. Да се докаже, че AG.BC≥CG.ABA G. B C \geq C G. A B.
РешениеРешение. Нека BE∩AC=DB E \cap A C=D. Нека ∠BAC=α\angle B A C=\alpha. Тогава ∠BFC=∠BDC=45∘+α2\angle B F C=\angle B D C=45^{\circ}+\frac{\alpha}{2}. Следователно четириъгълникът BFDCB F D C е вписан и оттук AC.AD=AB.AF=AE.AGA C. A D=A B. A F=A E. A G. Тогава и четириъгълникът DEGCD E G C е вписан и оттук ∠EGC+∠EGB=∠ADE+∠AFE\angle E G C+\angle E G B=\angle A D E+\angle A F E, откъдето следва, че ∠BGC=90∘+α\angle B G C=90^{\circ}+\alpha. Построяваме такава точка MM, че △BAC∼△BGM\triangle B A C \sim \triangle B G M. Тогава ∠CGM=90∘\angle C G M=90^{\circ}. Имаме ABBG=BCBM\frac{A B}{B G}=\frac{B C}{B M} и ∠ABG=∠CBM\angle A B G=\angle C B M и оттук △ABG∼△CBM\triangle A B G \sim \triangle C B M. Тогава CM=AG.BCABC M=\frac{A G. B C}{A B}, но от ∠CGM=90∘\angle C G M=90^{\circ} следва CG≤CMC G \leq C M и получаваме исканото неравенство.
Отвори задачатаБаза на maths.bgsomgeo2015-9-2

Задача 3

Пълен запис
Условие
Даден е изпъкналият четириъгълник ABCDA B C D, описан около окръжност с център II. Точката PP е такава, че ∠APC\angle A P C и ∠BPD\angle B P D имат обща вътрешна ъглополовяща ll. Да се докаже, че II лежи върху ll.
РешениеG3. Нека MM е точката на Микел за четирите прави AB,BC,CDA B, B C, C D и DAD A (това е пресечната точка на описаните окръжности на четирите триъгълника, образувани от тези прави). Ще докажем първо, че MM притежава описаното в задачата свойство, т. е., че ∠AMC\angle A M C и ∠BMD\angle B M D имат обща вътрешна ъглополовяща. Нека QQ и RR са такива, че △MIQ∼△MCB\triangle M I Q \sim \triangle M C B и △MIR∼△MAB\triangle M I R \sim \triangle M A B, като подобията са еднопосочни. Тогава △MDA∼△MIQ∼△MCB\triangle M D A \sim \triangle M I Q \sim \triangle M C B и следователно △BQA∼△CID\triangle B Q A \sim \triangle C I D. Оттук, ∠BQA+∠AIB=∠CID+∠AIB=180∘,AIBQ\angle B Q A+\angle A I B=\angle C I D+\angle A I B=180^{\circ}, A I B Q е вписан и ъглите между страните и диагоналите му са равни на половинките от ъглите на ABCDA B C D. Аналогично, същото е вярно и за ICRBI C R B. По този начин, тези два четириъгълника са подобни по равни съответни ълли и MICRB∼MAIBQM I C R B \sim M A I B Q, откъдето △MIC∼△MAI\triangle M I C \sim \triangle M A I и ∠CMI=∠IMA\angle C M I=\angle I M A. Аналогично получаваме и △MDI∼△MIB\triangle M D I \sim \triangle M I B и ∠DMI=∠IMB\angle D M I=\angle I M B, откъдето исканото следва. Да пристъпим сега към решението на задачата. Нека точката PP притежава описаното свойство и MPC′I′A′∼MDCIAM P C^{\prime} I^{\prime} A^{\prime} \sim M D C I A. Понеже ∠APC\angle A P C и ∠BPD\angle B P D имат обща вътрешна ъглополовяща и △CPD∼△BA′A\triangle C P D \sim \triangle B A^{\prime} A, имаме ∠BPA=∠CPD=∠BA′A\angle B P A=\angle C P D=\angle B A^{\prime} A, откъдето BAPA′B A P A^{\prime} е вписан. Аналогично, BCPC′B C P C^{\prime} също е вписан. Понеже BIB I е ъглополовяща и четириъгълниците BAPA′B A P A^{\prime} и BCPC′B C P C^{\prime} са вписани, имаме∠IBP=12(∠ABP+∠CBP)=12(∠AA′P+∠CC′P)=12(∠AA′M−∠PA′M+∠CC′M−∠PC′M).\begin{aligned} \angle I B P & =\frac{1}{2}(\angle A B P+\angle C B P)=\frac{1}{2}\left(\angle A A^{\prime} P+\angle C C^{\prime} P\right) \\ & =\frac{1}{2}\left(\angle A A^{\prime} M-\angle P A^{\prime} M+\angle C C^{\prime} M-\angle P C^{\prime} M\right). \end{aligned}Разделяме тази сума на части и ги преобразуваме поотделно. Понеже △AA′M∼△CC′M∼△II′M\triangle A A^{\prime} M \sim \triangle C C^{\prime} M \sim \triangle I I^{\prime} M, то12(∠AA′M+∠CC′M)==12(∠II′M+∠II′M)=∠II′M.\begin{gathered} \frac{1}{2}\left(\angle A A^{\prime} M+\angle C C^{\prime} M\right)= \\ =\frac{1}{2}\left(\angle I I^{\prime} M+\angle I I^{\prime} M\right)=\angle I I^{\prime} M. \end{gathered}Понеже BIB I е ъглополовяща, то12(∠PA′M+∠PC′M)==12(∠ABM+∠CBM)=∠IBM=∠PI′M.\begin{gathered} \frac{1}{2}\left(\angle P A^{\prime} M+\angle P C^{\prime} M\right)= \\ =\frac{1}{2}(\angle A B M+\angle C B M)=\angle I B M=\angle P I^{\prime} M. \end{gathered}И така, ∠IBP=∠II′M−∠PI′M=∠II′P\angle I B P=\angle I I^{\prime} M-\angle P I^{\prime} M=\angle I I^{\prime} P и следователно BIPI′B I P I^{\prime} е вписан. Оттук ∠BPI=∠BI′I\angle B P I=\angle B I^{\prime} I. От друга страна, от доказаното по-горе за точката MM имаме, че △MPI′∼△MDI∼△MIB\triangle M P I^{\prime} \sim \triangle M D I \sim \triangle M I B и следователно MDIP∼MIBI′M D I P \sim M I B I^{\prime} и ∠IPD=∠BI′I\angle I P D=\angle B I^{\prime} I. По този начин, ∠BPI=∠IPD\angle B P I=\angle I P D, което и трябваше да се докаже.
Отвори задачатаБаза на maths.bgsomgeo2015-9-3

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

3 задачи

Задача 1

Пълен запис
Условие
Дадени са 2015 кофи с еднаква вместимост от vv литра. На един ход Иван разпределя 1 литър вода в дадените кофи, а Петър може да изпразни произволни 2014 от кофите. Да се намерят всички стойности на vv, за които Иван може да напълни догоре някоя кофа за краен брой ходове.
РешениеЩе решим задачата за kk кофи. Да означим с aia_{i} най-голямото количество вода, което може да остане след ii-ия ход. Ясно е, че a1=1k<1k−1a_{1}=\frac{1}{k}\lt{}\frac{1}{k-1}. Ако an−1<1k−1a_{n-1}\lt{}\frac{1}{k-1}, то Иван може да разпредели водата така, че във всяка кофа да има по 1+an−1k\frac{1+a_{n-1}}{k} литра и по индукция намирамеan=1+an−1k<1+1k−1k=1k−1.a_{n}=\frac{1+a_{n-1}}{k}\lt{}\frac{1+\frac{1}{k-1}}{k}=\frac{1}{k-1}.Следователно an=1+an−1ka_{n}=\frac{1+a_{n-1}}{k}, т. е. kan−an−1=1k a_{n}-a_{n-1}=1. От това равенство и от kan−1−an−2=1k a_{n-1}- a_{n-2}=1 получавамеkan−(k+1)an+an−2=0.k a_{n}-(k+1) a_{n}+a_{n-2}=0.Корените на характеристичното уравнение x2−(k+1)x+1=0x^{2}-(k+1) x+1=0 са x1=1x_{1}=1 и x2=1kx_{2}=\frac{1}{k}, откъдето an=c1+c2kna_{n}=c_{1}+\frac{c_{2}}{k^{n}} за някакви константи c1c_{1} и c2c_{2}. От a1=1ka_{1}=\frac{1}{k} и a2=1+1kk=k+1k2a_{2}=\frac{1+\frac{1}{k}}{k}=\frac{k+1}{k^{2}} намираме c1=1k−1c_{1}=\frac{1}{k-1} и c2=−1k−1c_{2}=-\frac{1}{k-1}. Следователноan=1k−1−1(k−1)kna_{n}=\frac{1}{k-1}-\frac{1}{(k-1) k^{n}}откъдето lim⁡n→∞an=1k−1\lim _{n \rightarrow \infty} a_{n}=\frac{1}{k-1}. Ако 1k−1+1≤v\frac{1}{k-1}+1 \leq v, то an+1<1k−1+1≤va_{n}+1\lt{}\frac{1}{k-1}+1 \leq v, т. е. Иван не може да напълни никоя кофа. Ако 1k−1+1=kk−1>v\frac{1}{k-1}+1=\frac{k}{k-1}\gt{}v, то за ϵ=1k−1+1−v>0\epsilon=\frac{1}{k-1}+1-v\gt{}0 съществува nn, за което 1k−1−an<ϵ=1k−1+1−v\frac{1}{k-1}-a_{n}\lt{}\epsilon=\frac{1}{k-1}+1-v. Оттук an+1>va_{n}+1\gt{}v, т. е. една кофа може да се напълни догоре. При k=2015k=2015 търсените стойности са v<20152014v\lt{}\frac{2015}{2014}.
Отвори задачатаБаза на maths.bgsomcomb2015-9-1

Задача 2

Пълен запис
Условие
За всяка редица uu от нули и единици с дължина 5 с D(u)D(u) означаваме множеството от редиците с дължина 4, които могат да се получат чрез изтриване на един елемент на редицата uu. Множеството AA, съставено от няколко редици с дължина 5, е такова, че за всеки две редици u,v∈Au, v \in A е изпълнено, че множествата D(u)D(u) и D(v)D(v) нямат общи елементи. Да се намери max⁡∣A∣\max |A|.
РешениеМножеството A={00000,11111,11000,00011,10101,01110}A=\{00000, 11111, 11000, 00011, 10101, 01110\} е съставено от 6 редици, като директно се проверява, че при u,v∈Au, v \in A имаме D(u)∩D(v)=∅D(u) \cap D(v)=\emptyset. Следователно max⁡∣A∣≥6\max |A| \geq 6. Да допуснем, че съществува такова множество AA с повече от 6 редици. За x∈{0,1}x \in\{0, 1\}, ако xxxx∉D(u)x x x x \notin D(u) за всяко u∈Au \in A, то към AA можем да добавим xxxxxx x x x x. Ако xxxx∈D(u)x x x x \in D(u) за някое u∈Au \in A, то можем да заместим uu с редицатаxx⁡xxx\operatorname{xx} x x x. Следователно без ограничение 00000,11111∈A00000, 11111 \in A. Всяка от останалите поне 5 редици ще има две нули и три единици или три нули и две единици. Поне три от редиците имат равен първи член (нека без ограничение това е 0)0) и от тези три редици поне две имат равен последен член xx.0,u2,u3,u4,x,0,u2,u3,u4,x0, u_2, u_3, u_4, x, \quad 0, u_2, u_3, u_4, xАко x=0x=0, изтриваме нулите от u2,u3,u4u_2, u_3, u_4 и v2,v3,v4v_2, v_3, v_4 (във всяка от u2,u3,u4u_2, u_3, u_4 и v2,v3,v4v_2, v_3, v_4 има най-много по една нула) и получаваме 0110. Ако x=1x=1, директно се проверява, че единствените възможности са 01101 и 00011 или 00111 и 01001. И в двата случая директна проверка за третата редица с първи член 0 показва, че не се получава множество с търсеното свойство. Следователно търсената максимална стойност е 6.
Отвори задачатаБаза на maths.bgsomcomb2015-9-2

Задача 3

Пълен запис
Условие
Даден е правилен pp-ъгълник MM, където pp е просто число. Оцветяване на част от диагоналите и страните на MM в червено се нарича интересно, ако е оцветена поне една отсечка и върху всяка от оцветените отсечки може да се избере посока, така че сборът от получените вектори да е 0. Да се намери броят на интересните оцветявания.
РешениеЩе докажем, че едно оцветяване е интересно, ако в графа, образуван от върховете на pp-ъгълника и червените отсечки, всеки връх е от четна степен. Ако това е така, то ребрата се групират в няколко Ойлерови цикъла, във всеки от който може да се избере посока така, че сборът на получените вектори да е нула. Обратно, да разгледаме едно интересно оцветяване. Да означим върховете на pp-ъгълника с комплексните числа z,z2,…,zp=1z, z^{2}, \ldots, z^{p}=1. Съществуването на посока върху всяко оцветено ребро е еквивалентно на съществуване на линейна комбинация на върховете, която е равна на 0. Тъй като всеки вектор дава един коефициент 1 и един коефициент -1, то сборът от коефициентите на тази линейна комбинация е 0. Следователноf(z)=a0+a1z+⋯+ap−1zp−1f(z)=a_{0}+a_{1} z+\cdots+a_{p-1} z^{p-1}като a0+a1+⋯+ap−1=0a_{0}+a_{1}+\cdots+a_{p-1}=0. Полиномът g(z)=1+z+z2+⋯+zp−1g(z)=1+z+z^{2}+\cdots+z^{p-1} е минималният полином на zz и следователно f(z)f(z) дели g(z)g(z). Но f(z)f(z) и g(z)g(z) са с равни степени, откъдето g(z)=tf(z)g(z)=t f(z), за някоя константа tt. Ако f(z)f(z) не е нулевият полином, то това е невъзможно тъй като g(1)=pg(1)=p, а f(1)=0f(1)=0. Следователно f(z)=0f(z)=0, т. е. всеки връх е от четна степен. Остава да намерим броя на графите GG с pp върха, с поне едно ребро и всички върхове на който са от четна степен. Този брой е равен на броя на графите с p−1p-1 върха (от всеки граф с p−1p-1 върха с добавяне на връх, свързан с всички върхове с нечетна степен се получава граф от търсения вид с pp върха, а от всеки граф GG с даденото свойство след изтриване на връх и всичките ребра, които излизат от него, получаваме граф с p−1p-1 върха). Тъй като в граф с p−1p-1 върха има (p−12)\binom{p-1}{2} различни двойки върхове, то графите с p−1p-1 върха и поне едно ребро са точно 2(p−12)−12^{\left(\frac{p-1}{2}\right)}-1.
Отвори задачатаБаза на maths.bgsomcomb2015-9-3

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

3 задачи

Задача 1

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

Задача 2

Пълен запис
Условие
Ще решим следната по-обща задача. Дадени са естествени числа m≥3m \geq 3 и s≥2s \geq 2, като ss не се дели на 2[m+12]2^{\left[\frac{m+1}{2}\right]}. Да се докаже, че за всяко естествено число kk съществува естествено число nn, такова, че числото n2k−2m+1n 2^{k}-2^{m}+1 е точна ss-та степен на естествено число. Достатъчно е да покажем, че за всяко естествено kk сравнението xs≡1−2m( mod 2k)x^{s} \equiv 1-2^{m} \left(\bmod 2^{k}\right) има
Решениеx_{k}.При. При k \leq mтоваеочевидноможемдавземем това е очевидноможем да вземем x_{1}= x_{2}=\cdots=x_{m}=1.Ако. Ако x_{k}епринякое е при някое k \geq m,щеконструирамеxk+1, ще конструираме x_{k+1} за k+1k+1. Ако xks≡1−2m( mod 2k+1)x_{k}^{s} \equiv 1-2^{m}\left(\bmod 2^{k+1}\right), полагаме xk+1=xkx_{k+1}=x_{k}. Ако xks≢1−2m( mod 2k+1)x_{k}^{s} \not \equiv 1-2^{m}\left(\bmod 2^{k+1}\right), то xks≡1−2m+2k( mod 2k+1)x_{k}^{s} \equiv 1-2^{m}+2^{k}\left(\bmod 2^{k+1}\right). Нека s=2abs=2^{a} b, където bb е нечетно число, а a≤[m+12]−1a \leq\left[\frac{m+1}{2}\right]-1, т. е. a+1≤m+12⟺2a+1≤ma+1 \leq \frac{m+1}{2} \Longleftrightarrow 2 a+1 \leq m. Тогава полагаме xk+1=xk+2k−ax_{k+1}=x_{k}+2^{k-a}. Имаме последователноxk+1s=(xk+2k−a)s≡xks+sxks−12k−a≡1−2m+2k(1+bxks−1)≡1−2m( mod 2k+1)\begin{aligned} x_{k+1}^{s} & =\left(x_{k}+2^{k-a}\right)^{s} \equiv x_{k}^{s}+s x_{k}^{s-1} 2^{k-a} \\ & \equiv 1-2^{m}+2^{k}\left(1+b x_{k}^{s-1}\right) \equiv 1-2^{m}\left(\bmod 2^{k+1}\right) \end{aligned}(използвахме, че 2(k−a)≥k+1⟺k≥2a+12(k-a) \geq k+1 \Longleftrightarrow k \geq 2 a+1, което следва от k≥m≥2a+1k \geq m \geq 2 a+1 и че числата bb и xkx_{k} са нечетни).
Отвори задачатаБаза на maths.bgsomnt2015-9-2

Задача 3

Пълен запис
Условие
Дадени са редица Y=(y1,y2,…,yn−t)Y=\left(y_{1}, y_{2}, \ldots, y_{n-t}\right) от нули и единици, където n,t∈N,1≤t≤n−1n, t \in \mathbb{N}, 1 \leq t \leq n-1, и цяло число a∈{0,1,…,n}a \in\{0, 1, \ldots, n\}. Редицата X=(x1,x2,…,xnX=\left(x_{1}, x_{2}, \ldots, x_{n}\right. ), също от нули и единици, се нарича суперредица на YY, ако YY може да бъде получена от XX с премахване на tt елемента. Да се намери броят на суперредиците X=(x1,x2,…,xn)X=\left(x_{1}, x_{2}, \ldots, x_{n}\right) на YY, за които е изпълнено сравнениетоx1+2x2+⋯+nxn≡a( mod n+1)x_{1}+2 x_{2}+\cdots+n x_{n} \equiv a \quad(\bmod n+1)
РешениеПърво ще докажем, че всяка редица YY с дължина n−1n-1 може да бъде допълнена по единствен начин до нейна суперредица XX с дължина nn при условие, че разглежданото сравнение има решение. Нека добавеният символ s∈{0,1}s \in\{0, 1\} и нека pp е позицията на ss в XX, т. е. xp=sx_{p}=s. Да означим с L0L_{0} броят на нулите и с L1L_{1} броят на единиците отляво на xpx_{p} в XX и аналогично нека R0R_{0} (съответно R1R_{1} ) е броят на нулите (единиците) отдясно на xpx_{p} в XX. Очевидно имаме p=1+L0+L1p=1+L_{0}+L_{1}. Освен това, ако ww е теглото (т. е. броят на единиците) на YY, то w=L1+R1w=L_{1}+R_{1}. Нека S=∑iixi( mod n+1)S=\sum_{i} i x_{i}(\bmod n+1) и S′=∑iiyi( mod n+1)S^{\prime}=\sum_{i} i y_{i}(\bmod n+1). Ако s=0s=0, имамеS−S′( mod n+1)=R1≤w,S-S^{\prime} \quad(\bmod n+1)=R_{1} \leq w,а ако s=1s=1, тоS−S′( mod n+1)=p+R1=1+L0+L1+R1=1+L0+w>w.S-S^{\prime}(\bmod n+1)=p+R_{1}=1+L_{0}+L_{1}+R_{1}=1+L_{0}+w\gt{}w.Тъй като S≡a( mod n+1)S \equiv a(\bmod n+1), разликата отляво е известна. Ако тя не надминава ww, трябва да сме добавили 0, т. е. xp=0x_{p}=0, в противен случай xp=1x_{p}=1. В първия случай намираме еднозначно R1R_{1}, а във втория (отново еднозначно) L0L_{0} и това определя позицията pp (всъщност получаваме XX като добавим 0 отляво на R1R_{1} единици, броени отдясно наляво в YY, или 1 отдясно на L0L_{0} нули, броени отляво надясно). Остава да преброим суперредиците на YY с дължина n−1n-1. Лесно се вижда, че този брой е ∑i=0t−1(n−1i)\sum_{i=0}^{t-1}\binom{n-1}{i}.
Отвори задачатаБаза на maths.bgsomnt2015-9-3