Wszystkie możliwości rozmiany

[CupraR225]

Siemka, ile jest możliwości rozmiany banknotu 100zł na nominały 100zł, 50zł, 20zł, 10zł, 5zł, 2zł, 1zł
Tak aby suma tych nominałów wynosiła no wiadomo - 100zł
Czyli pierwszą możliwością będzie
1x 100zł
w trakcie np.
1x 50zł 2x 20zł 1x 5zł 2x 2zł 1x1zł
a ostatnią
100x 1zł

[Janusz Tracz]

Rozważmy funkcję:

\(\displaystyle{ \mathcal{G}(x)=\left( 1+x+x^2+...\right) \cdot \left( 1+x^2+x^4+...\right) \cdot \left( 1+x^5+x^{10}+...\right) \cdot \\ \left( 1+x^{10}+x^{20}+...\right) \cdot \left( 1+x^{20}+x^{40}+...\right) \cdot \left( 1+x^{50}+x^{100}+...\right) \cdot \left( 1+x^{100}+x^{200}+...\right) }\)

zauważmy, że funkcje tą można zapisać jako nieskończony wielomian gdzie wystąpią \(\displaystyle{ x^{a+2b+5c+10d+20e+50f+100g}}\) oraz pewne współczynniki stojące przed iksami. Nas interesują sytuację gdy \(\displaystyle{ a+2b+5c+10d+20e+50f+100g=100}\) odpowiadające, że w rozmienieniu \(\displaystyle{ 100}\) wzięło udział \(\displaystyle{ a}\) jednozłotówek, \(\displaystyle{ b}\) dwuzłotówek itd. Zatem interesujący wynik znajduje się przed \(\displaystyle{ x^{100}}\). Funkcję \(\displaystyle{ \mathcal{G}}\) można rozwinąć w szereg i odczytać co znajduje się przed \(\displaystyle{ x^{100}}\).

\(\displaystyle{ \mathcal{G}(x)=1+x+2 {{x}^{2}}+2 {{x}^{3}}+3 {{x}^{4}}+4 {{x}^{5}}+5 {{x}^{6}}+6 {{x}^{7}}+7 {{x}^{8}}+8 {{x}^{9}}+\\11 {{x}^{10}}+12 {{x}^{11}}+15 {{x}^{12}}+16 {{x}^{13}}+19 {{x}^{14}}+22 {{x}^{15}}+25 {{x}^{16}}+28 {{x}^{17}}+31 {{x}^{18}}+34 {{x}^{19}}+41 {{x}^{20}}+44 {{x}^{21}}+\\51 {{x}^{22}}+54 {{x}^{23}}+61 {{x}^{24}}+68 {{x}^{25}}+75 {{x}^{26}}+82 {{x}^{27}}+89 {{x}^{28}}+96 {{x}^{29}}+109 {{x}^{30}}+\\116 {{x}^{31}}+129 {{x}^{32}}+136 {{x}^{33}}+149 {{x}^{34}}+162 {{x}^{35}}+175 {{x}^{36}}+188 {{x}^{37}}+201 {{x}^{38}}+214 {{x}^{39}}+236 {{x}^{40}}+\\ 249 {{x}^{41}}+271 {{x}^{42}}+284 {{x}^{43}}+306 {{x}^{44}}+328 {{x}^{45}}+350 {{x}^{46}}+372 {{x}^{47}}+394 {{x}^{48}}+416 {{x}^{49}}+451 {{x}^{50}}+\\ 473 {{x}^{51}}+508 {{x}^{52}}+530 {{x}^{53}}+565 {{x}^{54}}+600 {{x}^{55}}+635 {{x}^{56}}+670 {{x}^{57}}+705 {{x}^{58}}+740 {{x}^{59}}+793 {{x}^{60}}+\\ 828 {{x}^{61}}+881 {{x}^{62}}+916 {{x}^{63}}+969 {{x}^{64}}+1022 {{x}^{65}}+1075 {{x}^{66}}+1128 {{x}^{67}}+1181 {{x}^{68}}+1234 {{x}^{69}}+\\ 1311 {{x}^{70}}+1364 {{x}^{71}}+1441 {{x}^{72}}+1494 {{x}^{73}}+1571 {{x}^{74}}+1648 {{x}^{75}}+1725 {{x}^{76}}+1802 {{x}^{77}}+1879 {{x}^{78}}+\\ 1956 {{x}^{79}}+2064 {{x}^{80}}+2141 {{x}^{81}}+2249 {{x}^{82}}+2326 {{x}^{83}}+2434 {{x}^{84}}+2542 {{x}^{85}}+2650 {{x}^{86}}+2758 {{x}^{87}}+\\ 2866 {{x}^{88}}+2974 {{x}^{89}}+3121 {{x}^{90}}+3229 {{x}^{91}}+3376 {{x}^{92}}+3484 {{x}^{93}}+3631 {{x}^{94}}+3778 {{x}^{95}}+3925 {{x}^{96}}+\\ 4072 {{x}^{97}}+4219 {{x}^{98}}+4366 {{x}^{99}}+\red{4563} {{x}^{100}}+...}\)

[Niepokonana]

Panie Tracz, mam pytanie - nie ma jakiegoś prostszego sposobu? Tak tylko pytam.

[a4karo]

Jest. Można policzyć setną pochodną funkcji \(\displaystyle{ \frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})}}\) w punkcie `0` i podzielić wynik przez `100!`

[Janusz Tracz]

Panie Tracz, mam pytanie - nie ma jakiegoś prostszego sposobu? Tak tylko pytam.

Dobre pytanie, choć prostota rozwiązania jest względna. Osobiście nie znam jakiegoś sposobu który w znaczący sposób by uprościł to rozwiązanie. Z perspektywy czasu i humorystycznej odpowiedzi a4karo zmienił bym wstępnie przyjętą funkcję \(\displaystyle{ \mathcal{G}}\), zaproponuję uproszczenie funkcji \(\displaystyle{ \mathcal{G}}\) do postaci:

\(\displaystyle{ \mathcal{G}(x)=\left( \sum_{k=0}^{100} x^{k}\right) \cdot \left( \sum_{k=0}^{50} x^{2k}\right)\cdot \left( \sum_{k=0}^{20} x^{5k}\right) \cdot \left( \sum_{k=0}^{10} x^{10k}\right)\cdot \left( \sum_{k=0}^{5} x^{20k}\right)\cdot \left( \sum_{k=0}^{2} x^{50k}\right)\cdot \left( \sum_{k=0}^{1} x^{100k}\right) }\)

tym samym mamy zwykły wielomian zatem rozwijanie w szereg czy liczenie pochodnych nie jest już konieczne do wyznaczenia współczynnika przy \(\displaystyle{ x^{100}}\). To jedno uproszczenie. Inną istotną rzeczą (którą być może potraktowałem lakonicznie) w rozwiązaniu jest sprowadzenie problemu opisanego w treści do czysto algebraicznej czynności jaką jest wyznaczenie liczby rozwiązań równania:

\(\displaystyle{ a+2b+5c+10d+20e+50f+100g=100}\)

gdy \(\displaystyle{ a,b,c,d,e,f,g\in\NN_{0}}\). Takimi zadaniami zajmuje się kombinatoryka, a w szczególności dział kombinacje z ograniczeniami. Choć zwykle z tego co widziałem sprowadzają się one do rozpatrywania takiej czy innej funkcji tworzącej \(\displaystyle{ \mathcal{G}}\). Jeszcze innym pomysłem na uproszczenie jest zapisanie ciągu rekurencyjnego, a dokładniej to układu rekurencji które śledziłyby liczbę rozmienień \(\displaystyle{ n}\) złotych na \(\displaystyle{ 1,2,5,...,100}\) złotych. Układ taki byłby raczej dość zagmatwany, a jego rozwiązanie znów prowadzi do funkcji tworzących czy metod im podobnych no chyba, że mamy komputer który szybko policzy wyraz numer \(\displaystyle{ 100}\). Ale tak jak mówiłem nie znam istotnie prostszego rozwiązania, to co zaproponowałem tu jest raczej kosmetyką, a nie faktycznym ulepszeniem.

[Niepokonana]

Jak gdyby nie patrzeć, to rozwiązanie a4karo jest na poziomie liceum, więc jest prostsze. XD
Chodzi mi o to, że problem w zadaniu jest dość prosty, więc spodziewałam się kombinatoryki na poziomie liceum, także Pańskie rozwiązanie mnie zaskoczyło.

[a4karo]

Jak gdyby nie patrzeć, to rozwiązanie a4karo jest na poziomie liceum, więc jest prostsze. XD

To tak dla ćwiczenia policz może trzecią pochodną tej funkcji. A potem pomyśl ile czasu zajmie policzenie setnej

[Niepokonana]

No może jednak nie jest na poziomie liceum, bo nie wiem, co to jest trzecia pochodna funkcji ani setna. W sensie pochodna, potem pochodna z tej pochodnej, pochodna z pochodnej pochodnej itd.?

[a4karo]

Tak

[Niepokonana]

Ok, ostatnie pytanie. Dlaczego tego problemu nie da się rozwiązać kombinatoryką na poziomie liceum?

[a4karo]

Pewnie się da, ale obliczenia z pewnością nie będą krótkie i bezbolesne. Rozwiązanie z wielomianami jest chyba najprostsze.

[Elayne]

Zobaczmy, jak to może być na piechotę. Przyjmijmy ogólne założenie, że stan początkowy to nominały jednozłotówkowe. Na początku mamy 100 sztuk po 1 zł. W jednym kroku zamieniamy dwie złotówki na jedną dwuzłotówkę. Takich kroków możemy zrobić 50. Następnie powracamy do stanu początkowego i zamieniamy pięć złotówek na pięciozłotówkę i powtarzamy od początku kroki. Zapis 0-50 oznacza, że stan zmienia się od 0 do 50. Co możemy zapisać np. w ten sposób:
0 x 5 zł, 0 x 2 zł, 100 x 1 zł - stan początkowy;
0 x 5 zł, 0-50 x 2 zł, 100-0 x 1 zł - 51 kombinacji;
1 x 5 zł, 0-47 x 2 zł, 95-1 x 1 zł - 48 kombinacji;
2 x 5 zł, 0-45 x 2 zł, 90-0 x 1 zł - 46 kombinacji;
3 x 5 zł, 0-42 x 2 zł, 85-1 x 1 zł - 43 kombinacji;
4 x 5 zł, 0-40 x 2 zł, 80-0 x 1 zł - 41 kombinacji;
5 x 5 zł, 0-37 x 2 zł, 75-1 x 1 zł - 38 kombinacji;
6 x 5 zł, 0-35 x 2 zł, 70-0 x 1 zł - 36 kombinacji;
7 x 5 zł, 0-32 x 2 zł, 65-1 x 1 zł - 33 kombinacji;
8 x 5 zł, 0-30 x 2 zł, 60-0 x 1 zł - 31 kombinacji;
9 x 5 zł, 0-27 x 2 zł, 55-1 x 1 zł - 28 kombinacji;
10 x 5 zł, 0-25 x 2 zł, 50-0 x 1 zł - 26 kombinacji;
11 x 5 zł, 0-22 x 2 zł, 45-1 x 1 zł - 23 kombinacji;
12 x 5 zł, 0-20 x 2 zł, 40-0 x 1 zł - 21 kombinacji;
13 x 5 zł, 0-17 x 2 zł, 35-1 x 1 zł - 18 kombinacji;
14 x 5 zł, 0-15 x 2 zł, 30-0 x 1 zł - 16 kombinacji;
15 x 5 zł, 0-12 x 2 zł, 25-1 x 1 zł - 13 kombinacji;
16 x 5 zł, 0-10 x 2 zł, 20-0 x 1 zł - 11 kombinacji;
17 x 5 zł, 0-7 x 2 zł, 15-1 x 1 zł - 8 kombinacji;
18 x 5 zł, 0-5 x 2 zł, 10-0 x 1 zł - 6 kombinacji;
19 x 5 zł, 0-2 x 2 zł, 5-1 x 1 zł - 3 kombinacje;
20 x 5 zł, 0-0 x 2 zł, 0-0 x 1 zł - 1 kombinacja.
Co razem daje:
\(\displaystyle{ 51+48+46+43+41+38+36+33+31+28+26+23+21+18+16+13+11+8+6+3+1=541}\) kombinacji.
Innymi słowy, 100 zł możemy rozmienić za pomocą nominałów 5 zł, 2 zł i 1 zł na 541 sposobów. Ok, dodajmy do tego kolejny nominał - 10 zł. Wracamy do stanu początkowego i zamieniamy dziesięć złotówek na nominał 10 zł. Pozostałe 90 zł możemy rozmienić za pomocą nominałów 5 zł, 2 zł i 1 zł na \(\displaystyle{ 541-(51+48)=442}\) sposoby. Zapiszmy to w słupku.
1 x 10 zł + 90 zł w nominałach po 5 zł, 2 zł i 1 zł - 442 kombinacji;
2 x 10 zł + 80 zł w nominałach po 5 zł, 2 zł i 1 zł - 353 kombinacji;
3 x 10 zł + 70 zł w nominałach po 5 zł, 2 zł i 1 zł - 274 kombinacji;
4 x 10 zł + 60 zł w nominałach po 5 zł, 2 zł i 1 zł - 205 kombinacji;
5 x 10 zł + 50 zł w nominałach po 5 zł, 2 zł i 1 zł - 146 kombinacji;
6 x 10 zł + 40 zł w nominałach po 5 zł, 2 zł i 1 zł - 97 kombinacji;
7 x 10 zł + 30 zł w nominałach po 5 zł, 2 zł i 1 zł - 58 kombinacji;
8 x 10 zł + 20 zł w nominałach po 5 zł, 2 zł i 1 zł - 29 kombinacji;
9 x 10 zł + 10 zł w nominałach po 5 zł, 2 zł i 1 zł - 10 kombinacji;
10 x 10 zł - 1 kombinacja.
Razem: \(\displaystyle{ 442+353+274+205+146+97+58+29+10+1=1615}\) kombinacji
I tak dalej.

[janusz47]

Stawiamy pytanie, na ile sposobów możemy przedstawić liczbę 100 w postaci kombinacji liniowej?

\(\displaystyle{ k\cdot 1 + l\cdot 2 + m\cdot 5 + n\cdot 10 + o\cdot 20 + p\cdot 50 + q\cdot 100 =100 \ \ (1)}\)

gdzie \(\displaystyle{ k, l, m, n, o, p, q \in \NN ? }\)

W tym celu rozważmy szereg potęgowy

\(\displaystyle{ S(x) = \sum_{k,l,m,n,o,p,q\in \NN}x^{k\cdot 1+ l\cdot 2 + m\cdot 5 + n\cdot 10 + p\cdot 50 + q\cdot 100}= a_{100}\cdot x^{100}}\),

gdzie współczynnik \(\displaystyle{ a_{100} }\) jest liczbą wszystkich siódemek \(\displaystyle{ (k, l, m, n, o, p, q). }\)

spełniających równanie \(\displaystyle{ (1) }\)

Szereg ten możemy przedstawić w postaci iloczynu Cauchyego szeregów:

\(\displaystyle{ S(x) = \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{k\cdot 1}\right)\cdot \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{l\cdot 2}\right) \cdot
\left (\sum_{k,l,m,n,o,p,q\in \NN}x^{m\cdot 5}\right) \cdot \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{n\cdot 10}\right)\cdot \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{o\cdot 20}\right)\cdot }\)
\(\displaystyle{ \cdot \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{p\cdot 50}\right)\cdot \left (\sum_{k,l,m,n,o,p,q\in \NN}x^{q\cdot 100}\right).}\)

Czynniki w powyższym iloczynie to szeregi geometryczne zbieżne jednostajnie w kole \(\displaystyle{ |x|< 1.}\)

Szereg \(\displaystyle{ S(x) }\) jako iloczyn szeregów jest też zbieżny jednostajnie w kole \(\displaystyle{ |x|< 1 }\) i jego suma

\(\displaystyle{ S(x)= \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^{10}}\cdot \frac{1}{1-x^{20}} \cdot \frac{1}{1 -x^{50}}\cdot \frac{1}{1-x^{100}} = }\)

\(\displaystyle{ =\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1 -x^{20})(1 - x^{50})( 1-x^{100})} \ \ (2) }\)

Poszukiwana liczba sposobów rozmienienia banktota \(\displaystyle{ 100}\) zł to współczynnik \(\displaystyle{ a_{100} }\) przy wyrazie \(\displaystyle{ x^{100} }\) w rozwinięciu funkcji \(\displaystyle{ (2).}\)

Do znalezienia wartości tego współczynnika skorzystamy z programu Mathematica 9.0.

Kod: Zaznacz cały

f[x_] := 1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - 
      x^50) (1 - x^100))
s = Series[f[x], {x, 0, 100}]
SeriesCoefficient[s, 100]

 1+x+2 x2+2 x3+3 x4+4 x5+5 x6+6 x7+7 x8+8 x9+11 x10+12 x11+15 x12+16 x13+19 x14+22 x15+25 x16+28 x17+31 x18+34 x19+41 x20+44 x21+51 x22+54 x23+61 x24+68 x25+75 x26+82 x27+89 x28+96 x29+109 x30+116 x31+129 x32+136 x33+149 x34+162 x35+175 x36+188 x37+201 x38+214 x39+236 x40+249 x41+271 x42+284 x43+306 x44+328 x45+350 x46+372 x47+394 x48+416 x49+451 x50+473 x51+508 x52+530 x53+565 x54+600 x55+635 x56+670 x57+705 x58+740 x59+793 x60+828 x61+881 x62+916 x63+969 x64+1022 x65+1075 x66+1128 x67+1181 x68+1234 x69+1311 x70+1364 x71+1441 x72+1494 x73+1571 x74+1648 x75+1725 x76+1802 x77+1879 x78+1956 x79+2064 x80+2141 x81+2249 x82+2326 x83+2434 x84+2542 x85+2650 x86+2758 x87+2866 x88+2974 x89+3121 x90+3229 x91+3376 x92+3484 x93+3631 x94+3778 x95+3925 x96+4072 x97+4219 x98+4366 x99+4563 x100+O[x]101
 
 4563 
 

Literatura
Sławomir Kolasiński, Michał Jóźwiakowski. Dodatek do skryptu Analiza Matematyczna 1 prof. Pawła Strzeleckiego MiMUW
28 Października 2011.

[a4karo]

Przecież to już wszystko było opisane

[janusz47]

Nieopisane dokładnie tylko fragmentarycznie na podstawie podanej literatury.