Купа на декана 2015

[mdc1600]

Ходихте ли?
Как бяха задачите?
Какво очаквате за втория кръг?
Старите кучета явиха ли се, и ако не, защо?

[mdc1600]

http://www.fmi.uni-sofia.bg/turniri_i_konkursi/turnir2015_2.pdf

Как са задачите?

[math10.com]

Готини задачи, доста лесни според мен и много слабо представяне на участващите.Аз лично 20 точки мога да изкарам за по-малко от 30 минути.Иначе темата е готина.1-ва задача е за 6-ти клас или там някъде , когато се учи делимост на числа.2-ра е рутинна геометрия, 4-та ми е от любимата тематика.3-та е малко неприятна система уравнения , но всеки може да налучка рационалните решения, а 5-та е хубава състезателна задача.То от класирането е видно , че на първите 3 места са участниците решили именно 5-та задача

[matst]

Задача 3. Полагам [tex]x=1+\cos \varphi[/tex]. Получава се [tex]y=1+\cos(2\varphi)[/tex], [tex]z=1+\cos(4\varphi)[/tex] и
[tex]x=1+\cos(8\varphi)[/tex]. От уравнението [tex]\cos\varphi=\cos(8\varphi)[/tex] се намират стойностите на [tex]\varphi[/tex] и след това решенията на системата.

[drago]

Относно 5-та задача: за намирането на B(N), човек трябв да знае един прийом, как да сведе преброяването на кобинации с повторение към кобминации без повторение. Малко вероятно е, ако не го знае, да го измисли по време на състезанието. Ето една подобна задача давана на подборен кръг: viewtopic.php?f=10&t=8183

[nevrodermit]

Задача 5:
Редиците с дължина [tex]n[/tex] са изградени от числата [tex]1,2,\ldots n[/tex] като нека числото [tex]i[/tex] се среща [tex]k_i[/tex] пъти. Редиците са ненамаляващи и значи са съставени от блоковете
[tex]\underbrace{11\ldots 1}_{k_1}\underbrace{22\ldots 2}_{k_2}\cdots \underbrace{nn\ldots n}_{k_n}[/tex]. Значи броят на редиците е броят целочислените неотрицателни решения на [tex]k_1+k_2+\cdots +k_n=n[/tex], за което има известна формула, че е [tex]{2n-1 \choose n}[/tex].

a) [tex]B(2015)={4029 \choose 2015}=\frac{4029!}{2015!2014!}[/tex].
Както знаем, най-високата степен на простото число [tex]p[/tex], която дели [tex]n![/tex] се дава от [tex]v(n,p)=\sum_{k=1}^{\infty}[\frac{n}{p^k}][/tex]. Значи, за да намерим степента на [tex]10[/tex], която дели [tex]B(2005)[/tex] трябва да намерим
[tex]\min(v(4029,2)-v(2015,2)-v(2014,2), v(4029,5)-v(2015,5)-v(2014,5))[/tex].

Смятаме:
[tex]v(4029,2)=[\frac{4029}{2^1}]+[\frac{4029}{2^2}]+[\frac{4029}{2^3}]+[\frac{4029}{2^4}]+[\frac{4029}{2^5}]+[\frac{4029}{2^6}]+[\frac{4029}{2^7}]+[\frac{4029}{2^8}]+[\frac{4029}{2^9}]+[\frac{4029}{2^{10}}]+[\frac{4029}{2^{11}}]+[\frac{4029}{2^{12}}]+\cdots =2014+1007+503+251+125+62+31+15+7+3+1+0+\cdots = 4019[/tex].

[tex]v(2015,2)=[\frac{2015}{2^1}]+[\frac{2015}{2^2}]+[\frac{2015}{2^3}]+[\frac{2015}{2^4}]+[\frac{2015}{2^5}]+[\frac{2015}{2^6}]+[\frac{2015}{2^7}]+[\frac{2015}{2^8}]+[\frac{2015}{2^9}]+[\frac{2015}{2^{10}}]+[\frac{2015}{2^{11}}]=1007+503+251+125+62+31+15+7+3+1=2005[/tex]
[tex]v(2014,2)=[\frac{2014}{2^1}]+[\frac{2014}{2^2}]+[\frac{2014}{2^3}]+[\frac{2014}{2^4}]+[\frac{2014}{2^5}]+[\frac{2014}{2^6}]+[\frac{2014}{2^7}]+[\frac{2014}{2^8}]+[\frac{2014}{2^9}]+[\frac{2014}{2^{10}}]+[\frac{2014}{2^{11}}]=1007+503+251+125+62+31+15+7+3+1=2005[/tex]
И значи най-високата степен на двойката, която дели [tex]B(2005)[/tex] е [tex]4019-2005-2005=9[/tex]

Сега правим същите сметки с числото 5:
[tex]v(4029,5)=[\frac{4029}{5^1}]+[\frac{4029}{5^2}]+[\frac{4029}{5^3}]+[\frac{4029}{5^4}]+[\frac{4029}{5^5}]+[\frac{4029}{5^6}]+\cdots = 805+161+32+6+1=1005[/tex]
[tex]v(2015,5)=[\frac{2015}{5^1}]+[\frac{2015}{5^2}]+[\frac{2015}{5^3}]+[\frac{2015}{5^4}]+[\frac{2015}{5^5}]+[\frac{2015}{5^6}]+\cdots =403+80+16+3=502[/tex]
[tex]v(2014,5)=[\frac{2014}{5^1}]+[\frac{2014}{5^2}]+[\frac{2014}{5^3}]+[\frac{2014}{5^4}]+[\frac{2014}{5^5}]+[\frac{2014}{5^6}]+\cdots =402+80+16+3=501[/tex]
И значи най-високата степен на петицата, която дели [tex]B(2005)[/tex] е [tex]1005-502-501=2[/tex].

Оттук най-високата степен на числото 10, която дели [tex]B(2005)[/tex] е [tex]\min(2,9)=2[/tex] и значи завършва на две нули.

b) В предната точка се питаше на колко нули завършва [tex]B(2015)[/tex], което ни въвежда на мисълта, да търсим нечетни стойности на [tex]B(n)[/tex]. Имаме [tex]B(n)=\frac{(2n-1)!}{n!(n-1)!}[/tex]. Тъй като четността се върти около числото [tex]2[/tex] ще пробваме с [tex]n=2^k[/tex] и ще търсим най-високата степен на числото 2, която дели [tex]B(n)[/tex].
[tex]v(2n-1,2)-v(n,2)-v(n-1,2)=v(2^{k+1}-1,2)-v(2^k,2)-v(2^k-1,2)[/tex]. Смятаме ги поотделно:
[tex]v(2^{k+1}-1,2)=[\frac{2^{k+1}-1}{2^1 }]+[\frac{2^{k+1}-1}{2^2 }]+[\frac{2^{k+1}-1}{2^3 }]+\cdots=(2^k-1)+(2^{k-1}-1)+(2^{k-2}-1)+\cdots =2^{k+1}-k[/tex]
[tex]v(2^k,2)=[\frac{2^k}{2^1}]+[\frac{2^k}{2^2}]+[\frac{2^k}{2^3}]+\cdots = 2^{k-1}+2^{k-2}+2^{k-3}+\cdots = 2^k-1[/tex]
[tex]v(2^k-1,2)=[\frac{2^k-1}{2}]+[\frac{2^k-1}{2^2}]=[\frac{2^k-1}{2^3}]+\cdots = 2^{k}-k+1[/tex]

Откъдето степента на 2-ката е [tex]2^{k+1}-k-2^k+1-2^k+k-1=0[/tex]

Сега да намерим за кои степени на 2-ката имаме 5 по модул 10.
От т-мата на Ойлер, понеже [tex]d(2,5)=1[/tex] и [tex]\varphi(5)=4[/tex] имаме, че [tex]2^4\equiv 1 \pmod{5} \Rightarrow 2^{4k} \equiv 1 \pmod{5}[/tex]. Разглеждаме
[tex]B(2^{4k+r})={2^{4k+r+1}-1 \choose 2^{4k+r}}=\frac{(2^{4k+r+1}-1)!}{2^{4k+r}!(2^{4k+r}-1)!}[/tex].
Искаме биномният коефициент да се дели на 5 и тъй като е нечетен ще следва, че завършва на 5.
За да се дели на 5 трябва
[tex]v(2^{4k+r+1}-1,5)>v(2^{4k+r},5)+v(2^{4k+r}-1, 5)[/tex]
Забелязваме, че [tex]2^{4k+r+1}-1=2^{4k+r} + (2^{4k+r}-1)[/tex], а както знаем [tex][x+y]\ge [x]+[y][/tex]. Т.е ако докажем, че неравенстово е строго за поне една степен на 5, то сме приключили.
Пробваме с първата степен:
[tex][\frac{2^{4k+r+1}-1}{5}][/tex], имаме [tex]2^{4k+r}\equiv 2^r \pmod{5}\Rightarrow 2^{4k+r}=5d+2^r[/tex]. Тогава [tex][\frac{2^{4k+r+1}-1}{5}]=[\frac{10d+2^{r+1}}{5}=2d+[\frac{2^{r+1}}{5}][/tex]. От друга страна [tex][\frac{2^{4k+r}}{5}]=[\frac{5d+2^r}{5}]=d+[\frac{2^r}{5}][/tex] и [tex][\frac{2^{4k+r}-1}{5}]=[\frac{5d+2^r-1}{5}]=d+[\frac{2^r-1}{5}][/tex].
Сега, ако [tex]r\le 1[/tex], то имаме равенство. Ако [tex]r=2[/tex] имаме неравенство. Ако пък е 3 ще получим [tex]3...1+1[/tex] значи и то е решение. Ако е 4, то [tex]6...3+3[/tex] значи не е решение. И така за [tex]r\in \{2,3\}[/tex] имаме безброй много такива коефициенти.