Komentarz

XXI OM - II -Zadanie 6

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz