szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 lut 2018, o 23:27 
Użytkownik

Posty: 306
Lokalizacja: Polska
Uzasadnij, że podzbiorów zbioru n-elementowego mocy parzystej jest tyle samo, co podzbiorów mocy nieparzystej. Ile?

No to nasz zbiór n ma moc parzystą, czyli ma w sobie tyle samo podzbiorów parzystej i nieparzystej mocy, no wydaje się to bardzo naturalne i jakoś niespecjalnie zaskakujące, ale ciężko dobrać słowa.
Co do mocy całego zbioru to 2^{n}, bo P(n), a podzbiory parzyste i nieparzyste 2^{ \frac{n}{2} }.

Przydałoby mi się lepsze wytłumaczenie tego faktu.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2018, o 23:45 
Użytkownik
Avatar użytkownika

Posty: 12428
Lokalizacja: czasem Warschau, czasem Breslau
Można to zrobić indukcyjnie, ale nie trzeba.

Podzbiorów k-elementowych zbioru n-elementowego jest {n \choose k}. Jeśli n jest liczbą nieparzystą, to wystarczy zauważyć, że {n \choose k}={n \choose n-k} i gdy k jest nieparzyste, to n-k jest parzyste, zaś gdy k jest parzyste, to n-kjest nieparzyste. Jeśli natomiast n jest liczbą parzystą, to wyróżnijmy jakiś element x z naszego zbioru n-elementowego A. Zbiór A\setminus\left\{ x\right\} ma nieparzyście wiele elementów, więc wiemy już, że ma on tyle samo podzbiorów o parzystej liczbie elementów, co podzbiorów o nieparzystej liczbie elementów.
Teraz zauważmy, że wszystkie podzbiory zbioru A, które nie są podzbiorami A\setminus\left\{ x\right\} powstają przez dołączenie x do pewnego podzbioru A\setminus \left\{ x\right\}. Do konkretnego zbioru możemy dołączyć element x tylko na jeden sposób, więc skoro jest tyle samo podzbiorów A\setminus\left\{ x\right\} o parzyście wielu i nieparzyście wielu elementach, to jest też tyle samo podzbiorów A, do których należy x, o parzyście wielu i nieparzyście wielu elementach (jak dokładamy x do podzbioru zbioru A \setminus \left\{x\right\} o nieparzyście wielu elementach, to otrzymujemy podzbiór o parzystej liczbie elementów itd.). To kończy dowód.
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2018, o 23:53 
Użytkownik

Posty: 306
Lokalizacja: Polska
A co do ilości elementów/ mocy zbiorów nie pomyliłem się?
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2018, o 00:13 
Użytkownik
Avatar użytkownika

Posty: 12428
Lokalizacja: czasem Warschau, czasem Breslau
Pomyliłeś się, po \frac{1}{2}\cdot 2^n=2^{n-1} parzystych i nieparzystych (skrótowo pisząc), a jak to uzasadnić, to napisałem powyżej (jest tyle samo podzbiorów k-elementowych zbioru n-elementowego, co podzbiorów n-k-elementowych).
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2018, o 00:48 
Użytkownik

Posty: 306
Lokalizacja: Polska
Rzeczywiście, to może przez tą późną już godzinę ;)
Ps: Super tłumaczenie z tym wyróżnionym elementem, pełen szacunek ;)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość rozwiązań równania, nierozróżnialne ulotki do 10 przeg  kondzixd  1
 ilość rozwiązań równania - zadanie 13  exupery  6
 Ilość trójkątów i czworokątów  Bartek1991  3
 ilość sposobu podziału - podzbiorowe liczby Stirlinga  SzalonyMjut  1
 zadanie na ilosc drog  Szczypior  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl