Ustalona suma
-
mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Ustalona suma
Ile jest liczb naturalnych mniejszych od \(\displaystyle{ N}\), ktorych suma cyfr jest równa \(\displaystyle{ r}\) ?
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Ustalona suma
Zadanie sprowadza się do rozwiązanie równania w liczbach całkowitych:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r}\) gdzie \(\displaystyle{ k}\) - ilość cyfr liczby \(\displaystyle{ N}\)
ale nasze iksy muszą być cyframi czyli mniejsze niż dziesięć...., trzeba odrzucać te co są większe od \(\displaystyle{ 9}\)
A tu z pomocą przyjdzie nam zasada wyłączania i włanczania:
będziemy mieć takie coś:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r}\) - będzie ich: \(\displaystyle{ {k \choose 0} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-10}\) - będzie ich: \(\displaystyle{ {k \choose 1} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-20}\) - będzie ich: \(\displaystyle{ {k \choose 2} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-30}\) - będzie ich: \(\displaystyle{ {k \choose 3} }\)
..................................................................
A ich ilość to wiadomo: \(\displaystyle{ {r+k-1-i \cdot 10 \choose k-1} }\)
To było łatwe , najgorsze było poszukać dokąd sumować, metodą prób i błędów ustaliłem, że górna granica sumy to:
\(\displaystyle{ \min\left\{ k, \frac{r}{10} \right\} }\)
reasumując mamy wzór:
\(\displaystyle{ a(r,k)= \sum_{i=0}^{\min\left\{ k, \frac{r}{10} \right\}}(-1)^i {k \choose i} \cdot {r+k-1-10i \choose k-1}}\)
gwoli ścisłości powinno się jeszcze wyliczyć \(\displaystyle{ k}\) w zależności od \(\displaystyle{ N}\)
No więc:
\(\displaystyle{ k=\left[ \frac{\ln N}{\ln 10} \right]+1 }\)
Przepraszam zapomniałem \(\displaystyle{ -1}\) do potęgi dać , ale już dałem...
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r}\) gdzie \(\displaystyle{ k}\) - ilość cyfr liczby \(\displaystyle{ N}\)
ale nasze iksy muszą być cyframi czyli mniejsze niż dziesięć...., trzeba odrzucać te co są większe od \(\displaystyle{ 9}\)
A tu z pomocą przyjdzie nam zasada wyłączania i włanczania:
będziemy mieć takie coś:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r}\) - będzie ich: \(\displaystyle{ {k \choose 0} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-10}\) - będzie ich: \(\displaystyle{ {k \choose 1} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-20}\) - będzie ich: \(\displaystyle{ {k \choose 2} }\)
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r-30}\) - będzie ich: \(\displaystyle{ {k \choose 3} }\)
..................................................................
A ich ilość to wiadomo: \(\displaystyle{ {r+k-1-i \cdot 10 \choose k-1} }\)
To było łatwe , najgorsze było poszukać dokąd sumować, metodą prób i błędów ustaliłem, że górna granica sumy to:
\(\displaystyle{ \min\left\{ k, \frac{r}{10} \right\} }\)
reasumując mamy wzór:
\(\displaystyle{ a(r,k)= \sum_{i=0}^{\min\left\{ k, \frac{r}{10} \right\}}(-1)^i {k \choose i} \cdot {r+k-1-10i \choose k-1}}\)
gwoli ścisłości powinno się jeszcze wyliczyć \(\displaystyle{ k}\) w zależności od \(\displaystyle{ N}\)
No więc:
\(\displaystyle{ k=\left[ \frac{\ln N}{\ln 10} \right]+1 }\)
Przepraszam zapomniałem \(\displaystyle{ -1}\) do potęgi dać , ale już dałem...
Ostatnio zmieniony 1 maja 2020, o 19:06 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
a4karo
- Użytkownik
- Posty: 22207
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3754 razy
Re: Ustalona suma
No to weźmy `N=11` i `r=8`arek1357 pisze: ↑1 maja 2020, o 18:49 Zadanie sprowadza się do rozwiązanie równania w liczbach całkowitych:
\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=r}\) gdzie \(\displaystyle{ k}\) - ilość cyfr liczby \(\displaystyle{ N}\)
ale nasze iksy muszą być cyframi czyli mniejsze niż dziesięć...., trzeba odrzucać te co są większe od \(\displaystyle{ 9}\)
Oczywiście jest tylko jedna liczba, która spełnia warunki zadanie, ale arek1357 zlicza również `17, 26, 35, 44, 53,62, 71, 80`
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Ustalona suma
Dokładnie tak to działa, masz rację wzięło się to stąd, że nie za bardzo przejmowałem się N, można na szybko wykonać test typu:
Jeżeli \(\displaystyle{ N-l> 0}\) to liczba jest dobra w przeciwnym wypadku nie , pewnie jest lepszy pomysł ale na razie nie zastanawiałem się...
Wiem, że to nie jest za dobry pomysł...
Dodano po 1 dniu 20 godzinach 49 minutach 18 sekundach:
No posiedziałem nad tym chwilę o coś wymyśliłem, ale nie jest to piękne...
Najpierw ustalmy:
\(\displaystyle{ N=\overline{a_{k}a_{k-1}a_{k-2}...a_{1}}}\)
Teraz musimy rozwiązać kilka równań tego typu:
\(\displaystyle{ x_{k-1}+x_{k-2}+...+x_{1}=r-l , 0 \le l \le a_{k}-1}\)
\(\displaystyle{ x_{k-2}+x_{k-3}+...+x_{1}=r-a_{k}-l , 0 \le l \le a_{k-1}-1}\)
\(\displaystyle{ x_{k-3}+x_{k-4}+...+x_{1}=r-a_{k}-a_{k-1}-l , 0 \le l \le a_{k-2}-1}\)
.........................................................................................
\(\displaystyle{ x_{2}+x_{1}=r-a_{k}-a_{k-1}-...-a_{4}-l , 0 \le l \le a_{3}-1}\)
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{4}-a_{3}-l , 0 \le l \le a_{2}-1}\)
zostaje jeszcze jedno zdegenerowane równanie:
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{3}-a_{2} \wedge x_{1}<a_{1} }\), które ma \(\displaystyle{ c}\) rozwiązań (pewnie zero lub jeden)...
I dzięki pierwszej części zadania teraz łatwo skorzystać ze wzoru już wyprowadzonego i napisać ile każde równanie ma rozwiązań:
\(\displaystyle{ \sum_{i=0}^{min\left\{ s-1, \left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2} }\)
Ale granice sumowania mamy:
\(\displaystyle{ 0 \le l \le a_{s}-1}\)
\(\displaystyle{ 2 \le s \le k}\)
więc obłóżmy to jeszcze dwiema sumami:
\(\displaystyle{ \sum_{s=2}^{k} \sum_{l=0}^{a_{s}-1} \sum_{i=0}^{min\left\{ s-1,\left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2}}\)
jeszcze musimy dodać "zdegenerowane" równanie , to znaczy ilość jego rozwiązań, a więc: \(\displaystyle{ c}\)
I mamy:
\(\displaystyle{ a(N,r)=\sum_{s=2}^{k} \sum_{l=0}^{a_{s}-1} \sum_{i=0}^{min\left\{ s-1,\left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2}+c}\)
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{2} , x_{1}<a_{1}}\)
Gwoli ścisłości trzeba jeszcze wyszukać (wyłuskać) wszystkie \(\displaystyle{ a_{i}}\) w zależności od\(\displaystyle{ N}\)
I jeszcze jedno jeżeli w którymś momencie:
\(\displaystyle{ r- \sum_{j=s+1}^{k}a_{j}-l <0}\)
To przerywamy i pozostajemy na tym etapie który zrobiliśmy dotychczas...
Dodano po 22 minutach 52 sekundach:
Teraz przetestujmy
\(\displaystyle{ N=11 , r=8}\)
\(\displaystyle{ a_{2}=1, a_{1}=1}\)
\(\displaystyle{ s=2 , l=0 , min=0}\)
mamy:
\(\displaystyle{ \sum_{s=2}^{2} \sum_{l=0}^{0} \sum_{i=0}^{0}(-1)^0 \cdot 1+c=1+c }\)
c jest ilością rozwiązań równania:
\(\displaystyle{ x_{1}=8-1=7 , x_{1}<a_{1}=1}\)
z tego:
\(\displaystyle{ c=0}\)
A więc ilość rozwiązań to jeden...
Dodano po 17 minutach 53 sekundach:
\(\displaystyle{ a_{s}}\) , liczymy ze wzoru:
\(\displaystyle{ a_{s}=\left[ \frac{N}{10^{s-1}} \right] -10 \cdot \left[ \frac{N}{10^s} \right] , 1 \le s \le k}\)
\(\displaystyle{ k=\left[ \frac{ln N}{ln 10} \right]+1 }\)
To mamy wszystko...
Jeżeli \(\displaystyle{ N-l> 0}\) to liczba jest dobra w przeciwnym wypadku nie , pewnie jest lepszy pomysł ale na razie nie zastanawiałem się...
Wiem, że to nie jest za dobry pomysł...
Dodano po 1 dniu 20 godzinach 49 minutach 18 sekundach:
No posiedziałem nad tym chwilę o coś wymyśliłem, ale nie jest to piękne...
Najpierw ustalmy:
\(\displaystyle{ N=\overline{a_{k}a_{k-1}a_{k-2}...a_{1}}}\)
Teraz musimy rozwiązać kilka równań tego typu:
\(\displaystyle{ x_{k-1}+x_{k-2}+...+x_{1}=r-l , 0 \le l \le a_{k}-1}\)
\(\displaystyle{ x_{k-2}+x_{k-3}+...+x_{1}=r-a_{k}-l , 0 \le l \le a_{k-1}-1}\)
\(\displaystyle{ x_{k-3}+x_{k-4}+...+x_{1}=r-a_{k}-a_{k-1}-l , 0 \le l \le a_{k-2}-1}\)
.........................................................................................
\(\displaystyle{ x_{2}+x_{1}=r-a_{k}-a_{k-1}-...-a_{4}-l , 0 \le l \le a_{3}-1}\)
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{4}-a_{3}-l , 0 \le l \le a_{2}-1}\)
zostaje jeszcze jedno zdegenerowane równanie:
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{3}-a_{2} \wedge x_{1}<a_{1} }\), które ma \(\displaystyle{ c}\) rozwiązań (pewnie zero lub jeden)...
I dzięki pierwszej części zadania teraz łatwo skorzystać ze wzoru już wyprowadzonego i napisać ile każde równanie ma rozwiązań:
\(\displaystyle{ \sum_{i=0}^{min\left\{ s-1, \left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2} }\)
Ale granice sumowania mamy:
\(\displaystyle{ 0 \le l \le a_{s}-1}\)
\(\displaystyle{ 2 \le s \le k}\)
więc obłóżmy to jeszcze dwiema sumami:
\(\displaystyle{ \sum_{s=2}^{k} \sum_{l=0}^{a_{s}-1} \sum_{i=0}^{min\left\{ s-1,\left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2}}\)
jeszcze musimy dodać "zdegenerowane" równanie , to znaczy ilość jego rozwiązań, a więc: \(\displaystyle{ c}\)
I mamy:
\(\displaystyle{ a(N,r)=\sum_{s=2}^{k} \sum_{l=0}^{a_{s}-1} \sum_{i=0}^{min\left\{ s-1,\left[ \frac{r- \sum_{j=s+1}^{k}a_{j}-l }{10}\right] \right\} }(-1)^i {r- \sum_{j=s+1}^{k}a_{j}-l +s-2-10i \choose s-2}+c}\)
\(\displaystyle{ x_{1}=r-a_{k}-a_{k-1}-...-a_{2} , x_{1}<a_{1}}\)
Gwoli ścisłości trzeba jeszcze wyszukać (wyłuskać) wszystkie \(\displaystyle{ a_{i}}\) w zależności od\(\displaystyle{ N}\)
I jeszcze jedno jeżeli w którymś momencie:
\(\displaystyle{ r- \sum_{j=s+1}^{k}a_{j}-l <0}\)
To przerywamy i pozostajemy na tym etapie który zrobiliśmy dotychczas...
Dodano po 22 minutach 52 sekundach:
Teraz przetestujmy
\(\displaystyle{ N=11 , r=8}\)
\(\displaystyle{ a_{2}=1, a_{1}=1}\)
\(\displaystyle{ s=2 , l=0 , min=0}\)
mamy:
\(\displaystyle{ \sum_{s=2}^{2} \sum_{l=0}^{0} \sum_{i=0}^{0}(-1)^0 \cdot 1+c=1+c }\)
c jest ilością rozwiązań równania:
\(\displaystyle{ x_{1}=8-1=7 , x_{1}<a_{1}=1}\)
z tego:
\(\displaystyle{ c=0}\)
A więc ilość rozwiązań to jeden...
Dodano po 17 minutach 53 sekundach:
\(\displaystyle{ a_{s}}\) , liczymy ze wzoru:
\(\displaystyle{ a_{s}=\left[ \frac{N}{10^{s-1}} \right] -10 \cdot \left[ \frac{N}{10^s} \right] , 1 \le s \le k}\)
\(\displaystyle{ k=\left[ \frac{ln N}{ln 10} \right]+1 }\)
To mamy wszystko...