LX OM - I - Zadanie 5

Dla każdej liczby całkowitej $ n \geqslant 1 $ wyznaczyć największą
możliwą liczbę różnych podzbiorów zbioru $ \{1,2,3, \cdots,n\} $ o
następującej własności: Dowolne dwa z tych podzbiorów są rozłączne
lub jeden z nich zawiera się w drugim.

Rozwiązanie

Odpowiedź: $ 2n $ podzbiorów.

Oznaczmy szukaną liczbę podzbiorów przez $ a_n $.

Nietrudno spostrzec, że dla $ n =1,2,3,\cdots $ następujące $ 2n $
podzbiorów zbioru $ \{1,2,3, \cdots,n\} $ ma daną w treści zadania własność:

\[<br /> \emptyset, \{1\}, \{2\}, \{3\}, \cdots, \{n\},<br /> \{1,2\}, \{1,2,3\}, \cdots, \{1,2,3, \cdots,n\}.<br /> \]

Rzeczywiście, dowolny z pierwszych $ n+1 $ zbiorów ma najwyżej jeden
element, zatem zawiera się w każdym zbiorze, z którym nie jest
rozłączny. Natomiast dla dowolnych dwóch spośród pozostałych
$ n - 1 $ zbiorów ten zbiór, który w powyższym ciągu jest wypisany
wcześniej, zawiera się w drugim zbiorze.

Udowodniliśmy w ten sposób, że

\[<br /> (1) a_n \geqslant 2n \text{ dla } n=1,2,3,\cdots.<br /> \]

Z drugiej strony, niech $ B_1, B_2, \cdots, B_t $ będą różnymi
podzbiorami zbioru $ \{1, 2, \cdots,m\} $ o własności opisanej w treści
zadania. Jeżeli wśród wypisanych podzbiorów nie występuje zbiór
$ \{1,2, \cdots,m\} $, to możemy go dopisać zwiększając o $ 1 $ liczbę tych
podzbiorów i nie naruszając prawdziwości postulowanego warunku.
Przyjmijmy więc, że $ B_t = \{1,2, \cdots,m\} $.

Spośród zbiorów $ B_1, B_2, \cdots, B_{t-1} $ wybierzmy ten, który
ma najwięcej elementów. Dla ustalenia uwagi niech będzie to $ B_1 $
i niech $ d $ oznacza liczbę jego elementów. Wówczas $ d<n $.
Ponadto równość $ d = 0 $ oznacza, że $ B_1 $ jest zbiorem pustym, co
z uwagi na wybór zbioru $ B_1 $ jest możliwe jedynie wtedy, gdy
$ t = 2 $. W dalszej części rozumowania przyjmujemy więc, że $ 0<d<n $.

Na mocy określenia zbioru $ B_1 $ każdy ze zbiorów
$ B_i $ ($ i=1,2,\cdots,t - 1) $ albo jest podzbiorem zbioru $ B_1 $,
albo też jest z nim rozłączny. Dokonując przenumerowania możemy
założyć, iż zbiory $ B_1, B_2, \cdots, B_r $ są podzbiorami zbioru
$ B_1 $, natomiast zbiory $ B_{r+1}, B_{r+2}, \cdots, B_{t-1} $ są
rozłączne z $ B_1 $.

Zbiory $ B_1, B_2, \cdots, B_r $ są różnymi podzbiorami
$ d $-elementowego zbioru $ B_1 $, z których dowolne dwa albo są
rozłączne, albo jeden zawiera się w drugim. Wynika stąd nierówność
$ r\leqslant a_d $. Wśród $ t-r-1 $ zbiorów
$ B_{r+1}, B_{r+2}, \cdots, B_{t-1} $ dowolne dwa albo są rozłączne,
albo jeden zawiera się w drugim, przy czym są one podzbiorami
$ (m-d) $-elementowego zbioru $ {1, 2, \cdots,m}\setminus B_1 $,
a ponadto nie występuje wśród nich zbiór pusty, jest on bowiem
podzbiorem $ B_1 $. Stąd otrzymujemy
$ t-r -1 \leqslant a_{m-d} -1 $ i w konsekwencji

\[<br /> t = r +(t-r -1)+1 \leqslant a_d +(a_{m-d} -1)+1 = a_d +a_{m-d}.<br /> \]

Skutkiem tego liczba podzbiorów zbioru $ \{1,2, \cdots,m\} $
o żądanej własności nie przekracza liczby $ a_d +a_{m-d} $.

Wykazaliśmy zatem, że $ a_m $ nie przekracza największej z liczb

\[<br /> a_d +a_{m-d} \text{ dla } d =1,2, \cdots,m-1.<br /> \]

Jeżeli więc w nierówności (1) równość ma miejsce dla
$ n =1, 2, \cdots,m - 1 $, to ma ona miejsce również dla $ n = m $.
Skoro dla $ n = 1 $ nierówność (1) staje się równością, stosując
indukcję stwierdzamy ostatecznie, że $ a_n =2n $ dla $ n =1,2,3, \cdots $.

Komentarze

Dodaj nową odpowiedź