forum.zadania.info

Rozważ dowolną rodzinę podzbiorów zbioru n-elementowego zawierającą więcej niż połowę wszystkich
podzbiorów. Wykaż, że w tej rodzinie muszą być dwa zbiory takie, że jeden zawiera się w drugim.

Wyróżnijmy dowolny element \(a\) z naszego zbioru. Teraz każdy podzbiór \(X\) zbioru \(n\)-elementowego, który nie zawiera \(a\), sparujmy ze zbiorem \(X\cup \left\{a \right\}\). Rozważmy jako szufladki takie pary. Liczba szufladek jest oczywiście równa połowie liczby wszystkich podzbiorów. Zatem rozmieszczając teraz w szufladkach podzbiory naszej rodziny, w którejś z nich znajdziemy dwa podzbiory i jeden z nich będzie podzbiorem drugiego.