LX OM - I - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

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ść:

$ \emptyset, \{1\}, \{2\}, \{3\}, \cdots, \{n\}, \{1,2\}, \{1,2,3\}, \cdots, \{1,2,3, \cdots,n\}. $

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

$ (1) a_n \geqslant 2n \text{ dla } n=1,2,3,\cdots. $

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

$ t = r +(t-r -1)+1 \leqslant a_d +(a_{m-d} -1)+1 = a_d +a_{m-d}. $

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

$ a_d +a_{m-d} \text{ dla } d =1,2, \cdots,m-1. $

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