XXI OM - I -Zadanie 10

Znaleźć największą liczbę naturalną $ k $ o następującej własności : istnieje $ k $ takich różnych podzbiorów zbioru $ n $-elementowego, że każde dwa mają niepustą część wspólną.

Rozwiązanie

Oznaczmy szukaną liczbę przez $ k(n) $. Udowodnimy, że $ k(n) =2^{n-1} $. Każdemu ciągowi $ n $-wyrazowemu o wartościach $ 0 $ lub $ 1 $ przyporządkowujemy zbiór takich wskaźników, że odpowiadające im wyrazy ciągu są równe $ 1 $. Przyporządkowanie to ustala odpowiedniość wzajemnie jednoznaczną między zbiorem wszystkich ciągów $ n $-wyrazowych o wartościach $ 0 $ lub $ 1 $, a zbiorem wszystkich podzbiorów zbioru $ n $-elementowego. Wynika stąd, że wszystkich podzbiorów zbioru $ n $-elementowego jest tyle, ile ciągów o $ n $ wyrazach, tzn. $ 2^n $ (por. zadanie przygotowawcze D, seria III).

Rozpatrzmy w $ n $-elementowym zbiorze $ X $ rodzinę jego podzbiorów zawierających ustalony element $ a $. Każde dwa podzbiory w tej rodzinie mają niepustą część wspólną, należy do niej bowiem element $ a $. Liczba podzbiorów należących do tej rodziny równa jest liczbie wszystkich podzbiorów $ (n -1) $-elementowych zbioru $ X - \{a\} $, czyli $ 2^{n-1} $. Zatem $ k(n) \geq 2^{n-1} $.

Z drugiej strony jeśli zbiór $ A $ należy do pewnej rodziny $ R $ podzbiorów zbioru $ X $, w której każde dwa podzbiory mają niepustą część wspólną, to zbiór $ X - A $ do $ R $ nie należy. Wobec tego liczba podzbiorów należących do rodziny $ R $ nie przekracza połowy liczby wszystkich podzbiorów zbioru $ X $, czyli $ k (n) \leq \frac{1}{2} \cdot 2^n = 2^{n-1} $.

Z obu udowodnionych nierówności wynika, że $ k(n) = 2^{n-1} $.

Komentarze

Dodaj nową odpowiedź