Sudé podmnožiny s lichými průniky

Úkol: Nechť $ A$ je množina velikosti $ n$. Nechť $ B$ je systém jejích podmnožin sudé velikosti takový, že průnik libovolných dvou prvků tohoto systému má lichou velikost. Potom $ \vert B\vert\le n$ pro $ n$ liché a $ \vert B\vert\le n-1$ pro $ n$ sudé. Postupujte podobně jako v příkladu 3.9, pro $ n$ sudé se zamyslete též nad regularitou matic vystupujících ve vyšetřovaném součinu. Dokažte, že tento odhad již nelze zlepšit.


Řešení: Nechť $ C$ je matice, jejíž řádky jsou charakteristické vektory množin systému $ B$ (viz příklad 3.6), pracujme nad {\bb Z}$ _2$. Potom $ CC^T$ je matice $ \mathbbm{1}+J$, kde $ \mathbbm{1}$ je jednotková matice řádu $ \vert B\vert$ a $ J$ je matice téhož řádu tvořená samými jedničkami. Dále rozlišme dva případy, podle parity $ n$.

Nechť $ n$ je liché a předpokládejme existenci systému $ B$$ n+1$ prvky (množinami). Ukážeme, že matice (sudého řádu $ n+1$) $ \mathbbm{1}+J$ je regulární. Nechť tedy existuje nenulový vektor $ \vec{w}$ takový, že $ (\mathbbm{1}+J)\vec{w}=0$, tedy $ J\vec{w}=-\mathbbm{1}
\vec{w}=\mathbbm{1}\vec{w}=\vec{w}$. Protože všechny řádky matice $ J$ jsou stejné, musí být všechny složky vektoru $ J\vec{w}$ stejné a protože $ \vec{w}$ je nenulový vektor, musí nutně platit $ \vec{w}=(1,\ldots,1)^T$, a tedy i $ (\mathbbm{1}+J)\vec{w}=\mathbbm{1}
\vec{w}+(0,\ldots,0)^T=\vec{w}$ -- což je spor. Matice $ \mathbbm{1}+J$ je tedy regulární. Potom ale hodnost matice $ C$ musí být, podle věty o hodnosti součinu matic, alespoň $ n+1$, což není možné, neboť matice $ C$ má pouze $ n$ sloupců. Tedy nemůže existovat $ (n+1)$-prvkový (a tím spíše víceprvkový) systém $ B$ s uvedenými vlastnostmi. Uvedený odhad nelze zlepšit, což dosvědčuje systém $ B$ tvořený všemi $ (n-1)$-prvkovými podmnožinami množiny $ A$.

Nechť je naopak $ n$ sudé a předpokládejme existenci systému $ B$$ n$ prvky (množinami). Matice (sudého řádu $ n$) $ \mathbbm{1}+J$ je regulární. Tedy hodnost matice $ C$ musí být, podle věty o hodnosti součinu matic, alespoň $ n$. To by ale znamenalo, že matice $ C$ je regulární (má $ n$ sloupců, $ n$ řádků a plnou hodnost). Součet všech sloupců matice $ C$ je však nulový vektor (v každém řádku je sudý počet jedniček), a tedy matice $ C$ je singulární -- což je spor. Tedy nemůže existovat $ n$-prvkový (a tím spíše víceprvkový) systém $ B$ s uvedenými vlastnosti.

Uvedený odhad nelze zlepšit. Zvolme si libovolnou $ (n-1)$-prvkovou podmnožinu množiny $ A$ a do systému $ B$ zařaďme všechny její $ (n-2)$-prvkové podmnožiny. Systém $ B$ splňuje podmínky zadání příkladu a obsahuje $ n-1$ podmnožin.

$ \ast$DK$ \ast$