Liché podmnožiny se sudými průniky

Úkol: Nechť $ A$ je množina velikosti $ n$. Nechť $ B$ je systém jejích podmnožin liché velikosti takový, že průnik libovolných dvou prvků tohoto systému má sudou velikost. Potom $ \vert B\vert\le n$. Postupujte podobně jako při důkazu Fisherovy nerovnosti10 (příklad 6.7) a pracujte nad tělesem {\bb Z}$ _2$. Dokažte, že tento odhad nelze zlepšit.


Řešení: Označme $ C$ matici, jejíž řádky jsou charakteristické vektory množin systému $ B$ (viz příklad 3.6). Pracujme nad {\bb Z}$ _2$. Podle podmínek kladených na systém $ B$ v zadání příkladu je matice $ CC^T$ jednotková matice řádu $ \vert B\vert$. Podle věty o hodnosti součinu matic musí být hodnost matice $ C$ alespoň $ \vert B\vert$ a protože počet jejích sloupců je $ n$, je její hodnost zároveň nejvýše $ n$. Odtud tedy ihned plyne $ \vert B\vert\le n$.

Uvažme systém $ B$ podmnožin $ A$ tvořený všemi jejími jednoprvkovými podmnožinami. Velikost tohoto systému je $ n$ a zřejmě splňuje podmínky, které na něj klade zadání příkladu. Tedy právě dokázaný horní odhad na velikost systému $ B$ nelze zlepšit.

$ \ast$DK$ \ast$