Matematické Fórum

bojga · 09. 11. 2012 22:53

Porádí mi prosím někdo aspoň s jednou úlohou z úloh:
1)kolika způsoby lze vyplatit 100Kč pomocí mincí hodnoty 1,2,5 a 10Kč
2)Určete kolika způsoby lze vyjádřit přirozené číslo n>1 ve tvaru součinu n=xy kde x,y jsou přiroz.čísla taková, že x/y.
3)dokažte, že počet všech rozkladů přirozeného čísla n na několik sčítanců je roven počtu všech rozkladů čísla 2n na n sčítanců
Děkuji za jakoukoliv pomoc.

JohnPeca18

U te 1) me napada napsat si to ako soucin polynomu
$(\sum_{n=0}^{100}x^n)(\sum_{n=0}^{50}x^{2n})(\sum_{n=0}^{20}x^{5n})(\sum_{n=0}^{10}x^{10n})$
Rozepsat si to podle vzorce na geometrickou posloupnost a zistit koeficient u $x^{100}$
Melo by to byt neco
$(\frac{1-x^{101}}{1-x})(\frac{1-(x^2)^{51}}{1-x^2})(\frac{1-(x^5)^{21}}{1-x^5})(\frac{1-(x^{10})^{11}}{1-x^{10}})$
Ale nevim ted jestli to vede nejak rozumne k cili. Tam je potreba si nejak pohrat s generujicimi funkcemi, v podstate zjistit koeficient u x^100 generujucej funkcie.
$\frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})}$

u 3) Zalezi na poradi scitancov?
podla toho sa jedna bud o integer partitions
http://en.wikipedia.org/wiki/Partition_ … _theory%29
alebo integer compositions
http://en.wikipedia.org/wiki/Compositio … _theory%29

JohnPeca18 · 10. 11. 2012 01:20

u 2) ak som to dobre pochopil, ked x deli y, tak hladame rozklad $n=kx^2$ To by slo rozlozit n na prvocisla a zistit kolkymi sposobmi mozme vybrat sucin prvocisel so sudym exponentom.
napr ked $n=2^3*3^2*5$ tak mozme urcit $x^2=2^2*3^2, x^2=3^2, x^2=2^2, x^2=1, k=n/x^2$

bojga · 10. 11. 2012 09:29

↑ JohnPeca18:
děkuji za radu, myslím, že na pořadí nezáleží, tak to zkusím vyřešit podle druhého odkazu :-)

JohnPeca18

Jo pri tej 1) tak zavedeme si znaceni
$a_n=1$
$b_{n=2k}=1, b_{n\neq 2k}=0$
$c_{n=5k}=1, b_{n\neq 5k}=0$
$d_{n=10k}=1, b_{n\neq 10k}=0$
a teda
$(\sum_{n=0}^{\infty}x^{n}=\sum_{n=0}^{\infty}a_nx^n$
$(\sum_{n=0}^{\infty}x^{2n}=\sum_{n=0}^{\infty}b_nx^n$
$(\sum_{n=0}^{\infty}x^{5n}=\sum_{n=0}^{\infty}c_nx^n$
$(\sum_{n=0}^{\infty}x^{10n}=\sum_{n=0}^{\infty}d_nx^n$
A chceme spocist koeficient soucinu tychto rad u n=100. To nam da vsetky moznosti
ako zaplatit 100 korun pomocou 1,2,5,10 korunacok. Najprv vynasobim rady $a$ a $b$
cim si vyjadrim radu f. Potom vynasobim radu $c$ a $d$ cim vznikne rada $g$ . A nakoniec
vynasobim $f$ a $g$ .
$(\sum_{n=0}^{\infty}x^n)(\sum_{n=0}^{\infty}x^{2n})=(\sum_{n=0}^{\infty}a_nx^n)(\sum_{n=0}^{\infty}b_nx^{n})=\sum_{n=0}^{\infty}f_nx^n$
potom ze soucinu mocninych rad vime, ze koeficient u n muzeme spocist.
Tiez vyuzijeme, ze an=1 a b_n=1 jen pro sude cisla.
$f_n=\sum_{k=0}^{n}a_kb_{n-k}=\lfloor\frac{n+1}{2}\rfloor$
a nech
$(\sum_{n=0}^{\infty}x^{5n})(\sum_{n=0}^{\infty}x^{10n})=(\sum_{n=0}^{\infty}c_nx^n)(\sum_{n=0}^{\infty}d_nx^{n})=\sum_{n=0}^{\infty}g_nx^n$
potom pre n=5l
$g_{5l}=\sum_{k=0}^{5l}c_{k}d_{5l-k}=\sum_{k=0}^{l}c_{5k}d_{5l-5k}=\lfloor\frac{l+1}{2}\rfloor$
inak $g_n=0$
a nech
$(\sum_{n=0}^{\infty}f_nx^n)(\sum_{n=0}^{\infty}g_nx^{n})=\sum_{n=0}^{\infty}h_nx^n$
Tu uz chceme spocitat koeficient pri n=100, takze mozme zapisat
$h_{100}=\sum_{k=0}^{100}f_kg_{100-k}=$
$\sum_{l=0}^{20}f_{5l}g_{100-5l}=\sum_{l=0}^{20}\lfloor\frac{5l+1}{2}\rfloor\lfloor\frac{20-l+1}{2}\rfloor$ Rozdelim na pripady $l=2j$ a $l=2j+1$
$=\sum_{j=0}^{10}\lfloor\frac{5.(2j)+1}{2}\rfloor.\lfloor\frac{20-2j+1}{2}\rfloor+\sum_{j=0}^{9}\lfloor\frac{5.(2j+1)+1}{2}\rfloor.\lfloor\frac{20-(2j+1)+1}{2}\rfloor=$
$\sum_{j=0}^{10}5j(10-j)+\sum_{j=0}^{9}(5j+3)(10-j+1)$
No a to se da rozumne uz spocist po roznasobeni jsou tam aritmeticke posloupnosti a suma z $j^2$ . Kde sa da najst aj vzorec, ale da sa to aj rucne dopocist. Snad by to melo byt dobre.