priklad SRR help

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
ondr4
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 31. 5. 2009 11:17
Typ studia: Informatika Bc.

priklad SRR help

Příspěvek od ondr4 »

Vite nekdo jak dokazat existenci SRR v teto uloze?

Bud I = {1, ... , n} indexova mnozina a Mi vlastna podmnozina X, (i patri do I), navzajem ruzne mnoziny velikosti n-2. Dokazte, ze mnozinovy system (X, Mi, i patri do I) ma system ruznych reprezentantu.

Priklad byl uz ve starsich tematech, ale nikde k nemu neni reseni. Muj jediny napad je dokazovat postupne pro I={1,..,n-2}, I={1,..,n-1} a nakonec pro I={1,...,n} a pouzit argument, ze mnoziny Mi jsou navzajem ruzne (kazde dve se lisi alespon v jednom prvku). Ale pripada mi to pritazene za vlasy.
Muzete mi s tim nekdo pomoci?
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: priklad SRR help

Příspěvek od beny »

Jak napsal Fin 3.6.2008:
"5) se dalo dokazat pres Hallovu podminku, pro J velikosti do n-2 jasne plati, n-1 taky protoze ty mnoziny jsou ruzne(tj kazde dve se lisi alespon v jednom prvku) a pro n plati protoze sjednoceni n mnozin velikosti n-2 nemuze byt n-1, pocet podmnozin velikosti n-2 z n-1 prvku je (n-1)nad(n-2) coz je n-1 (aspon myslim ze to tak bylo, kazdopadne nejaky podobny argument)."

Nevim, jestli ti to pomuze, mozna jsi na to uz taky narazil :-)
ondr4
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 31. 5. 2009 11:17
Typ studia: Informatika Bc.

Re: priklad SRR help

Příspěvek od ondr4 »

Ano, na to jsem uz narazil :-). Rozumim rozdeleni na pripady a i argumentu u n-1, ale nechapu, jak pocet podmnozin n-1 velikosti n-2 dokazuje platnost pro n...?
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: priklad SRR help

Příspěvek od Osiris »

ondr4 píše:Ano, na to jsem uz narazil :-). Rozumim rozdeleni na pripady a i argumentu u n-1, ale nechapu, jak pocet podmnozin n-1 velikosti n-2 dokazuje platnost pro n...?
Jednoduše, počet různých podmnožin množiny s n-1 prvky velikosti n-2 je n-1. My ale máme n různých množin velikosti n-2. To znamená, že ta poslední to dorovná na n.
Osiris
ondr4
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 31. 5. 2009 11:17
Typ studia: Informatika Bc.

Re: priklad SRR help

Příspěvek od ondr4 »

Aha, už mi to je jasne. Moc děkuju!
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“