XXI OM - II -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Jeśli $A$ jest podzbiorem zbioru $X$ , to przyjmujemy $A^1 = A$ , $A^{-1} = X - A$ . Podzbiory $A_1, A_2, \ldots, A_k$ nazywamy wzajemnie niezależnymi, jeśli iloczyn $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k}$ jest niepusty dla każdego układu liczb $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k$ , takiego, że $|\varepsilon_2| = 1$ dla $i = 1, 2, \ldots, k$ .
Jaka jest maksymalna liczba wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego?

Rozwiązanie

Ponieważ liczba wszystkich ciągów $n$ -wyrazowych o wartościach $-1$ i $1$ równa jest $2^n$ (patrz zadanie przygotowawcze D serii III), więc możemy przyjąć, że elementami rozważanego zbioru $2^n$ -elementowego $X$ są takie ciągi.

Oznaczmy dla $i = 1, 2, \ldots, n$ przez $A_i$ zbiór wszystkich ciągów należących do $X$ , których $i$ -ty wyraz jest $1$ . Wykażemy, że podzbiory $A_1, A_2, \ldots, A_n$ są wzajemnie niezależne.

Ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , gdzie $|\varepsilon_j| = 1$ , należy do każdego ze zbiorów $A_i^{\varepsilon_i}$ dla $i = 1, 2, \ldots, n$ . Jeśli bowiem $\varepsilon_i= 1$ , to rozważany ciąg ma $i$ -ty wyraz równy $1$ , a więc należy do $A_i^{\varepsilon_i} = A_i^1$ ; jeśli zaś $\varepsilon_i = -1$ , to rozważany ciąg ma $i$ -ty wyraz równy $- 1$ , czyli należy do $X - A_i = A_i^{-1}$ . Wobec tego zbiór $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \cap \ldots \cap A_n^{\varepsilon_n}$ zawiera ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , a więc jest niepusty.

Wykażemy z kolei, że jeśli $r > n$ i $B_1, B_2, \ldots, B_r$ są pewnymi podzbiorami zbioru $X$ , to nie są one wzajemnie niezależne. Jeśli ciągi $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_r)$ i $(\varepsilon'_1, \varepsilon'_2, \ldots, \varepsilon'_r)$ o wartościach $-1$ i $1$ są różne, to zbiory

$<br /> B = B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r} \textrm{ i }<br /> B' = B_1^{\varepsilon'_1} \cap B_2^{\varepsilon'_2} \cap \ldots \cap B_r^{\varepsilon'_r}<br />$

są rozłączne. Mianowicie, jeśli np. $\varepsilon_i = 1$ , a $\varepsilon_i' = - 1$ , to mamy $B \subset B_i^{\varepsilon_i} = B_i$ oraz $B' \subset B_i^{-1} = X - B_i$ , a zbiory $B_i$ i $X - B_i$ oczywiście są rozłączne.

Zatem, gdyby zbiory $B_1, B_2, \ldots, B_r$ były wzajemnie niezależne, to wszystkie zbiory postaci $B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r}$ byłyby niepuste i parami rozłączne. Zbiorów tych jest $2^r > 2^n$ . Jest to niemożliwe, ponieważ zbiór $X$ zawiera tylko $2^n$ elementów.

Udowodniliśmy więc, że $n$ jest maksymalną liczbą wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego.