Pomoc k projektu do DIM

Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
Petarda
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 4. 12. 2008 16:15
Typ studia: Informatika Bc.

Pomoc k projektu do DIM

Příspěvek od Petarda »

Kombinatorika
Vypočítejte, kolik existuje šesticiferných čísel dělitelných čtyřmi, přičemž každé z nich má právě jednu lichou cifru.

Teorie grafů
Na večírku je alespoň 6 osob. Někteří se znají a někteří ne. POZOR! Zde chápeme relaci "býti známý s" jako symetrickou relaci, tedy zná-li se x s y, tak y se zná s x. Dokažte, že mezi těmito lidmi je určitě nějaká trojice lidí, kteří se všichni navzájem znají, nebo trojice lidí, kteří se všichni navzájem neznají.
Návod: Představte si kompletní graf Kn, n≥6, jehož vrcholová množina představuje jednotlivé lidi na večírku a má dva druhy hran. Jedny symbolizují, že se koncové vrcholy znají, druhé, že se koncové vrcholy neznají.

Pokud sem dá někdo reseni budu vdecny :D
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Pomoc k projektu do DIM

Příspěvek od Osiris »

Petarda píše:...
Vypadá to, že studenti MFF pracují jako vypracovávači úloh z VŠB :-) Rozvracíme konkurenci :-)

Teorie grafů:
Toto je přímý důsledek Ramseyovy teorie. Kompletní řešení je zde:http://en.wikipedia.org/wiki/Ramsey%27s_theorem (odstavec s R(3,3)).
Osiris
Jookyn
Matfyz(ák|ačka) level III
Příspěvky: 115
Registrován: 13. 9. 2008 21:42
Typ studia: Informatika Mgr.

Re: Pomoc k projektu do DIM

Příspěvek od Jookyn »

No, tu kombinatoriku bych počítal nějak takhle...


Dělitelnost 4ma určujou poslední 2 číslice. Posledních dvojčíšlí, který jsou delitelný 4ma je 25, z toho 10 jich má jednu lichou číslici a 15 obě sudý. Teď si to rozdělim na 2 části. K těm co mají jednu lichou přidam 4 sudý číslice, což je 4*5^3 (4 možné číslice na první místo (aby to nezačínalo nulou) a 5 sudých číslic na každé ze zbývajících 3 míst) a to vynásobim 10ti dvojčíslíma, který už mam. Druhá část je, když jsou obě číslice sudý, tak pak si vyberu kolik je možností, kam dát tu lichou. Buď jí dam na první místo a na zbejvající 3 místa dam sudý (5^3) nebo jí dam na jedno ze třech dalšíh míst, na první místo dam jednu ze 4 sudých a na další 2 jednu z 5ti sudých (celkem tedy 5*5^3 + 3*5*4*5^2) tzn, celkem 10*4*5^3 + 15*(5*5^3 + 3*5*4*5^2)

Zkušenější na to mají určitě lepší postup, než můj otrockej středoškolskej, ale snad by to mělo bejt dobře, prosim ještě o kontrolu.


A nevim ke komu chodíš (jestli chodíš :) ) na přednášky, ale my jsme na první přesnášce s Králem tu druhou úlohu jednoduše dokazovali, aniž bychom použili slovo graf, jestli máš zájem, ozvi se, naskenuju ti to...
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Pomoc k projektu do DIM

Příspěvek od Osiris »

Jookyn píše:...
On nechodí na MFF, ale VŠB.
Osiris
Odpovědět

Zpět na „DMI002 Diskrétní matematika“