forum.zadania.info

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 ?

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

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.

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.

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 ?

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.

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

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

Ma to sens ale w rozumowaniu jest błąd

Ćwiczenie: Znajdź ten błąd.

...

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

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

Nie ma się co denerwować. Zadanie jest trudne.

Czyli nie przedstawisz? No trudno, taka wiedza nas omija...

Przedstawię, spokojnie. Chcę pokazać, że jest to jednak bardzo logiczne, żebyś się przekonał.

No pokaż, czekamy.

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