Rozważ dowolną rodzinę podzbiorów zbioru \(\displaystyle{ 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ę.
podzbiory zbioru n-elem - Dirichlet
-
rivit
- Użytkownik
- Posty: 163
- Rejestracja: 28 paź 2018, o 17:31
- Płeć: Mężczyzna
- Podziękował: 70 razy
- Pomógł: 2 razy
podzbiory zbioru n-elem - Dirichlet
Ostatnio zmieniony 7 gru 2018, o 00:17 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
szw1710
Re: podzbiory zbioru n-elem - Dirichlet
Połowa zbiorów to zbiory "zwykłe", a druga połowa to ich dopełnienia. Więc do tej rodziny należy przynajmniej jeden zbiór \(\displaystyle{ A}\) wraz ze swoim dopełnieniem \(\displaystyle{ A'}\). Tak bym zaczynał rozumowanie.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: podzbiory zbioru n-elem - Dirichlet
Ja miałem taki pomysł:
pokażemy indukcyjnie, że w dowolnym zbiorze \(\displaystyle{ n}\)-elementowym \(\displaystyle{ A}\) można ustawić podzbiory w pary
podzbiór właściwy-jego nadzbiór, bez powtórzeń (oczywiście tych par będzie \(\displaystyle{ \frac 1 2\cdot 2^n=2^{n-1}}\)).
Oddzielnego rozpatrzenia wymaga \(\displaystyle{ n=1, \ n=2}\):
dla \(\displaystyle{ n=1}\) po prostu dobieramy \(\displaystyle{ A}\) i \(\displaystyle{ \varnothing}\), dla \(\displaystyle{ n=2}\) działamy jakkolwiek sensownie, dobieramy \(\displaystyle{ A}\) z jednym z singletonów i drugi z singletonów z \(\displaystyle{ \varnothing}\).
Przypuśćmy, że takie skojarzenie podzbiorów w pary istnieje w dowolnym zbiorze \(\displaystyle{ n}\)-elementowym dla pewnego \(\displaystyle{ n\in \NN^+}\) i rozważmy zbiór \(\displaystyle{ A}\) o \(\displaystyle{ n+1}\) elementach. Wyróżnijmy w nim pewien konkretny element \(\displaystyle{ a\in A}\) i rozpatrzmy na chwilę zbiór \(\displaystyle{ A\setminus\left\{ a\right\}}\). Zgodnie z założeniem indukcyjnym podzbiory zbioru \(\displaystyle{ A\setminus\left\{ a\right\}}\) możemy dobrać w \(\displaystyle{ 2^{n-1}}\) par podzbiór właściwy-jego nadzbiór, bez powtórzeń. Zauważmy teraz, że dowolny podzbiór \(\displaystyle{ A}\), do którego należy element \(\displaystyle{ a}\), można przedstawić w postaci sumy mnogościowej \(\displaystyle{ \left\{ a\right\}}\) i pewnego podzbioru zbioru \(\displaystyle{ A\setminus \left\{ a\right\}}\). Ponadto jeśli pewne dwa zbiory \(\displaystyle{ B, C\subset A\setminus\left\{ a\right\}}\) spełniają warunek \(\displaystyle{ B\subset C}\), to także
\(\displaystyle{ B\cup\left\{ a\right\} \subset C\cup\left\{ a\right\}}\).
Dla podzbiorów \(\displaystyle{ A}\), które mają element \(\displaystyle{ a}\) postępujemy więc tak, że do pewnej pary \(\displaystyle{ B, C}\) podzbiorów zbioru \(\displaystyle{ A\setminus\left\{ a\right\}}\) spełniającej \(\displaystyle{ B\subset C}\) i wybranej w procedurze umożliwionej przez założenie indukcyjne dorzucamy
\(\displaystyle{ \left\{ a\right\}}\), tworząc nową parę \(\displaystyle{ B\cup\left\{ a\right\} \subset C\cup\left\{ a\right\}}\). To kończy dowód na mocy zasady indukcji matematycznej.
Ustalmy dowolny zbiór \(\displaystyle{ n}\)-elementowy \(\displaystyle{ A}\) i dokonajmy wspomnianego doboru podzbiorów \(\displaystyle{ A}\) w pary.
Mamy więc \(\displaystyle{ 2^{n-1}}\) par nadzbiór-jego podzbiór właściwy i wybierając co najmniej \(\displaystyle{ 2^{n-1}+1}\) podzbiorów zbioru \(\displaystyle{ n}\)-elementowego na mocy zasady szufladkowej wybierzemy oba elementy z którejś pary, co kończy dowód tezy zadania.
pokażemy indukcyjnie, że w dowolnym zbiorze \(\displaystyle{ n}\)-elementowym \(\displaystyle{ A}\) można ustawić podzbiory w pary
podzbiór właściwy-jego nadzbiór, bez powtórzeń (oczywiście tych par będzie \(\displaystyle{ \frac 1 2\cdot 2^n=2^{n-1}}\)).
Oddzielnego rozpatrzenia wymaga \(\displaystyle{ n=1, \ n=2}\):
dla \(\displaystyle{ n=1}\) po prostu dobieramy \(\displaystyle{ A}\) i \(\displaystyle{ \varnothing}\), dla \(\displaystyle{ n=2}\) działamy jakkolwiek sensownie, dobieramy \(\displaystyle{ A}\) z jednym z singletonów i drugi z singletonów z \(\displaystyle{ \varnothing}\).
Przypuśćmy, że takie skojarzenie podzbiorów w pary istnieje w dowolnym zbiorze \(\displaystyle{ n}\)-elementowym dla pewnego \(\displaystyle{ n\in \NN^+}\) i rozważmy zbiór \(\displaystyle{ A}\) o \(\displaystyle{ n+1}\) elementach. Wyróżnijmy w nim pewien konkretny element \(\displaystyle{ a\in A}\) i rozpatrzmy na chwilę zbiór \(\displaystyle{ A\setminus\left\{ a\right\}}\). Zgodnie z założeniem indukcyjnym podzbiory zbioru \(\displaystyle{ A\setminus\left\{ a\right\}}\) możemy dobrać w \(\displaystyle{ 2^{n-1}}\) par podzbiór właściwy-jego nadzbiór, bez powtórzeń. Zauważmy teraz, że dowolny podzbiór \(\displaystyle{ A}\), do którego należy element \(\displaystyle{ a}\), można przedstawić w postaci sumy mnogościowej \(\displaystyle{ \left\{ a\right\}}\) i pewnego podzbioru zbioru \(\displaystyle{ A\setminus \left\{ a\right\}}\). Ponadto jeśli pewne dwa zbiory \(\displaystyle{ B, C\subset A\setminus\left\{ a\right\}}\) spełniają warunek \(\displaystyle{ B\subset C}\), to także
\(\displaystyle{ B\cup\left\{ a\right\} \subset C\cup\left\{ a\right\}}\).
Dla podzbiorów \(\displaystyle{ A}\), które mają element \(\displaystyle{ a}\) postępujemy więc tak, że do pewnej pary \(\displaystyle{ B, C}\) podzbiorów zbioru \(\displaystyle{ A\setminus\left\{ a\right\}}\) spełniającej \(\displaystyle{ B\subset C}\) i wybranej w procedurze umożliwionej przez założenie indukcyjne dorzucamy
\(\displaystyle{ \left\{ a\right\}}\), tworząc nową parę \(\displaystyle{ B\cup\left\{ a\right\} \subset C\cup\left\{ a\right\}}\). To kończy dowód na mocy zasady indukcji matematycznej.
Ustalmy dowolny zbiór \(\displaystyle{ n}\)-elementowy \(\displaystyle{ A}\) i dokonajmy wspomnianego doboru podzbiorów \(\displaystyle{ A}\) w pary.
Mamy więc \(\displaystyle{ 2^{n-1}}\) par nadzbiór-jego podzbiór właściwy i wybierając co najmniej \(\displaystyle{ 2^{n-1}+1}\) podzbiorów zbioru \(\displaystyle{ n}\)-elementowego na mocy zasady szufladkowej wybierzemy oba elementy z którejś pary, co kończy dowód tezy zadania.