Ustalona suma

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 6007
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2499 razy
Pomógł: 666 razy

Ustalona suma

Post autor: mol_ksiazkowy » 29 kwie 2020, o 16:03

Ile jest liczb naturalnych mniejszych od \(\displaystyle{ N}\), ktorych suma cyfr jest równa \(\displaystyle{ r}\) ?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Ustalona suma

Post autor: arek1357 » 1 maja 2020, o 16:26

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...
Ostatnio zmieniony 1 maja 2020, o 19:06 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

a4karo
Użytkownik
Użytkownik
Posty: 18116
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 5 razy
Pomógł: 3060 razy

Re: Ustalona suma

Post autor: a4karo » 1 maja 2020, o 19:23

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}\)
No to weźmy `N=11` i `r=8`

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`

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Ustalona suma

Post autor: arek1357 » 1 maja 2020, o 20:37

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...

ODPOWIEDZ