Matematické Fórum

martanko

minuly rok boli na skuske nasledujuce priklady..vie si dat s nimi niekto rady?? lebo cely nas rocnik pozera ze o co tam ide...

kolko je v useku od 1 po 400 cisel ktore nie su delitelne ani jednym z cisel 6,10,14,15,21,35

kolkymi sposobmi mozno vyjadrit sumu n v korunach s pouzitim len 2 a 5 korunovych minci? tam treba rekurentny vztah len sa k nemu neviem dopracovat

napiste vytvyrajucu funkciu pre pocet podmnozin mnoziny (1,2,....,n) takych ze 1 vzdy patri do danej mnoziny

martanko · 02. 06. 2009 11:28

dokaze s tym urobit aspon niekto nieco?

Saturday · 02. 06. 2009 11:44

- kolko je v useku od 1 po 400 cisel ktore nie su delitelne ani jednym z cisel 6,10,14,15,21,35

Zkusil bych použít princip inkluze a exkluze, ale je to v tomto pripade docela dost (mechanicke) prace.

martanko · 02. 06. 2009 11:53

↑ Saturday:
presne tak..toto sme medzicasom vyratali pomocou inkluzie a exluzie, pre istotu sme tie cisla aj vypisali.. a vyslo to

problem robi druha a tretia uloha
pri tej druhej ma napadlo riesit to ako diofanticku rovnicu 2x+5y=n, kde x = 3n-5z a y = 2z - n ... len z toho sa neda povedat kolko ma uloha rieseni, napr. ak je suma 15 tak mozme mat 2+2+2+2+2+5 ale aj 5+5+5 .. dve riesenia, vlastne postupnost rieseni je 0,1,01,1,1,1,1,1,2,1,2,1,2,2,2,2,2,2,.... dalsi napad je riesit to cez charakteristicku rovnicu ale to zatim stroskotalo.. :(

Saturday · 02. 06. 2009 12:06

martanko: musixx napsal uz reseni, nicmene obdobny priklad s temi mincemi (a na vytvorujici funkce) je v kapitolach z diskretni matematiky od Matouska a Nesetrila - tam je to pro pevne n, kdyz chces zjistit jak poskladat ty mince, abys dostal danou castku. Dela se to pomoci nasobeni polynomu a hledani koeficientu u x^(pozadovana hodnota) -- pisu to "popularne" protoze je rychlejsi si precist tu kapitolu v te knize :)

musixx · 02. 06. 2009 12:09 — Editoval musixx (02. 06. 2009 12:36)

<edit> Zapisu to i s oduvodnenim, proc by byly nektere kroky spatne. Osobne jsem to timto smerem resil a muze to ukazat cesty, kudy se nepoustet. </edit>

Pod $a_i$ znacme pocet moznosti, kterymi lze zaplatit castku i korun pomoci danych minci.
$a_1=0\nla_2=1\nla_3=0\nla_4=1\nla_5=1$ ,
to je jasne. No a ted pro i>5 to bude bud dvoukoruna + zbylych i-2 korun nejak, nebo petikoruna + zbylych i-5 korun nejak, tedy by se nabizelo $a_i=a_{i-2}+a_{i-5}$ .

Ovsem to je spatne, protoze treba sedm korun by slo zaplatit jako 5+2, ale i jako 2+5, cimz bychom dostali dve moznosti, ale ona je jen jedna (predpokladam, ze na poradi minci nezalezi).

Takze si platbu i korun predstavme tak, ze nejprve zaplatime vsema potrebnyma dvoukorunama a pak az petikorunama. Jde-li castka i-2 zaplatit, pak staci castku i platit tak, ze zacnu dvoukorunou a pak pokracuju tak, jak bych platil castku i-2 a o to, ze bych zacal petikorunou se vubec nestaram. Pokud castka i-2 zaplatit nejde, tak se pokusim primo zacit petikorunou. Zapsat to treba takto $a_i=a_{i-2}+\left(1-{\rm sgn}\ a_{i-2}\right)\cdot a_{i-5}$ je ovsem opet spatne, protoze nemam zadnou zaruku, ze v tom $a_{i-5}$ nejsou nejake dvoukoruny (i-5=10 --> mohu platit i peti dvoukorunama).

Druha cast vlastne znamena, ze platim pouze petikorunama, takze $a_i=a_{i-2}+\begin{cases}1&\ \ {\rm pro}\ 5|i\nl0&\ \ {\rm jinak}\end{cases}$ , coz mohu napsat take treba pomoci necele casti realneho cisla jako $a_i=a_{i-2}+1-{\rm sgn}\left\langle\frac i5\right\rangle$ (a pak staci explicitne zadat pouze prvni dva cleny posloupnosti).

martanko

↑ musixx:
uff..dik teda ale toto je pre mna spanielska dedina :( musim si to precitat este aspon 3x a snad to pochopim

takze ten uplne posledny vyraz je konecny vysledok?

musixx · 02. 06. 2009 12:44 — Editoval musixx (02. 06. 2009 12:45)

↑ martanko: Muze byt konecny vysledek ( $a_1=0,\ a_2=1,\ a_i=a_{i-2}+1-{\rm sgn}\left\langle\frac i5\right\rangle\ {\rm pro}\ i>2$ ). Ale zcela jiste to neni jedina moznost, jak to zapsat.

Matematické Fórum

#1 02. 06. 2009 10:21 — Editoval martanko (02. 06. 2009 10:21)

kombinatorika - skuska :(

#2 02. 06. 2009 11:28

Re: kombinatorika - skuska :(

#3 02. 06. 2009 11:44

Re: kombinatorika - skuska :(

#4 02. 06. 2009 11:53

Re: kombinatorika - skuska :(

#5 02. 06. 2009 12:06

Re: kombinatorika - skuska :(

#6 02. 06. 2009 12:09 — Editoval musixx (02. 06. 2009 12:36)

Re: kombinatorika - skuska :(

#7 02. 06. 2009 12:42 — Editoval martanko (02. 06. 2009 12:43)

Re: kombinatorika - skuska :(

#8 02. 06. 2009 12:44 — Editoval musixx (02. 06. 2009 12:45)

Re: kombinatorika - skuska :(

Zápatí