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?
priklad SRR help
-
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 31. 1. 2008 12:51
- Typ studia: Informatika Bc.
- Login do SIS: benat7am
Re: priklad SRR help
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
"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
-
- 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
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...?
-
- 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
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.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...?
Osiris
-
- 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
Aha, už mi to je jasne. Moc děkuju!