szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 kwi 2016, o 17:32 
Użytkownik
Avatar użytkownika

Posty: 1466
Lokalizacja: Rzeszów/Kraków
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 [1, 1000000] o sumie cyfr równej 14?

Dla mniejszej sumy cyfr można by rozpatrywać przypadki i następnie je sumować, ale w tym przypadku to chyba samobójstwo.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2016, o 17:47 
Użytkownik

Posty: 707
https://oeis.org/A007953/list

Widzisz jakąś zależność?
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2016, o 18:10 
Użytkownik
Avatar użytkownika

Posty: 1466
Lokalizacja: Rzeszów/Kraków
Widzę, od 59 co dziewiąta liczba ma taką sumę cyfr, ale działa to tylko do 95, później zaś - od 149 znów, aż do 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?
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2016, o 18:51 
Użytkownik

Posty: 707
Dobra wpadłem na inne rozwiązanie:

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

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

No i sprawdzenie na kompie np. takim programem (C++):
Kod:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 10872 - zgadza się.
Góra
Mężczyzna Offline
PostNapisane: 16 kwi 2016, o 19:09 
Użytkownik
Avatar użytkownika

Posty: 1466
Lokalizacja: Rzeszów/Kraków
Ładne rozumowanie, dzięki za pomoc.
Góra
Mężczyzna Offline
PostNapisane: 17 kwi 2016, o 12:30 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
dec1 napisał(a):
Wychodzi 10872 - zgadza się.
Oczywiście, ale nie wiem, dlaczego przypadki cyfr większych od 9 obliczasz innym sposobem niż przypadek ogólny. Jeśli chcemy, żeby w jednym pojemniku było ponad 9 kul, to na początku wkładamy tam 10 kul i potem mamy już tylko 4 kule do podziału.

\binom{14+5}5 - 6\cdot \binom{4+5}5=10872.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczby Armstronga - algorytm  michal_2  4
 Czterocyfrowe liczby parzyste  loleq  0
 liczby stucyfrowe  Billie Jean  4
 Tworzymy liczby sześciocyfrowe...  Natmat  2
 tworzenie kombinacji cyfr, inicjały mieszkańców osiedla  Scintilla_wwy  11
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl