Matematické Fórum

Dennina · 26. 08. 2017 22:19

Ahoj, potřebovala bych poradit s rovnicí.

Kolika způsoby lze rozložit 30 Kč pomocí 1, 2, 5 Kč?

děkuji moc

misaH · 26. 08. 2017 23:12 — Editoval misaH (26. 08. 2017 23:14)

↑ Dennina:

No - neviem, čo toto zadanie hľadá v zaujímavých...

Koľko je mincí?

Musia sa použiť vždy všetky tri druhy mincí?

Začala by som päťkorunáčkami.

Potom by som počet päťkorunáčiek zmenšila o 1 a zvyšok by som dopĺňala ostatnými mincami.

Dennina · 27. 08. 2017 10:12

↑ misaH:

počet mincí není nijak omezený.

nemusí se vždy použít všechny mince.

Ano tento způsob mě také napadl ale já bych to potřebovala spočítat nejlépe přes diofantické rce...

A mohu se zeptat kolik Vám vyšlo způsobů? Já jsem došla ke 27 možnostem a nejsem si jistá správností výsledku

check_drummer · 27. 08. 2017 10:23

↑ Dennina:
Ahoj, zjistil bych, které částky mezi 0 a 30 lze vyplatit jen pomocí 2 a 5 a zbytek doplnit 1 Kč.

misaH · 27. 08. 2017 11:15

↑ check_drummer:

:-)

Ak to robíš "po mojom", ide to rýchlo a mechanicky, lebo po päťkorunáčkach dopĺňaš dvojkorunáčky a z ich maximálneho počtu vždy o jednu dvojkorunu zmenšuješ.
Jednokoruny sa už doplnia samy.

Napr.:

3 päťkoruny = 15 Kč

Zvyšných 15 Kč dvojkorunami - maximálne 7 (8 pôsobov, lebo nasleduje dvojkorún 6,5,4,3,2,1,0).

Atď.

vanok · 27. 08. 2017 17:04 — Editoval vanok (28. 08. 2017 08:26)

Poznamka.
Uz som tu vo fore naznacil ako je mozne riesit rovnice typu $x+ 2y+5z=30$ pre cele nezaporne cisla
( ak niekto vie nast ten prispevok, moze tu dat odkaz).
Jedna mozna metoda je pouzitie vhodnych rad, vdaka tomuto vysledku:

Pocet rieseni $A_n$ , rovnice $x+ 2y+5z=n$ je urceny vdaka sucinu rad.
$\sum_{n=0}^{+\infty}A_n t^n=(\sum_{n=0}^{+\infty}t^n)(\sum_{n=0}^{+\infty}t^{2n})(\sum_{n=0}^{+\infty}t^{5n})=\frac 1 {(1-t)(1-t^2)(1-t^5)}$

V pripade $x+ 2y+5z=30$ staci uvazovat na pravej strane polynomy, ktorych stupen nepresahuje 30.
( ak niekto vypocita ten sucin tak ma riesenia $x+ 2y+5z=n$ , pre n=0, 1, ... , 30; a i ked sucin polynomov ma stupen 90, tak vsetki koeficienty clenov od stupna 31 nie su pre nas zaujimave .... tak ich ani nemusite pocitat! ). Pochopitelne mozete pouzit aj mocnivovy rozvoj posledneho vyrazu.

Honzc · 28. 08. 2017 09:52 — Editoval Honzc (28. 08. 2017 09:52)

↑ Dennina:
Podle mě je nejjednodušší řešení toto:
$x+2y+5z=30$ kde $x,y,z\in N+\{0\}$ a $z=\{0,1,2,3,4,5,6\}$
Dostaneme (pro počet řešení):
$x+2y=0\,(0\,\text{div}\,2=0+1=1)$
$x+2y=5\,(5\,\text{div}\,2=2+1=3)$
$x+2y=10\,(10\,\text{div}\,2=5+1=6)$
$x+2y=15\,(15\,\text{div}\,2=7+1=8)$
$x+2y=20\,(20\,\text{div}\,2=10+1=11)$
$x+2y=25\,(25\,\text{div}\,2=12+1=13)$
$x+2y=30\,(30\,\text{div}\,2=15+1=16)$

Celkem tedy 1+3+6+8+11+13+16=58 řešení

vanok · 28. 08. 2017 10:29

Ahoj ↑ Honzc:,
Ano je to jedno ine mozne riesenie.
A som tu uz pisal o viacerych moznych rieseniach a jedno z nich je tvoje.
Povedat, ze jedno je jednoduchsie ako ine je subjektivne.

Dobre pokracovanie.

check_drummer · 29. 08. 2017 00:00

↑ Honzc:
Podobně mi to vychází obecným rekurentním vzorcem. Označíme-li s(n) počet řešení s pravou stranou n (v našem případě je n=30), a označíme-li q(n) počet řešení, kdy je povoleno použít pouze čísla 1 a 2, tak platí s(n)=s(n-5)+q(n) (rozdělili jsme řešení na ta, která obsahují alespoň jednu 5 - ta zmenšíme o 5 - a ostatní) - a lze ukázat, že $q(n)=\lfloor n/2 \rfloor +1$ . A z toho již dosatneme obecný vzorec:
$\lfloor \frac{n}{2} \rfloor +1 + \lfloor \frac{n-5}{2} \rfloor +1 + ..$

vanok · 29. 08. 2017 03:12 — Editoval vanok (30. 08. 2017 16:59)

Ahoj ↑ check_drummer:,
A skusal si tu ↑ vanok: vyjadrit tu generacnu funkciu poctu rieseni $A_n$ .
(Co je tiez pekne pouzitie rozkladu na jednoduche zlomky).
Asi by sa ti to zdalo zrazu uzitocne, keby sme chceli vediet pocet rieseni rovnic vo vsebecnom pripade
$x+2y+5z=n$ .

Honzc · 29. 08. 2017 08:42

↑ check_drummer:
Nebylo by lepší (pro daný příklad-použití 1,2,5 Kč) přepsat to takhle:
$p=\sum_{i=0}^{\lfloor \frac{n}{5} \rfloor}(\lfloor \frac{n-5i}{2} \rfloor+1)$ kde $n$ je požadovaná částka a $p$ počet možností

vanok · 30. 08. 2017 16:56 — Editoval vanok (30. 08. 2017 17:00)

Poznamka, co sa tyka generacnej funkcie poctu rieseni $A_n$
Mozme ukazat a potom pouzit, ze
$\sum_{n=0}^{+\infty}A_n t^n=(\sum_{n=0}^{+\infty}t^n)(\sum_{n=0}^{+\infty}t^{2n})(\sum_{n=0}^{+\infty}t^{5n})=\frac 1 {(1-t)(1-t^2)(1-t^5)}=$ $\frac 15.\frac{-t^4-t^3+t^2+1}{1-t^5} +\frac{13}{40}.\frac 1{1-t}+\frac 14.\frac1{(1-t)^2}+\frac1{10}.\frac 1{(1-t)^3}+\frac 18.\frac 1{1+t}$
Ak treba mozem dat viac podrobnosti.
Ina metoda je napr. pouzitie sucinu troch radov $\frac 1 {(1-t)(1-t^2)(1-t^5)}$
Co sa tyka metody kolegu Honz je zaujimave konstatovat ze ide ide o sucet dvoch arimetmickych postupnosti ( parne a neparne i).

misaH · 30. 08. 2017 20:24 — Editoval misaH (31. 08. 2017 07:55)

↑ Dennina:

Ahoj.

Takže:

30=6*5 ...... 1 možnosť

30=5*5+2*2......... zvyšok potom jednokorunáčky
............+1*2
............+0*2.......3 možnosti

30=4*5+5*2...... 6 možností

30=3*5+7*2 ......8 možností

30=2*5+10*2 ..... 11 možností

30=1*5+12*2 ..... 13 možností

30=0*5+15*2 ......16 možností

Možnosti sú vždy počet dvojkorunáčok +1.

Spolu možností 1+3+6+8+11+13+16=58 možností

:-)

Radšej si to mala dať do ZŠ, SŠ alebo VŠ.

Samozrejme, že postupy sa líšia podľa levelu školy...

Ako si prišla na tých 27?

check_drummer · 30. 08. 2017 21:23

↑ Honzc:
Ahoj, ano, to je vlastně přesný zápis té mé sumy, která je neúplná (ale snad z ní bylo zřejmé, jaké členy obsahuje).

vanok · 02. 09. 2017 20:41

Ahoj ↑ check_drummer:,
Asi si si nevsimol poznamku, ze $p=\sum_{i=0}^{\lfloor \frac{n}{5} \rfloor}(\lfloor \frac{n-5i}{2} \rfloor+1)$ je vlastne sucet dvoch aritmetickych postupnosti (pozri parne a neparne indexy). A to moze zjednodut konecny vysledok.

Co sa tyka mojho postupu, pochopitelne mozem pridat podrobnosti.

check_drummer · 02. 09. 2017 21:59

↑ vanok:
Ahoj, nevšiml, je to tak, děkuji za upozornění. Opravdu se tím dá ta suma zjednodušit, a uvést v uzavřeném tvaru.

vanok · 11. 09. 2017 20:20 — Editoval vanok (11. 09. 2017 20:22)

Pozdravujem,
Pre zaujemcov doplnim rozvoj ktory som dostal,
$\frac 15.\frac{-t^4-t^3+t^2+1}{1-t^5} +\frac{13}{40}.\frac 1{1-t}+\frac 14.\frac1{(1-t)^2}+\frac1{10}.\frac 1{(1-t)^3}+\frac 18.\frac 1{1+t}$
Na to pouzijem generacne rady
$\frac{-t^4-t^3+t^2+1}{1-t^5}=(-t^4-t^3+t^2+1).(1+t^5+t^{10}+t^{15}+...)= 1+t^2-t^3-t^4+t^5+t^7-t^8-t^9+...$
( posledny clen znamena ze jeho koeficienty monomu $t^n$ modulo 5 su postupne $a_n= 1; 0; 1; -1; -1$ , lopatisticky povedane, to znamena ze tato pätica sa periodicky opakuje )
A tiez $\frac 1{1-t}= 1+t+t^2+t^3+...$
$\frac 1{(1+t)^2} =\sum_{n=0}^{\infty}(n+1)t^n$
$\frac 1{(1+t)^3} =\sum_{n=0}^{\infty} {n+2 \choose 2 } .t^n$
$\frac 1{t-1}=\sum_{n=0}^{\infty} (-1)^n .t^n$

Dalej oznacim $b_n$ koeficienty monomov $t^n$ rozvoja $\frac{13}{40}.\frac 1{1-t}+\frac 14.\frac1{(1-t)^2}+\frac1{10}.\frac 1{(1-t)^3}+\frac 18.\frac 1{1+t}$
Po jednoduchom vypocte dostanem
$b_n=\frac {13}{40}+\frac 14+\frac 1{10}+\frac 25 n+\frac {n^2}{20}+(-1)^n\frac 18=\frac {27}{40}+\frac 25 n+\frac {n^2}{20}+(-1)^n\frac 18$

Konecne tak pocet kladnych rieseni danej diofantickej rovnice $x+2y+5z=n$ je $\frac 15 .a_n+b_n$ .