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.
Zasada Szufladkowa Dirichleta zadanie
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Witam na forum
- Posty: 5
- Rejestracja: 11 lut 2019, 21:23
- Podziękowania: 2 razy
- Płeć:
-
- Fachowiec
- Posty: 1070
- Rejestracja: 07 maja 2010, 12:48
- Podziękowania: 2 razy
- Otrzymane podziękowania: 357 razy
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
info na priv