suma cyfr równa 16

[matrix2000]

Ile jest liczb ze zbioru {0...9999} których suma cyfr jest równa 16?

[Xitami]

\(\displaystyle{ \left(\sum_{i=0}^{9}x^i\right)^4=1+4x^{1} +10x^{2} +20x^{3} +35x^{4} +56x^{5} +84x^{6} +120x^{7} +165x^{8} +220x
^{9} +282x^{10} +348x^{11} +415x^{12} +480x^{13} +540x^{14} +592x^{15} +633x^{16
} +660x^{17} +670x^{18} +660x^{19} +633x^{20} +592x^{21} +540x^{22} +480x^{23} +
415x^{24} +348x^{25} +282x^{26} +220x^{27} +165x^{28} +120x^{29} +84x^{30} +56x^
{31} +35x^{32} +20x^{33} +10x^{34} +4x^{35} +x^{36}}\)

Pytałeć o \(\displaystyle{ n=16}\), a u masz odpowiedź dla \(\displaystyle{ 0\leq n\leq 36}\)

[piotr88]

moglbys napisac skad to wzioles ;

[Xitami]

Liczba to \(\displaystyle{ T*1000+S*100+D*10+J}\) (Tysiące, Setki, itd)
pytanie jest równoważne rozwiązaniu równania\(\displaystyle{ T+S+D+J=n}\) lub \(\displaystyle{ \sum_{k=1}^{4} z_i=n}\)
(Dokładniej, to znalezieniu liczby rozwiązań)
Nie podejmuję się tłumaczenia podstaw (zobacz np. Herbert Wilf, generatingfunctionology) (jak nie znajdziesz to podeślę)
Funkcje tworzące (mnie jednak bardziej podoba się generujące)

\(\displaystyle{ \left(\sum_{i=0}^9}x^i\right)^4}\)
4-liczba cyfr
0 i 9 - ograniczenia nałożone na \(\displaystyle{ z_i}\)
Współczynniki występujące przy odpowienich potęgach \(\displaystyle{ x}\) (=n) to właśnie liczba rozwiązań
Skoro mamy 4 cyfry, to maksymalna ich suma to \(\displaystyle{ 4*9=36}\), minimalna to...?

[matrix2000]

wielkie dzieki Wygląda to bardzo ciekawie do tego typu zadań, musze to sobie pzreanalizować

[piotr88]

dzieki Xitami, a nie pokusilbys sie zerknac na zadanie ;

[matrix2000]

w gruncie rzeczy to jednak nie ułatwia sprawy na tyle ile bym chciał Wyliczyłeś to w jakims programie? Problem jest taki że trzeba tu jakby otrzymać wszystkie możliwości ale wymnożenie poprawnie tylu zmiennych na kole jest raczej niemożliwe
\(\displaystyle{ (x^{0}+x^{1}+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}+x^{8}+x^{9})^{4}}\)

[Xitami]

Mathematica pewnie to potrafi, nie mam jej więc napisałem sobie maleńki, Pascal'owy programik.

[ Dodano: 27 Czerwca 2007, 13:29 ]
Wszystkich sposobów na jakie można zapisać 16 w postaci sumy jest 231.
Takich, które składają się z maksymalnie 4 składników jest 64, a jeżeli ograniczymy się do takich, że składniki nie przekroczą 9 jest już tylko (?) 41.
np.
16=9+7, czyli 9, 7 (i 2 zera) możemy ustawić na \(\displaystyle{ {4\choose1}{3\choose1}}\) sposobów
16=9+5+1+1 \(\displaystyle{ {4\choose1}{3\choose1}{2\choose2}}\)
Suma tych 41 iloczynów to rozwiązanie.

Sposób niestety dobry raczej dla komputera, a nie człowieka

Kod: Zaznacz cały

    1 )  9 7                  12          12
    2 )  9 6 1                24          36
    3 )  9 5 2                24          60
    4 )  9 5 1 1              12          72
    5 )  9 4 3                24          96
    6 )  9 4 2 1              24         120
    7 )  9 3 3 1              12         132
    8 )  9 3 2 2              12         144
    9 )  8 8                   6         150
   10 )  8 7 1                24         174
   11 )  8 6 2                24         198
   12 )  8 6 1 1              12         210
   13 )  8 5 3                24         234
   14 )  8 5 2 1              24         258
   15 )  8 4 4                12         270
   16 )  8 4 3 1              24         294
   17 )  8 4 2 2              12         306
   18 )  8 3 3 2              12         318
   19 )  7 7 2                12         330
   20 )  7 7 1 1               6         336
   21 )  7 6 3                24         360
   22 )  7 6 2 1              24         384
   23 )  7 5 4                24         408
   24 )  7 5 3 1              24         432
   25 )  7 5 2 2              12         444
   26 )  7 4 4 1              12         456
   27 )  7 4 3 2              24         480
   28 )  7 3 3 3               4         484
   29 )  6 6 4                12         496
   30 )  6 6 3 1              12         508
   31 )  6 6 2 2               6         514
   32 )  6 5 5                12         526
   33 )  6 5 4 1              24         550
   34 )  6 5 3 2              24         574
   35 )  6 4 4 2              12         586
   36 )  6 4 3 3              12         598
   37 )  5 5 5 1               4         602
   38 )  5 5 4 2              12         614
   39 )  5 5 3 3               6         620
   40 )  5 4 4 3              12         632
   41 )  4 4 4 4               1         633