Английска задача

[Spider Iovkov]

Нека [tex][x][/tex] означава цялата част на числото [tex]x[/tex], тоест най-голямото цяло число, ненадминаващо [tex][x][/tex]. Да се пресметне сумата
[tex][\frac{n+1}{2}]+[\frac{n+2}{2^2}]+[\frac{n+2^2}{2^3}]+...+[\frac{n+2^k}{2^{k+1}}]+...[/tex] .

[Реклама]

[Spider Iovkov]

Р е ш е н и е № 1 :

Нека запишем числото [tex]n[/tex] в двоична изчислителна система:
[tex]n=2^ma_{m}+2^{m-1}a_{m-1}+...+2a_{1}+a_{0}[/tex], където [tex]a_{1}=0,1, i=1, 2, ..., p[/tex].
Написваме [tex](i+1)[/tex]-вия член:
[tex][\frac{n+2^i}{2^{i+1}}]=[\frac{2^m a_{m}+...+2^{i+1} a_{i+1}+2^i a_{i}+...+a_{0}+2^i}{2^{i+1}}]=2^{m-1-1}:2^{i+1}+2^i:2^{i+1}=2^i a_{1}:2^{i+1}+2^i:2^{i+1}:[/tex]
[tex](1) 2^i a_{1}:2^{i+1}+2^i:2^{i+1}=0 \Leftrightarrow a_{1}=0,[/tex]
[tex](2) 2^i a_{1}:2^{i+1}+2^i:2^{i+1}=a_{1} \Leftrightarrow a_{1}=1[/tex].
Всички следващи събираеми са равни на нула.
Изчисляваме сумата
[tex]\sum _{i=0}^{m-1}(2^{m-i-1}a_{m}+2^{m-i-2}a_{m-1}+...+a_{i+1}+a_{1})=a_{m}(\sum_{i=0}^{m-1}2^{m-i-1}+1)+a_{m-1}(\sum_{i=1}^{m-1}2^{m-i-2}+1)+...+2a_{1}+a_{0}=a_{m}2^m+a_{m-1}2^{m-1}+...+2a_{1}+a_{0}=n[/tex].
И така
[tex][\frac{n+1}{2}]+[\frac{n+2}{2^2}]+...+[\frac{n+2^k}{2^{k+1}}]+...=n[/tex].

[Spider Iovkov]

Р е ш е н и е № 2 :

[tex][\frac{n+2^s}{2^{s+1}}]=[\frac{a_{p}.2^p+a_{p-1}.2^{p-1}+...+a_{s+1}.2^{s+1}+a_{s}.2^s+...+a_{0}+2^s}{2^{s+1}}]=[a_{p}.2^{p-s-1}+a_{p-1}2^{p-s-2}+...+a_{s+1}+\frac{a_{s}+1}{2}+\frac{\sum_{i=1}^{s-1}a_{i}.2^i}{2^{s+1}}]=\sum_{i=s+1}^{p}a_{1}.2^{p-s-1}+[\frac{a_{s}}+1{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}][/tex].
Но [tex]a\le1 \Rightarrow \sum_{i=0}^{s-1}a_{i}2^i\le \sum_{i=0}^{s-1}2^i[/tex].
Освен това [tex]a_{s}=0[/tex] или [tex]a_{s}=1[/tex].
Ако [tex]a_{s}=0[/tex], то [tex]\frac{a_{s}+1}{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}<\frac{a_{s}+1}{2}+\frac{1}{2}=1[/tex]
[tex]\Rightarrow [\frac{a_{s}+1}{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}]=0=a_{s}[/tex].
Ако [tex]a_{1}=1[/tex], то [tex]\frac{a_{s}+1}{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}<\frac{a_{s}+1}{2}+\frac{1}{2}=1\frac{1}{2}[/tex].
Но [tex]\frac{a_{s}+1}{2}=1 \Rightarrow [\frac{a_{s}+1}{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}]=a_{s}[/tex].
Или въобще [tex][\frac{a_{s}+1}{2}+\frac{\sum_{i=0}^{s-1}a_{i}2^i}{2^{s+1}}]=a_{s}[/tex].
Оттук следва
[tex][\frac{n+2^s}{2^{s+1}}]=a_{p}2^{p-s-1}+a_{p-1}2^{p-s-2}+...+a^{s+1}+a_{s}[/tex].
Прилагаме последователно този резултат:
[tex][\frac{n+1}{2}]=a_{p}2^{p-1}+a_{p-1}2^{p-2}+...+a_{3}2+a_{2}+a_{1},[/tex]
[tex][\frac{n+2}{2^2}]=a_{p}2^{p-2}+a_{p-1}2^{p-3}+...+a_{3}+a_{2},[/tex]
[tex]..........................................................................................................,[/tex]
[tex][\frac{n+2^{p-1}}{2^p}]=a_{p}+a_{p-1},[/tex]
[tex][\frac{n+2^p}{2^{p+1}}]=a_{p},[/tex]
[tex][\frac{n+2^q}{2^{q+1}}]=0, q>p[/tex].
След сумиране на всички тези равенства и след прилагане на формулата за сума на геометрична прогресия получаваме
[tex]\sum_{i=0}^{\infty}[\frac{n+2^i}{2^{i+1}=a_{p}[2^p-1+1]+a_{p-1}[2^{p-1}-1+1]+...+a_{2}.2+a_{1}=a_{p}2^p+a_{p-1}2^{p-1}+...+2a_{2}+a_{1}[/tex].
[tex]\sum_{i=0}^{p}a_{i}2^i=n[/tex]
[tex]\Rightarrow \sum_{i=0}^{\infty}[\frac{n+2^i}{2^{i+1}}]=n[/tex].

Ужасен ужас!

[Spider Iovkov]

Р е ш е н и е № 3 :

Отбелязваме, че щом като [tex]2^i>n[/tex], този член и всички следващи се обръщат в нула, затова даденият в условието ред е краен.
При прехода от [tex]n=k-1[/tex] към [tex]n=k[/tex] всеки член на реда или се запазва, или се увеличава с единица. Ако членът се увеличава с единица, то за никое цяло [tex]m[/tex]
[tex]\frac{k-1+2^i}{2^{i+1}}<m\le \frac{k+2^i}{2^{i+1}}[/tex]
[tex]\Rightarrow k-1<m.2^{i+1}-2^i=2^i(2m-1)\le k[/tex].
Оттук следва, че цялото число [tex]k=2^i(2m-1)[/tex]. Но за произволно [tex]k[/tex] имаме точно едно значение на показателя [tex]i, i\ge0[/tex] за което това е вярно. И обратно, за [tex]k=2^i(2m-1)[/tex] съответстващият член се увеличава с единица.
Нека използваме помощната теорема
[tex][x+\frac{1}{2}]=[2x]-[x][/tex].
Доказателство на лемата. Всяко число [tex]x[/tex] може да се представи или като [tex]x=k+\alpha[/tex] или като [tex]x=k+\frac{1}{2}+\alpha[/tex], където [tex]k[/tex] е цяло и [tex]0\le \alpha<\frac{1}{2}[/tex].
За [tex]=k+\alpha; [k+\alpha+\frac{1}{2}]=k, [2k+2\alpha]=2k, [k+\alpha]=k[/tex], тоест [tex][x+\frac{1}{2}]=[2x]-[x][/tex].
За [tex]x=k+\frac{1}{2}+\alpha; [k+\frac{1}{2}+\alpha+\frac{1}{2}]=k+1, [2k+2\alpha+1]=2k+1, [k+\frac{1}{2}+\alpha]=k[/tex], тоест и в този случай [tex][x+\frac{1}{2}]=[2x]-[x][/tex]. Лемата е доказана.
Преписваме сумата и прилагама помощната теорема:
[tex][\frac{n}{2}+\frac{1}{2}]+[\frac{n}{4}+\frac{1}{2}]+...+[\frac{n}{2^{k+1}}+\frac{1}{2}]+...=[n]-[\frac{n}{2}]+[\frac{n}{2}]-[\frac{n}{4}]+...+[\frac{n}{2^k}]-[\frac{n}{2^{k+1}}]+...=n[/tex], тъй като при [tex]k>log_{2}n[/tex] членът [tex][\frac{n}{2^k}][/tex] и всички следващи са равни на нула.