Rozważ dowolną rodzinę podzbiorów zbioru n-elementowego.... asdf: 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, ze jeden zawiera sie w drugim. Mógłby ktoś mi to objaśnić? Wiem tyle, że można skorzystać z zasady szufladkowej Dirichleta... Serdecznie dziękuję.
7 gru 00:19
asdf: podbijam
7 gru 09:56
jc: Indukcja względem n. Dla n=1 twierdzenie jest prawdziwe (dlaczego?). Załóżmy, że twierdzenie jest prawdziwe dla n. Weźmy rodzinę złożoną z co najmniej 2n+1 podzbiorów zbioru n+1 elementowego. Podzielmy rodzinę na dwie rodziny: zbiory do których należy element n+1 i zbiory do których nie należy. Jedna z tych rodzin liczy co najmniej 2n−1+1 elementów. Z założenia indukcyjnego wynika, że zawiera dwa podzbiory, z których jeden zawarty jest w drugim, n+1 element niczego nie psuje.
7 gru 11:00