XXI OM - I -Zadanie 10

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

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}$ .