[Kombinatoryka] Parzyste zbiory

[Swistak]

Zbiorami parzystymi nazwijmy zbiory o parzystej liczbie elementów. Niech n będzie liczbą parzystą, a \(\displaystyle{ S_1, S_2, ..., S_n}\) parzystymi podzbiorami zbioru \(\displaystyle{ \{1, 2, ..., n\}}\). Udowodnij, że istnieją takie \(\displaystyle{ i}\) oraz \(\displaystyle{ j}\), że \(\displaystyle{ S_i \cap S_j}\) ma parzystą liczbę elementów.

[ordyh]

Hmm, a co dla \(\displaystyle{ n=6}\) i zbiorów \(\displaystyle{ \{1,2\}, \{3,4\}, \{5,6\}, \{1,2,3,4\}, \{3,4,5,6\}, \{1,2,3,4,5,6\}}\)?

[Swistak]

Sorry, miało być oczywiście parzystą, a nie nieparzystą w tezie. Jak widać godzina oraz ósemka, która doszła Smulemu na riverze, przez którą mam 75zł mniej niż powinienem, robią swoje.

[jerzozwierz]

Przedstaw całe rozdanie

Jakby co, to zadanie ze zwardonia 08

[zaudi]

Wystarczy, że będzie się miało dwa zbiory parzyste które są rozłączne. Zbiór pusty jest najmniejszym zbiorem parzystym

[Dumel]

nie zrozumiałeś treści. to ma zachodzić dla dowolnych zbiorów S_i

[jerzozwierz]

Wciąż czekam na relację z rozdania.

Rozwiązanie zadania:

Ukryta treść:    

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.