zliczanie liczb, co jest źle ?
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- 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 ?
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 ?
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 ?
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
-
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: zliczanie liczb, co jest źle ?
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.
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.
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
Re:
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 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
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
Na prawdę ma to sens. W rozumowaniu w pierwszym poście jest błąd. Zachęcam do próby wykrycia na czym polega.Po co liczysz te które się sumują do 14?
W takim razie jaką masz inną metodę ? Ze swojej strony mogę przedstawić bardzo szybką, opartą o "14tkę".Ten moment powinieneś zmienić
Jeśli chodzi o liczenie na pałę to nie będzie to łatwe, szybkie ani eleganckie.
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.Twoje rozumowanie nie jest nic warte
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
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
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
6401380
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
Re:
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żę.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
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
-
- Fachowiec
- Posty: 1751
- Rejestracja: 05 sie 2009, 13:08
- Otrzymane podziękowania: 207 razy
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
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ć.
\((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ć.