Liczby o danej sumie cyfr

[NogaWeza]

Witam. Natrafiłem na ciężkie zadanie i niestety nie mam absolutnie żadnego pomysłu na rozwiązanie go.

Ile jest liczb naturalnych z przedziału \(\displaystyle{ [1, 1000000]}\) o sumie cyfr równej \(\displaystyle{ 14}\)?

Dla mniejszej sumy cyfr można by rozpatrywać przypadki i następnie je sumować, ale w tym przypadku to chyba samobójstwo.

[dec1]

Kod: Zaznacz cały

https://oeis.org/A007953/list

Widzisz jakąś zależność?

[NogaWeza]

Widzę, od \(\displaystyle{ 59}\) co dziewiąta liczba ma taką sumę cyfr, ale działa to tylko do \(\displaystyle{ 95}\), później zaś - od \(\displaystyle{ 149}\) znów, aż do \(\displaystyle{ 194}\). Niestety dalej nie widzę jak miałoby mnie to doprowadzić do rozwiązania, nie będę przecież sumował tego setkami aż do samego miliona, prawda?

[dec1]

Dobra wpadłem na inne rozwiązanie:

Suma cyfr miliona to \(\displaystyle{ 1}\), więc interesują nas tylko liczby naturalne o sześciu lub mniej cyfrach.
\(\displaystyle{ a,b,c,d,e,f}\) - cyfry liczby
Interesują nas liczby, dla których \(\displaystyle{ a+b+c+d+e+f=14}\)
Liczba rozwiązań w liczbach naturalnych to \(\displaystyle{ \binom{19}{5}=11628}\) (dlaczego?)
Ale żadna z cyfr oczywiście nie jest większa od \(\displaystyle{ 9}\). Czyli musimy wykluczyć przypadki:
• \(\displaystyle{ a=10 \Leftrightarrow b+c+d+e+f=4}\) Liczba rozwiązań: \(\displaystyle{ \binom{8}{4}=70}\)
• \(\displaystyle{ a=11 \Leftrightarrow b+c+d+e+f=3}\) Liczba rozwiązań: \(\displaystyle{ \binom{7}{4}=35}\)
• \(\displaystyle{ a=12 \Leftrightarrow b+c+d+e+f=2}\) Liczba rozwiązań: \(\displaystyle{ \binom{6}{4}=15}\)
• \(\displaystyle{ a=13 \Leftrightarrow b+c+d+e+f=1}\) Liczba rozwiązań: \(\displaystyle{ \binom{5}{4}=5}\)
• \(\displaystyle{ a=14 \Leftrightarrow b+c+d+e+f=0}\) Liczba rozwiązań: \(\displaystyle{ \binom{4}{4}=1}\) Jedynym rozwiązaniem jest liczba \(\displaystyle{ 00000}\), ale zauważ, że \(\displaystyle{ 000000}\) też spełniło \(\displaystyle{ a+b+c+d+e+f=14}\), więc też trzeba je będzie odjąć.
Suma rozwiązań: \(\displaystyle{ 70+35+15+5+1=126}\)

Oczywiście nie tylko \(\displaystyle{ a}\) może być większa od \(\displaystyle{ 9}\), więc musimy liczbę rozwiązań pomnożyć przez \(\displaystyle{ 6}\); wychodzi \(\displaystyle{ 756}\)
Teraz od liczby rozwiązań pierwszego równania odejmujemy przypadki które nas nie interesują i mamy wynik: \(\displaystyle{ 11628-756=10872}\)

No i sprawdzenie na kompie np. takim programem (C++):

Kod: Zaznacz cały

#include <iostream>
using namespace std;

int suma_cyfr(int i) {
int n=i,s=0,d;
while(n!=0) {
d=n%10;
s+=d;
n/=10;
}
return s;
}

int main() {
int liczby=0;
for(int i=1;i<=1000000;i++) {
if(suma_cyfr(i)==14)
liczby++;
}
cout<<"Liczba liczb: "<<liczby<<endl;
return 0;
}

Wychodzi \(\displaystyle{ 10872}\) - zgadza się.

[NogaWeza]

Ładne rozumowanie, dzięki za pomoc.

[norwimaj]

Wychodzi \(\displaystyle{ 10872}\) - zgadza się.

Oczywiście, ale nie wiem, dlaczego przypadki cyfr większych od \(\displaystyle{ 9}\) obliczasz innym sposobem niż przypadek ogólny. Jeśli chcemy, żeby w jednym pojemniku było ponad \(\displaystyle{ 9}\) kul, to na początku wkładamy tam \(\displaystyle{ 10}\) kul i potem mamy już tylko \(\displaystyle{ 4}\) kule do podziału.

\(\displaystyle{ \binom{14+5}5 - 6\cdot \binom{4+5}5=10872.}\)