od borek » 1. 2. 2020 14:27
Standardně dvě otázky, problém a věta:
1) Napište a dokažte lemma o velikosti orbity a stabilizátoru.
2) Mějme množinu
![$ [n]=\{1,2,...,n\} $](http://latex.codecogs.com/gif.latex?$ [n]=\{1,2,...,n\} $)
. Kolik jejích podmnožin můžeme vybrat tak, aby každé dvě měly průnik?
Řešení:
1) Viz přednáška.
2) Rozmyslíme si, že jich můžeme vybrat
, například tak, že vybereme jeden prvek, který budou všechny obsahovat, a dáme k němu všechny podmnožiny zbylých
prvků. Proč jich nemůžeme vybrat víc? Uvědomíme si, že oněch
podmnožin je právě polovina všech. Proč právě polovina? Protože když vybereme nějakou podmnožinu, tak její doplněk již vybrat nemůžeme.
Standardně dvě otázky, problém a věta:
1) Napište a dokažte lemma o velikosti orbity a stabilizátoru.
2) Mějme množinu [latex]$ [n]=\{1,2,...,n\} $[/latex]. Kolik jejích podmnožin můžeme vybrat tak, aby každé dvě měly průnik?
Řešení:
1) Viz přednáška.
2) Rozmyslíme si, že jich můžeme vybrat [latex]$ 2^{n-1} $[/latex], například tak, že vybereme jeden prvek, který budou všechny obsahovat, a dáme k němu všechny podmnožiny zbylých [latex]$n-1$[/latex] prvků. Proč jich nemůžeme vybrat víc? Uvědomíme si, že oněch [latex]$ 2^{n-1} $[/latex] podmnožin je právě polovina všech. Proč právě polovina? Protože když vybereme nějakou podmnožinu, tak její doplněk již vybrat nemůžeme.