Zasada Szufladkowa Dirichleta zadanie

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Darek_Popiela
Witam na forum
Witam na forum
Posty: 5
Rejestracja: 11 lut 2019, 22:23
Podziękowania: 2 razy
Płeć:

Zasada Szufladkowa Dirichleta zadanie

Post autor: Darek_Popiela » 13 lut 2019, 13:22

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.

Crazy Driver
Fachowiec
Fachowiec
Posty: 1070
Rejestracja: 07 maja 2010, 12:48
Podziękowania: 2 razy
Otrzymane podziękowania: 357 razy

Post autor: Crazy Driver » 25 mar 2019, 16:41

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.
Korki z matmy, rozwiązywanie zadań
info na priv