Matematyka.pl

Zdefiniujmy macierz nxn nad ciałem \(\displaystyle{ Z_2}\) następująco: w \(\displaystyle{ i}\)-tym wierszu i w \(\displaystyle{ j}\)-tej kolumnie wstawiamy jedynkę wtedy, gdy element \(\displaystyle{ i}\)-ty należy do zbioru \(\displaystyle{ S_j}\). Nazwijmy tę macierz \(\displaystyle{ A}\). Z założeń zadania wynika, że w każdym wierszu tej macierzy jest parzysta liczba jedynek. Wynika z tego, że \(\displaystyle{ A \cdot 1 = 0}\), gdzie \(\displaystyle{ 1}\) oznacza wektor z samych jedynek, a \(\displaystyle{ 0}\) wektor z samych zer. Wiadomo, że wyznacznik macierzy nad dowolnym ciałem jest niezerowy wtedy i tylko wtedy, gdy równanie \(\displaystyle{ A \cdot v = 0}\) ma tylko jedno rozwiązanie, mianowicie wektor zerowy. Mamy więc \(\displaystyle{ det(A) = 0}\). Załóżmy nie wprost, że każde dwa zbiory mają nieparzyste przecięcie. Jest to równoważne temu, że \(\displaystyle{ A \cdot A^T = \left[ \begin{array}{ccccc} 0&1&1&...&1 \\ 1&0&1&...&1 \\ 1&1&0&...&1 \\ .&.&.&.&. \\ 1&1&1&...&0 \end{array} \right]}\) Można łatwo pokazać, że gdy \(\displaystyle{ n}\) jest parzyste, to taka macierz ma niezerowy wyznacznik: oznaczając \(\displaystyle{ a_k}\) wyznacznik takiej macierzy rzędu \(\displaystyle{ k}\), i \(\displaystyle{ b_k}\) wyznacznik takiej macierzy rzędu \(\displaystyle{ k}\), tyle że w lewym górnym rogu z jedynką, stosując rozwinięcie Laplace'a (dodajemy drugi wiersz do pierwszego) mamy rekurencję
\(\displaystyle{ a_{k+1} = a_k + b_k}\), oraz \(\displaystyle{ b_{k+1} = b_k}\) (wszystko modulo 2), co w połączeniu z \(\displaystyle{ a_2 = 1}\) i \(\displaystyle{ b_2 = 1}\), daje nam \(\displaystyle{ a_k = 1}\) dla \(\displaystyle{ k}\) parzystych i \(\displaystyle{ 0}\) dla nieparzystych. Jednak wtedy \(\displaystyle{ 0 = det(A) \cdot det(A^T) = det(A \cdot A^T) = 1}\), sprzeczność. Wobec tego pewne dwa zbiory muszą mieć parzyste przecięcie, ckd.

Na marginesie, dla \(\displaystyle{ n}\) nieparzystych teza nie jest prawdziwa: wystarczy przyjąć \(\displaystyle{ S_1 = \left\{ 2,3,...,n \right\}}\) oraz \(\displaystyle{ S_i = \left\{ 1,i \right\}}\) dla \(\displaystyle{ i}\) większych od 1.