S(n)

[v1rusman]

Нека S(n) е сумата от всички цифри на всички цели числа от 1 до "n" включително,записани в десетична бройна система.Колко е S(681) ?
а) 2724 б) 8049 в)18049 г) 235631 д) 235632

[Реклама]

[Мирослав Стоенчев]

[0,10], [1*10,2*10], ... , [67*10,68*10], [1]

S(681)≡68(1+2+...+9)+1≡1(mod 10) => последната цифра на S(681) e 1.
Тази задача не е подходяща за 9-12 клас, по-скоро 6-7.

[r2d2]

Може ли малко по-подробно?

[Мирослав Стоенчев]

Сумираме само последните цифри на числата 1,2,...,681. Т.е. сумираме числата 1,2,...,681 по модул 10, и понеже имаме 68 интервала с дължина 10 ( последните цифрите са 1,2,...,9,0) то имаме 68(1+2+...+9)+1≡1(mod 10) => последната цифра на S(681) е 1.

[r2d2]

Kaква е последната цифра на S(11), S(21)?

[Мирослав Стоенчев]

1+2+...+681= 681*682/2=(680+1)341≡1(mod 10), макар,че 5-токласниците не знаят сума на аритметична прогресия.Ясно е че последната цифра на числото S(681)=1+2+...+681 e 1.
Не разбирам защо тази задача е тук след като е за 5-клас?

[Мирослав Стоенчев]

О, не! Не бях видял че S(n) e сума на цифрите на числата а не на самите числа. Ей сега ще си поправя грешката.

[r2d2]

Не мисля, че има явна ф-ла за S(n).

[Мирослав Стоенчев]

Нека под S(n)-разбираме сумата от цифрите на числото "n".
Ще докажем,че ∑S(i)=8049, където сумирането е по i=1,2,...,681.Нека s=a_k10^k+...+a₁10+1 и a₁≤8.
Ще покажем,че s и s+9 имат равни суми на цифрите.Наистина s+9=a_k10^k+...+(a₁+1)10 =>S(s+9)=a_k+...+a₁+1=S(s).
Значи интервалите [s,s+9], когато цифрата на десетиците в десетичното представяне на s не е 9, а цифрата на единиците е 1, то полагаме S[s,s+9]=S(s)+S(s+1)+...+S(s+9)=9S(s)+S(s+9)+1+2+...+8=10.S(s)+36
Да разгледаме числата k≡9*10+1(mod 100),т.е. които имат последни 2 цифри в десетичното си представяне 9 и 1. За конкретния интервал [0,681] имаме следните числа k=91,191,291,391,491,591.Да разгледаме интервалите [91,100],[191,200],[291,300],[391,400],[491,500],[591,600].Тъй като всеки два поредни се отличават с 100, то и разликата в сумите от цифрите им е 10. Имаме S[91,100]=9*9+(1+2+...+9)+1=80+47, тогава директно намираме останалите:
S[191,200]=10+S[91,100] .
Значи ∑S[k,k+9]=S[91,100]+S[191,200]+S[291,300]+S[391,400]+S[491,500]+S[591,600]=127+137+147
+157+167+177=(127+177)*3=912. Да сумираме по всички s с последна цифра 1 и s≠k, s≤680.Tогава s=1,11,...,81,101,111,...181,201,211,...281,...,671.Teзи s са 68-6=62
∑S[s,s+9]=∑10.S(s)+36=62*36+10*∑S(s)=2232+10[(1+2+...+9)+(2+3+...+10)+...+(7+8+...+14)]
=2232+10[489]=7122
Значи ako сумираме по всички i=1,2,...,681 то ∑S(i)=S(681)+∑S[s,s+9]+∑S[k,k+9]=15+7122+912=8049.
Задачата не е за 6-7 но става за 8-ми клас.

[g_kulekov]

?

[v1rusman]

Това е верният отговор - 8049-браво Шпенглер! Задачата е от "Черноризец Храбър" 9-12 клас за 1994 г.
Не ми е ясно решението на авторите и ако някой схване логиката,ще го помоля да обясни
решението:
S(681)=100.(0+1+2+3+4+5)+6.S(99)+S(81)+6.82=1500+6.S(99)+S(81)+492
S(99)=10.(0+1+2+3+4+5+6+7+8+9)+10.S(9)=20.S(9)=20.45=900
S(81)=10.(0+1+2+3+4+5+6+7)+8.S(9)+S(1)+8.2=280+8.45+1+16=657
=>S(681)=1500+6.900+657+492=8049

[r2d2]

Ето едно просто решение. Означаваме [tex]\mu(a,b)[/tex] сумата на цифрите на числата от а до b. Ясно е че [tex] \mu(0,9)=45[/tex]. Ако k е някоя цифра [tex]\mu(k0,k9)=10k+\mu(0,9)=10k+45.[/tex]. Например [tex]\mu(40,49)=10.4+45=85[/tex].
Toгава [tex]S(99)=\mu(0,9)+\mu(10,19)+...+\mu(90,99)=10(0+1+...+9)+10.45=900[/tex].
Аналогично [tex]\mu(k00,k99)=100k+\mu(0,99)=100k+900[/tex].
Тогава [tex]S(599)=\mu(0,99)+\mu(100,199)+...+\mu(500,599)=100(0+1+..5)+6.900=6900[/tex], a
[tex]S(699)=S(599)+\mu(600,699)=6900+600+900=8400[/tex]

От S(599)<S(681)<S(699) виждаме, че единственият възможен отговор е 8049.

Това решение е за четвърти клас! Разбира се, като знаем S(699) лесно можем да пресметем S(681), но никой не го иска (нещо, което авторите на теста явно са забравили).

Интересно е да се намери приблизителна (асимптотична) оценка за S(n).

[krassi_holmz]

Асимптотичната оценка наистина е интересна: както в повечето такива случаи става, [tex]S(x) = \Theta(x\ln{x})[/tex].
Нека [tex]\mu(n) = \mu(0,10^n-1)[/tex]. С горните разсъждения се достига до рекурсията:
[tex]\mu(1) = 45;\mu(n + 1) = 45 *10^n + 10 \mu(n)[/tex]
с решение:
[tex]\mu(n) = 45*10^{n-1} n[/tex].
Сега,
[tex]S(10^n) = \mu(n) = 45*10^{n-1} n[/tex]
Правим си заместване за асимптотичното поведение:
[tex]S(x) = \frac{9}{2}x \log_{10}{x} = \Theta(x\ln{x})[/tex]