zliczanie liczb, co jest źle ?

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

zliczanie liczb, co jest źle ?

Post autor: tukan »

Mamy znaleźć liczbę liczb w przedziale \([1; 10^6]\) takich, że ich suma cyfr daje \(40\).

Policzyłem komputerem te liczby: \(10872\)
Ale chcę matematyką.
Na początek zakładam, że nie mam zer. I to co robię to tak:
Możemy powiedzieć, że równoważnie możemy policzyć liczbę liczb których cyfry sumują się do 14tki. Dlaczego ?
A bo mamy bijekcję pomiędzy tymi liczbami. Weźmy dowolną sześciocyfrową liczbę, która "cyframi" sumuje się do 14stki.
Teraz każdej cyfrze nadam ujemny znak (nie w sensie dosłownym), a następnie dodam do każdej z nich \(9\).
Otrzymałem liczbę o sumie cyfr \(40\).

Np:
\(123422\) - sumuje się do 14stki.
Teraz robię tak:
\(-1 + 9 = 8\)
\(...\)
\(-2 + 9 = 7\)
Otrzymuję:
\(876577\) - sumuje się do 40stki.
I teraz zliczę liczby które sumują się do 14tki.
(ma być sześć cyfr i nie być zer (na razie zera ignoruję)).
Niech nasza liczba (jej cyfry) to: \(x_1x_2x_3x_4x_5x_6\)
\(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 14\ \ \ \ \ \ x_i > 0\)
Ile mamy różnych rozwiązań (uwzględniając różne permutacje):
\(\binom{14 - 1}{6 - 1} = 1287\)

Czyli tyle jest liczb, które sumują się do 14tki (a więc i do 40tki), ale nie mają zera.

Teraz szukam liczb, które mają w sobie zera i sumują się do 40tki. Widać, że może być tylko jedno \(0\) gdy jest więcej nie uzyskamy sumy równej \(40\).

Więc zobaczmy jedyne możliwości podziału liczby \(40\) na \(5\) liczb, gdzie każda z nich jest mniejsza niż \(10\)
\(4 9 9 9 9 \\
5 8 9 9 9 \\
6 7 9 9 9 \\
6 8 8 9 9 \\
7 7 8 9 9 \\
7 8 8 8 9 \\
8 8 8 8 8\)

I teraz tak - obliczam możliwości zgodnie z tym co przedstawiłem:
\(5 * 6 + 3 * \frac{6!}{3!} + 2 * \frac{6!}{2!2!} + 6 = 756\)

I jeśli teraz dodam:
\(756 + 1287 \neq 10872\)

Ale myślałem nad tym chwilę - a błędu nie widzę.
Co jest źle ?
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

Po co liczysz te które się sumują do 14? Zupelnie nielogiczne to jest i jak widać daje nieprawidłowy wynik.

Ten moment powinieneś zmienic
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
Panko
Fachowiec
Fachowiec
Posty: 2946
Rejestracja: 20 gru 2013, 21:41
Lokalizacja: Radom
Otrzymane podziękowania: 1556 razy
Płeć:

Re: zliczanie liczb, co jest źle ?

Post autor: Panko »

Oznaczmy dla liczby \(n \in N\) ,\(\\) jej sumę cyfr jako \(S(n)\)
Policzyłem przed chwilą w Ideone.com ile jest \(5\)-cyfrowych liczb naturalnych o \(S(n)=40\) .
Odpowiedź : \(126\)
............................................................................................
Szukanie liczb \(n \in [1, 10^6]\) , takich że \(S(n)=40\) ogranicza się natychmiast do \(5\)- cyfrowych , lub \(6\)- cyfrowych.
Dla \(5\)- cyfrowych są to liczby bez zera .
Dla \(6\)- cyfrowych są to liczby bez zera lub z dokładnie jednym zerem .
............................................................................................
Rachunek dla ilości liczb \(5\)--cyfrowych , takich że \(S(n)=40\)
To jak budowa drzewa rozwiązań równania \(x_1+x_2+x_3+x_4+x_5=40\)
Wychodzimy od równości : \(9+9+9+9+9=45\) czyli jest dokładnie jedna realizacja liczby o sumie \(S(n)=45\)
Teraz odejmuję \(1\) od obu stron i dostaję : jedną realizacją (8,9,9,9,9) , liczb jest oczywiście \({5 \choose 4} =5\) . To te o sumie \(S(n)=44\)
Ponownie odejmuję \(1\) i dostaję te o sumie \(S(n)=43\) i ich realizacje : \((7,9,9,9,9)\) , \((8,8,9,9,9)\) .

Tak postępuję do osiągnięcia \(S(n)=40\) i dostaję łącznie nastepujące realizacje : \((4,9,9,9,9)\) , \((5,8,9,9,9)\) , \((6,8,8,9,9)\) ,\((6,7,9,9,9)\) ,\((7,7,8,9,9)\) , \((7,8,8,8,9)\) , \((8,8,8,8,8)\)
Łączna ilość liczb \(5\) --cyfrowych które można utworzyć z kolejno siedmiu realizacji to : \(5+20+30+20+30+20+1=126\) . Zgadza się.
.................................................................................................
Zliczenie \(6\)--cyfrowych należy rozbić na :
Zliczenie \(6\)--cyfrowych z dokładnie jednym zerem . Będzie tego = \(4 \cdot 126\) .
Zliczenie \(6\) --cyfrowych bez zera . Tu na chwilę obecną NIE wiem jak prosto się z tym uporać , bo zastosowanie metody powyżej ( budowa drzewa rozwiązań równania \(x_1+x_2+x_3+x_4+x_5+x_6=40\) ) jest zbyt pracochłonna.
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Re:

Post autor: tukan »

miodzio1988 pisze:Po co liczysz te które się sumują do 14? Zupelnie nielogiczne to jest i jak widać daje nieprawidłowy wynik.

Ten moment powinieneś zmienic
Jest bardzo logiczne. Warto przemyśleć dlaczego. Mi udało się to rozwiązać, bardzo szybką metodą, właśnie korzystając z tej 14tki.
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

Jeżeli byś przedstawił jakieś rozumowanie względem tego naliczenia do 14-stki to by było warto coś pomyśleć, tak to Twoje rozumowanie nie jest nic warte+ daje bledny wynik, wiec o co chodzi ?
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: tukan »

Po co liczysz te które się sumują do 14?
Na prawdę ma to sens. W rozumowaniu w pierwszym poście jest błąd. Zachęcam do próby wykrycia na czym polega.
Ten moment powinieneś zmienić
W takim razie jaką masz inną metodę ? Ze swojej strony mogę przedstawić bardzo szybką, opartą o "14tkę".
Jeśli chodzi o liczenie na pałę to nie będzie to łatwe, szybkie ani eleganckie.
Twoje rozumowanie nie jest nic warte
No właśnie próbuję przekonać, że jest warte. Jest w nim błąd, ale sama idea z sumowaniem do 14tki jest kluczowa w zadaniu.
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

Ma to sens ale w rozumowaniu jest błąd :) :)

Zadnego rozumowania nie przedstawiles swoją drogą, więc nie wiem po co jeszcze piszemy...

No to przedstawiaj, kto Ci broni?

I znowu, jest warte ale jest w rozumowaniu błąd. Jest warte, z wyrazem na g na początku
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Re:

Post autor: tukan »

miodzio1988 pisze:Po co liczysz te które się sumują do 14? Zupelnie nielogiczne to jest i jak widać daje nieprawidłowy wynik.

Ten moment powinieneś zmienic
Tutaj stwierdziłeś, że nielogicznie postępuję licząc te, które sumują się do 14tki. A to na prawdę jest logiczne. Nie chcę przedstawiać, najpierw sam spróbuj zrozumieć. Jak będziesz chciał to Ci pokażę.
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: tukan »

Ma to sens ale w rozumowaniu jest błąd :) :)
Ćwiczenie: Znajdź ten błąd.
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

...

Pozniej placze, że na studiach sobie nie radzi. Z takim "rozumowaniem" się nie dziwię.

Przedstawiaj zatem swoje mądrości, wtedy będziemy mogli o czymś konkretnie pogadać.
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: tukan »

Pozniej placze, że na studiach sobie nie radzi. Z takim "rozumowaniem" się nie dziwię.
Nie ma się co denerwować. Zadanie jest trudne.
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

Czyli nie przedstawisz? :) No trudno, taka wiedza nas omija...
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: tukan »

Przedstawię, spokojnie. Chcę pokazać, że jest to jednak bardzo logiczne, żebyś się przekonał.
miodzio1988
Fachowiec
Fachowiec
Posty: 1751
Rejestracja: 05 sie 2009, 13:08
Otrzymane podziękowania: 207 razy

Post autor: miodzio1988 »

No pokaż, czekamy.
W sprawie rozwiązania zadań proszę pisać na numer GG
6401380
tukan
Fachowiec
Fachowiec
Posty: 985
Rejestracja: 18 paź 2010, 20:45
Podziękowania: 509 razy
Otrzymane podziękowania: 4 razy
Płeć:

Post autor: tukan »

Chodzi o podziały liczby. I zapiszmy tą naszą sześciocyfrową liczbę:

\((x_1x_2x_3x_4x_5x_6).\)
I chcemy teraz zliczyć wszystkie liczby, których suma cyfr sumuje się do 14stki.

\(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 14\)

I o co teraz chodzi.
Szukamy po prostu rozwiązań (uporządkowanych) - tzn ilość rozwiązań, całkowitych nieujemnych.

Jest to \(14 + 6 - 1\choose 6 - 1\)

Ale teraz uwaga:
Ale policzyłem za dużo - a mianowicie np: \(x_1 = 12\ x_2 = ...\)
Tego nie możemy zaakceptować, bo to miały być cyfry.

Ale spokojnie mogę odjąć teraz każdy z tych "złych przypadków".
Tzn ustalmy że \(x_6 =10\) (potem pomnożę razy 6)
Wtedy policzymy ilość rozwiązań równania (analogicznie jak przedtem):
\(x_1 +x _2 + x_3 + x_4 +x _5 = 4\)
To samo zrobię gdy \(x_6 = 11, 12, 13, 14\)
I to wszystko odejmę od \(14 + 6 - 1\choose 6 - 1\).

I na czym polega sens sumowania do 14tki.
Zobacz:
Po pierwsze tych przypadków do odjęcia mam mało (10,11,12,13,14). Ale tak na prawdę chodzi o co innego ( o coś zupełnie innego).
Jak zakładam, że mam x_6 = 10 i odejmuję wszystkie te przypadki, to potem odejmując przypadek x_6 = 11 nie odejmę DRUGI raz przypadku x_6 = 10. (Podkreślam, że trzeba rozsądnie zrozumieć co rozumiem przez przypadek). A dlaczego ? No właśnie dzięki 14tce. Jeśli juz wziąłem jedno jako 11, to nie ma szans, żeby inny iks był 10tką.

W ten sposób dostanie się żądany wynik.

Jeśli coś nie jasne to daj znać.
ODPOWIEDZ