Matematické Fórum

Ahoj, je to zajímavé, že je to vedené jako problém analýzy. Výčtem všech možností to půjde, otázka je, zda existuje něco jednoduššího, asi nějaká cesta přes násobení polynomů, ale otázka je, zda to nakonec nebude podobně pracné ty polynomy pronásobit....

↑ vanok:

Co mě napadá - 1 cent je doplněk, kterým lze doplnit vše, takže ten bych neřešil a zkoumal jen ty ostatní mince - kolika způsoby lze jimi vyplatit maximálně 1$. Vše vydělit 5 a minicemi 1,2,5,10 vyplatit max 20centů... Což je totéž jako mincemi 2,5,10 max 20 centů. Dále 10 ignorujme a uvažujme jen 2,5 a s každým případem, kdy použijeme sudy počet 5centů získáme i případy pro 10centů.

Pozdravujem ↑ laszky:,
Ano to je jedno mozne riesenie. 
Najdeme ze mame 292 rieseni.

Poznamka.
Problem n° 2 z citovanej knihy je zovseobecnenie problemu n°1; a riesenie navrznute autormy je analogicke tvojmu rieseniu.

↑ Eratosthenes:
Ono to půjde nějak sofistikovaněji i bez počítače, jak píšu výše, jenom mi to zatím vyšlo 242 a ne 292, podívám se kde mám chybu....

↑ check_drummer:

Tak už jsem chybu našel. Hledáme tedy počet vyplacení nejvýše 20 (kdy jsme vše vydělili 5) pomocí 2,5. Rozdělíme to na případy, kdy v každém případu budeme uvežovat pevný počet hodnot 5, např. 2x5: Potom do 20 máme nejvýše 5 hodnot 2, tedy buď (+) 0,1,...., nebo 5, tedy 6 možností. u každé možnosti ovšem musíme zbylé peníze do 100 centů vyplatit kombinací 5centů a 1centů (řástky před vydělením 5), tedy např. použíjeme-li 3x2, tak do 20 centů zbydou 4 - a buď 0,1,2... nebo až 4 lze vyplatit pomocí pěticentů a zbytek pomocí centů - to je celkem 5 možností, a pro všechny možnosti viz (+) máme clkem možnosti pro 1 a 5 centy: 1,3,5,..,11, dohromydy tedy 36 možností, ovšem 2x5 můžeme vyplatit i jako 1x10 - a tedy je to ne 36, ale 2x tolik, tj. 72 možností.
A to když se udělá pro každou pevnou hodnotu počtu 5, tak získáme postupně počty výplat 121,72,72,24,3, tedy celkem 292.

Na vysvětlení je to složitější, ale jinak na tom nic není. A asi ten výčet půjde provést i snadněji.

↑ check_drummer:



Toto je celkem jednoduché, ale to omezení na nezáporné hodnoty asi nebude o moc jednodušší než nějaký mechanický výčet, do kterého se mi tedy nechce :-(

Pozdravujem
Ina  mozna metoda.

Tu   V prispevku #12 https://les-mathematiques.net/vanilla/d … as-general
je na inom priklade pouzita vhodna metoda “echolonement des colones “ co je nic ine ako Gauss-ova eliminacna metoda na stlpcoch  matice… https://en.wikipedia.org/wiki/Gaussian_elimination.

Lakho to nas moze inspirovat aj na nas problem.

check_drummer napsal(a):

Trochu jednodušší postup jak získat výčet všech možností: Zkoumejme, kolika způsoby lze vyplatit maximálně 20 centů pomocí 1,2,5,10. Zvolme pevně jen centy 5,10 (může jich být i víc) - a ty doplníme několika centy 1,2. Bude stačit zjistit, kolika způsoby lze vyplatit pomocí 1,2 nejvýše n centů - tento počet označne a(n). Ještě označme p(n) počet způsobů, kterými lze vyplatit pomocí 1,2 právě n centů. Snadno lze ukázat, že platí:
p(2n)=p(2n-1)+1
p(2n-1)=p(2n-2)
a(n)=p(n)+a(n-1)
p(1)=1, a(1)=2.
Snadno získáme, že p(n) je posloupnost 1,2,2,3,3,4,4,5,5,..
A tedy a(n) je posloupnost 2,4,6,9,12,16,20,25,30,36,42,49,50,64,72,81,90,100,110,121,..
(Lze ukázat, že každý čtverec je v této poslounosti obsažen, ale to nebudeme potřebovat.)
Důležité pro nás je:
a(20)=121
a(15)=72
a(10)=36
a(5)=12
(Jak si lze všimnout jsou to ta čísla co mám v řešení výše.)

A teď už tedy zkoumejme kolika zolsoby lze v nejvýše 20centech mít přítomné 5 nebo 10 centů:

součet 20: 10,10 nebo 10,5,5 nebo 5,5,5 - celkem 3 možnosti
součet 15: 10,5 nebo 5,5,5 - celkem 2 možnosti a každou doplnit a(5) způsoby centy 1 nebo 2 - tedy celkem 2.12=24 možností
součet 10: 10 nebo 5,5 - celkem 2 možnosti - a každou doplnit a(10) způsoby centy 1 nebo 2 - tedy celkem 2.36 možností
součet 5: 5 - doplnit a(15) způsoby centy 1 nebo 2 - tedy celkem 72 možností
součet 0: doplnit a(20) způsoby centy 1 nebo 2 - tedy celkem 121 možností

Dohromady 292 možností.

Moc hezké, ale musel sis pěkně máknout :-) Moje celočíselné řešení je celkem jednoduché, ale jak z toho nějak rozumně dostat jenom nezáporná, to fakt nevím :-)

↑ vanok:

No, ještě tak umět francouzky :-)

Pozdravujem,
Co sa tyka navrhnu riesena problemu 2 v citovanej knihe, tak na urcenie [mathjax]A_n[/mathjax] poctu prirodzeneych rieseni  diofantickej rovnice [mathjax]a_1x_1+…+a_ kx_k=n[/mathjax], je navrhnute pouzit postupne vhodne koeficienty rozvojov:
[mathjax](1- x)^{-1}[/mathjax]
[mathjax](1- x)^{-1}(1-x^5)^{-1}[/mathjax]
….
[mathjax](1- x)^{-1}(1-x^5)^{-1}…(1-x^{50})^{-1}[/mathjax]

A tak, ze pre  kazdy sucin postupne sa pouziju  oblznikove takulky.

Pozdravujem,

Poznate Stirlimgove cisla druheho druhu?

Nasledujuce otazky co tu pridam budu inspirovane problemamy na tuto temu zo 100 rocnej knihy cf #1.

Pozdravujem,
Napriklad tu https://cs.wikipedia.org/wiki/Stirlingo … D%C3%ADsla   najdete odpoved na otazku z #22.