Kombinatorika a grafy II - Jelínek 16.1.2020
Napsal: 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 . 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.
1) Napište a dokažte lemma o velikosti orbity a stabilizátoru.
2) Mějme množinu . 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.