Zasada Szufladkowa Dirichleta zadanie

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij Thank icon

Zasada Szufladkowa Dirichleta zadanie

Postprzez 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.
Darek_Popiela
Dopiero zaczynam
Dopiero zaczynam
 
Posty: 5
Dołączenie: 11 Lut 2019, 22:23
Płeć: On
Otrzymane podziękowania: 0

Postprzez Crazy Driver » 25 Mar 2019, 16:41

Wyróżnijmy dowolny element [math] z naszego zbioru. Teraz każdy podzbiór [math] zbioru [math]-elementowego, który nie zawiera [math], sparujmy ze zbiorem [math]. 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
Crazy Driver
Expert
Expert
 
Posty: 1069
Dołączenie: 07 Maj 2010, 12:48
Otrzymane podziękowania: 359


Powróć do Pomocy! - matematyka dyskretna



Kto jest na forum

Użytkownicy przeglądający to forum: Brak zarejestrowanych użytkowników oraz 1 gość